Job Shop Scheduling and Sequencing

Job Shop Scheduling and Sequencing

Job Shop Scheduling and Sequencing: Sequencing Rules, Johnson's Rule, Flow-Shop Heuristics, Dispatching, Active Schedules and Branch and Bound

What the tool does

A shop has jobs to run and machines to run them on; a schedule says which job each machine works on and when. The tool sequences the jobs for six shop types, prints the schedule with its measures and, wherever the problem is small enough, proves what the best possible schedule is. The shop type follows the problem chosen on the form: a single machine (every job one operation), a two-machine flow shop (every job first on machine 1 then on machine 2), an m-machine flow shop (every job through the same machines in the same order), a job shop (every job its own routing), identical parallel machines (every job on any one of m machines) and a single machine with sequence-dependent setups. Times are plain numbers in one unit, named under Options.

Input format

One job per line: a one-word name, then up to three bare numbers in order (release time r_j, due date d_j, weight w_j; a lone "-" leaves one blank; blank release = 0, no due date = the due-date rules are skipped, blank weight = 1), then the routing as machine:time tokens in the order the job visits the machines (M1:3 M2:4 … or 1:3 2:4). "after:J1" makes the job follow J1 (Lawler's rule on the single machine). Machines are named by first appearance. The OR-Library matrix is read too: a first line "n m", then one line per job of m "machine time" pairs with machines numbered from 0, as in Beasley's jobshop1.txt; the FT06 and FT10 entries of the problem list load the Fisher and Thompson instances in that form. Limits: 30 jobs, 20 machines. The setup problem takes an n × n matrix of setup times (row = the job just finished, column = the next job) with an optional first row for the setup from the machine's initial state.

Measures

For job j with completion C_j: flow time F_j = C_j − r_j, lateness L_j = C_j − d_j, tardiness T_j = max(0, L_j), tardy indicator U_j = 1 when T_j > 0. The schedule measures are the makespan C_max = max C_j, the mean flow time, the mean and maximum lateness, the total tardiness, the number tardy and the weighted completion Σ w_j C_j (Conway, Maxwell and Miller 1967).

Single machine

SPT (shortest processing time first) minimises the mean flow time, hence the mean completion and the mean number of jobs in the shop. WSPT (least p_j/w_j first, Smith 1956) minimises Σ w_j C_j. EDD (earliest due date first) minimises the maximum lateness and the maximum tardiness. Moore-Hodgson (Moore 1968) minimises the number of tardy jobs: jobs are added in EDD order and, whenever the job just added would be late, the longest job scheduled so far is removed and goes to the end; the removed jobs are the late ones. Lawler (1973) minimises the maximum of any non-decreasing cost f_j(C_j) under precedence constraints, here f_j = C_j − d_j: the sequence is filled from the back; with P the total time of the jobs not yet placed, the job with no unplaced successor whose cost f_j(P) is least goes last, P is reduced by its time, and so on. Without precedence it gives EDD's maximum lateness. FCFS is the order entered. Total tardiness has no simple rule (the problem is NP-hard); the table shows what each rule gives. With release times the rules run as non-delay dispatching (among the jobs already released); Moore-Hodgson and Lawler are then not applied.

Two-machine flow shop: Johnson's rule

Every job runs first on machine 1 for a_j, then on machine 2 for b_j. Johnson (1954) proved that the makespan is minimised by placing the jobs with a_j < b_j first in increasing a_j and the others after them in decreasing b_j: job i precedes job k when min(a_i, b_k) ≤ min(a_k, b_i). The tool prints the two sets, the sequence, the completion times on both machines and the idle time of the second machine. Johnson's three-machine case: when the middle machine is dominated, min a_j ≥ max b_j or min c_j ≥ max b_j, the rule on the pseudo times a_j + b_j and b_j + c_j is optimal; the tool tests the condition and, when it fails, reports the heuristics and the exact search instead.

m-machine flow shop

Permutation schedules (the same job order on every machine) are compared. Palmer (1965) sorts the jobs by decreasing slope index s_j = Σ_k (2k − m − 1) p_jk, which puts jobs whose work lies late in the routing first. Campbell, Dudek and Smith (1970) solve m − 1 two-machine problems by Johnson's rule, the k-th with a_j = the first k times and b_j = the last k, and keep the best makespan. Nawaz, Enscore and Ham (1983) take the jobs by decreasing total work and insert each at the position of the partial sequence that gives the least makespan. The lower bound is, over the machines, the least head (work before the machine) + the machine's total work + the least tail (work after it). The exact branch and bound (up to 8 jobs) searches the permutations depth first with the bound at each node = max over machines of (completion of the partial sequence + remaining work + least remaining tail), children ordered by bound, the best heuristic as the incumbent; a time box stops it. For three or more machines a non-permutation schedule can in principle be shorter than the best permutation; the bound holds for every schedule.

Job shop

Dispatching rules are run by discrete-event simulation of the routings as non-delay schedules: whenever a machine is free and an operation is ready for it, the lowest-numbered such machine takes the operation the rule prefers (ties to the lower job number): SPT and LPT by the operation's time, FCFS by the time the operation arrived in the queue, EDD by the job's due date, least slack by d_j − t − remaining work, critical ratio by (d_j − t) / remaining work, MWKR and LWKR by the work remaining in the job. Giffler and Thompson (1960) generate active schedules: at each step the schedulable operation with the least earliest completion C* fixes the machine M*; the conflict set is every schedulable operation on M* that could start before C*; the rule picks one and it is appended to M*. A schedule is active when no operation can start earlier without delaying another; every non-delay schedule is active, the active set contains an optimal schedule for any regular measure, and the tool confirms the property on every schedule it prints.

Lower bound (disjunctive graph): no schedule finishes before the longest job chain r_j + Σ_k p_jk, nor before any machine's least head + total work + least tail, the one-machine relaxation of Carlier (1982) without its sequencing. Exact branch and bound: depth-first search over the Giffler-Thompson conflict sets, so that every leaf is an active schedule and the tree holds an optimum; at each node the bound is the maximum over the machines of Jackson's preemptive one-machine schedule of the unscheduled operations (heads from the partial schedule, tails the remaining job chains), children are ordered by bound, the incumbent is the best heuristic schedule, and a time box of 1 to 20 s stops the search. The 6 × 6 instance FT06 is proven at 55 in a fraction of a second; FT10 (optimum 930, Carlier and Pinson 1989) is not proven within the box and the page reports the best schedule found with the open bound. Critical path: from the operation that ends at C_max, back through a predecessor (job or machine) whose completion equals the start, to time zero; every link is tight and the lengths add to C_max. The Gantt charts outline the critical operations in red. Utilisation is busy time over the makespan.

Identical parallel machines

LPT list scheduling (Graham 1969): the jobs in decreasing processing time, each to the least-loaded machine. Its makespan never exceeds (4/3 − 1/(3m)) times the optimum, and the ratio is attained by Graham's worst case (2m + 1 jobs of 2m − 1, 2m − 1, …, m + 1, m + 1, m, m, m). The lower bound is max(p_max, ⌈Σ p_j / m⌉); up to 12 jobs the exact optimum is found by enumerating the assignments with symmetry breaking.

Sequence-dependent setups

With fixed processing times the makespan Σ p_j + Σ setups is least when the total setup is least, an open travelling-salesman path from the machine's initial state. The tool builds a nearest-neighbour sequence (the job with the least setup next), improves it by 2-opt (Croes 1958: every reversal of a segment that lowers the total is applied until none is left) and, up to 8 jobs, confirms the optimum by enumeration; 2-opt can stop at a local optimum, and the page says when it does. The Network Flow and Routing tool solves the closed tour exactly (Held-Karp bound and dynamic programming). Lot splitting and batching (Ohno's small-lot production, the economic batch under setup cost) change the problem's data rather than its sequence and are not modelled.

Limits

Up to 30 jobs and 20 machines; one operation per job on the single, parallel and setup problems; flow shops need the same machines in the same order on every job; the exact job-shop search is a time-boxed depth-first search meant for small instances (about 6 × 6), larger ones get the heuristics and the bound; no preemption, no machine breakdowns, no transport times, no re-entrant routings (a machine twice in one job is accepted by the dispatching and the search but not by the flow-shop readers).

Checks

The test script (test-scripts/test_job_shop_scheduling.php) checks Johnson's rule against brute-force enumeration on ten seeded two-machine instances and five three-machine instances meeting the condition, Moore-Hodgson against enumeration on ten instances, SPT / EDD / WSPT / Lawler against the enumerated optimum of their measures, Palmer, CDS and NEH against the enumerated optimum on eight seeded 5-job instances (the branch and bound equal to it), the dispatching simulation and Giffler-Thompson against an independent numpy implementation rule by rule on FT06, FT10, the default shop and six seeded shops (makespans equal, every schedule active), the exact branch and bound against scipy's MILP optimum (Manne's disjunctive formulation) on FT06 (55) and the seeded shops, LPT against the enumerated optimum with Graham's ratio and his worst cases, the setup heuristics against enumeration, and the rendered page through the site harness. Sources and the check script are filed in References/Job-Shop/.