Conference Proceeding

Dispatching Rules for Production Scheduling: a Hyper-heuristic Landscape Analysis



Ochoa G, Vazquez-Rodriguez JA, Petrovic S & Burke E (2009) Dispatching Rules for Production Scheduling: a Hyper-heuristic Landscape Analysis. In: IEEE Congress on Evolutionary Computation, 2009 CEC '09. Piscataway, NJ, USA: IEEE Press, pp. 1873-1880.;

Hyper-heuristics are an emergent search methodology that seeks to automate the process of selecting or combining simpler heuristics in order to solve hard computational search problems. The distinguishing feature of hyper-heuristics, as compared to other heuristic search algorithms, is that they operate on a search space of heuristics rather than directly on the search space of solutions to the underlying problem. Therefore, a detailed understanding of the properties of these heuristic search spaces is of utmost importance for understanding the behaviour and improving the design of hyper-heuristic methods. Heuristics search spaces can be studied using the metaphor of fitness landscapes. This paper formalises the notion of hyper-heuristic landscapes and performs a landscape analysis of the heuristic search space induced by a dispatching-rule-based hyper-heuristic for production scheduling. The studied hyper-heuristic spaces are found to be ldquoeasyrdquo to search. They also exhibit some special features such as positional bias and neutrality. It is argued that search methods that exploit these features may enhance the performance of hyper-heuristics.

Design methodology; Dispatching; Heuristic algorithms; Performance analysis; Processor scheduling; Production; Scheduling algorithm; Search methods; Search problems; Space technology; dispatching; production control; scheduling; search problems; computational search problem; dispatching rules; fitness landscapes; heuristic search space; hyperheuristic landscape; production scheduling

Publication date31/12/2009
PublisherIEEE Press
Publisher URL…isnumber=4982922
Place of publicationPiscataway, NJ, USA
ConferenceIEEE Congress on Evolutionary Computation, 2009 CEC '09

People (1)


Professor Gabriela Ochoa

Professor Gabriela Ochoa

Professor, Computing Science