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

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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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.
SprogEngelsk
TidsskriftNaval Research Logistics
Vol/bind61
Udgave nummer5
Sider386–402
ISSN0894-069X
DOI
StatusUdgivet - 2014
Udgivet eksterntJa

Emneord

  • Lot-sizing
  • Biobjective
  • Expenditure
  • Pareto efficient outcomes
  • Complexity analysis

Citer dette

@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.

I: Naval Research Logistics, Bind 61, Nr. 5, 2014, s. 386–402.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer 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 -