An O(Tˆ3) algorithm for the capacitated lot sizing problem with minimum order quantities

Arbeitspapier

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 suffcient solvability conditions and apply the general dynamic programming technique to develop an O(T³) 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.

Object Details

• Language: Englisch

References and Relationships

• Bibliographic citation: Series: Discussion Paper ; No. 284

Classification and Topics

• Classification: Wirtschaft
• Subject: production planning ; capacitated lot sizing problem ; single item ; minimum order quantities ; capacity constraints ; dynamic programming ; Produktionsplanung ; Kapazitätsplanung ; Auftragsfertigung ; Losgröße ; Dynamische Optimierung ; Theorie

Contributors, Places and Time

• Event: Geistige Schöpfung
• (who): Okhrin, Irena ; Richter, Knut
• Event: Veröffentlichung
• (who): European University Viadrina, Department of Business Administration and Economics
• (where): Frankfurt (Oder)
• (when): 2010

Further information

• Handle: http://hdl.handle.net/10419/41404
• Last update: 10.03.2025, 11:42 AM CET