Evolving Dispatching Rules for the Unrelated Parallel Machines Scheduling Problem with Precedence and Resource Constraints with Genetic Programming

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.