Deep Learning for Unrelated-Machines Scheduling: Handling Variable Dimensions

AI summary

Overview

Research area: Machine learning for combinatorial optimization, specifically learning-based scheduling on unrelated parallel machines.

Technical level: Advanced (requires familiarity with Markov decision processes, LSTM/Transformer architectures, attention mechanisms, and scheduling notation such as the three-field notation used in equation 1).

Scope: This paper proposes a neural network architecture that handles variable input and output dimensions to produce complete offline schedules for unrelated-machines scheduling problems with a compound objective combining makespan and weighted tardiness of jobs and machines.

What This Paper Is About

The paper addresses deterministic offline scheduling of J jobs on M unrelated machines, where every job-machine pair has its own processing time, so the number of jobs, the number of machines, and the feature dimensions all change from instance to instance. The goal is to minimize a compound objective: the makespan C_max plus the total weighted tardiness of jobs plus the total weighted tardiness of machines (equation 1). Existing learning-based methods for unrelated machines avoid this variability by looking at only one job at a time or by reducing the action space to selecting a dispatching rule; this paper instead produces a full schedule from the entire input at once.

Key Contributions

1. An NLP-inspired network architecture for variable dimensions. The model combines a sequential embedding stage (bidirectional LSTM over per-job machine data), a Transformer encoder for inter-job context, and an Action-Pointer decoder, allowing it to process any number of jobs and machines with feature dimensions that vary with M.

2. An offline formulation as a deterministic MDP. States are constructed whenever a machine becomes free, and actions are either assigning a pending job or deactivating the machine. Because each state contains full information about pending jobs and active machines, the method is an offline solution, and the Markov property also allows online application.

3. A supervised training scheme on very small instances. Targets are softmax-scaled Q-values (equation 3), data is generated by simulating 100,000 problems with 8 jobs and 4 machines, and exact state-action values are computed on these small instances — avoiding the slower convergence of reinforcement learning.

4. A tailored dispatching rule as a benchmark. In the absence of a standard benchmark, the authors build an advanced dispatching rule with a priority function matched to the compound objective, and use it to measure generalization across job and machine counts.

Main Findings

• Near-optimal per-decision performance at training size: Across all tested combinations of 3 to 8 pending jobs and 2 to 4 active machines, the model averaged below 1% additional relative cost per state decision (Table II(a)); values in the test setting range from 0.13 to 0.63.

• Full-schedule costs at training size: For 8 jobs and 4 machines, the network policy μ_ϑ with early optimal cutoff (μ_ϑ,opt) induced 2.51% additional costs over optimal, and the plain policy μ_ϑ induced 4.47% (Table II(b)). The dispatching rule produced 34.46% (μ_rule,opt) and 45.33% (μ_rule) respectively.

• Generalization to larger instances: Trained only on 8 jobs and 4 machines, the network was tested on configurations up to 100 jobs and 10 machines. Across the tested settings in that range, the dispatching rule incurred 22.22% higher average scheduling costs than the network.

• Where the network's advantage is largest: The biggest gains were not at the training size of 8 jobs and 4 machines but at 8 to 20 jobs with 4 to 6 machines, and at 15 to 30 jobs with 5 to 8 machines. The maximum value in Table III is 38.27 (15 jobs, 6 machines).

• Where performance converges: Performance tends to equalize around 12 machines; at 12 machines many entries in Table III fall below 5, including 01.47 (8 jobs), 00.29 (10 jobs), 02.04 (11 jobs), 02.90 (12 jobs), 03.48 (15 jobs), 04.87 (20 jobs), 04.39 (30 jobs), 04.13 (50 jobs), 03.72 (75 jobs), and 03.27 (100 jobs), with the 9-job/12-machine entry reported as -01.44.

• Advantage across smaller machine counts: Except for two configurations, in settings with up to 30 jobs and between 3 and 8 machines, the dispatching rule created schedules with average costs more than 20% higher than the network, often exceeding 30%.

• Model size: The network has 117,292 parameters in total, split across the sequential embedding (4,476), Transformer encoder (9,136), and Action-Pointer (103,680); the embedded job representation has dimension 16 and the decoder query has dimension 128 (Table I).

• Training cost: Training used TensorFlow with the Adam optimizer, learning rate 0.001, batch size 128, and 30 epochs on an AMD Ryzen 5 3500 CPU (2.1 GHz, 4 cores, 8 threads), 8 GB RAM, and an 80 GB SSD, taking approximately 24 hours.

Methodology in Plain English

The scheduling problem is converted into a sequence of decision points: every time a machine becomes free, the system must either assign a waiting job to it or switch the machine off (which is only allowed if another machine is still active). Each decision point becomes a "state" containing all pending jobs and active machines, so the network always sees the whole picture rather than one job at a time.

Two practical obstacles are addressed. First, machine and job vectors are sorted by deterministic rules (machines by remaining runtime, then weight, then deadline; jobs by processing time on the free machine, then weight, then deadline) so the network sees a consistent ordering. Second, because the number of machines changes the size of each job's feature vector, each job's machine data is broken into two parts: a resource matrix with one row per machine (variable size) and an urgency vector holding the job's earliness and weight (fixed size). The variable part is compressed into a fixed-size vector by a bidirectional LSTM, and the fixed part is contextualized through a self-attention layer, after which the two are concatenated.

A Transformer encoder then lets each job representation see how other jobs interact with the same machines. The Action-Pointer decoder uses a bidirectional LSTM followed by a second bidirectional LSTM and an attention mechanism to produce a probability distribution over J jobs plus one deactivation option, so the output size automatically matches the number of pending jobs.

For training, 100,000 small problems (8 jobs, 4 machines) are simulated with weights up to 10, deadlines up to 30 (described as resembling a month), processing times up to a value drawn from [1/3·d_max, 3/2·d_max], and machine runtimes drawn from [1/3·p_max, p_max]. For each problem, 18 states are selected — one for each combination of 3 to 8 pending jobs and 2 to 4 active machines — and balanced with respect to the optimal action. Targets are softmax-scaled ratios of optimal Q-values to optimal state values (equation 3), and training minimizes mean squared error rather than cross-entropy, in order to penalize deviations from near-optimal actions precisely. Validation used 10,000 problems, a separate test set used 10,000 problems, and generalization experiments used 10,000 problems for each job/machine combination in Table III.

Why This Matters

Impact on research: The paper targets a documented gap — reviews of learning-based scheduling found that 50 out of 80 selected publications dealt with job-shop or flow-shop problems, and only a few addressed unrelated machines, all of which sidestepped variable state and action spaces by feeding one job at a time or by restricting the action space to dispatching-rule selection. This work shows that a carefully designed architecture can handle varying input dimensions and output dimensions directly, and that supervised training on tiny instances can transfer to environments with more than ten times as many jobs.

Real-world applications:

• Production and manufacturing scheduling where each job runs at a different speed on each machine, such as jobs routed across heterogeneous CNC machines or assembly lines.
• Maintenance and service operations where machines can be deactivated, with penalties for missing machine deactivation deadlines as well as job deadlines.
• Cloud or cluster resource allocation where tasks have different execution times on different hardware and machines have their own availability windows.
• Logistics and transport loading, where the "machines" are vehicles or docks with individual processing characteristics and shutdown deadlines.

Industry relevance: The authors emphasize rapid retraining enabled by the supervised setup, which contrasts with rule-based methods that require a custom solution per problem setting and with deep reinforcement learning approaches that are significantly slower to converge. State-level input normalization means the model is invariant to absolute time scale, so a trained network can be applied to problems whose time values fall outside the training ranges.

Future Directions

1. Scaling the training distribution. The authors state that additional computational resources and GPUs — taking advantage of the architecture's inherent parallelization — could expand the training set to improve generalization, particularly for higher numbers of machines, since performance currently tends to equalize around 12 machines.

2. Generalizing the problem class. The specific problem (equation 1) could become an edge case of a broader formulation by adding constraints with minimal architectural changes; setting job or machine weights to zero removes that tardiness term, and uniform-machines scheduling can be modeled by making processing times proportional.

3. Extending to stochastic settings. The paper is currently limited to deterministic problems; the authors suggest incorporating expected processing times, or, for discrete distributions, separate vectors representing potential processing times and their associated probabilities.

4. Combining with reinforcement learning. Because the framework is compatible with DRL, the authors suggest leveraging it to further improve performance while starting from the strong supervised foundation — though they do not report any DRL experiments here.

Target Audience

This paper is most useful to machine learning researchers working on neural approaches to combinatorial optimization, particularly those interested in architectures that tolerate variable problem dimensions; to operations research practitioners who need fast, retrainable heuristics for unrelated-machine scheduling; and to industrial engineers and production planners dealing with heterogeneous machine fleets and compound objectives involving both makespan and tardiness. Readers should be comfortable with scheduling notation, Markov decision processes, and sequence models such as LSTMs and Transformers. The trained model and source code are stated to be publicly available in an online repository.

Authors’ abstract

Deep learning has been effectively applied to many discrete optimization problems. However, learning-based scheduling on unrelated parallel machines remains particularly difficult to design. Not only do the numbers of jobs and machines vary, but each job-machine pair has a unique processing time, dynamically altering feature dimensions. We propose a novel approach with a neural network tailored for offline deterministic scheduling of arbitrary sizes on unrelated machines. The goal is to minimize a complex objective function that includes the makespan and the weighted tardiness of jobs and machines. Unlike existing online approaches, which process jobs sequentially, our method generates a complete schedule considering the entire input at once. The key contribution of this work lies in the sophisticated architecture of our model. By leveraging various NLP-inspired architectures, it effectively processes any number of jobs and machines with varying feature dimensions imposed by unrelated processing times. Our approach enables supervised training on small problem instances while demonstrating strong generalization to much larger scheduling environments. Trained and tested on instances with 8 jobs and 4 machines, costs were only 2.51% above optimal. Across all tested configurations of up to 100 jobs and 10 machines, our network consistently outperformed an advanced dispatching rule, which incurred 22.22% higher costs on average. As our method allows fast retraining with simulated data and adaptation to various scheduling conditions, we believe it has the potential to become a standard approach for learning-based scheduling on unrelated machines and similar problem environments.