滚动时域下最小加工时间批调度与粒子群求解

王宗光，谢小青，杨玉龙，廖世龙*

(1.兰州理工大学经济管理学院，甘肃 兰州 730050； 2.山东大学管理学院，山东 济南 250100)

1 引言

批调度问题主要指工件排序及工件合批，是半导体生产过程中提炼出的新型调度问题[1]。合批根据批处理设备的容量、工件形状材质、工件到达时间以及加工成本等多种因素综合处理。因此，批调度在求解难度上远高于古典调度[2]。实践生产中，批调度以适当的时间周期或事件驱动进行循环调度，仅需考虑怎样对某一时段内的工件分批、排程[3]，将动态、长期的全局调度问题分解为各时段内静态的局部子调度问题。传统批调度在各调度周期内只使用一种方法和一种确定的规则来解决问题，以便于调度的实现。而滚动时域调度方法则是时间驱动的循环调度策略。

当前批调度的研究可分为两种：一是理论。Liu的研究表明即便单台机器的工件集只有两个到达时间，批调度问题也是NP难题[4]。Zhao证明了目标为拖期惩罚的连续型批调度问题为强NP难[5]。二是算法，研究主要集中于初始时刻全局信息完全时，利用常规算法或群智能优化算法等离线算法进行一次的全局静态调度，获得调度最优值[6-8]。Melouks和Damodaran分别采用模拟退火算法、遗传算法对制造跨度进行优化研究[9，10]。Tang和Song设计了离散粒子群算法并将其应用在钢辊热处理混合流水车间[11]。闫萍和袁媛以化工领域设备批处理过程为研究对象，构建了分批与批调度决策的优化模型并提出改进的DE算法，仿真得出与PSO算法相比，改进的DE算法性能更好[12]。……