A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks

In simple flow shop problems, each machine operation center includes just one machine. If at least one machine center includes more than one machine, the scheduling problem becomes a flexible flow shop problem (FFSP). Flexible flow shops are thus generalization of simple flow shops. Flexible flow shop scheduling problems have a special structure combining some elements of both the flow shop and the parallel machine scheduling problems. FFSP can be stated as finding a schedule for a general task graph to execute on a multiprocessor system so that the schedule length can be minimized. FFSP is known to be NP-hard. In this study, we present a particle swarm optimization (PSO) algorithm to solve FFSP. PSO is an effective algorithm which gives quality solutions in a reasonable computational time and consists of less numbers parameters as compared to the other evolutionary metaheuristics. Mutation, a commonly used operator in genetic algorithm, has been introduced in PSO so that trapping of solutions at local minima or premature convergence can be avoided. Logistic mapping is used to generate chaotic numbers in this paper. Use of chaotic numbers makes the algorithm converge fast towards near-optimal solution and hence reduce computational efforts further. The performance of schedules is evaluated in terms of total completion time or makespan (C-max). The results are presented in terms of percentage deviation (PD) of the solution from the lower bound. The results are compared with different versions of genetic algorithm (GA) used for the purpose from open literature. The results indicate that the proposed PSO algorithm is quite effective in reducing makespan because average PD is observed as 2.961, whereas GA results in average percentage deviation of 3.559. Finally, influence of various PSO parameters on solution quality has been investigated.