The multi-item capacitated lot-sizing problem with setup times and shortage costs

Nabil Absi (absiemse.fr)
Safia Kedad-Sidhoum (safia.kedad-sidhoumlip6.fr)

Abstract: We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem is NP-hard. A mixed integer mathematical formulation is presented. Our approach in this paper is to propose some classes of valid inequalities based on a generalization of Miller et al. 2003 and Marchand and Wolsey 1999 results. We also describe fast combinatorial separation algorithms for these new inequalities. We use them in a branch-and-cut framework to solve the problem. Some experimental results showing the effectiveness of the approach are reported.

Keywords: multi-item, capacitated lot-sizing, setup times, shortage costs, production planning, mixed integer programming, branch-and-cut.

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Working paper - LIP6 - July 2005 - European Journal of Operational Research 185 (3) (2008) 1351-1374

Download: [Postscript][PDF]

Entry Submitted: 09/21/2005
Entry Accepted: 09/21/2005
Entry Last Modified: 11/06/2007

Modify/Update this entry