Computational Complexity of Finding Pareto Efficient Outcomes for Biobjective Lot-sizing Models

H. Edwin Romeijn, Dolores Romero Morales, Wilco Van den Heuvel

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

In this article, we study a biobjective economic lot-sizing problem with applications, among others, in green logistics. The first objective aims to minimize the total lot-sizing costs including production and inventory holding costs, whereas the second one minimizes the maximum production and inventory block expenditure. We derive (almost) tight complexity results for the Pareto efficient outcome problem under nonspeculative lot-sizing costs. First, we identify nontrivial problem classes for which this problem is polynomially solvable. Second, if we relax any of the parameter assumptions, we show that (except for one case) finding a single Pareto efficient outcome is an inline image-hard task in general. Finally, we shed some light on the task of describing the Pareto frontier.
In this article, we study a biobjective economic lot-sizing problem with applications, among others, in green logistics. The first objective aims to minimize the total lot-sizing costs including production and inventory holding costs, whereas the second one minimizes the maximum production and inventory block expenditure. We derive (almost) tight complexity results for the Pareto efficient outcome problem under nonspeculative lot-sizing costs. First, we identify nontrivial problem classes for which this problem is polynomially solvable. Second, if we relax any of the parameter assumptions, we show that (except for one case) finding a single Pareto efficient outcome is an inline image-hard task in general. Finally, we shed some light on the task of describing the Pareto frontier.
LanguageEnglish
JournalNaval Research Logistics
Volume61
Issue number5
Pages386–402
ISSN0894-069X
DOIs
StatePublished - 2014
Externally publishedYes

Keywords

    Cite this

    @article{46d13ec76dda4ddd89e8e06f082039e2,
    title = "Computational Complexity of Finding Pareto Efficient Outcomes for Biobjective Lot-sizing Models",
    abstract = "In this article, we study a biobjective economic lot-sizing problem with applications, among others, in green logistics. The first objective aims to minimize the total lot-sizing costs including production and inventory holding costs, whereas the second one minimizes the maximum production and inventory block expenditure. We derive (almost) tight complexity results for the Pareto efficient outcome problem under nonspeculative lot-sizing costs. First, we identify nontrivial problem classes for which this problem is polynomially solvable. Second, if we relax any of the parameter assumptions, we show that (except for one case) finding a single Pareto efficient outcome is an inline image-hard task in general. Finally, we shed some light on the task of describing the Pareto frontier.",
    keywords = "Lot-sizing, Biobjective, Expenditure, Pareto efficient outcomes, Complexity analysis",
    author = "Romeijn, {H. Edwin} and Morales, {Dolores Romero} and {Van den Heuvel}, Wilco",
    year = "2014",
    doi = "10.1002/nav.21590",
    language = "English",
    volume = "61",
    pages = "386–402",
    journal = "Naval Research Logistics",
    issn = "0894-069X",
    publisher = "Wiley-Blackwell",
    number = "5",

    }

    Computational Complexity of Finding Pareto Efficient Outcomes for Biobjective Lot-sizing Models. / Romeijn, H. Edwin; Morales, Dolores Romero; Van den Heuvel, Wilco.

    In: Naval Research Logistics, Vol. 61, No. 5, 2014, p. 386–402.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - Computational Complexity of Finding Pareto Efficient Outcomes for Biobjective Lot-sizing Models

    AU - Romeijn,H. Edwin

    AU - Morales,Dolores Romero

    AU - Van den Heuvel,Wilco

    PY - 2014

    Y1 - 2014

    N2 - In this article, we study a biobjective economic lot-sizing problem with applications, among others, in green logistics. The first objective aims to minimize the total lot-sizing costs including production and inventory holding costs, whereas the second one minimizes the maximum production and inventory block expenditure. We derive (almost) tight complexity results for the Pareto efficient outcome problem under nonspeculative lot-sizing costs. First, we identify nontrivial problem classes for which this problem is polynomially solvable. Second, if we relax any of the parameter assumptions, we show that (except for one case) finding a single Pareto efficient outcome is an inline image-hard task in general. Finally, we shed some light on the task of describing the Pareto frontier.

    AB - In this article, we study a biobjective economic lot-sizing problem with applications, among others, in green logistics. The first objective aims to minimize the total lot-sizing costs including production and inventory holding costs, whereas the second one minimizes the maximum production and inventory block expenditure. We derive (almost) tight complexity results for the Pareto efficient outcome problem under nonspeculative lot-sizing costs. First, we identify nontrivial problem classes for which this problem is polynomially solvable. Second, if we relax any of the parameter assumptions, we show that (except for one case) finding a single Pareto efficient outcome is an inline image-hard task in general. Finally, we shed some light on the task of describing the Pareto frontier.

    KW - Lot-sizing

    KW - Biobjective

    KW - Expenditure

    KW - Pareto efficient outcomes

    KW - Complexity analysis

    U2 - 10.1002/nav.21590

    DO - 10.1002/nav.21590

    M3 - Journal article

    VL - 61

    SP - 386

    EP - 402

    JO - Naval Research Logistics

    T2 - Naval Research Logistics

    JF - Naval Research Logistics

    SN - 0894-069X

    IS - 5

    ER -