A new dispatching rule based genetic algorithm for the multi-objective job shop problem

A new dispatching rule based genetic algorithm for the multi-objective job shop problem

0.00 Avg rating0 Votes
Article ID: iaor20107586
Volume: 16
Issue: 6
Start Page Number: 771
End Page Number: 793
Publication Date: Dec 2010
Journal: Journal of Heuristics
Authors: ,
Keywords: scheduling
Abstract:

Hyper-heuristics or ‘methodologies to choose heuristics’ are becoming increasingly popular given their suitability to solve hard real world combinatorial optimisation problems. Their distinguishing feature is that they operate in the space of heuristics or heuristic components rather than in the solution space. In Dispatching Rule Based Genetic Algorithms (DRGA) solutions are represented as sequences of dispatching rules which are called one at a time and used to sequence a number of operations onto machines. The number of operations that each dispatching rule in the sequence handles is a parameter to which DRGA is notoriously sensitive. This paper proposes a new hybrid DRGA which searches simultaneously for the best sequence of dispatching rules and the number of operations to be handled by each dispatching rule. The investigated DRGA uses the selection mechanism of NSGA-II when handling multi-objective problems. The proposed representation was used to solve different variants of the multi-objective job shop problem as well as the single objective problem with the sum of weighted tardiness objective. Our results, supported by the statistical analysis, confirm that DRGAs that use the proposed representation obtained better results in both the single and multi-objective environment overall and on each particular set of instances than DRGAs using the conventional dispatching rule representation and a GA that uses the more common permutation representation.

Reviews

Required fields are marked *. Your email address will not be published.