Parallel and sequential evolutionary algorithms for the flow shop scheduling problem

Abstract

Determining an optimal schedule to m1mm1ze the completion time of the last job abandoning the system (makespan) become a very difficult problem when there are more than two machines in the flow shop. Due both to its economical impact and complexity attention to solve the Flow Shop Scheduling problem (FSSP) has been paid by many researchers. Current trends involve distinct evolutionary computation approaches. Parallel implementations of Evolutionary Algorithms aim to improvements on performance. This work shows an implementation of parallel and sequential evolutionary approaches for the FSSP. The first one implements the island model on diverse number of island while the second evolves a single population. Experiments include also latest approaches using a multiplicity feature: Multiple Crossovers per Couple (MCPC) on a set of flow shop scheduling instances. A discussion on implementation details, analysis and comparisons of sequential, parallel, single and multirecombinated evolutionary approaches to the problem are shown.