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

Abstrakt

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.
OriginalsprogEngelsk
TidsskriftNaval Research Logistics
Vol/bind61
Udgave nummer5
Sider (fra-til)386–402
ISSN0894-069X
DOI
StatusUdgivet - 2014
Udgivet eksterntJa

Emneord

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

Citationsformater