刘 琴， 陈 进

(江南大学 机械工程学院，江苏 无锡214122)

一般柔性数控加工车间，对提高设备利用率和及时完成给定的任务有很高的需求。在此需求下，应该将任务的每道工序都分配到合适的设备上加工。每个任务中的每道工序都可以在多台不同的设备上加工完成。设备可分为3 种［1］:有相同功能完全相同的平行设备，功能不同但加工时间相同的同类设备，以及功能和加工时间都不相同的不相关设备。

在有n 个任务、m 台设备的调度问题中，每个任务都有规定的工艺路线，每道工序都可以由一组具有相同或不同特点的设备来完成。其中最关键的问题就是为每道工序选择合适的设备，使加工成本最低。

目前，国内外就此研究方法主要有图论法、动态规划法、线性规划法以及遗传算法等。Gupta 等［2］将同类并行设备的车间调度问题纳入考虑范畴，并为最小最大延迟设计了2 种启发式算法，但并没有考虑到设备利用率问题。Kang 等［3］提出了一种用于处理包括返工概率、交货日期以及根据工艺路线设置时间的并行设备调度方法，但此方法是以假定每台设备上每个任务的返工概率是可以通过设备上的历史数据采集为基础的。Ozlen 等［4］则考虑到重新规划的问题，当一组任务已经分配给不相关的并行设备时，他们提出可以指数次算法来生成所需的有效解决方案，并使特定功能运算达到最优化，但其运算过程较为复杂，运算周期较长。

文中研究的主要问题是，在满足作业车间相关约束和规范的前提下，找到加工一组任务的最优序列。……