Lagrangean decomposition has been recognized as a promising approach for solving large-scale optimization problems. However, Lagrangean decomposition is critically dependent on the method of updating the Lagrangean multipliers used to decompose the original model. This paper presents a Lagrangean decomposition approach based on Nelder-Mead optimization algorithm to update the Lagrangean multipliers. The main advantage of the proposed approach is that it results in improved objective function values for the majority of iterations. The efficiency of the proposed approach is illustrated with examples from the literature and the solution of scheduling problems. (c) 2006 Elsevier Ltd. All rights reserved.