A parallel genetic algorithm for a flexible job-shop scheduling problem with sequence dependent setups

The flexible job-shop scheduling problem is an extension of the classical job-shop scheduling problem by allowing an operation to be assigned to one of a set of eligible machines during scheduling. Thus, the problem is to simultaneously assign each operation to a machine (routing problem), prioritize the operations on the machines (sequencing problem), and determine their starting times. The minimization of the maximal completion time of all operations is a widely used objective function in solving this problem. This paper presents a mathematical model for a flexible job-shop scheduling problem incorporating sequence-dependent setup time, attached or detached setup time, machine release dates, and time lag requirements. In order to efficiently solve the developed model, we propose a parallel genetic algorithm that runs on a parallel computing platform. Numerical examples show that parallel computing can greatly improve the computational performance of the algorithm.