A lagrangian relaxation approach for supply chain planning with order/setup costs and capacity constraints - Archive ouverte HAL Access content directly
Journal Articles Journal of Systems Science and Systems Engineering Year : 2003

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.

Dates and versions

hal-02477173 , version 1 (13-02-2020)

Identifiers

Cite

Haoxun Chen, Chengbin Chu. A lagrangian relaxation approach for supply chain planning with order/setup costs and capacity constraints. Journal of Systems Science and Systems Engineering, 2003, 12 (1), pp.98-110. ⟨10.1007/s11518-006-0123-9⟩. ⟨hal-02477173⟩

Collections

CNRS UTT LOSI
15 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More