A hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search for job shop scheduling problems |
| |
| Authors: | Fuqing Zhao Zhongshi Shao Junbiao Wang Chuck Zhang |
| |
| Affiliation: | 1. School of Computer and Communication Technology, Lanzhou University of Technology, Lanzhou, China;2. Key Laboratory of Contemporary Design &3. Integrated Manufacturing Technology, Ministry of Education, Northwestern Polytechnical University, Xi’an, China;4. Key Laboratory of Contemporary Design &5. H. Milton Stewart School of Industrial &6. Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA |
| |
| Abstract: | Job shop scheduling problem (JSSP) is a typical NP-hard problem. In order to improve the solving efficiency for JSSP, a hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search is proposed in this paper, which combines the merits of Estimation of distribution algorithm and Differential evolution (DE). Meanwhile, to strengthen the searching ability of the proposed algorithm, a chaotic strategy is introduced to update the parameters of DE. Two mutation operators are adopted. A neighbourhood search (NS) algorithm based on blocks on critical path is used to further improve the solution quality. Finally, the parametric sensitivity of the proposed algorithm has been analysed based on the Taguchi method of design of experiment. The proposed algorithm was tested through a set of typical benchmark problems of JSSP. The results demonstrated the effectiveness of the proposed algorithm for solving JSSP. |
| |
| Keywords: | estimation of distribution algorithm differential evolution algorithm neighbourhood search hybrid optimisation job shop scheduling |
|
|
