A Dual Ascent and Column Generation Heuristic for the Discrete Lotsizing and Scheduling Problem with Setup Times
研究单台机器上多产品动态需求下的离散批量与调度问题，提出一种对偶上升和列生成启发式算法，能给出上下界并有效求解，计算实验表明算法在解质量和计算时间上表现良好。
In this paper the Discrete Lotsizing and Scheduling Problem (DLSP) with setup times is considered. DLSP is the problem of determining the sequence and size of production batches for multiple items on a single machine. The objective is to find a minimal cost production schedule such that dynamic demand is fulfilled without backlogging. DLSP is formulated as a Set Partitioning Problem (SPP). We present a dual ascent and column generation heuristic to solve SPP. The quality of the solutions can be measured, since the heuristic generates lower and upper bounds. Computational results on a personal computer show that the heuristic is rather effective, both in terms of quality of the solutions as well as in terms of required memory and computation time.