A New Hybrid Scatter Search Algorithm for Solving the Flexible Job Shop Scheduling Problems

Abstract

Flexible job shop scheduling (FJSS) is derived by inheriting the features of the job-shop scheduling problem. FJSS has an extra routing sub-problem of the job-shop scheduling. FJSS is well known as an NP-hard problem in the literature. A new hybrid scatter search (HSS) method is proposed to solve the FJSS problem. The proposed HSS method is integrating a local and global search for generating an initial population. The performance of the proposed new HSS method is dependent on the selected parameters. These parameters are the size of the initial population and reference set; the number of subsets, reference set updating and population sub updating; reproduction, crossover, and mutation operators, and their ratio. A full factorial experimental design is made to determine the best values of control parameters and operators for the proposed new HSS to solve the FJSS problems. The proposed new HSS method is tested on a set of the well-known benchmark FJSS instances from the literature. The computational results indicated that the proposed new HSS is an effective method for solving the FJSS problems.