A Genetic Programming Framework for Heuristic Generation for the Job-Shop Scheduling Problem

Abstract

The Job-Shop Scheduling problem is a combinatorial optimization problem present in many real-world applications. It has been tackled with a colorful palette of techniques from different paradigms. Particularly, hyper-heuristics have attracted the attention of researchers due to their promising results in various optimization scenarios, including job-shop scheduling. In this study, we describe a Genetic-Programming-based Hyper-heuristic approach for automatically producing heuristics (dispatching rules) when solving such a problem. To do so, we consider a set of features that characterize the jobs within a scheduling instance. By using these features and a set of mathematical functions that create interactions between such features, we facilitate the construction of new heuristics. We present empirical evidence that heuristics produced by our approach are competitive. This conclusion arises from comparing the makespan of schedules obtained from our proposed method against those of some standard heuristics, over a set of synthetic Job-Shop Scheduling problem instances.

Xavier F. C. Sánchez Díaz

PhD candidate in Artificial Intelligence

PhD candidate in Artificial Intelligence at the Department of Computer Science (IDI) of the Norwegian University of Science and Technology