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.
****************************************************
Dr SC Brailsford
School of Management
University of Southampton
Southampton S017 1BJ
Tel: +44 (0)23 8059 3567
Fax: +44 (0)23 8059 3844
http://www.soton.ac.uk/~scb
***************************************************