Multi Parents Extended Precedence Preservative Crossover For Job Shop Scheduling Problems

Abstract

Job Shop Scheduling Problem (JSSP) is one of the hard combinatorial scheduling problems. This paper proposes a genetic algorithm with multi parents crossover called Extended Precedence Preservative Crossover (EPPX) that can be suitably modified and implemented with, in principal, unlimited number of parents which differ from conventional two parents crossover. JSSP representation encoded by using permutation with repetition guarantees the feasibility of chromosomes thus eliminates the legalization on children (offspring).The simulations are performed on a set of benchmark problems from the literatures and they indicate that the best solutions have the tendencies to be appeared by using 3-6 numbers of parents in the recombination. The comparison between the results of EPPX and other methodologies show the sustainability of multi parents recombination in producing competitive results to solve the JSSP.