考虑任务拆分特性与簇准备时间的并行机调度

Parallel Machines Scheduling with Job-splitting Property and Family Setups

在印制电路板钻孔任务调度等工程实际中,普遍存在一类具有任务拆分特性与簇准备时间的并行机调度问题,尚缺乏高效的优化模型和方法。针对该问题,首先建立以总拖期最小为目标的数学模型,以约束的形式将两个现有优势定理嵌入其中。为了高效求解实际规模问题,进一步提出嵌入优势定理的模拟退火算法。最后,基于随机生成的算例构造计算实验,以验证所建模型和算法的有效性。实验结果表明,嵌入优势定理的数学模型在问题求解规模和计算效率方面均优于现有数学模型,嵌入优势定理的模拟退火算法同样优于现有模拟退火算法。

The parallel machines scheduling problem with job-splitting property and family setups is common in engineering practice such as drilling task scheduling of printed circuit boards.Until now,there is still a lack of efficient optimization model and method.To address this issue,a mathematical model with the objective to minimize the total tardiness is first constructed,and then two existing dominance rules are embedded in the form of constraints.In order to solve a practical size problem efficiently,the simulated annealing algorithms with embedded dominance rules are proposed.Finally,computational experiments based on randomly generated instances are designed to validate the effectiveness of the constructed models and algorithms.Experimental results show that the proposed mathematical model with embedded dominance rules is superior to the existing model in terms of the size of the problem that can be solved and the computational efficiency.In addition,the proposed simulated annealing algorithm with embedded dominance rules are also superior to the existing simulated annealing algorithm.