Multirecombination and different representation in evolutionary algorithms for the flow shop scheduling problem

Abstract

The flow shop scheduling problem (FSSP) has held the attention of many researchers. In a simplest usual situation, a set of jobs must follow the same route to be executed on a set of machines (resources) and the main objective is to optimize some performance variable (makespan, tardiness, lateness, etc.). In the case of the makespan, it have been proved that when the number of machines is greater than or equal to three, the problem is NP-hard. EC is an emergent research field, which provides new heuristics to problem optimization where traditional approaches make the problem computationally intractable, is continuously showing its own evolution and enhanced approaches included latest multi-recombinative methods involving multiple crossovers per couple (MCPC) and multiple crossovers on multiple parents (MCMP). The present paper discusses the new multi-recombinative methods and shows the improvement of performance of enhanced evolutionary approaches under permutation and decode representation. Results of the methods proposed for each chromosome representation are here contrasted and results are shown.