The Southern OR Group is holding a Joint Seminar with the University of
Oxford, Department of Statistics. All are welcome.
Venue: 1 South Parks Road, Oxford
Thursday, 27th May, 2.15pm
Capacitated two-level lot-sizing models: NP-hard problems?
Dolores Romero Morales, Said Business School, University of Oxford
Abstract
In this talk we discuss a model integrating the production and distribution
processes in a supply chain. Consider a planning horizon of T periods, a
retailer who faces a nonnegative demand for a given item, and a
manufacturer with production and transportation capacities. In each period
production may take place at the manufacturer site. The items that are
produced may be stored at the manufacturer or transported to the retailer.
Items may be transported before demand occurs but never later, i.e.
inventory at the retailer is allowed but backlogging is not. We assume that
the production and the transportation costs are given by general concave
functions, and the inventory holding costs by linear functions. This
problem can be formulated as a two-level capacitated lot-sizing model.
The classical one-level lot-sizing problem is polynomially solvable under
stationary production capacities. (Note that transportation is not an
option there.) Nevertheless, the complexity of the two-level capacitated
lot-sizing problem under stationary production and transportation
capacities is still an open issue. We have been able to find some scenarios
under which the problem can be solved in polynomial time. In particular, we
have found polynomial time algorithms for the cases where the
transportation costs are either linear, or are concave with a fixed-charge
structure. We make the additional common and reasonable assumption that the
variable transportation and inventory costs are such that holding
inventories at the manufacturer is more attractive than at the retailer
from a variable cost perspective. This assumption can be relaxed when the
transportation capacities are not binding and the transportation costs are
linear.
Simchi-Levi and Kaminsky (2003) have addressed the non-binding
transportation capacities scenario. They assume linear production
costs but the transportation cost functions can present more
complex nonlinearities under stationarity assumption. They also
show some polynomial results which together with ours illustrate
the difficulty of proving any complexity result for this two-level
problem.
|