Polynomial Time Algorithms for the Minimax Regret Uncapacitated Lot Sizing Model

Research output: Working paperResearchpeer-review

Abstract

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
Number4149
Volume12

Cite this

Li, D., & Romero Morales, D. (2013). Polynomial Time Algorithms for the Minimax Regret Uncapacitated Lot Sizing Model. www: Mathematical Optimization Society. Optimization Online, No. 4149, Vol.. 12
Li, Dong ; Romero Morales, Dolores . / Polynomial Time Algorithms for the Minimax Regret Uncapacitated Lot Sizing Model. www : Mathematical Optimization Society, 2013. (Optimization Online; No. 4149, Vol. 12).
@techreport{af7ce71f7ec14203bb2f8bded0c5d6d7,
title = "Polynomial Time Algorithms for the Minimax Regret Uncapacitated Lot Sizing Model",
abstract = "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.",
keywords = "Robust optimiz ation, Minimax regret, Lot sizing, Production cost and demand uncertainties",
author = "Dong Li and {Romero Morales}, Dolores",
year = "2013",
language = "English",
publisher = "Mathematical Optimization Society",
address = "United States",
type = "WorkingPaper",
institution = "Mathematical Optimization Society",

}

Polynomial Time Algorithms for the Minimax Regret Uncapacitated Lot Sizing Model. / Li, Dong; Romero Morales, Dolores .

www : Mathematical Optimization Society, 2013.

Research output: Working paperResearchpeer-review

TY - UNPB

T1 - Polynomial Time Algorithms for the Minimax Regret Uncapacitated Lot Sizing Model

AU - Li, Dong

AU - Romero Morales, Dolores

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Robust optimiz ation

KW - Minimax regret

KW - Lot sizing

KW - Production cost and demand uncertainties

M3 - Working paper

BT - Polynomial Time Algorithms for the Minimax Regret Uncapacitated Lot Sizing Model

PB - Mathematical Optimization Society

CY - www

ER -