Multiplicity of parents and crossovers, the stud and the neh heuristic for searching the optimal makespan in fssp

Abstract

Different evolutionary approaches using genetic algorithms were proposed to solve the Flow Shop Scheduling Problem (FSSP). Variants point to the selection mechanism, genetic operators and the decision to include or not in the initial population an individual generated by some conventional heuristic (Reeves). New trends to enhance evolutionary algorithms for solving the FSSP introduced multiple-crossovers-per couple (MCPC) and multiple-crossovers-on-multiple-parents (MCMP). MCMP-S, a multiple-crossovers-on-multiple-parents variant, selects the stud (breeding individual) among the multiple intervening parents and mates it, more than once, with every other parent in a multiple crossover operation. In previous works, two versions of MCMP-S were faced. In the first one (MCMP-SOP), the stud and every other parent were selected from the old population. In the second one (MCMP-SRI), the stud was selected from the old population, and the other parents (random immigrants) were generated randomly. This paper introduces MCMP-NEH. The idea is to use the NEH heuristic, where the stud mates individuals in the mating pool coming from two sources: random immigrants and NEH-based individuals. These NEH-individuals are produced from randomly chosen individuals of the population and used as the starting points of the NEH heuristic. Experiments were conducted to contrast this novel proposal with a conventional evolutionary algorithm, with the only objective of establishing the improvement degree despite computational effort. Implementation details and a comparison of results for a set of flow shop scheduling instances of distinct complexity, using every evolutionary approach, are shown.