Heuristic for no-wait flow shops with makespan minimization based on total idle-time increments  

作　　者：LI XiaoPing1,2 & WU Cheng3 1 School of Computer Science & Engineering, Southeast University, Nanjing 210096, China 2 Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education, Nanjing 210096, China 3 Department of Automation, Tsinghua University, Beijing 100084, China 

出　　处：《Science in China(Series F)》2008年第7期896-909,共14页中国科学（F辑英文版）

基　　金：the National Natural Science Foundation of China (Grant Nos.60504029 and 60672092);the National High Technology Re-search and Development Program of China (863 Program) (Grant No.2008AA04Z103)

摘　　要：No-wait flow shops with makespan minimization are classified as NP-hard. In this paper, the optimization objective is equivalently transformed to total idle-time minimization. The independence relationship between tasks is analyzed, and objective increment properties are established for the fundamental operators of the heuristics. The quality of the new schedules generated during a heuristic is judged only by objective increments and not by the traditional method, which computes and compares the objective of a whole schedule. Based on objective increments, the time complexity of the heuristic can be decreased by one order. A seed phase is presented to generate an initial solution according to the transformed objective. Construction and improvement phases are introduced by experimental analysis. The FCH （fast composite heuristic） is proposed and compared with the most effective algorithms currently available for the considered problem. Experimental results show that the effectiveness of the FCH is similar to that of the best methods but requires far less computation time. The FCH can also be efficient in real time scheduling and rescheduling for no-wait flow shops.No-wait flow shops with makespan minimization are classified as NP-hard. In this paper, the optimization objective is equivalently transformed to total idle-time minimization. The independence relationship between tasks is analyzed, and objective increment properties are established for the fundamental operators of the heuristics. The quality of the new schedules generated during a heuristic is judged only by objective increments and not by the traditional method, which computes and compares the objective of a whole schedule. Based on objective increments, the time complexity of the heuristic can be decreased by one order. A seed phase is presented to generate an initial solution according to the transformed objective. Construction and improvement phases are introduced by experimental analysis. The FCH （fast composite heuristic） is proposed and compared with the most effective algorithms currently available for the considered problem. Experimental results show that the effectiveness of the FCH is similar to that of the best methods but requires far less computation time. The FCH can also be efficient in real time scheduling and rescheduling for no-wait flow shops.

关 键 词：no-wait flow shops HEURISTIC MAKESPAN Tabu search 

分 类 号：TP11[自动化与计算机技术—控制理论与控制工程]