Steel Production Line
The Problem
Why steel production is a no-wait scheduling challenge
Continuous Casting & Hot Rolling
In continuous casting and steel production, molten steel slabs must pass through a series of processing stages — heating in a furnace, rolling in a mill, and controlled cooling — without any waiting between stages. The metal cannot be allowed to cool down between steps; if a slab sits idle between the furnace and the rolling mill, it loses temperature, resulting in defective products, wasted energy for reheating, or scrapped material entirely.
This operational constraint maps directly to the No-Wait Flow Shop Scheduling Problem (Fm | prmu, no-wait | Cmax). The objective is to find the optimal sequence of steel slabs through all stages that minimizes the total production time (makespan), while ensuring that each slab transitions immediately from one machine to the next.
n steel slabs, m processing stages (machines)
Each slab j has processing time p[j][i] on stage i
No waiting allowed: slab must move immediately to next stage
Complexity: NP-hard for m ≥ 3 machines
Stages
- Furnace (Reheating)
- Rolling Mill
- Cooling Line
No-Wait Constraint
A slab finishing in the furnace must enter the rolling mill immediately. The start of a slab on a later machine is completely determined by its start time on the first machine, creating contiguous processing blocks.
Try It Yourself
Interactive no-wait flow shop solver for steel slab scheduling
Steel Slab Scheduling
5 slabs · 3 stages (Furnace, Rolling Mill, Cooling) · Click any cell to editValues in minutes
| Slab | Furnace | Rolling Mill | Cooling |
|---|
The Algorithms
How no-wait flow shop heuristics work under the hood
Delay Matrix Computation
The key data structure in no-wait flow shop scheduling is the delay matrix
D[j][k]. This gives the minimum time gap between the start of job
j and the start of job k (on machine 1) such that no-wait
is preserved for job k on all machines.
( ∑i=1r p[j][i] ) - ( ∑i=1r-1 p[k][i] )
This ensures that on every machine r, job k does not start
before job j finishes on that machine. The no-wait constraint
forces job k to start at exactly D[j][k] time units after job j
begins on the first machine.
Because D[j][k] is generally not equal to D[k][j], the delay matrix is asymmetric. This makes the no-wait flow shop reducible to an Asymmetric Traveling Salesman Problem (ATSP), where the delay values serve as arc costs between jobs.
Nearest Neighbor Heuristic
A greedy algorithm analogous to the nearest-neighbor heuristic for TSP, adapted for the no-wait constraint using the delay matrix.
- Start with the first unscheduled job (or try all starting jobs in multi-start variant).
- At each step, pick the unscheduled job
kwith the smallest delayD[last][k]from the most recently scheduled joblast. - Append
kto the sequence and repeat until all jobs are scheduled.
NEH-NW (Nawaz-Enscore-Ham for No-Wait) Heuristic
The celebrated NEH constructive heuristic adapted for the no-wait variant. Widely regarded as the best constructive heuristic for PFSP, extended here using delay-matrix-based makespan evaluation.
- Sort all jobs in descending order of total processing time
(
∑i p[j][i]). Jobs with longer total processing times are considered first. - Begin with the first job in the sorted order as the initial partial sequence.
- For each remaining job, try inserting it into every possible position in the current partial sequence.
- Evaluate the no-wait makespan at each insertion position using the delay matrix. Keep the position yielding the minimum makespan.
- Repeat until all jobs are inserted.
each position requiring O(m) for delay-based makespan
Gangadharan-Rajendran Heuristic
A priority-index heuristic proposed by Gangadharan & Rajendran (1993), specifically designed for no-wait flow shops. It uses position-dependent weights that emphasize earlier stages more heavily.
- Compute a weighted processing time index for each job:
W[j] = ∑i=1m (m - i + 1) × p[j][i], giving higher weight to earlier stages. - Sort jobs in descending order of
W[j]to form the initial sequence. - Apply pairwise interchange improvement: for each pair of adjacent jobs, swap them if it reduces the makespan.
- Repeat the improvement pass until no further swaps reduce the makespan.
Real-World Complexity
Why industrial steel scheduling goes beyond the textbook model
Temperature Constraints
Slabs must maintain specific temperature ranges at each stage. Temperature loss during transfer is non-linear and depends on slab thickness, alloy composition, and ambient conditions.
Equipment Maintenance Windows
Rolling mills require periodic maintenance shutdowns. Scheduling must account for planned downtime, roll changes, and calibration periods that create unavailability windows on machines.
Time-of-Day Energy Costs
Electricity prices vary significantly throughout the day. Furnace operations are energy-intensive, creating incentives to schedule heating during off-peak hours, adding a cost-aware objective.
Quality Grades & Multiple Casters
Different steel grades (structural, automotive, stainless) require distinct processing paths and temperatures. Plants with multiple continuous casters add parallel machine routing decisions.
References
Key literature on no-wait flow shop scheduling
Need to optimize your production line?
Reach out to discuss how operations research can improve your manufacturing scheduling.
Data shown is illustrative. Processing times are simplified for demonstration. Real steel production involves additional constraints not modeled here.