Job shop scheduling (ft06)
The problem
In the job shop problem, each job is a sequence of operations, and each operation needs one machine for a fixed time. A job visits the machines in its own order, one operation at a time. A machine does one operation at a time, without interruption. The goal is the shortest makespan: the time when the last operation ends.
ft06 is the 6×6 instance of Fisher and Thompson (1963): 6 jobs, each with one operation on each of 6 machines, of 1 to 10 time units. Job 0, for example, takes 1 unit on machine 2, then 3 on machine 0, 6 on machine 1, 7 on machine 3, 3 on machine 5 and 6 on machine 4. The optimal makespan is 55.
What makes it hard
The job shop problem is NP-hard (Garey, Johnson and Sethi, 1976, Mathematics of Operations Research 1(2): 117-129). Each machine's order of its 6 operations can be chosen, but some combinations of machine orders deadlock: two machines each wait for the other.
The obvious bounds are far from the optimum. The longest job takes 47 units in all, and the busiest machine is busy for 43. The optimum, 55, has idle time that no schedule avoids.
Representation
A Permutation of the 36 operations, read as a sequence of jobs: entry k counts for job k / 6,
rounded down, so each job appears 6 times. This permutation with repetition is Bierwirth's encoding
(1995, OR Spektrum 17: 87-92). The n-th time a job appears, its n-th operation is scheduled.
The decoder starts each operation as early as its job and its machine allow, in the order of the sequence: a semi-active schedule. Every sequence gives a valid schedule, since the order within each job is kept and nothing can deadlock. Listing an optimal schedule's operations by start time gives a sequence that decodes to a schedule at least as short, so the optimum is reachable.
The six operations of a job are interchangeable in the sequence. The 36! permutations give 36! / (6!)⁶ ≈ 2.7 × 10²⁴ different sequences, and many sequences give the same schedule. The fitness is the makespan, to minimize.
Algorithm
A genetic algorithm with the operators that genoxide's guide lists for sequences:
- a population of 100;
- tournament selection of size 3;
- order crossover: the child keeps a segment of one parent, and takes the other entries in the order they have in the other parent. It goes back to the modified crossover of Davis (1985, Proceedings of IJCAI-85: 162-164), which keeps the first part of a parent instead of a segment;
- swap mutation, which exchanges two entries;
- the default generational scheme, which keeps the best individual.
The run stops at the optimum, 55, or after 5,000 generations.
Output
The first line gives the best makespan and the generations it took. The next six give each machine's jobs in the order the machine does them, with the jobs and machines numbered from 0. Together, those orders define the schedule.
The project page plays this run back.
Good results
The optimum is 55. The run reaches it after about 120 generations. Over seeds 1 to 100, every run reached it, half of them within 190 generations and 90 within 620; the slowest took 1,680.
Known optimum: 55 (makespan)
Source: examples/jobshop_ft06
Interactive run: tachsin.gr/projects/genoxide/examples/jobshop-ft06
cargo run --release --example jobshop_ft06
//! Job shop scheduling: Fisher and Thompson's 6×6 instance (ft06), whose shortest makespan is 55.
//!
//! Six jobs each go through the six machines in their own order, and a machine does one operation
//! at a time. A permutation of the 36 operations, where operation `k` counts for job `k / 6`, is
//! read as a sequence of jobs (a permutation with repetition): the n-th time a job appears, its
//! n-th operation starts as early as its job and its machine allow (a semi-active schedule). A
//! genetic algorithm with order crossover and swap mutation searches the sequences.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its run for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example jobshop_ft06
//! ```
mod trace;
use genoxide::prelude::*;
const JOBS: usize = 6;
const MACHINES: usize = 6;
// each job's operations in order: (machine, duration)
const INSTANCE: [[(usize, u32); MACHINES]; JOBS] = [
[(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 OPTIMUM: f64 = 55.0;
// the start time of each job's operations in the semi-active schedule of `order`
fn schedule(order: &Order) -> [[u32; MACHINES]; JOBS] {
let mut starts = [[0; MACHINES]; JOBS];
let mut next = [0; JOBS];
let mut job_free = [0; JOBS];
let mut machine_free = [0; MACHINES];
for &operation in order.iter() {
let job = operation / MACHINES;
let (machine, duration) = INSTANCE[job][next[job]];
let start = job_free[job].max(machine_free[machine]);
starts[job][next[job]] = start;
next[job] += 1;
job_free[job] = start + duration;
machine_free[machine] = start + duration;
}
starts
}
// when the last operation ends
fn makespan(order: &Order) -> f64 {
let starts = schedule(order);
let last = MACHINES - 1;
let end = |job: usize| starts[job][last] + INSTANCE[job][last].1;
f64::from((0..JOBS).map(end).max().unwrap_or(0))
}
fn main() -> Result<()> {
let ga = Ga::builder(Permutation::new(JOBS * MACHINES)?)
.population_size(100)
.select(Tournament::new(3)?)
.crossover(OrderCrossover)
.mutate(SwapMutation::new())
.minimize()
.seed(1)
.build()?;
// with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
let mut trace = trace::Trace::from_env();
let outcome = Engine::new(ga, makespan)
.stop_when(Stop::target(OPTIMUM).or(Stop::generations(5_000)))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
println!(
"makespan {} after {} generations (the optimum: {OPTIMUM})",
outcome.best_fitness(),
outcome.generations()
);
// each machine's jobs, in the order it does them
let starts = schedule(outcome.best_genome());
for machine in 0..MACHINES {
let mut jobs: Vec<(u32, usize)> = Vec::new();
for (job, operations) in INSTANCE.iter().enumerate() {
for (step, &(on, _)) in operations.iter().enumerate() {
if on == machine {
jobs.push((starts[job][step], job));
}
}
}
jobs.sort_unstable();
let jobs: Vec<usize> = jobs.into_iter().map(|(_, job)| job).collect();
println!("machine {machine}: jobs {jobs:?}");
}
trace.write();
Ok(())
}
python examples/jobshop_ft06/main.py
"""Job shop scheduling: Fisher and Thompson's 6×6 instance (ft06), whose shortest makespan is 55.
Six jobs each go through the six machines in their own order, and a machine does one operation at
a time. A permutation of the 36 operations, where operation ``k`` counts for job ``k // 6``, is
read as a sequence of jobs (a permutation with repetition): the n-th time a job appears, its n-th
operation starts as early as its job and its machine allow (a semi-active schedule). A genetic
algorithm with order crossover and swap mutation searches the sequences.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its run for the plot on the example's
page, with trace.py.
python examples/jobshop_ft06/main.py
"""
import genoxide as gx
from trace import Trace
JOBS = 6
MACHINES = 6
# each job's operations in order: (machine, duration)
INSTANCE = [
[(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)],
]
OPTIMUM = 55
def schedule(order):
"""The start time of each job's operations in the semi-active schedule of ``order``."""
starts = [[0] * MACHINES for _ in range(JOBS)]
next_step = [0] * JOBS
job_free = [0] * JOBS
machine_free = [0] * MACHINES
for operation in order.tolist():
job = operation // MACHINES
machine, duration = INSTANCE[job][next_step[job]]
start = max(job_free[job], machine_free[machine])
starts[job][next_step[job]] = start
next_step[job] += 1
job_free[job] = start + duration
machine_free[machine] = start + duration
return starts
def makespan(order):
"""When the last operation ends."""
starts = schedule(order)
return float(max(starts[job][-1] + INSTANCE[job][-1][1] for job in range(JOBS)))
ga = gx.Ga(
gx.Permutation(JOBS * MACHINES),
population_size=100,
select=gx.Tournament(3),
crossover=gx.OrderCrossover(),
mutation=gx.SwapMutation(),
objective="minimize",
seed=1,
)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(INSTANCE, MACHINES, OPTIMUM, schedule)
result = ga.run(makespan, target=OPTIMUM, generations=5_000, on_generation=trace.on_generation)
print(
f"makespan {result.best_fitness:.0f} after {result.generations} generations "
f"(the optimum: {OPTIMUM})"
)
# each machine's jobs, in the order it does them
starts = schedule(result.best_genome)
for machine in range(MACHINES):
jobs = sorted(
(starts[job][step], job)
for job, operations in enumerate(INSTANCE)
for step, (on, _) in enumerate(operations)
if on == machine
)
print(f"machine {machine}: jobs {[job for _, job in jobs]}")
trace.write()
What it prints, from a seeded run:
makespan 55 after 117 generations (the optimum: 55)
machine 0: jobs [0, 3, 2, 5, 1, 4]
machine 1: jobs [1, 5, 3, 4, 0, 2]
machine 2: jobs [2, 0, 1, 4, 3, 5]
machine 3: jobs [2, 5, 3, 0, 1, 4]
machine 4: jobs [1, 4, 3, 2, 5, 0]
machine 5: jobs [2, 5, 1, 0, 4, 3]