Flexible job shop scheduling using hybrid differential evolution algorithms |
| |
Authors: | Yuan Yuan Hua Xu |
| |
Affiliation: | State Key Laboratory of Intelligent Technology and Systems, Tsinghua National Laboratory for Information Science and Technology, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, PR China |
| |
Abstract: | This paper proposes hybrid differential evolution (HDE) algorithms for solving the flexible job shop scheduling problem (FJSP) with the criterion to minimize the makespan. Firstly, a novel conversion mechanism is developed to make the differential evolution (DE) algorithm that works on the continuous domain adaptive to explore the problem space of the discrete FJSP. Secondly, a local search algorithm based on the critical path is embedded in the DE framework to balance the exploration and exploitation by enhancing the local searching ability. In addition, in the local search phase, the speed-up method to find an acceptable schedule within the neighborhood structure is presented to improve the efficiency of whole algorithms. Extensive computational results and comparisons show that the proposed algorithms are very competitive with the state of the art, some new best known solutions for well known benchmark instances have even been found. |
| |
Keywords: | Scheduling Flexible job shop Differential evolution Local search Neighborhood structure Makespan |
本文献已被 ScienceDirect 等数据库收录! |
|