Constrained Resource Scheduling

Shortest Task First Tasks are ordered in terms of duration, with the shortest first. In general, this rule will maximize the number of tasks that can be completed by a system during some time period.

Most Resources First Activities are ordered by use of a specific resource, with the largest user heading the list. The assumption behind this rule is that more important tasks usually place a higher demand on scarce resources. Minimum Slack First This heuristic orders activities by the amount of slack, least slack going first. (It is common, when using this rule, to break ties by using the shortest-task-first rule.)

Most Critical Followers Tasks are arranged by number of critical activities following them. The ones with the greatest number of critical followers go first. Most Successors This is the same as the previous rule, except that all followers, not merely critical ones, are counted.

There are many such priority rules employed in scheduling heuristics. Most of them are simple adaptations and variations of the heuristics used for the traditional "job shop scheduling" problem of production/operations management, a problem that has much in common with multiproject scheduling and resource allocation. Also, most heuristics use a combination of rules—a primary rule, with a secondary rule used to break ties.

Several researchers (19, 28, 29| have conducted tests of the more commonly used schedule priority rules. Although their findings vary somewhat because of slightly different assumptions, the minimum slack rule was found to be best or near-best quite often and rarely caused poor performance. It usually resulted in the minimum amount of project schedule slippage, the best utilization of facilities, and the minimum total system occupancy time.

As the scheduling heuristic operates, one of two events will result. The routine runs out of activities (for the current period) before it runs out of the resources, or it runs out of resources before all activities have been scheduled. (While it is theoretically possible for the supply of resources to be precisely equal to the demand for such resources, even the most careful planning rarely produces such a tidy result.) If the former occurs, the excess resources are left idle, assigned elsewhere in the organization as needed during the current period, or applied to future tasks required by the project—always within the constraints imposed by the proper precedence relationships. If one or more resources are exhausted, however, activities requiring those resources are slowed or delayed until the next period when resources can be reallocated.

If the minimum slack rule is used, resources would be devoted to critical or nearly critical activities, delaying those with greater slack. Delay of an activity uses some of its slack, so the activity will have a better chance of receiving resources in the next allocation. Repeated delays move the activity higher and higher on the priority list. We consider later what to do in the potentially catastrophic event that we run out of resources before all critical activities have been scheduled.

The heuristic procedure just described is probably the most common. There are, however, other heuristic procedures that work in a similar manner. One works In reverse and schedules jobs from the end of the project instead of from its beginning. Activities that just precede the project finish are scheduled to be completed just barely within their latest finish times. Then, the next-to-last tasks are considered, and so on. The purpose of this approach is to leave as much flexibility as possible for activities that will be difficult to schedule in the middle and early portions of the project. This logic seems to rest on the idea that flexibility early in the project gives the best chance of completing early and middle activities on time and within budget, thereby improving the chances of being on time and budget with the ending activities.

Other heuristics use the branch and bound approach. They generate a wide variety of solutions, discard those that are not feasible and others that are feasible but poor solutions. This is done by a tree search that prunes infeasible solutions and poor solutions when other feasible solutions dominate them. In this way, the heuristic narrows the region in which good, feasible solutions may be found. If the "tree" is not too large, this approach can locate optimal solutions, but more computer search time will be required. See |55) for further details.

these heuristics are usually embedded in a computer simulation package that; describes what will happen to the project(s) if certain schedules or priority rules are followed. A number of different priority rules can be tried in the simulation in order to derive a set of possible solutions. Simulation is a powerful tool and can also handle unusual project situations. Consider, for example, the following problem in resource contouring.

Given the network and resource demand shown in Figure 9-9, find the best schedule using a constant crew size. Each day of delay beyond 15 days incurs a penalty of $1000. Workers cost $100 per day, and machines cost $50 per day Workers are interchangeable, as are machines. Task completion times vary directly with the number of workers, and partial work days are acceptable. The critical time. for the project is 15 days, given the resource usage shown in Figure 9-9. (There are: other jobs in the system waiting to be done.)

Figure 9-9 lists the total worker-days and machines per day normally required by each activity (below the activity arc). Because activity times are proportional to worker demands, path b-c-e-i is most demanding and this path uses 149 worker-days.

Figure 9-9: Network for resource load simulation.Note: The numbers on the arcs represent, respectively, worker-days, machines per day.

15,2

15,2

Figure 9-9: Network for resource load simulation.Note: The numbers on the arcs represent, respectively, worker-days, machines per day.

The fact that completion times vary with the number of workers means that activity a could be completed in 6 days with ten workers or in 10 days with six workers. Applying some logic and trying to avoid the penalty, which is far in excess of the cost of additional resources, we can add up the total worker-days required on all activities, obtaining 319. Dividing this by the 15 days needed to complete the project results in a requirement of slightly more than 21 workers-say, 22. How should they be allocated to the activities? Figure 9-10 shows one way, arbitrarily determined. Workers are shown above the "days" axis and machines below. We have 22 workers at S100 per day for 15 days ($33,000) and 128.5 machine days at $50 per day ($6425). The total cost of this particular solution is $39,425.

The "critical path" illustrated in Figure 9-10 is a-g-i, which takes 15 days. However, inspecting Figure 9-9, activity g does not follow activity a so how can this be a true "critical path"? The reason is: when resources are shared among activities, the resources for one activity may not be available because an earlier activity (though not necessarily a predecessor) is still using them. Thus, in theory, g (and f too) could have started at day 4 when b was completed but there were no workers available.

Cost

Workers $33,000 Machines 6,425

Penalty _0

Total $39,425

Figure 9-10: Load chart for a simulation problem.

The availability of workers is indicated by the shaded regions in Figure 9-10. Thus, if we use the 6 idle workers shown between activities f and h (for 0.7 days, thereby releasing 4.2 worker-days) to reduce the length of activity g, we could reduce it by 4.2/3 (workers) = 1.4 days, finishing now at 9.6 days. However, path b-c-d-h would then become critical at 10.8 days, resulting in only 0.2 days of overall project reduction. Using the 4.2 worker-days to reduce not only activity g but also activities d and e, would allow us to complete all of activities e, h, and g at day 10.32, thereby reducing the project time by 0.68 days. The idle labor following activity ] could be used similarly to reduce activity i.

After all reallocations, it is important to recalculate the demand for machines since this will also change. Note that we have assumed that machine use depends only on time and is independent of the number of workers: if this is not the case, then a different set of calculations are required to determine the machine requirements. Finally, there may be limitations on the total number of workers or machines that are available at any one time and this can affect the solution. For example, how would the solution change if only 20 workers were available?

The purpose of reassignments is not to decrease labor cost in the project. This is fixed by the base technology implied by the worker/machine usage data. The reassignments do, however, shorten the project duration and make the resources available for other work sooner than expected. If the tradeoffs are among resources, for instance, trading more labor for fewer machines or more machines for less material input, the problem is handled in the same way. Always, however, the technology itself constrains what is possible. The Chinese build roads in the mountains by using' labor. In the United States machines are used. Both nations exercise an option because either labor-intensive or machine-intensive technology is feasible. The ancient Israelites, however, could not substitute labor for straw in making bricks: No straw, no bricks. ^

On small networks with simple interrelationships among the resources, it is notj, difficult to perform these resource trade-offs by hand. But for networks of a realistic^ size, a computer is clearly required. If the problem is programmed for computer sc.-f-lution, many different solutions and their associated costs can be calculated. BuK|| as with heuristics, simulation does not guarantee an optimal, or even feasible, solud* tion. It can only test those solutions fed into it. :Ji

Another heuristic procedure for leveling resource loads is based on the concep®""' of minimizing the sum of the squares of the resource requirements in each peri» That is, the smooth use of a resource over a set of periods will give a smaller sui ^ of squares than the erratic use of the resource that averages out to the samiJ| amount as the smooth use. This approach, called Burgess's method, was applied bjm Woodworth and Willie [611 to a multiproject situation involving a number of r^p. sources. The method was applied to each resource sequentially, starting with thi most critical resource first.

Next, we briefly discuss some optimizing approaches to the constrained resource scheduling problem.

Project Management Made Easy

Project Management Made Easy

What you need to know about… Project Management Made Easy! Project management consists of more than just a large building project and can encompass small projects as well. No matter what the size of your project, you need to have some sort of project management. How you manage your project has everything to do with its outcome.

Get My Free Ebook


Post a comment