Job-shop scheduling

Deep dive

How it works

Parts:

• Operation node — job, step, machine, duration p.
• Disjunctive pair — two operations on one machine; "a before b" or "b before a" is an arc direction. A full selection is a schedule if the graph is acyclic.
• Longest path — start time = longest path from the source; makespan = longest path to the sink. Operations on it are critical; runs on one machine are blocks.
• Generator — Giffler-Thompson builds an active schedule from a priority rule.
• Improver — neighbourhood move plus tabu list, or a CP model with interval variables.

Steps:

1. Generate (Giffler-Thompson): among each job's next operation take o* with the smallest earliest completion c*, on machine m*. The conflict set is every ready operation on m* that could start before c*. Pick by rule (SPT: shortest p; MWKR: most work remaining in its job), schedule it, repeat. This yields active schedules, which contain an optimal one; non-delay schedules (no machine idles while work waits) are fewer and may miss it.
2. Evaluate: orient machine arcs, run a topological longest-path pass, trace predecessors for a critical path (critical path analysis).
3. Neighbours: swap adjacent operations on a critical block; this never creates a cycle (van Laarhoven et al. 1992). N5 (Nowicki & Smutnicki 1996) keeps only the first two and last two of each block.
4. Tabu search: take the best admissible neighbour even if worse, ban the reverse swap for a few iterations, keep the best schedule.
5. CP alternative: an interval variable per operation, no-overlap per machine, job precedences, minimise the maximum end; edge-finding and other propagators prune start windows (constraint propagation).
6. Flexible job shop: each operation picks one of several machines: optional intervals with exactly one present, or a move-to-other-machine neighbourhood.

J0: [m2:1]-->[m0:3]-->[m1:6]        job arcs fixed
J2: [m2:5]-->[m3:4]-->...
machine m2 order choice:  J0.op0 -> J2.op0   (or reversed)   <- disjunctive arc
critical path = longest source-to-sink chain; blocks = runs on one machine

Code

ft06 (Fisher & Thompson 6x6; data typed from memory, and the run reaches the known optimum 55). Asserts cover precedence, machine overlap, makespan = longest path, search never worse, determinism.

use std::time::Instant;
const FT06: [[(usize, i64); 6]; 6] = [
    [(2, 1), (0, 3), (1, 6), (3, 7), (5, 3), (4, 6)],
    [(1, 8), (2, 5), (4, 10), (5, 10), (0, 10), (3, 4)],
    [(2, 5), (3, 4), (5, 8), (0, 9), (1, 1), (4, 7)],
    [(1, 5), (0, 5), (2, 5), (3, 3), (4, 8), (5, 9)],
    [(2, 9), (1, 3), (4, 5), (5, 4), (0, 3), (3, 1)],
    [(1, 3), (3, 3), (5, 9), (0, 10), (4, 4), (2, 1)],
];
const N: usize = 6; // jobs; each has M ops, one per machine
const M: usize = 6;
type Seqs = Vec<Vec<usize>>; // per machine: op ids (job*M + k) in processing order
fn dur(o: usize) -> i64 { FT06[o / M][o % M].1 }
fn mach(o: usize) -> usize { FT06[o / M][o % M].0 }
// Giffler-Thompson: generates active schedules; SPT picks within the conflict set.
fn giffler_thompson() -> Seqs {
    let (mut next, mut jr, mut mr) = ([0usize; N], [0i64; N], [0i64; M]);
    let mut seqs: Seqs = vec![vec![]; M];
    for _ in 0..N * M {
        let cand: Vec<usize> = (0..N).filter(|&j| next[j] < M).map(|j| j * M + next[j]).collect();
        let start = |o: usize| jr[o / M].max(mr[mach(o)]);
        let &star = cand.iter().min_by_key(|&&o| (start(o) + dur(o), o)).unwrap();
        let (m, ect) = (mach(star), start(star) + dur(star));
        // conflict set: ops on m* that could start before ect; pick the shortest
        let &pick = cand.iter().filter(|&&o| mach(o) == m && start(o) < ect)
            .min_by_key(|&&o| (dur(o), o)).unwrap();
        let (j, s) = (pick / M, start(pick));
        jr[j] = s + dur(pick); mr[m] = jr[j]; next[j] += 1;
        seqs[m].push(pick);
    }
    seqs
}
// Longest path over job arcs + chosen machine arcs: (starts, makespan, critical path); None on a cycle.
fn evaluate(seqs: &Seqs) -> Option<(Vec<i64>, i64, Vec<usize>)> {
    let n = N * M;
    let mut mpred = vec![usize::MAX; n];
    for s in seqs { for w in s.windows(2) { mpred[w[1]] = w[0]; } }
    let jpred = |o: usize| if o % M > 0 { o - 1 } else { usize::MAX };
    let (mut st, mut via, mut done) = (vec![0i64; n], vec![usize::MAX; n], vec![false; n]);
    let mut cnt = 0;
    while cnt < n { // O(n^2) topological sweep; fine for 36 nodes
        let mut progressed = false;
        for o in 0..n {
            if done[o] { continue; }
            let (a, b) = (jpred(o), mpred[o]);
            if [a, b].iter().any(|&p| p != usize::MAX && !done[p]) { continue; }
            for p in [a, b] {
                if p != usize::MAX && st[p] + dur(p) > st[o] { st[o] = st[p] + dur(p); via[o] = p; }
            }
            done[o] = true; cnt += 1; progressed = true;
        }
        if !progressed { return None; }
    }
    let end = (0..n).max_by_key(|&o| (st[o] + dur(o), o)).unwrap();
    let mut path = vec![end];
    while via[*path.last().unwrap()] != usize::MAX { path.push(via[*path.last().unwrap()]); }
    path.reverse();
    let mk = st[end] + dur(end);
    Some((st, mk, path))
}

// Tabu search: best admissible adjacent critical swap, even if worse; no swap-back for TENURE steps.
fn local_search(mut seqs: Seqs, iters: usize) -> (Seqs, i64) {
    const TENURE: usize = 8;
    let (_, mut cur, mut path) = evaluate(&seqs).unwrap();
    let (mut best, mut best_seqs) = (cur, seqs.clone());
    let mut tabu = vec![vec![0usize; N * M]; N * M]; // tabu[a][b]: "a before b" banned until then
    for it in 1..=iters {
        let mut pick: Option<(i64, usize, usize, Vec<usize>)> = None;
        for w in path.windows(2) {
            let (a, b) = (w[0], w[1]);
            if mach(a) != mach(b) { continue; }
            let s = &mut seqs[mach(a)];
            let i = s.iter().position(|&o| o == a).unwrap();
            s.swap(i, i + 1);
            if let Some((_, mk, p)) = evaluate(&seqs) {
                let ok = tabu[b][a] <= it || mk < best; // aspiration: a new best overrides tabu
                if ok && pick.as_ref().map_or(true, |x| mk < x.0) { pick = Some((mk, a, b, p)); }
            }
            seqs[mach(a)].swap(i, i + 1);
        }
        let Some((mk, a, b, p)) = pick else { break };
        let s = &mut seqs[mach(a)];
        let i = s.iter().position(|&o| o == a).unwrap();
        s.swap(i, i + 1);
        tabu[a][b] = it + TENURE; // now b precedes a; ban putting a back before b
        (cur, path) = (mk, p);
        if cur < best { best = cur; best_seqs = seqs.clone(); }
    }
    (best_seqs, best)
}

fn check(seqs: &Seqs, st: &[i64], mk: i64) {
    for j in 0..N { for k in 1..M { assert!(st[j * M + k] >= st[j * M + k - 1] + dur(j * M + k - 1)); } }
    for s in seqs { for w in s.windows(2) { assert!(st[w[1]] >= st[w[0]] + dur(w[0])); } }
    assert_eq!(mk, (0..N * M).map(|o| st[o] + dur(o)).max().unwrap());
}

fn run() -> (i64, i64, Seqs) {
    let s0 = giffler_thompson();
    let (st, m0, _) = evaluate(&s0).unwrap();
    check(&s0, &st, m0);
    let (s1, m1) = local_search(s0, 500);
    let (st, m1b, _) = evaluate(&s1).unwrap();
    check(&s1, &st, m1b);
    assert_eq!(m1, m1b);
    assert!(m1 <= m0);
    (m0, m1, s1)
}

fn main() {
    let t = Instant::now();
    let (m0, m1, s1) = run();
    let el = t.elapsed();
    assert_eq!((m0, m1, s1), run()); // deterministic
    println!("GT+SPT makespan {m0}, after critical-swap tabu search {m1} (known optimum 55), {el:?}");
}

Run (release): GT+SPT 94; 500 tabu iterations reach 55 in about 1.4 ms (three runs, 1.39-1.48 ms). Strict descent on critical swaps stayed at 94.

Complexity and constants

• Generation O(n^2) by scan, O(n log n) with heaps. Evaluation O(n) with a topological order (the code's sweep is O(n^2) for brevity). A tabu iteration costs O(n) evaluations.
• Cost drivers: evaluation count and allocation. Memory O(n).

Efficiency

• Cost: compute-bound, tiny working set; measured about 1.4 ms for 500 tabu iterations on 36 operations.
• Levers:
  • Block-end moves only (N5) — fewer evaluations per iteration (Nowicki & Smutnicki 1996) — always.
  • Incremental heads/tails, estimating a swap before applying it — avoids a full pass per neighbour — large instances.
  • Time limit plus the heuristic schedule as CP hint — bounds search time — when proof is not needed.
• Naive → standard → state of the art: random orders, full evaluation · poor · dispatching plus critical-block tabu · near-optimal, ms to s · hybrid CP/large neighbourhood search · best known.

Implementation notes

• Index job * M + step: job predecessor is o - 1; a swap is two writes, undone in place.
• Release dates or deadlines: weighted source/sink arcs, or time-window feasibility.
• CP-SAT: new_interval_var, add_no_overlap per machine, minimise a makespan variable; new_optional_interval_var for flexible.

Pitfalls

• Non-adjacent or non-critical swaps can create cycles or do nothing; test for cycles.
• Plateaus: many swaps keep the makespan, so pure descent stalls (here at 94).

Variants and alternatives

In production

• CP solvers expose interval variables, no-overlap and edge-finding: OR-Tools CP-SAT, IBM CP Optimizer.

Implementations

Sources

• Giffler, Thompson, Algorithms for Solving Production-Scheduling Problems, Operations Research 8(4), 1960, 487-503. paper
• Nowicki, Smutnicki, A Fast Taboo Search Algorithm for the Job Shop Problem, Management Science 42(6), 1996, 797-813. paper
• van Laarhoven, Aarts, Lenstra, Job Shop Scheduling by Simulated Annealing, Operations Research 40(1), 1992, 113-125. paper
• Carlier, Pinson, An Algorithm for Solving the Job-Shop Problem, Management Science 35(2), 1989, 164-176. paper
• Taillard, Benchmarks for basic scheduling problems, European Journal of Operational Research 64(2), 1993, 278-285. paper
• Fisher, Thompson, Probabilistic learning combinations of local job-shop scheduling rules, in Muth, Thompson (eds.), Industrial Scheduling, Prentice-Hall, 1963, 225-251.