A lagrangian relaxation approach for supply chain planning with order/setup costs and capacity constraints

Abstract

A heuristic approach is developed for supply chain planning modeled as multi-item multi-level capacitated lot sizing problems. The heuristic combines Lagrangian relaxation (LR) with local search. Different from existing LR approaches that relax capacity constraints and/or inventory balance constraints, our approach only relaxes the technical constraints that each 0-1 setup variable must take value 1 if its corresponding continuous variable is positive. The relaxed problem is approximately solved by using the simplex algorithm for linear programming, while Lagrange multipliers are updated by using a surrogate subgradient method that ensures the convergence of the dual problem in case of the approximate resolution of the relaxed problem. At each iteration, a feasible solution of the original problem is constructed from the solution of the relaxed problem. The feasible solution is further improved by a local search that changes the values of two setup variables at each time. By taking the advantages of a special structure of the lot-sizing problem, the local search can be implemented by using a modified simplex algorithm, which significantly reduces its computation time. Numerical experiments show that our approach can find very good solutions for problems of realistic sizes in a short computation time and is more effective than an existing commercial optimization code.

Keywords

Supply chain planning / lot sizing / lagrangian relaxation / local search / linear programming / simplex algorithm

References

[1] Billington P. J., McClain J. O., Thomas L. L. J.. Heuristics for Multilevel Lot-Sizing with a Bottleneck. Management Science, 1986, 32(8): 989-1006.

[2] Federgruen, A., “Centralized Planning Models for Multi-Echelon Inventory Systems under Uncertainty”, Graves, S. C., Rinnooy Kan, A. H. G., and Zipkin, P. H., Logistics of Production and Inventory, North-Holland, pp133–173, 1993.

[3] Drexl A., Kimms A.. Lot Sizing and Scheduling Survey and Extensions. European Journal of Operational Research, 1997, 99: 221-235.

[4] Harrison, T. P. and Lewis, H. S., “Lot Sizing in Serial Assembly Systems with Multiple Constrained Resources”, Management Science, Vol. 41, No. 11, 1995.

[5] Katok E., Lewis, H. S., and Harrison T. P., “Lot Sizing in General Assembly Systems with Setup Costs, Setup Times and Multiple Constrained Resources”, Management Science, Vol. 44, No. 6, 1998.

[6] Salomon M.. Determining Lotsizing Models for Production Planning, in Lecture Notes in Economics and Mathematical Systems, 1991, Heidelberg: Springer Verlag

[7] Secuk E. S., Simpson N. C., Vakharia A. J.. Integrated Production/Distribution Planning in Supply Chains: An Invited Review. European Journal of Operational Research, 1999, 115: 219-236.

[8] Silver E. A., Pyke D. F., Peterson R.. Inventory Management and Production Planning and Scheduling, 1998, New York: Wiley

[9] Tempelmeier H., Derstroff M.. A “Lagrangean-Based Heuristics for Dynamic Multi-Level Multi-Item Constrained Lotsizing with Setup Times. Management Science, 1996, 42: 738-757.

[10] Tempelmeier H., Helber S.. A Heuristtic for Dynamic Multi-Item Multi-Level Capacitated Lotsizing for General Product Structure. European Journal of Operational Research, 1994, 75: 296-311.

[11] Zhao X., Luh P. B., Wang J.. TheSurrogate Gradient Algorithm for Lagrangian Relaxation Method. Journal of Optimization Theory and Applications, 1999, 100(3): 699-71.