Shift Scheduling

Shift Scheduling

Shift Scheduling: Cyclic Staffing, the Covering Program, Branch and Bound and Days-Off Scheduling

What the tool does

A service that runs around the clock or around the week needs a known number of people in every period: agents at an airport counter in each two-hour block, buses on the road in each four-hour block, toll collectors in each half hour, clerks on each day of the week. The people come in shifts (or weekly patterns) that each span several periods, so the question is how many to put on each shift so that every period has at least its requirement at the least cost or with the fewest people. That is the cyclic staffing problem first written as a linear program by Dantzig in his 1954 comment on Edie's toll-booth study. The tool solves two forms of it: shift coverage over the periods of a day (any period lengths, typed or generated shifts, optional unpaid breaks) and days-off scheduling over a week (five consecutive days on, two off).

The covering program

Let the periods be t = 1 … P, forming a cycle (the period after the last is the first, so a night shift may wrap around). Let d_t be the staff required in period t, let shift j cover the set of periods S_j with a cost c_j per person, and let x_j be the number of people assigned to shift j. The program is

minimize Z = Σ_j c_j x_j   subject to   Σ_{j : t ∈ Sj} x_j ≥ d_t for every period t,   x_j ≥ 0 and integer.

Dantzig wrote the coefficient a_tj = 1 when shift j works in period t and 0 otherwise; his toll-collector tour was 15 half-hour periods with the eighth free for the meal, so a_tj = 1 for t = j … j+6 and j+8 … j+14. The tool reproduces that pattern when a break position is entered for generated shifts: every shift of the chosen length has that period unpaid and uncovered. Hillier and Lieberman's Union Airways example (Section 3.4) is the same program with five typed shifts and ten periods of unequal length; the bus problem printed by Jensen and Bard (after Taha) has six four-hour periods and eight-hour shifts starting at each of them.

With the objective "headcount" every c_j is 1 and Z counts people. With "cost" the entered cost per person applies; relative costs are enough (1, 1.3 and 1.6 for 8-, 10- and 12-hour shifts, say).

Input formats

Demand. One period per line: a label (any text without a trailing number: "6-8 am", "14:00", "Mon") and the whole number of people required. Lines of numbers only are numbered periods. Periods may differ in length; the only assumption is that they form a cycle.

Typed shifts. One shift per line, fields separated by commas: an optional name (or "name:" before the fields), the periods covered as first-last with the period numbers of the demand list (inclusive; 9-2 wraps past the last period) or as start × length (9 x 4), a cost per person (a bare number or "cost 170"; blank = 1), and "break 7" for an unpaid period inside the shift (several: "break 7 12").

Generated shifts. Lengths in hours, one cost per length, the hours per period and an optional break position (counted in periods from the start of the shift). For every length the generator makes one candidate shift per starting period, so hourly periods with three lengths give 72 candidates and half-hourly periods with one length give 48. The limits are 96 periods and 96 candidate shifts.

Solution method

The LP relaxation (integrality dropped) is solved by the two-phase simplex method of the site's Linear Programming tool. Its objective Z_LP is a lower bound on every integer plan; when every cost is an integer the bound is ⌈Z_LP⌉. If the LP solution is already integral it is the answer: the cyclic coverage matrix has consecutive ones in each column, and such interval matrices are totally unimodular when the shifts do not wrap, so integral LP optima are the rule rather than the exception (every published example in the tool's test set comes out integral; Dantzig remarked in 1954 that fractional optima "did not occur" in the cases he tested).

Otherwise an integer plan is built by rounding the LP solution up (feasible, because every coefficient is non-negative) and trimming it greedily, costliest shift first, while coverage holds. If that plan meets the rounded bound it is optimal and no search is needed (Winston's post office: Z_LP = 67/3, bound 23, rounded plan 23). If not, branch and bound (Land and Doig) runs best-bound first: the most fractional variable is split into x_j ≤ ⌊v⌋ and x_j ≥ ⌈v⌉, each child's LP is solved, and a node is fathomed when infeasible, integer, or when its bound cannot beat the incumbent. The search is proven optimal when no node remains; a node or time limit (1,500 nodes, 15 s) stops it otherwise, and the page then says the plan is the best found and quotes the open bound. The node table is printed when "Show LP Details" is on.

Reading the results

Staffing table. The people on each shift used, with the cost. Coverage by period. Demand, staff on duty and the surplus; periods met exactly are the ones that fix the plan. Shadow prices. From the LP relaxation: the rise in Z_LP per extra person required in a period, zero where there is surplus; they say which periods drive the cost and are valid for the relaxation within its ranging limits, not for the integer program. Utilization. Required person-periods over worked person-periods; the difference is paid idle time forced by the shift shapes.

Lower bounds on the headcount. The peak requirement (that many people are on duty at once in the busiest period) and the work bound ⌈Σ d_t / w_max⌉, where w_max is the most periods one shift works; this is Edie's booth-hours measure (344 booth-hours at 6.25 net hours per collector give 55.04, so 56 collectors at least, and a schedule with 56 is 98.3 % efficient). The LP bound is at least as sharp as either.

Days-off scheduling

Over a cycle of D days (a week), every employee works D − 2 consecutive days and is off the two that follow, so there are D patterns, one per starting day; x_i is the number of employees whose block starts on day i (Winston, Section 3.5). The coverage of day j is the sum of the x_i whose block contains j, and the program is the covering program above with the patterns as shifts. Optional pattern costs (seven numbers) make weekend-off patterns dearer; blank costs minimize the workforce.

Two closed-form bounds are printed: ⌈Σ d_j / (D − 2)⌉ (each employee supplies D − 2 person-days) and max d_j. They are necessary, not sufficient: Winston's post office needs 23 employees although the bounds are 21 and 19, because no mix of fixed weekly patterns fits the 105 required person-days exactly (the tool's test script confirms by enumeration that 21 and 22 are infeasible). The rounded LP bound is the sharper one. Baker (1974) and Burns and Carter (1985) derive closed-form workforce sizes for rotating schedules and for rules on weekends off and work stretches; those models are not implemented here, and the tool quotes their papers only as the source of the bounds' logic.

Limits

Up to 96 periods and 96 candidate shifts; one skill class (no mixed qualifications); integer staff; coverage must be met in every period (no understaffing penalty); breaks are fixed positions within a shift (the flexible break assignment of Bechtold and Jacobs is not modelled); tour scheduling that combines shifts and days off is not offered. The days-off part takes 3 to 14 days with two consecutive days off. Shadow prices and reduced costs refer to the LP relaxation.

Checks

The test script reproduces Hillier and Lieberman's Union Airways plan (48, 31, 39, 43, 15 agents, 30,610 per day, integral LP, HiGHS shadow prices 10, 160, 0, 0, 0, 0, 175, 5, 0, 195), Winston's post office (LP 67/3, 23 employees, 21 and 22 infeasible by enumeration), the 26-bus optimum of the Jensen and Bard page with its printed plan among 145 alternative optima, Dantzig's work pattern, Edie's efficiency figures, and 26 seeded random covering and days-off instances against scipy's milp and linprog (HiGHS), with the branch-and-bound path forced on every fractional case.