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.
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.
LanguageEnglish
Place of Publicationwww
PublisherMathematical Optimization Society
Number of pages6
StatePublished - 2013
Externally publishedYes
SeriesOptimization Online
Number4149
Volume12

Keywords

    Cite this

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

    Research output: Working paperResearchpeer-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 -