Hyper-heuristic Evolution of Dispatching Rules: A Comparison of Rule Representations

Area of Science:

• Operations Research
• Artificial Intelligence
• Manufacturing Systems Engineering

Background:

• Dispatching rules are crucial for real-time scheduling in complex manufacturing.
• Manual design of these rules is time-consuming and relies on expert trial-and-error.
• Evolutionary algorithms offer automated design possibilities.

Purpose of the Study:

• To empirically compare three distinct rule representations for automated dispatching rule design.
• To evaluate the suitability of linear, artificial neural network (ANN), and tree representations.
• To assess the robustness and understandability of evolved dispatching rules.

Main Methods:

• Employed evolutionary algorithms: CMA-ES for linear and ANN representations, genetic programming for tree representation.
• Tested representations in a dynamic stochastic job shop scheduling scenario.
• Analyzed rule robustness against scenario variations and visualized rule behavior.

Main Results:

• Tree representation with genetic programming yielded the best performance when many rules could be evaluated.
• ANN representation provided good results with moderate computational resources.
• Linear representation was competitive only for very limited computational budgets.

Conclusions:

• The choice of representation significantly impacts the success of evolutionary algorithms for dispatching rule design.
• Tree and ANN representations are promising for automated rule design in dynamic job shop environments.
• Visualizing evolved rules aids in understanding their decision-making processes.