Precast Scheduling
Permutation Flow Shop · Prefabrication · Fm | prmu | Cmax
Construction · Schedule & Sequence · TacticalPrecast concrete elements, prefab modular units, and factory-built structural assemblies all flow through a fixed sequence of production stations: casting → curing → finishing → quality control → delivery. When every element visits the stations in the same order, the production line is a classical permutation flow shop \( F_m \mid prmu \mid C_{\max} \) — one of the most-studied problems in scheduling OR. The optimal sequence of elements minimises the delivery-ready time (makespan) of the entire batch. Chan & Hu (2002) and Leu & Hwang (2002) adapted the classical Nawaz, Enscore & Ham (1983) NEH heuristic to precast plants, delivering near-optimal sequences for real-world batches of 20–50 elements per day.
Where This Decision Fits
Offsite production planning — the highlighted step is what this page optimises
The Problem
Sequence n elements through m identical-order stations
A precast plant has \( m \) stations (casting bed, steam-cure chamber, stripping area, quality check, yard staging). \( n \) elements must be produced today, each with a known processing time \( p_{ij} \) at station \( j \). All elements visit stations in the same order \( 1, 2, \ldots, m \) (permutation flow shop). The scheduling decision is the sequence \( \pi \) — a permutation of \( \{1, \ldots, n\} \) — in which elements are released to the line. Once \( \pi \) is chosen, each element's start time at each station is determined by chaining.
Here \( [k] \) is the element at position \( k \) in the permutation, so \( C_{[k], j} \) is the finish time of the \( k \)-th processed element at station \( j \). The recurrence is left-max-of-(up, down) — the element can only start at station \( j \) once the previous element has left it and it has finished at station \( j-1 \).
For \( m = 2 \) stations, Johnson (1954) gave an exact \( O(n \log n) \) algorithm. For \( m \ge 3 \), the problem becomes strongly NP-hard; Nawaz, Enscore & Ham (1983)'s NEH heuristic remains the best-known constructive method and is what this page's solver uses. Chan & Hu (2002) and Leu & Hwang (2002) demonstrated NEH's effectiveness on real precast plants with 3–5 stations and daily batches of 20–60 elements.
See base RCPSP — precedence without the flow-shop structureTry It Yourself
Compare NEH, Johnson (if 2 stations), and a random sequence
Precast Flow-Shop Scheduler
10 Elements · 4 StationsPick a scenario and algorithm, then click Sequence.
The Algorithms
From Johnson's rule to NEH to modern metaheuristics
Johnson's Rule (1954)
O(n log n) for 2 stations; also optimal for m=3 under restrictive conditionsJohnson (1954)'s elegant result: for a 2-station flow shop, partition elements into those with \( p_{i1} \le p_{i2} \) and those with \( p_{i1} > p_{i2} \); sort the first group by ascending \( p_{i1} \), the second by descending \( p_{i2} \), concatenate. Provably optimal for \( m = 2 \). For \( m = 3 \) it is optimal only when the middle station is dominated — a condition rarely met in real precast plants.
NEH (Nawaz-Enscore-Ham 1983)
O(n\u00b2 m) constructive insertionSort elements by decreasing total processing time \( \sum_j p_{ij} \). Seed the sequence with the two longest; for each subsequent element, try inserting it at every position and keep the position that gives the lowest makespan so far. After 40+ years of benchmarking, NEH still delivers within 3–5% of optimum on the Taillard benchmarks — outstanding for an O(n\u00b2m) constructive. Chan & Hu (2002) adapted it directly to precast plants. This is the default algorithm on this page.
Iterated Greedy (Ruiz-Stützle)
Iterative · destroy-d + NEH-reinsertionFor larger plants (80+ elements/day), Ruiz & Stützle (2007)'s Iterated Greedy beats NEH by another 1–2%. Repeatedly remove \( d \) random elements and re-insert them NEH-style; accept the new sequence by a Metropolis criterion. The state of the art for PFSP; implementable in Python in 50 lines.
Real-World Complexity
Why real precast plants go beyond textbook PFSP
Beyond Standard Flow Shop
- Curing is time-constrained — Concrete must cure for a minimum duration and cannot be stripped before a quality threshold. This is a no-wait or time-window flow shop (Hall & Sriskandarajah 1996 classification).
- Parallel beds per station — A plant with 4 casting beds + 1 cure chamber is a hybrid flow shop, not pure permutation; the HFS variants (Ribas et al. 2010) apply.
- Element-to-mould compatibility — Not every element fits every mould. A setup cost is incurred when consecutive elements use different moulds; sequence-dependent setup-time variants (SDST-FSP, Ruiz & Andrés 2007) apply.
- Delivery-time-window coordination — Late elements delay site erection; early ones clog yard staging. Ko & Wang (2010) integrated precast production with delivery scheduling via genetic algorithms.
- Demand-driven small batches — Modern modular construction (Katerra-style) targets small batches with rapid mix changes, stressing setup-cost modelling.
- Material availability — Reinforcing steel, prestressing strands, and special-mix additives all have lead times; truly integrated plants solve joint procurement + sequencing problems.
Related Scheduling Variants
Precast is the offsite-production sibling of on-site RCPSP
Key References
Cited above · DOIs & permanent URLs
Running a precast plant or modular factory?
From daily sequencing to integrated production-and-delivery scheduling, OR turns precast plants from craft-based to data-driven. Let's discuss how Operations Research can work for your precast or prefab operation.