Optimization Online


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

Nabil Absi (absi***at***emse.fr)
Safia Kedad-Sidhoum (safia.kedad-sidhoum***at***lip6.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society