Incest prevention and multirecombination in evolutionary algorithms to deal with the flow shop scheduling problem

Abstract

Scheduling concerns the allocation of limited resources for tasks over time. It is a process of making decisions that has, as a goal, the optimization of one or more objectives. Frequently, the main objective to be minimized is the completion time of the last job to abandon the system, which is called makespan. In many production systems a number of operations must be done on every job and often these operations have to be done in the same order on all jobs. This scheduling approach is known as the Flow Shop Scheduling Problem (FSSP). The present paper discusses the new multi-recombinative method and shows the performance of enhanced evolutionary approaches under permutation representation combined with a successfull previous approach proposed by another researchers, the extended incest prevention (EIP), consist of maintaining information about ancestors within the chromosome and modifying the selection for reproduction in order to impede mating of in di viduals belonging to the same "family", for a predefined number of generations. Results of the methods proposed here are contrasted with those obtained under previous evolutionary approaches to the FSSP.