工件到达时间未知的动态车间滚动重调度  

Rescheduling Algorithm Based on Rolling Horizon Decomposition for a Dynamic Job Shop with Uncertain Arriving Time

作　　者：刘琳[1] 谷寒雨[1] 席裕庚[1] 

机构地区：[1]上海交通大学自动化研究所,上海200240

出　　处：《机械工程学报》2008年第5期68-75,共8页Journal of Mechanical Engineering

基　　金：国家自然科学基金(60474002;60504026);国家高技术研究发展计划(863计划;2006AA04Z173)资助项目。

摘　　要：研究工件动态到达且到达时间未知的车间重调度问题,目标是最小化所有工件的拖期和。动态事件频繁的调度环境,对调度算法的计算效率要求很高。在滚动时域分解方法框架下,提出关键工序集的概念,采用混合遗传算法确定关键工序集合及其对应的最优部分调度。在解码过程中,采用混合调度生成器将染色体中的基因转化为部分可行调度,对没有参与遗传进化的工序采用改进的修正交货期(Modified due date,MDD)规则确定其在机器上的加工顺序,以完全调度的目标值评价染色体的适应度。对大量算例的仿真表明基于关键工序集的重调度算法对动态事件的响应速度,大大优于基于完全工序集的重调度算法,并且具有良好的全局性能,兼顾了实际动态Job shop系统对调度性能和计算效率的要求。The dynamic job shop scheduling with uncertain arriving time is studied, and the objective is to minimize total tardiness of all jobs. When rescheduling is frequent, the computational efficiency of the scheduling algorithm is necessarily high. Based on the rolling horizon decomposition, the critical operation set is denoted. A hybrid genetic algorithm is proposed to determine the critical operation set as well as optimizing total tardiness. The hybrid scheduler is used to convert the chromosome into partially feasible schedule, and the improved modified operation rule is used to determine the sequence of the remaining operations out of the chromosome. Then the fitness is evaluated by the objective value of the complete scheduling for the total operations to process. The simulation results of many instances show that the proposed algorithm significantly improves the computational efficiency compared with the genetic algorithm based on the complete operation set, and the performance of scheduling is satisfying.

关 键 词：动态调度 滚动时域分解 关键工序集 遗传算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]