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

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 - Morales,Dolores Romero

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 -