A BACTERIAL EVOLUTIONARY ALGORITHM FOR THE JOB SHOP SCHEDULING PROBLEM

作     者：Luh, Guan-Chun Lee, Shih-Wei Guan-Chun Luh;Shih-Wei Lee

作者机构：Tatung Univ Dept Mech Engn 40 ChungShan North Rd3rd Sect Taipei 104 Taiwan 

出 版 物：《JOURNAL OF INDUSTRIAL AND PRODUCTION ENGINEERING》 (工业工程学刊)

年 卷 期：2006年第23卷第3期

页      面：185-191页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 

主　　题：bacterial evolutionary algorithm gene transfer job shop scheduling problem niche scheme 

摘      要：The job-shop scheduling problem is one of the most complicated and well-known hardest combinatorial optimization problems. It s purpose is to improve the production efficiency and reduce the processing duration so as to gain profits as high as possible. In addition, it has been illustrated that job-shop scheduling is usually an NP-hard combinatorial problem and is therefore unlikely to be solvable in polynomial time. In this study, a bacterial evolutionary algorithm is proposed for finding multiple optimal solutions to the job-shop scheduling problem. Bacterial evolutionary algorithm is an optimization method that incorporates special mechanisms inspired by natural phenomena of microbial evolution. Gene transfer and bacterial mutation operators are incorporated to improve the performance of the proposed method. Moreover, niche scheme is employed to discover multiple solutions. Numerous well-studied benchmark examples were utilized to evaluate the effectiveness of the proposed approach.