Upgrading evolutionary algorithms through multiplicity for multiobjective optimization in job shop scheduling problems

Abstract

In previous works the ability of CPS-MCPC (an evolutionary, co-operative, population search method with multiple crossovers per couple) to build well delineated Pareto fronts in diverse multiobjective optimization problems (MOOPs) was demonstrated. To test the potential of the novel method when dealing with the Job Shop Scheduling Problem (JSSP), regular and non-regular objectives functions were chosen. They were the makespan and the mean absolute deviation (of job completion times from a common due date, an earliness/tardiness related problem). Diverse representations such as priority list representation (PLR), job-based representation (JBR) and operation-based representation (OBR) among others were implemented and tested. The latter showed to be the best one. As a good parameter setting can enhance the behaviour of an evolutionary algorithm distinct parameters combinations were implemented and their influence studied. Multiple crossovers on multiple parents (MCMP), a powerful multirecombination method showed some enhancement in single objective optimization when compared with MCPC. This paper shows the influence of different recombination schemes when building the Pareto front under OBR and using the best parameter settings determined in previous works on a set of demonstrative Lawrence´s instances. Details of implementation and results are discussed.