基于数学规划的平行机批量调度固定优化算法

MIP based fix-and-optimize algorithm for parallel machine lot sizing and scheduling

以半导体制造行业为应用背景,研究带产能约束的平行机批量调度问题。该问题需要同时考虑基于产品加工顺序的生产准备时间约束、产品加工的时间窗约束、设备和产品的匹配约束以及设备偏好性等约束。为此,构建了混合整数规划(MIP)模型,并设计了基于MIP模型的固定优化启发式算法。该算法先按照随机设备柔性最小优先规则把设备预先分配给需要加工的产品,从而可以通过更新设备和产品匹配关系矩阵来降低子问题的求解难度;再利用基于设备分解和基于时间分解的两种分解方法,固定住MIP模型中的大部分0-1变量,从而可以有效地利用MIP求解器优化剩余的一小部分0-1变量。大量随机产生的实验算例和半导体工厂真实算例表明:该算法优于现有文献中其他基于MIP的启发式算法,特别是当算例中设备柔性较高和需求变动较大时,该算法绩效更加显著。

This paper examines the capacitated lot sizing and scheduling problem with sequence-dependent setup times, time windows, machine eligibility and preference constraints. Such problems frequently arise in the semiconductor manufacturing industry. A mixed integer programming （MIP） model is constructed with a fix-and optimize algorithm in which the machines are first pre allocated using the randomized least flexible machine rule and the machine product eligibility matrix is then updated. Machine based and time-based decomposition with most of the binary decision variables fixed in the MIP model and the rest of the decision variables determined by an MIP solver. Extensive tests show that the algorithm outperforms state-of-the-art MIP based heuristic algorithms in the literature, especially for instances with highmachine flexibility and high demand variations.