Evolving Dispatching Rules for the Unrelated Parallel Machines Scheduling Problem with Precedence and Resource Constraints with Genetic Programming
TL;DR
The results show that the proposed GP-based approach enables the automated generation of high-quality DRs, outperforming manually designed heuristics for the considered problem.
Abstract
The unrelated parallel machines scheduling problem is an important and challenging problem with significant industrial relevance. This paper addresses a specific variant involving precedence constraints between jobs and the requirement of additional resources for job execution. The problem is NP-hard, and practical solution approaches are therefore predominantly heuristic. In dynamic scheduling environments, dispatching rules (DRs) represent one of the most effective and widely used heuristic approaches. A DR consists of a schedule generation scheme (SGS) and a priority function (PF). The manual design of high-quality DRs is difficult and time-consuming, making the problem well suited for hyper-heuristic and evolutionary approaches. In this work, genetic programming (GP) is employed to automatically evolve the PF component of DRs. Additionally, several problem-specific SGSs are proposed and evaluated. The evolved DRs are compared against adapted state-of-the-art DRs from the literature. The results show that the proposed GP-based approach enables the automated generation of high-quality DRs, outperforming manually designed heuristics for the considered problem.