Polynomial Time Algorithms for the Minimax Regret Uncapacitated Lot Sizing Model

Publikation: Working paperForskningpeer review

Resumé

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.
OriginalsprogEngelsk
Udgivelses stedwww
UdgiverMathematical Optimization Society
Antal sider6
StatusUdgivet - 2013
Udgivet eksterntJa
NavnOptimization Online
Nummer4149
Vol/bind12

Emneord

  • Robust optimiz ation
  • Minimax regret
  • Lot sizing
  • Production cost and demand uncertainties

Citer dette

Li, D., & Romero Morales, D. (2013). Polynomial Time Algorithms for the Minimax Regret Uncapacitated Lot Sizing Model. www: Mathematical Optimization Society. Optimization Online, Nr. 4149, Bind. 12
Li, Dong ; Romero Morales, Dolores . / Polynomial Time Algorithms for the Minimax Regret Uncapacitated Lot Sizing Model. www : Mathematical Optimization Society, 2013. (Optimization Online; Nr. 4149, Bind 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",
series = "Optimization Online",
publisher = "Mathematical Optimization Society",
number = "4149",
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.

Publikation: Working paperForskningpeer 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

T3 - Optimization Online

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

PB - Mathematical Optimization Society

CY - www

ER -