Contrasting two MCMP alternatives in evolutionary algorithms to solve the job shop scheduling problem

Abstract

Many researchers have shown interest to solve the job shop scheduling problem (JSSP) applying evolutionary algorithms (EAs). In a previous work we reported an enhanced evolutionary algorithm, which uses a multiplicity feature to solve JSSP. The evolutionary approach was enhanced by means of multiple crossovers on multiple parents (MCMP) and the selection of a stud among the intervening parent. Partially mapped crossover (PMX) was used on each multiple crossover operation and job based representation (permutation of jobs) was adopted as a coding technique. The traditional MCMP approach is based on scanning crossover. But the application of this operator to permutations will yield illegal offspring in the sense that some jobs may be missed while some other jobs may be duplicated in the offspring, so some modifications to their mechanism are necessary to guarantee the offspring legality. This paper contrasts both MCMP approaches, discusses implementation details and shows results for a set of job shop scheduling instances of distinct complexity.