An O(T3) algorithm for the capacitated lot sizing problem with minimum order quantities
This paper explores a single-item capacitated lot sizing problem with minimum order quantity, which plays the role of minor set-up cost. We work out the necessary and sufficient solvability conditions and apply the general dynamic programming technique to develop an O(T3) exact algorithm that is based on the concept of minimal sub-problems. An investigation of the properties of the optimal solution structure allows us to construct explicit solutions to the obtained sub-problems and prove their optimality. In this way, we reduce the complexity of the algorithm considerably and confirm its efficiency in an extensive computational study.
Year of publication: |
2011
|
---|---|
Authors: | Okhrin, Irena ; Richter, Knut |
Published in: |
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 211.2011, 3, p. 507-514
|
Publisher: |
Elsevier |
Keywords: | Production planning Capacitated lot sizing problem Single item Minimum order quantities Capacity constraints Dynamic programming |
Saved in:
Saved in favorites
Similar items by person
-
Solving a Production and Inventory Model with a Minimum Lot Size Constrain
Richter, Knut, (2007)
-
The linear dynamic lot size problem with minimum order quantities
Okhrin, Irena, (2010)
-
An O(Tˆ3) algorithm for the capacitated lot sizing problem with minimum order quantities
Okhrin, Irena, (2010)
- More ...