Combined Timetabling Procedure and Complete Local Search for No-Wait Job Shop Scheduling with Total Tardiness  

作　　者：杨玉珍 顾幸生 

机构地区：[1]Key Laboratory of Advanced Control and Optimization for Chemical Process,Ministry of Education,East China University of Science and Technology

出　　处：《Journal of Donghua University(English Edition)》2014年第2期83-91,共9页东华大学学报（英文版）

基　　金：National Natural Science Foundations of China(Nos.61174040,61104178);Shanghai Commission of Science and Technology,China(No.12JC1403400);the Fundamental Research Funds for the Central Universities,China

摘　　要：The strong non-deterministic polynomial-hard( NP-hard)character of job shop scheduling problem( JSSP) has been acknowledged widely and it becomes stronger when attaches the nowait constraint,which widely exists in many production processes,such as chemistry process, metallurgical process. However,compared with the massive research on traditional job shop problem,little attention has been paid on the no-wait constraint.Therefore,in this paper, we have dealt with this problem by decomposing it into two sub-problems, the timetabling and sequencing problems,in traditional frame work. A new efficient combined non-order timetabling method,coordinated with objective of total tardiness,is proposed for the timetabling problems. As for the sequencing one,we have presented a modified complete local search with memory combined by crossover operator and distance counting. The entire algorithm was tested on well-known benchmark problems and compared with several existing algorithms.Computational experiments showed that our proposed algorithm performed both effectively and efficiently.The strong non-deterministic polynomial-hard （NP-hard） character of job shop scheduling problem （JSSP） has been acknowledged widely and it becomes stronger when attaches the no-wait constraint, which widely exists in many production processes, such as chemistry process, metallurgical process. However, compared with the massive research on traditional job shop problem, little attention has been paid on the no-wait constraint. Therefore, in this paper, we have dealt with this problem by decomposing it into two sub-problems, the timetabling and sequencing problems, in traditional frame work. A new efficient combined non-order timetabling method, coordinated with objective of total tardiness, is proposed for the timetabling problems. As for the sequencing one, we have presented a modified complete local search with memory combined by crossover operator and distance counting. The entire algorithm was tested on well-known benchmark problems and compared with several existing algorithms. Computational experiments showed that our proposed algorithm performed both effectively and efficiently.

关 键 词：job shop scheduling NO-WAIT TIMETABLING TARDINESS complete local search with memory 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]