A Heuristic Genetic Algorithm for No-Wait Flowshop Scheduling Problem  

作　　者：CHANG Jun-lin GONG Dun-wei MA Xiao-ping 

机构地区：[1]School of lnformation and Electrical Engineering, China University of Mining ＆ Technology, Xuzhou, Jiangsu 221008, China

出　　处：《Journal of China University of Mining and Technology》2007年第4期582-586,共5页中国矿业大学学报（英文版）

基　　金：Project 60304016 supported by the National Natural Science Foundation of China

摘　　要：No-wait flowshop scheduling problems with the objective to minimize the total flow time is an important se-quencing problem in the field of developing production plans and has a wide engineering background. Genetic algo-rithm (GA) has the capability of global convergence and has been proven effective to solve NP-hard combinatorial op-timization problems,while simple heuristics have the advantage of fast local convergence and can be easily imple-mented. In order to avoid the defect of slow convergence or premature,a heuristic genetic algorithm is proposed by in-corporating the simple heuristics and local search into the traditional genetic algorithm. In this hybridized algorithm,the structural information of no-wait flowshops and high-effective heuristics are incorporated to design a new method for generating initial generation and a new crossover operator. The computational results show the developed heuristic ge-netic algorithm is efficient and the quality of its solution has advantage over the best known algorithm. It is suitable for solving the large scale practical problems and lays a foundation for the application of meta-heuristic algorithms in in-dustrial production.No-wait flowshop scheduling problems with the objective to minimize the total flow time is an important se-quencing problem in the field of developing production plans and has a wide engineering background. Genetic algo-rithm （GA） has the capability of global convergence and has been proven effective to solve NP-hard combinatorial op-timization problems,while simple heuristics have the advantage of fast local convergence and can be easily imple-mented. In order to avoid the defect of slow convergence or premature,a heuristic genetic algorithm is proposed by in-corporating the simple heuristics and local search into the traditional genetic algorithm. In this hybridized algorithm,the structural information of no-wait flowshops and high-effective heuristics are incorporated to design a new method for generating initial generation and a new crossover operator. The computational results show the developed heuristic ge-netic algorithm is efficient and the quality of its solution has advantage over the best known algorithm. It is suitable for solving the large scale practical problems and lays a foundation for the application of meta-heuristic algorithms in in-dustrial production.

关 键 词：production scheduling genetic algorithm FLOWSHOP NO-WAIT 

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