An asymptotically optimal greedy heuristic for the multiperiod single‐sourcing problem: The cyclic case

The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single‐sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end‐of‐study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 412–437, 2003     

Computational complexity of finding Pareto efficient outcomes for biobjective lot‐sizing models

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 ‐hard task in general. Finally, we shed some light on the task of describing the Pareto frontier. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 386–402, 2014