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

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