Abstract
A new integer linear programming formulation for the discrete lot-sizing and scheduling problem is presented. This polynomial-size formulation is obtained from the model with the natural variables by splitting these variables. Its linear programming relaxation is shown to be tight, by reformulating it as a shortest path problem. The latter also provides a dynamic programming formulation for the discrete lot-sizing and scheduling problem.
Original language | English |
---|---|
Pages (from-to) | 342-353 |
Number of pages | 12 |
Journal | European Journal of Operational Research |
Volume | 75 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1994 |