Source-linked AI summary
Transformer-Based Flow Shop Scheduling Using MILP-Generated Training Data
Roderich Wallrath
TL;DR
The paper asks whether transformers can learn optimized non-permutation flow shop schedules with secondary resources, especially for a fixed recurring job pool. It trains a decoder-only transformer on MILP-generated tokenized schedules and completes random prefixes with constrained decoding. The transformer outperforms GA, NEH, and random search, but is outperformed by IG and MILP.
Problem
Learning-based scheduling has focused mainly on RL and related methods, leaving comparatively little evidence on supervised learning directly from rigorously optimized schedules for this setting.
Method
A decoder-only transformer learns next-token prediction from MILP-generated schedules, then completes prefixes using constrained decoding and sampling-based search.
Results
The transformer outperforms GA, NEH, and random search, but is outperformed by IG and MILP in makespan comparisons.
Takeaways & Limitations
Transformer models can learn patterns from MILP-optimized non-permutation flow shop schedules for a fixed job pool.
Takeaways & Limitations
The model is tied to its fixed training job pool, and generalization to unseen jobs, processing times, eligibility structures, larger flow shops, or industrial cases remains future work.
Abstract
from arXiv · showhide
Advances in machine learning (ML) have created new opportunities to complement traditional operations research (OR) methods. In particular, transformer models can capture complex interactions in token sequences by mapping tokens into a high-dimensional embedding space and propagating contextual information via attention. This makes them a candidate to model non-permutation flow shop scheduling with secondary resources as a next-token prediction task, where tokens represent job-machine-secondary resource tuples. For training, mixed-integer linear programming (MILP)-generated schedules are tokenized and used as next-token prediction data. During inference, partial token sequences (prefixes) are randomly generated and completed by the trained transformer through constrained decoding. A computational study is conducted on a flow shop with 8 jobs, 4 machines, and 3 secondary resources, where jobs are selected from a fixed pool of 20 jobs that is sampled during training and provides the candidates during prefix completion. The transformer achieves better solution quality (smaller makespans) compared to a genetic algorithm (GA), the NEH heuristic, and random search. It is outperformed only by the MILP model and the iterated greedy (IG) heuristic. The study concludes that transformer models can, to some extent, learn patterns from MILP-optimized non-permutation flow shop schedules and that transformer-based scheduling represents an interesting direction for future research, particularly in settings with a fixed, recurring job set.
1 Introduction
This section motivates learning-based flow shop scheduling and frames transformers as a candidate for learning optimized schedules from structured token sequences. The paper focuses on supervised learning from MILP-generated schedules for a fixed, recurring job pool.
- Flow shop scheduling is NP-hard, motivating progression from simple heuristics toward GA, MILP, CP, and ML methods.
- General scheduling rules and compact representations raise the question of whether ML can approximate NP-hard flow shop optimization.
- Transformers model schedules as token sequences and use attention to capture long-range interactions among operations.
- The study uses supervised next-token prediction on MILP-generated schedules for a non-permutation flow shop with secondary resources and a fixed job pool.
2 Related Work
Prior learning-based scheduling research is dominated by reinforcement learning and related guided approaches, while direct supervised learning from rigorously optimized schedules has received comparatively little attention. This paper addresses that gap with a decoder-only transformer trained on MILP-generated schedules.
- Existing learning-based scheduling studies commonly use reinforcement learning, diverse neural architectures, imitation learning, self-labeling, or reward and action-space design.
- RL studies can match or outperform heuristics in some settings, but comparisons with rigorous methods and performance on unseen instances remain concerns.
- Guided approaches combine RL with supervised signals, local search, or graph-based imitation learning, but reported comparisons include solver limits and suboptimal reference solutions.
- The paper proposes a decoder-only transformer trained with next-token prediction on MILP-generated schedules for non-permutation flow shops with secondary resources.
3 Transformer-based flow shop scheduling
The paper represents feasible non-permutation flow shop schedules as sequences of job-machine-worker tokens and trains a transformer to complete partial sequences. Constrained decoding masks infeasible choices so generated sequences remain valid schedules.
- 3.1 Problem description and training data generation: The problem minimizes makespan while jobs visit machines in a common order, may change sequence between machines, and require capacity-limited eligible worker groups.
- 3.1 Problem description and training data generation: Each schedule becomes exactly T = N · M tokens, with each token encoding a job, machine, and assigned worker group.
- 3.2 Transformer-based schedule completion: The transformer predicts each next operation token from the preceding prefix and autoregressively completes the sequence to length T.
- 3.2 Transformer-based schedule completion: Constrained decoding masks tokens violating machine order, worker eligibility, job completion, or the limit of N distinct jobs.
- 3.2 Transformer-based schedule completion: Sampling-based search generates K_s completions, simulates them with the ground-truth DES model, and reports the sequence with the smallest makespan.
4 Computational study
The computational study benchmarks a transformer and several scheduling methods on partial non-permutation flow-shop schedules, using shared prefixes, job pools, and evaluation budgets. It examines solution quality, decision-space complexity, runtime, and the quality of MILP-generated training labels.
- Experimental setup: The study uses 8 jobs, 4 machines, a 20-job candidate pool, three worker groups, and 40,000 MILP-generated training schedules.Processing times are uniformly sampled from [1, 100], and worker-group capacities are (2, 2, 3).
- Evaluation process: All methods receive the same prefix and job pool, complete exactly 8 jobs, and are evaluated by the DES makespan of the resulting full schedule.The transformer, IG, GA, and random search receive the same budget of 1,600 candidate-schedule evaluations per prefix instance.
- Problem complexity: The completion problem combines operation sequencing, job selection, and worker-group assignment, producing a very large decision space.With tp = 8 and all jobs eligible for three worker groups, the sequencing space alone can reach approximately 1.85 × 10^25 schedules.
- Problem complexity: The transformer sees only a small fraction of the possible training and prefix spaces, so memorizing training schedules is a negligible explanation for its performance.The training set contains 40,000 schedules, while the paper describes much larger feasible-schedule and prefix spaces.
- Results: Across prefix lengths, MILP performs best, IG follows, and the transformer is competitive with NEH while outperforming GA and random search on average.The transformer’s mean makespans are 10.6% larger than MILP’s across tp = 1, ..., 8, and 6% smaller than random search when averaged over all prefix lengths.
- Runtime and label quality: Transformer inference takes 20–40 s, but training-data generation and model training require substantial offline computation before amortization.Generating 40,000 MILP schedules requires approximately 40,000 CPU-hours, and training adds approximately three days; the reported break-even point against IG is about 18,000 instances.
5 Conclusion
The study shows that a transformer can learn non-permutation flow shop scheduling with secondary resources from MILP-generated schedules for a fixed job pool. Its preliminary results indicate competitive solution quality and fast inference, while generalization and larger-scale evaluation remain open.
- The transformer learns non-permutation flow shop scheduling with secondary resources as a next-token prediction task from MILP-generated schedules.
- It outperforms the GA, NEH heuristic, and random search, but is outperformed by the IG heuristic and MILP model.
- Training is compute-intensive and requires many sample schedules, although a relatively simple architecture and process are effective.
- The model is tied to its fixed training job pool because it learns purely from token identities.
- Generalization to unseen jobs, processing times, eligibility structures, larger flow shops, and industrial cases remains future work.
A Transformer architecture
The transformer represents tokens with learned embeddings and processes them through stacked attention-based layers with relative position information and feed-forward networks.
- Each unique token is mapped through a learnable embedding layer to a 128-dimensional representation.
- The architecture contains 4 stacked layers with 8 attention heads per layer.
- Each layer combines bidirectional multi-head self-attention, padding masks, learned relative position bias, and a positionwise feed-forward network.
B MILP model
The MILP model jointly selects jobs, schedules their operations, and assigns eligible worker groups while enforcing flow-shop, machine, and resource constraints.
- The MILP performs job selection, scheduling, and worker-group assignment, and generates training data through an equivalent time-indexed variant.
- Constraint (2) selects exactly N jobs and fixes the prefix jobs.
- Constraint (3) enforces each selected job’s machine order, while constraint (4) sets unselected jobs’ completion times to zero.
- Constraints (5)–(6) impose big-M disjunctions between selected jobs on machines.
- Constraint (7) assigns every selected operation to exactly one eligible worker group, while resource constraints prevent excessive overlap.
C Detailed makespan results
Figure 7 presents DES makespan distributions across 50 evaluated instances for different prefix lengths. Although instance-level spread is considerable, the methods’ relative performance is consistent across the population.
- The spread across instances is considerable because each seed creates a different random prefix and completion problem.
- Relative method performance remains consistent across the instance population.
- Figure 7 reports DES makespan per prefix length for all methods over 50 evaluated instances.
- The top panel covers tp = 1, . . . , 8, while the bottom panel covers tp = 9, . . . , 16.