HEURISTIC METHOD FOR DYNAMIC JOB SHOP SCHEDULING PROBLEM WITH OPERATION RELATIVITY

XIONG Hegen¹  LI Jianjun²  KONG Jianyi¹ YANG Jintang¹ JIANG Guozhang¹

(1. College of Mechanical Automation, Wuhan University of Science and Technology, Wuhan 430081；

2. State Key Laboratory of Plastic Forming Simulation and Die & Mould Technology, Huazhong University of Science and Technology, Wuhan 430074)

Abstract: 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.

Key words: Dynamic job shop scheduling  Operation relativity  Heuristic method  Dispatching rules Simulation

CLC No: TH166

湖北省自然科学基金(2000J134)和博士点专项基金(2000048717)资助项目.Received 20051102, received in revised form 20060424