王 崐，郑树琴

（1.山西省煤炭规划设计院，山西 太原 030045；2.太原理工大学机械工程学院，山西 太原 030024）

0 引 言

调度是在有限生产资源约束中优化效益目标函数的决策过程。多机调度旨在为一系列工作的加工处理过程建立适当的调度次序，以保所有工作在合适的时间内完成；在此过程中需要解决的问题包括：机器的分配、工作处理次序、调度合理性等。多机调度问题分为针对并行机和串行机，均被证明为NP-hard问题[1]。并行机调度可按系统配置分为三种：等同机、同类机、变速机的调度。实际调度需要考虑系统随机性和动态性的影响[2]，例如：加工时间的不确定性和订单到达率随时间的动态性。大型系统的多目标调度时常出现，需要深入研究；因此文章建立仿真模型模拟动态随机环境中的等同机调度，进而研究不同策略在此系统中的作用，以求达到同时最大化吞吐率和最小化延迟工件量的双重目的。

多目标调度问题应用广泛，但其理论研究有待完善。Andres等[3]提出了多目标遗传算法解决流水车间调度问题，目标函数包括最小化调度时长和拖期，模型约束包括基于工序排序的调整时间和顺序的约束。Lee和Asllani[4]针对工序的调整时间的最小化拖期工件量和调度时长的单机调度问题，建立了混合整数规划模型及相关遗传算法。Jungwattanaki等[5]采用遗传算法和模拟退火算法，解决工序的调整时间的最小化加权调度时长和拖期工件量的流水车间调度问题。Picard和Queyranne[6]将单机调度问题建模成时间相关的旅行者问题（Traveling Salesman Problem）并运用分支定界法求解，以达到最小化拖期和加权拖期的目的。……