Exploring Selection and Generation Hyper-heuristic Approaches for the Job Shop Scheduling Problem

Abstract

The job-shop scheduling problem (JSSP) represents a challenging field of study with many industrial and real-world applications that skyrocket its importance. Solving a JSSP requires allocating a set of jobs in a set of machines, subject to the constraint that each machine can only handle one job at a time. Also, each job consists of a set of ordered activities that have a processing order through the machines. The number of possible schedules to analyze is huge: j! × m if we consider j jobs and m machines. Given the complexity of JSSPs, hyper-heuristics have attracted the attention of researchers on this topic due to their promising results in this, and other optimization problems. However, hyper-heuristic implementations for JSSPs are not conclusive and, more importantly, some exciting ideas remain unexplored. This investigation explores novel hyper-heuristics models that consider aspects such as heuristic selection, generation, and refinement. These models also rely on different techniques from both machine learning and evolutionary computation, which include neural networks, clustering, Q-learning, and genetic programming. In total, three models were designed and implemented as a result of this investigation. The first model relies on a feed-forward neural network to refine existing hyper-heuristics. The general idea is that even when hyper-heuristics produce reliable results for many situations, there are cases where hyper-heuristics behave unexpectedly. This phenomenon suggests that, in some models, there is a high variation in the training process, sometimes producing underfitted hyper-heuristics. Then, this model aims at exploring the idea that we can improve how hyper-heuristics work by learning from the behavior of existing ones. The general idea is that a neural network learns the decisions made from an already trained hyper-heuristic and generalizes its behavior. In some cases, the model produces promising results. However, the results are bounded to the selected hyper-heuristic to improve. The second model removes the dependency on existing hyper-heuristics and explores heuristic selection through a reward-based hyper-heuristic approach that is powered by k-means and Q-learning. The model starts by identifying regions in the instance space that are commonly visited throughout the search process. Then, the model keeps a record of the performance of each heuristic for those regions by using the concept of a reward. After training completes, such records are used to determine the most suitable heuristic for a given region of the instance space. Finally, the third model leaves heuristic selection behind to explore heuristic generation by means of genetic programming. In this case, heuristics are decomposed into their building blocks (the criteria they use to make their decisions). By using genetic programming, the model combines features to create new criteria that gives place to new heuristics.