牛 群 周台金 王小海 张红运

(上海大学上海市电站自动化技术重点实验室，上海200072)

(上海大学机电工程与自动化学院，上海200072)

并行机调度是生产调度中一类典型的调度问题，近年来受到研究者的广泛关注.已经证明目标函数为最小化最大完工时间即Makespan 最小时，仅有两台机器的并行机调度问题便是NP-hard 问题［1］.在相同并行机的研究中，大多数研究假设工件之间的调整时间(setup time)是可忽略不计的.这种假设能够简化问题模型，便于求解，但在实际的生产条件下，尤其是调整时间依赖于工件加工顺序中的前一个加工工件及工件的分组技术时，调整时间是不可忽略的.研究表明，在生产调度中，若充分考虑调整时间的影响，会使调度模型能更好地解决实际问题，从而为企业降低成本.带调整时间的相同并行机调度问题的研究方法主要包括精确方法和启发式方法.

Lee 等［2］针对该问题，提出了一种三阶段启发式方法.Armentano 等［3］研究了带调整时间的相同并行机调度问题，提出了一种贪婪式随机搜索自适应程序，并且结合基于记忆准则的方法来构造初始种群.何军辉等［4］对含有非常数调整时间的并行机作业排序问题，设计了一种遗传算法的实现形式.

由于精确算法仅适于小规模调度问题，因此智能优化方法被广泛应用于调度问题，如遗传算法、模拟退火等，并取得了良好的效果，由于智能方法简洁、方便、易于实现，因此已成为解决调度问题的一个研……