Minimizing Makespan in Flexible Job Shop Problems by Adapting the Differential Evolution

Abstract

The Flexible Job Shop Scheduling Problem (FJSP) is an extension of the classical Job Shop Scheduling Problem (JSP) that allows the operation of a job to be operated on one machine selected from a group of capable machines, and this additional requirement to determine the assignment of operations on proper machines makes the FJSP more complicated than the JSP. This paper discusses the implementation of two adapted differential evolution (DE) algorithms for minimizing makespan in the FJSP. The modified algorithms aim to enhance the efficiency of the original DE by dynamically balancing the exploration and exploitation ability and avoiding the common problem of premature convergence. The first algorithm, called DE with a subgroup strategy, allows the DE population to simultaneously perform different mutation strategies in order to exploit their various strengths and compensate for the weaknesses of each individual strategy in order to enhance overall performance. The second algorithm, called DE with a switching strategy, allows the entire DE population to change the search behavior whenever the solutions do not improve. As a consequence, the chance of getting trapped at a local optimum is reduced. The performances of two adapted DE are evaluated based on a set of benchmark problems and compared with the results obtained from the original DE. The experiment results show that both adapted DE algorithms generate results that are competitive with the original DE.