Resource Loading and Leveling

Resource Loading and Leveling

Resource Loading and Leveling

Why a time schedule is not yet a plan

The critical path method answers one question: how early can each activity start and how late can it finish without delaying the project, given only the order in which the work must be done. It assumes that every activity can be staffed and equipped the moment its predecessors are finished. Real projects draw on a crew, a test rig, a specialist or a budget that is available in limited quantity, and when the early-start schedule asks for more of it on some day than exists, the schedule cannot be executed as drawn. Loading the schedule with its resources shows where that happens; leveling and resource-constrained scheduling decide what to do about it. The NASA Schedule Management Handbook (NASA/SP-2010-3403, §5.6) calls resource loading "the recommended method to accurately validate whether the scheduled project completion is achievable with the allotted resources available" and warns that a baseline set without it "is to assume a significant risk in achieving project completion within budget and on schedule". The GAO Schedule Assessment Guide (GAO-16-89G) makes assigning resources to activities its fourth best practice, and the DCMA interpretation guide and the Corps of Engineers' ER 1-1-11 require resource-loaded schedules on their contracts.

Inputs

The activities are pasted as text in the Project Schedule tool's format, one per line: id, name, duration in whole working days, the predecessors (with the FS, SS, FF and SF relations and lags of the precedence diagramming method, finish-to-start by default), and then the resource demands as name:units, meaning that many units of the resource on every working day of the activity (the uniform loading that scheduling tools assume unless told otherwise, NASA/SP-2010-3403 §5.6.1). A token p=3 gives an activity an entered priority. The resources are listed on their own lines with the units available per day, an optional cost rate per unit per day, and optional periods of different availability (10-14:2 means two units on working days 10 to 14). Durations and availability are plain numbers; the resource units are whatever the analyst chooses (people, machines, crews), the cost is in one currency without a symbol. A start date and a working week turn the day numbers into calendar dates; a deadline in working days is compared with each schedule.

Loading: the resource histogram

With every activity at its early start, the usage of a resource on day t is the sum of the demands of the activities running that day, u_r(t) = Σ_{i running at t} r_i. Plotted against time it is the resource histogram, and set against the availability L_r(t) it shows the over-allocated days, their excess in unit-days, the peak demand and the idle capacity. The total demand Σ_i d_i r_i in unit-days is a property of the work, not of the schedule: every schedule of the same activities uses the same number of unit-days, so leveling can only move them in time. The utilization, demand over the capacity L_r T of the critical-path duration, says at once whether a schedule of that length is possible at all (above 100 % it is not) and how much room there is for smoothing.

Leveling within float

Time-constrained leveling keeps the project end where the critical path puts it and moves the non-critical activities within their float so that the histogram is as smooth as possible. Burgess and Killebrew (1962) gave the criterion that has been used ever since: the sum over the days of the squared usage, Σ_t u(t)². For a fixed total of unit-days the sum of squares is smallest when the usage is spread uniformly, so lowering it cuts the peaks and fills the valleys at the same time, which a peak criterion alone would not do. With several resources the tool adds the sums weighted by 1/L_r², F = Σ_r (1/L_r²) Σ_t u_r(t)², so that a resource with large units does not dominate one with small; the per-resource sums are reported unweighted.

The procedure follows the paper: the activities are taken in order of decreasing late finish (the last ones first, so that moving them to the right frees the earlier days for those that follow in the list), each is tried at every start from its earliest precedence-feasible day to its late start, and it is placed where F is least, ties going to the latest start. One refinement is added: when a candidate start would violate a successor's constraint, that successor and its own successors are pushed forward to their earliest feasible days before F is evaluated, which lets a chain move together where Burgess and Killebrew's one-at-a-time rule would have left both activities stuck. A pass over all the activities is repeated until none moves. The result is a local optimum of F: on small networks the tool enumerates every precedence-feasible combination of starts within the windows and prints the true optimum beside it, so that the gap, if any, is seen. In the test instances the heuristic reached the optimum in each case where the enumeration was run.

Leveling can only use the float that exists. Two critical activities that run in parallel and together demand more than the availability leave an over-allocation that no shift within float can remove; the tool reports which resources are still over-allocated after leveling and hands the conflict to the next step. With the "Level to Deadline" box on and a deadline later than the critical path, the project end is held at the deadline instead, every late start moves out by the difference and the extra float is used.

Resource-constrained scheduling

When the conflicts cannot be removed within float, the project must be lengthened, and the question becomes by how little. Finding the shortest resource-feasible schedule is the resource-constrained project scheduling problem, NP-hard in general (Blazewicz, Lenstra and Rinnooy Kan 1983), so practice uses priority-rule heuristics, which Kolisch (1996) classified into two schedule-generation schemes.

The serial scheme (Kelley 1963) builds the schedule activity by activity: among the activities whose predecessors are all scheduled, the one that comes first under the priority rule is placed at the earliest day on which its precedence constraints hold and its resources are free for its whole duration; this is repeated until every activity is placed. The parallel scheme builds it time by time: at each decision time (the start, then every finish) the eligible activities are started in priority order as long as the resources suffice, and time moves on to the next finish. The two schemes explore different sets of schedules, the serial one the active schedules (no activity can start earlier without delaying another) and the parallel one the non-delay schedules (no resource is left idle while an eligible activity could use it), and neither is better in every case, so both durations are printed and the chosen one is reported in full.

The priority rules offered are the static rules of the literature, all taken from the critical path calculation: minimum total float (the activity with the least room first), latest start, latest finish, shortest duration, longest path to the end (the activity heading the longest remaining chain first), most successors, greatest resource demand (duration times units, the heaviest activity first) and an entered priority. Ties are broken by late start and then by input order. Minimum float and latest finish are the rules that do best on average in Kolisch's computations; the entered priority lets a planner impose the order of a programme. With splitting allowed in the serial scheme, an activity may be interrupted when its resources are taken and resumed when they are free, its duration being consumed in whole days; this can shorten the project where a short activity would otherwise wait for a long one, at the cost of the handovers that real work dislikes.

On networks of up to twelve activities the tool also enumerates every precedence-feasible ordering of the activities under the serial scheme, with a longest-path bound to prune the search. Kolisch proved that the serial scheme over all priority lists generates the active schedules, which contain an optimal one when the availability is constant, so the enumeration gives the exact minimum makespan and the heuristic schedule can be judged against it. The search stops when it reaches the critical path length, which no schedule can beat, and is reported as a bound only if its node cap is hit.

Reading the results

The activity table gives the critical path quantities and the demands; the resource table the availability, demand, capacity and utilization. The loading section lists the over-allocated days of the early schedule. The leveling section prints the sum of squares before and after, the moves made (which activity, from which start to which, and the F reached), the exact optimum where enumerated, and the per-resource peaks and over-allocations before and after. The resource-constrained section gives the schedule in the order the scheme placed the activities, the start and finish of each with its delay against the early start, the project duration, its extension over the critical path, the other scheme's duration, the exact optimum and the verdict against the deadline. The comparison table sets the three schedules side by side: duration, peak, over-allocated days, sum of squares and idle unit-days per resource. The Gantt chart draws the three schedules one under the other for each activity, with the float of the early schedule as a light band, and the histograms draw the three usage profiles against the availability.

Cost loading

A rate per unit-day on each resource turns the histogram into a daily cost and, summed, into the cumulative cost curve of the schedule. This is the bottom-up, time-phased budget that NASA/SP-2010-3403 §5.6.3 recommends as the performance measurement baseline: the planned value curve of earned value management, against which the Earned Value tool measures progress. The early-start and late-start curves are the two envelopes within which every feasible plan lies; the leveled and resource-constrained curves fall between them and end at the same total, since the total cost Σ_r rate_r Σ_i d_i r_i,r does not depend on the schedule.

Worked example on the page

The default is an illustrative twelve-activity building project: site preparation, foundations, framing, electrical and plumbing rough-in, roofing, exterior finish, insulation, drywall, interior finish, landscaping and the final inspection, with a crew of four and two technicians. The critical path is 27 working days through the framing, the two rough-ins (which run in parallel), insulation, drywall and the interior finish. At the early schedule the roofing and the exterior finish overlap the rough-ins, so the crew is needed at six on three days and the technicians at four on one day and three on two. Leveling moves the exterior finish, the roofing and the landscaping within their float: the crew peak falls to four and the project stays at 27 days, but the two rough-ins are both critical and together need three technicians against two, which no shift can cure. The serial scheme with the minimum-float rule runs the electrical rough-in first and the plumbing after it, placing the roofing in the gap, and finishes in 30 working days; the parallel scheme and the exact enumeration give the same 30, so the three-day extension is the least possible with two technicians. With the rates of 400 and 500 per unit-day the project costs 50,000 in every schedule, and the cumulative curve of the constrained schedule lags the early-start curve by the delayed activities. Every number of the page is reproduced by the independent numpy implementation filed with the tool's references.

Limits

• Durations and lags are whole working days and the demand of an activity is uniform over its duration; a resource is renewable (the same units are available every day), not consumable like a material quantity or a budget.
• Leveling is the Burgess and Killebrew heuristic with the forward cascade; it is exact only where the enumeration confirms it. The resource-constrained heuristics are the standard schemes, exact only on networks small enough for the enumeration.
• The exact enumeration assumes constant availability (Kolisch's active-schedule argument); with time-phased availability it is still a valid schedule but may not be the optimum.
• No multiple modes (an activity done faster with more resource), no resource-dependent durations, no calendars per resource, no cost of lateness: the deadline is compared, not optimized against.
• Activity splitting is offered in the serial scheme only and ignores the cost of interruption.