Source-linked AI summary
Graph-Enhanced Deep Reinforcement Learning for Multi-Objective Unrelated Parallel Machine Scheduling
Bulent Soykan, Sean Mondesire, Ghaith Rabadi, Grace Bochenek
TL;DR
The paper addresses multi-objective UPMSP with release dates, eligibility restrictions, and sequence- and machine-dependent setups, where TWT and TST must be minimized together. It combines PPO with a heterogeneous GNN and an explicit multi-objective reward to learn direct scheduling policies. Across tested problem sizes, PPO-GNN outperformed GA and ATCSR_Rm on both objectives and generated decisions much faster than GA.
Problem
Existing approaches face difficulty balancing TWT and TST in UPMSP with release dates, eligibility restrictions, and sequence- and machine-dependent setups.
Method
The framework uses PPO with a heterogeneous GNN representation of jobs, machines, setups, eligibility, processing, and transition relationships, guided by a multi-objective reward.
Results
PPO-GNN consistently achieved the lowest Avg TWT and Avg TST across all tested problem sizes, with significant differences reported at p < 0.01.
Takeaways & Limitations
PPO-GNN dominated GA and ATCSR_Rm on the averaged TWT-TST trade-off and produced inference times under 1.6 seconds on the largest problems.
Takeaways & Limitations
The formulation constrains each job to its eligible machine set and assumes sequence- and machine-dependent setup times, including initial setup states.
Abstract
from arXiv · showhide
The Unrelated Parallel Machine Scheduling Problem (UPMSP) with release dates, setups, and eligibility constraints presents a significant multi-objective challenge. Traditional methods struggle to balance minimizing Total Weighted Tardiness (TWT) and Total Setup Time (TST). This paper proposes a Deep Reinforcement Learning framework using Proximal Policy Optimization (PPO) and a Graph Neural Network (GNN). The GNN effectively represents the complex state of jobs, machines, and setups, allowing the PPO agent to learn a direct scheduling policy. Guided by a multi-objective reward function, the agent simultaneously minimizes TWT and TST. Experimental results on benchmark instances demonstrate that our PPO-GNN agent significantly outperforms a standard dispatching rule and a metaheuristic, achieving a superior trade-off between both objectives. This provides a robust and scalable solution for complex manufacturing scheduling.
1 INTRODUCTION
The paper frames constrained UPMSP scheduling as a difficult multi-objective problem and proposes a PPO-GNN framework with a tailored state representation and reward function.
- Problem context: UPMSP assigns jobs to unrelated machines whose processing times vary by job-machine pair, reflecting heterogeneous industrial equipment.Such settings occur in sectors including semiconductor manufacturing and textile production.
- Problem context: Realistic instances combine release dates, machine eligibility restrictions, and sequence- and machine-dependent setup times.These interacting constraints increase the difficulty of finding optimal or near-optimal schedules.
- Problem context: TWT and TST are conflicting objectives because prioritizing one can negatively affect the other.The paper targets simultaneous minimization of total weighted tardiness and total setup time.
- Proposed approach: The proposed approach uses DRL with GNNs to represent the variable relational structure of jobs, machines, and eligibility information.The GNN supports learning within a sequential scheduling environment.
- Proposed approach: The research contributes a PPO direct scheduling policy, a heterogeneous GNN state representation, and an explicit multi-objective reward function.The reward guides policies that balance the conflicting objectives.
2 Related Work
Prior work spans classical optimization, DRL, and GNN-based scheduling, but the paper identifies a gap in direct multi-objective UPMSP policies with tailored relational representations.
- Scheduling literature: UPMSP complexity increases with sequence-dependent setups, machine-dependent setups, release dates, and machine eligibility restrictions.Common objectives in the literature include makespan, total completion time, and total tardiness.
- Scheduling literature: Heuristics and dispatching rules are widely used for NP-hard UPMSP variants, especially when dynamic environments require rapid decisions.Their performance can degrade in settings with interacting setups and multiple objectives.
- Scheduling literature: Metaheuristics explore solution spaces more broadly than simple heuristics but typically require problem-specific tuning and can be computationally intensive.The cited approaches include GA, Tabu Search, Simulated Annealing, and Ant Colony Optimization.
- DRL and GNNs: DRL learns policies mapping system states to actions through environment interaction and can handle high-dimensional scheduling state spaces.This makes it suitable for sequential decision-making and combinatorial optimization.
- DRL and GNNs: GNN-based scheduling research has progressed toward graph-encoded state representations and end-to-end operation selection.Earlier approaches often selected among predefined dispatching rules.
- DRL and GNNs: PPO uses clipped or KL-constrained policy updates to limit destabilizing changes during training.Its stability, sample efficiency, and practical performance motivate its selection for this scheduling problem.
- Research gap: Prior UPMSP DRL studies often optimize one objective, select predefined heuristics, or tune rule parameters rather than learn direct multi-objective policies.The paper also identifies a need for graph representations tailored to balancing TWT and TST.
- Research gap: The proposed framework combines PPO, an explicit reward for minimizing TWT and TST, and a heterogeneous GNN with job, machine, and setup nodes.Its edge types encode eligibility, processing, setup, and transition relationships.
3 Problem Formulation
The formulation defines unrelated machines, job and machine parameters, assignment and sequencing decisions, feasibility constraints, and the conflicting TWT and TST objectives.
- Formal definition: The problem consists of independent jobs processed on unrelated parallel machines, with processing time p_jk varying arbitrarily by job and machine.This machine model distinguishes the formulation from identical or uniform-machine settings.
- Parameters: Each job has a release date r_j, due date d_j, and weight w_j used to determine timing feasibility and weighted tardiness.The release date is the earliest possible processing start, while the due date is the target completion time.
- Parameters: Setup time s_ijk depends on the job sequence and machine, including an initial setup from the machine’s idle state J_0.The initial setup is denoted s_0jk for the first job on machine M_k.
- Decisions and constraints: Each job must be assigned to an eligible machine M_k ∈ M_j; assignments implicitly determine start times, completion times, and schedule performance.The eligibility restriction excludes machines outside M_j.
- Decisions and constraints: The decisions determine which eligible machine processes each job and the processing order of jobs assigned to each machine.The schedule also enforces release dates, non-preemption, machine capacity, and setup-separated starts.
- Objectives: The formulation simultaneously minimizes total weighted tardiness and total setup time as conflicting objectives.Tardiness is T_j = max(0, C_j − d_j), while setup time is accumulated across machine sequences.
4 Methodology: PPO-GNN for Multi-Objective UPMSP
The paper formulates multi-objective UPMSP scheduling as a DRL problem solved by PPO with a tailored heterogeneous GNN. The agent interacts with a discrete-event simulator, selecting feasible job-machine assignments while balancing TWT and TST through reward design.
- PPO is combined with a tailored GNN architecture for solving multi-objective UPMSP.
- At each decision point, the agent observes the schedule state, assigns a job to a machine or waits, and receives a reward after simulation advances.The resulting experience is used to update PPO policy and value parameters.
- The state combines global system features with a heterogeneous graph representing jobs, machines, and setup relationships.Global features summarize queues, arrivals, performance, and machine status, while graph features describe entity-specific properties.
- Job-machine edges encode eligibility, processing time, and estimated setup time, while machine-setup and job-setup edges represent setup relationships.
- The action space consists of feasible job-machine pairs satisfying release, eligibility, and machine-availability conditions.Action masking assigns zero or highly negative probability to infeasible assignments.
- The reward function is designed to steer the agent toward simultaneously minimizing total weighted tardiness and total setup time.The paper considers dense, event-based, and hybrid reward structures.
5 Experimental Setup
The experiments evaluate PPO-GNN on generated UPMSP instances spanning job, machine, due-date, setup, and eligibility conditions. Performance is compared with a dispatching rule and a genetic algorithm using separate test instances and the two target objectives.
- Instance Generation: The study evaluates PPO-GNN using generated UPMSP instances that vary job counts, machine counts, due-date parameters, setup ratios, and eligibility density.The instance design follows methodologies adapted from established literature.
- Baseline Methods: The ATCSR_Rm dispatching rule serves as a heuristic baseline because it accounts for setup times and release dates.
- Baseline Methods: A tailored genetic algorithm encodes per-machine job sequences and minimizes a weighted sum of normalized TWT and TST.Its search uses selection, crossover, and mutation operators.
- Training Configuration: The PPO agent uses a GATv2-based GNN feature extractor with four layers and a 128-dimensional hidden representation.Shared GNN features feed separate actor and critic MLP heads.
- Evaluation Metrics: All methods are evaluated on test instances kept separate from training and hyperparameter tuning.
- Evaluation Metrics: Average TWT and Average TST are the primary metrics, calculated across test instances for each evaluated method.
6 Results and Discussion
Across tested problem sizes, PPO-GNN achieved the best average tardiness and setup-time performance while remaining substantially faster than GA during evaluation. Its advantage persisted across both objectives and larger instances.
- Objective performance: PPO-GNN consistently achieved the lowest Avg TWT and Avg TST for n=20/m=5, n=50/m=10, and n=100/m=15.GA improved upon ATCSR_Rm but was consistently outperformed by PPO-GNN.
- Objective performance: 420.0 Avg TWT and 225.0 Avg TST were achieved by PPO-GNN on n=100, m=15, versus 475.0 and 255.0 for GA.ATCSR_Rm recorded 610.0 Avg TWT and 290.0 Avg TST on the same largest instances; paired t-tests reported p < 0.01.
- Computational efficiency: Under 1.6 seconds was PPO-GNN’s inference time even for the largest problems, compared with around 60 seconds for GA evaluation.ATCSR_Rm executed almost instantaneously, while GA spent time on iterative search.
- Computational efficiency: PPO-GNN required a one-time offline training cost but delivered fast inference, whereas GA required a substantial computational budget for every new instance.The authors note that GA performance depends strongly on parameter settings and allowed search time.
- Multi-objective trade-off: PPO-GNN dominated GA and ATCSR_Rm in the Avg TST–Avg TWT comparison, placing performance closer to the ideal bottom-left objective vector.The comparison averages both objectives across problem sizes rather than representing merely a different Pareto-front trade-off.
- Scalability: Both Avg TWT and Avg TST increased with problem size, while PPO-GNN’s relative advantage remained consistent or slightly increased within the tested training distribution.This pattern suggests reasonable generalization to larger problems within that distribution.
- Interpretation: The GNN captured dependencies among jobs, machines, eligibility, and setups, enabling PPO to learn a policy that balanced conflicting objectives with rapid deployment execution.The design contrasts with myopic dispatching rules and potentially time-consuming metaheuristic search.
7 Conclusion and Future Work
The paper applies PPO with a heterogeneous GNN and a multi-objective reward to the constrained UPMSP. Across generated benchmark scales, PPO-GNN outperformed ATCSR_Rm and GA on average Avg TWT and Avg TST.
- Problem scope: The study addresses UPMSP with release dates, sequence- and machine-dependent setup times, and machine eligibility constraints.These constraints are evaluated alongside the conflicting objectives of tardiness and setup time.
- Proposed framework: PPO combined with an enhanced heterogeneous GNN represents job, machine, and setup information in a direct scheduling policy.The framework uses a multi-objective reward to guide simultaneous minimization of TWT and TST.
- Conclusion: Across various problem scales, PPO-GNN achieved lower Avg TWT and Avg TST than both ATCSR_Rm and GA.The result supports learning high-quality policies for complex multi-objective scheduling scenarios.