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

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

0.00 Avg rating0 Votes
Article ID: iaor20112894
Volume: 211
Issue: 3
Start Page Number: 507
End Page Number: 514
Publication Date: Jun 2011
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: dynamic
Abstract:

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(T 3) 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.

Reviews

Required fields are marked *. Your email address will not be published.