Multirecombining random and seed immigrants in evolutionary algorithms to face the shop scheduling problem

Abstract

In an m-machines n-jobs flow-shop sequencing problem each job consists of m operations and each operation requires a different machine, so n jobs have to be processed in the same sequence on m machines. The processing time of each job on each machine is given. Frequently, the main objective is to find the sequence of jobs minimizing the maximum flow time, which is called the makespan. The flow-shop problem has been proved to be NP-complete. Evolutionary algorithms (EAs) have been successfully applied to solve scheduling problems. Improvements in evolutionary algorithms consider multirecombination, allowing multiple crossover operations on a pair of parents (MCPC, multiple crossovers per couple) or on a set of multiple parents (MCMP. Multiple crossovers on multiple parents). MCMP-STUD and MCMP-SRI are novel MCMP variants, which considers the inclusion of a stud-breeding individual as a seed in a pool of random immigrant parents. Random immigrants provide genetic diversity while seed-immigrants afford the knowledge of some conventional robust heuristics. Members of the mating pool subsequently undergo multiple crossover operations. Another question in a multirecombined EA is the setting of parameters n1 (number of crossovers) and n2 (number of parents). In the experiments conducted they were empirically determined, by a deterministic rule or by self adaptation of parameters n1 and n2. In the last case the idea is to code the parameters within the chromosome and undergo genetic operations. Hence it is expected that better parameter values be more intensively propagated.