Polynomial Time Algorithms for the Minimax Regret Uncapacitated Lot Sizing Model

Research output: Working paperResearchpeer-review


We study the Minimax Regret Uncapacitated Lot Sizing (MRULS) model, where the production cost function and the demand are subject to uncertainty. We propose a polynomial time algorithm which solves the MRULS model in O(n^6) time. We improve this running time to O(n^5) when only the demand is uncertain, and to O(n^4) when only the production cost function is uncertain.
Original languageEnglish
Place of Publicationwww
PublisherMathematical Optimization Society
Number of pages6
Publication statusPublished - 2013
Externally publishedYes
SeriesOptimization Online

Cite this