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.
Original languageEnglish
JournalNaval Research Logistics
Volume61
Issue number5
Pages (from-to)386–402
ISSN0894-069X
DOIs
Publication statusPublished - 2014
Externally publishedYes

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

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

JF - Naval Research Logistics

SN - 0894-069X

IS - 5

ER -