Tools › Operations Research › Scheduling

Scheduling

2 tools in the Operations Research area.

Shift Scheduling

Finds the cheapest or smallest staff that covers a cyclic demand: the requirement in every period of the day or week is pasted in, the candidate shifts are typed (start, end, cost, optional break) or generated for every start of 8-, 10- and 12-hour shifts in the work patterns of Dantzig (1954), and the covering integer program is solved by branch and bound on its linear-programming relaxation, with the staffing table, the coverage and surplus per period, the shadow price of each period and the LP bound beside the integer optimum. A second part assigns days off: daily requirements over a week, every employee working five consecutive days with two consecutive days off, the minimum workforce with its pattern table and the closed-form bounds. The default is the Union Airways agent-scheduling example of Hillier and Lieberman (48, 31, 39, 43 and 15 agents on the five shifts, 30,610 per day); Winston's post-office days-off problem (23 employees) and a bus-scheduling case are built in.

1 worked example reproduced, listed on the tool page.

Job Shop Scheduling and Sequencing

Sequences jobs on one machine, through a flow shop or through a job shop with its own routings and compares the schedules. Single machine: SPT, EDD, WSPT, first come first served, Moore-Hodgson (fewest late jobs) and Lawler's backward rule for the maximum lateness with precedence, each with the makespan, mean flow time, lateness, tardiness and number tardy. Two-machine flow shop: Johnson's rule (optimal makespan) and his three-machine special case. m-machine flow shop: the Palmer slope index, Campbell-Dudek-Smith and Nawaz-Enscore-Ham heuristics against an exact branch and bound (up to 8 jobs). Job shop: eight dispatching rules by discrete-event simulation, Giffler-Thompson active schedules, the disjunctive-graph lower bound, an exact time-boxed branch and bound (proves the Fisher-Thompson 6 x 6 optimum of 55), Gantt charts per machine and per job, machine utilisation and the critical path. Parallel machines: LPT list scheduling with Graham's bound and the exact optimum. Sequence-dependent setups: nearest neighbour and 2-opt. The default is an illustrative 5-job, 4-machine shop; the FT06 and FT10 instances of Fisher and Thompson (OR-Library data) load from the problem list.

1 worked example reproduced, listed on the tool page.

Other Operations Research sections

Optimization · Queueing and Simulation · Inventory and Supply Chain · Decision Analysis · Networks and Routing