论文部分内容阅读
以半导体制造行业为应用背景,研究带产能约束的平行机批量调度问题。该问题需要同时考虑基于产品加工顺序的生产准备时间约束、产品加工的时间窗约束、设备和产品的匹配约束以及设备偏好性等约束。为此,构建了混合整数规划(MIP)模型,并设计了基于MIP模型的固定优化启发式算法。该算法先按照随机设备柔性最小优先规则把设备预先分配给需要加工的产品,从而可以通过更新设备和产品匹配关系矩阵来降低子问题的求解难度;再利用基于设备分解和基于时间分解的两种分解方法,固定住MIP模型中的大部分0-1变量,从而可以有效地利用MIP求解器优化剩余的一小部分0-1变量。大量随机产生的实验算例和半导体工厂真实算例表明:该算法优于现有文献中其他基于MIP的启发式算法,特别是当算例中设备柔性较高和需求变动较大时,该算法绩效更加显著。
Taking the semiconductor manufacturing industry as the application background, this paper studies the parallel machine batch scheduling problem with capacity constraint. This problem needs to consider both production preparation time constraints, product processing time window constraints, equipment and product matching constraints and equipment preferences based on the order of product processing. To this end, a hybrid integer programming (MIP) model is constructed and a fixed optimization heuristic algorithm based on the MIP model is designed. In this algorithm, the device is pre-assigned to the product to be processed according to the minimum priority rule of random device flexibility, so that the difficulty of solving the sub-problem can be reduced by updating the relationship matrix between the device and the product. Reusing both the device-based decomposition and the time-based decomposition Decomposition method, which fixes most of the 0-1 variables in the MIP model so that the MIP solver can effectively optimize the remaining small fraction of the 0-1 variables. A large number of random generated experimental examples and semiconductor factory real examples show that the algorithm is superior to other existing MIP-based heuristics in the literature, especially when the device flexibility is high and the demand fluctuates greatly, Performance is more significant.