Tools › Operations Research › Scheduling › Job Shop Scheduling and Sequencing › Example

Five-job, four-machine job shop: eight dispatching rules, Giffler-Thompson active schedules, the disjunctive-graph bound and the exact branch and bound

ToolJob Shop Scheduling and Sequencing
SourceGiffler, B., and Thompson, G. L. (1960). "Algorithms for Solving Production-Scheduling Problems." Operations Research, Vol. 8, No. 4, pp. 487–503 (active-schedule generation); Carlier, J. (1982). "The One-Machine Sequencing Problem." European Journal of Operational Research, Vol. 11, No. 1, pp. 42–47 (head-body-tail bound, Jackson's preemptive schedule); Fisher, H., and Thompson, G. L. (1963). "Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules." In Muth, J. F., and Thompson, G. L. (eds.), Industrial Scheduling, Prentice-Hall, Englewood Cliffs, NJ, pp. 225–251 (the FT06 instance, optimum 55, loadable from the problem list).
LevelUndergraduate

Problem

Five jobs with release 0, due dates 14 / 16 / 18 / 12 / 20 h and weights 1 / 2 / 1 / 1 / 1 run through four machines on their own routings: J1 M1(3) M2(4) M3(2) M4(3); J2 M2(2) M1(5) M4(3) M3(4); J3 M3(4) M2(3) M1(2) M4(5); J4 M1(2) M3(3) M2(4) M4(2); J5 M4(3) M1(4) M2(2) M3(3). Find the lower bound on the makespan, the makespan of each dispatching rule (non-delay simulation and Giffler-Thompson), the optimal makespan by branch and bound, and the schedule's utilisation and critical path.

Inputs to Enter

  • Problem: Job shop, illustrative 5 jobs, 4 machines (the default job lines); time unit h; search time 5 s; Gantt schedule: best found
Open the Job Shop Scheduling and Sequencing tool (loaded with this example)

Answers

  • Lower bound 21 h: machine M1 (least head 0 + work 16 + least tail 5 = 21) binds; longest job chain 14 h (J3 and J5)
  • Non-delay dispatching makespans: SPT 28, LPT 27, FCFS 23, EDD 23, least slack 23, critical ratio 23, MWKR 23, LWKR 25 h; Giffler-Thompson: SPT 25, LPT 26, FCFS 23, EDD 23, SLACK 23, CR 23, MWKR 26, LWKR 32 h; every schedule active
  • Branch and bound over the Giffler-Thompson conflict sets with Jackson's preemptive bound: optimal makespan 21 h, proven (equal to the bound; scipy MILP on Manne's formulation gives 21 as well), improving the best heuristic 23 by 2 h
  • Optimal schedule: utilisation M1 / M2 / M3 / M4 = 76.2 / 71.4 / 76.2 / 76.2 % (16, 15, 16, 16 h busy of 21); critical path J3/M3 (0–4) → J4/M3 (4–7) → J4/M2 (7–11) → J4/M4 (11–13) → J3/M4 (13–18) → J1/M4 (18–21), length 21 h; mean flow time 17.4 h, maximum lateness 7 h (J1), total tardiness 9 h, 3 jobs tardy, Σ w_j C_j = 101 h

Notes

The tool's default inputs are this shop; press Submit. The shop is illustrative (stated on the page); every value is checked by test_job_shop_scheduling.php (643 checks) against an independent numpy re-implementation of the rules (same tie-breaking) and scipy's MILP; the FT06 instance from the problem list is proven at the published 55 in 160 nodes, and FT10 (optimum 930) is reported as not proven within the time box.