Development of Both the AIS and PSO for Solving the Flexible Job Shop Scheduling Problem

The flexible job shop scheduling problem (FJSP) is to assign each operation to an appropriate machine and to sequence the operations on the machines. The paper describes the development and the application of the artificial immune system (AIS) and the particle swarm optimization (PSO) for solving the flexible job shop scheduling problem with sequence-dependent setup times (SDST-FJSP). A series of the experiments have been designed using the analysis of variance to recognize best settings of parameters. Finally, 30 examples of the different sizes in the SDST-FJSP with the objective of minimizing makespan and mean tardiness have been used to verify the performance of the proposed algorithms, and to compare them with the existing meta-heuristic algorithms in the literature, such as the genetic algorithm (GA), the parallel variable neighborhood search (PVNS), and the variable neighborhood search (VNS). The obtained results show that the proposed PSO outperforms the GA and the PVNS approaches. It is found that the average best-so-far solutions obtained from the proposed AIS are better than those produced by the GA, the PVNS, the VNS, and the PSO algorithms for all the examples.