A Hybrid Genetic Algorithm for Flexible Job Shop Scheduling Problem With Sequence-Dependent Setup Times and Job Lag Times

This paper addresses the flexible job shop scheduling problem with sequence-dependent set-up times and job lag times (FJSP-SDST-LT), which characteristics are important in modern manufacturing systems. We first present a mathematical model with the objective to minimize the makespan. Then a hybrid algorithm (HGA-TS) which combines genetic algorithm (GA) and tabu search (TS) is proposed to solve the FJSP-SDST-LT. The GA performs powerful global search by genetic operators and serves as exploration, while based on the specific structure of SDST and LT, the TS is able to perform an effective local search by relocating operations and serves as exploitation. Therefore, the proposed HGA-TS integrates good searching ability with strong diversifying ability. In order to solve the FJSP-SDST-LT effectively, we adopt effective encoding and decoding methods, genetic operators in GA, and four neighborhood structures in TS. We conduct computational experiments on two classes of instances generated from two classic data sets and the results show the great performance of HGA-TS in solving FJSP-SDST-LT.