An efficient two-stage genetic algorithm for a flexible job-shop scheduling problem with sequence dependent attached/detached setup, machine release date and lag-time

摘要

In a flexible job-shop scheduling problem (FJSP), an operation can be assigned to one of a set of eligible machines. Therefore, the problem is to simultaneously determine both the assignment of operations to machines and their sequences. Accordingly, the solution encoding of many regular genetic algorithms (RGAs) developed in literature has two parts: one part encodes the assignment decision and the other the sequencing decision. The genetic search determines both the assignment and the sequencing of the operations simultaneously through a random process guided by the principles of natural selection and evolution. In this paper, we develop a two-stage genetic algorithm (2SGA) with the first stage being different from a typical RGA for FJSP found in the literature. The first stage of 2SGA has a solution encoding that only dictates the sequence in which the operations are considered for assignment. Whenever an operation is considered for assignment, the machine that can complete this operation the soonest is selected while taking into account the operations that are already assigned to this machine. The order in which the operations are assigned to machines determines their sequence. The second stage, starting from the solutions of the first stage, follows the common approach of genetic algorithm for FJSP to enable the algorithm to search the entire solution space by including solutions that might have been excluded because of the greedy nature of the first stage. We tested the proposed algorithm by solving many benchmark problems and several other large-size problems of a comprehensive FJSP model with sequence-dependent setup, machine release date, and lag-time. The performance of the proposed two-stage algorithm greatly exceeds that of the common approach of genetic algorithm for FJSP. We also show that further performance improvement of the proposed algorithm can be achieved using high-performance parallel computation. However, the more interesting result we found was that the sequential version of the proposed algorithm (using a single CPU) outperformed a parallel implementation of the regular genetic algorithm that uses many CPUs. We also noted that the superiority of the proposed algorithm over RGA is much greater when solving large-size problems, rendering the proposed algorithm as a viable choice for solving practical problems that are typically encountered in industries.