An Effective Hybrid Particle Swarm Optimization for Flexible Job Shop Scheduling Problem

ABSTRACT

The job shop scheduling problem is one of the most arduous combinatorial optimization problems. Flexible job shop scheduling problem (FJSP) is an important extension of the classical job shop scheduling problem, where the same operation could be processed on more than one machine. This paper proposed a new effective approach based on the hybridization of the particle swarm optimization (PSO) and local search algorithm of variable neighborhood search (VNS) to solve the FJSP for minimizing the makespan, the maximal machine workload, and the total workload of machines. PSO is a highly efficient evolutionary computation technique inspired by bird’s flight and communication behaviors. PSO integrating the local search and global search has highly search ability. VNS has the strong local search ability. Benchmark problems are used to evaluate and study the performance of the proposed algorithm. Computational results show that the proposed hybrid algorithm is an efficient and effective approach.

Keywords:

Particle swarm optimization, Variable neighborhood search, Local search, Multi objective, Flexible job shopscheduling problem.