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.