GPMS: A Generalized Parallel Machine Scheduling Framework with Rich Temporal and Resource Constraints

Abstract

Classical scheduling problems such as Unrelated Parallel Machine Scheduling (UPMSP), Flexible Job Shop Scheduling (FJSP), and Resource-Constrained Project Scheduling (RCPSP) each capture important aspects of industrial scheduling, but real-world applications often require a combination of constraints from several of these formulations and additional requirements that are typically not supported in standard models. We propose a Generalized Parallel Machine Scheduling (GPMS) framework that, to the best of our knowledge, is the most general machine scheduling formulation to date and unifies machine eligibility with machine-dependent processing times, sequence- and machine-dependent setup times, rich temporal constraints, and secondary-resource constraints in a single formulation. Temporal constraints include machine calendars and precedence relations with min/max time lags and conditional machine eligibilities. Secondary resources are modeled with capacity calendars and pulse or step demands. To model and solve this generalized problem, we investigate a constraint programming approach and propose two CP models: a solver-agnostic high-level model and an interval-variable model. We also develop a randomized construction heuristic that finds feasible, high-quality schedules even for large and highly constrained instances; these schedules serve as warm starts for the interval-variable model. We evaluate 216 generated and 91 real-world instances, comparing the interval-variable model to the solver-agnostic model and to the construction heuristic. The warm-start interval-variable model attains the best objective on the majority of both generated and real-world instances, proves optimality for many small-to-medium instances, and finds near-optimal schedules for most industrial instances within a one-hour time limit. We release all models, code, and instances to support reproducible research.