Computational complexity of finding Pareto efficient outcomes for bi-objective lot-sizing models

Romeijn, H. Edwin, Romero-Morales, Dolores and van den Heuvel, W. (2014) Computational complexity of finding Pareto efficient outcomes for bi-objective lot-sizing models. Naval Research Logistics, 61 (5). pp. 386-402.

Abstract

In this paper we study a Bi-Objective 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, while the second one minimizes the maximum production and inventory block expenditure. We derive (almost) tight complexity results for the Pareto efficient outcome problem under non-speculative lot-sizing costs. First, we identify non-trivial 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 $\mathcal{NP}$-hard task in general. Finally, we shed some light on the task of describing the Pareto frontier.

Item Type: Article
Keywords: lot-sizing, bi-objective, expenditure, Pareto efficient outcomes, complexity analysis
Subject(s): Management science
Centre: Faculty of Management Science
Date Deposited: 10 Jun 2014 15:45
Last Modified: 23 Oct 2015 14:08
URI: http://eureka.sbs.ox.ac.uk/id/eprint/5092

Actions (login required)

Edit View Edit View