考虑工序相关性的动态Job shop调度问题启发式算法

HEURISTIC METHOD FOR DYNAMIC JOB SHOP SCHEDULING PROBLEM WITH OPERATION RELATIVITY

提出一类考虑工序相关性的、工件批量到达的动态Job shop调度问题,在对工序相关性进行了定义和数学描述的基础上,进一步建立了动态Job shop调度问题的优化模型。设计了一种组合式调度规则RAN(FCFS,ODD),并提出了基于规则的启发式算法以及该类动态Job shop调度问题的算例生成方法。为验证算法和比较评估调度规则的性能,对算例采用文献提出的7种调度规则和RAN(FCFS,ODD)进行了仿真调度,对调度结果的分析表明了算法的有效性和RAN(FCFS,ODD)调度规则求解所提出的动态Job Shop调度问题的优越性能。

A dynamic job shop scheduling problem with operation relativity and job releasing in batch are proposed. Based on defining operation relativity and giving its mathematical description systematically, the optimization model of the dynamic job shop scheduling is put forward. A new combinatorial dispatching rule, RAN（FCFS,ODD）, and a heuristic method are designed. In order to validate the method and compare and evaluate the new combinatorial dispatching rule, a simulation method is presented, then seven dispatching rules proposed in literatures and RAN（FCFS,ODD） are adopted in scheduling simulation. Simulation results indicate that the heuristic method is effective and RAN（FCFS,ODD） outperforms the other seven dispatching rules with respect to the dynamic job shop scheduling problem proposed.