Elsevier

Discrete Applied Mathematics

Volume 48, Issue 3, 15 February 1994, Pages 289-303
Discrete Applied Mathematics

The single-item discrete lotsizing and scheduling problem: optimization by linear and dynamic programming

https://doi.org/10.1016/0166-218X(92)00182-LGet rights and content
Under an Elsevier user license
open archive

Abstract

This paper considers the single-item discrete lotsizing and scheduling problem (DLSP). DLSP is the problem of determining a minimal cost production schedule, that satisfies demand without backlogging and does not violate capacity constraints. We formulate DLSP as an integer programming problem and present two solution procedures.

The first procedure is based on a reformulation of DLSP as a linear programming assignment problem, with additional restrictions to reflect the specific (setup) cost structure. For this linear programming (LP) formulation it is shown that, under certain conditions on the objective, the solution is all integer. The second procedure is based on dynamic programming (DP). Under certain conditions on the objective function, the DP algorithm can be made to run very fast by using special properties of optimal solutions.

Keywords

Dynamic programming
integer programming
lotsizing

Cited by (0)

Supported by the Dutch Organization for Scientific Research (NWO) under grant 611-340-017.