Multi-item capacitated lot-sizing problem with setup times and shortage costs : Polyhedral results

Abstract: We address a multi-item capacitated lot-sizing problem with setup times, stock and demand shortages. Demand cannot be backlogged, but can be totally or partially lost. Safety stock is an objective to reach rather than an industrial constraint to respect. In this paper we consider an approach based on a lagrangean relaxation of the capacity constraints to generate a lower bound of the optimal value. This relaxation induces N single-item uncapacitated lot-sizing problems, where N denotes the number of items. A polynomial algorithm is developed to solve the sub-problems optimally. Some experimental results showing the effectiveness of the approach are reported. Copyright c ○ 2006 IFA