A comparison of computer search heuristics to analyze activity/networks with limited resources
University of Central Florida
Traditional critical path methods fail to include resource considerations and are, therefore, not very realistic. In this article, practical resource allocation approaches are studied.
Recently it has been realized that with the speed of computers a new form of heuristic can be tried involving a search procedure . In these procedures the networks are analyzed with a family of heuristics and the best solution found for network output. The excess computer time seems warranted based upon the improved results available. This is particularly true when multiple resources are considered. The computer is best suited for situations such as this, especially with the recent reduction in computing costs.
In most commercial resource allocation packages, the heuristic ACTIM  is used. ACTIM is quite simple but gives inconsistent results, particularly for large, multi-resource networks. Whitehouse  reported an attempt at developing a family of algorithms called GENRES. The algorithm was applied to relatively small single resource networks. A 5% average decrease in project duration was found over the algorithm most commonly used for commercial resource allocation programs. It would be expected that this improvement would be greater for larger and multi-resource networks.
This article considers another approach similar to the COMSOAL  approach used in the balancing of production lines. The approach is closely related to simulation and has already shown considerable promise.
Project Scheduling Under Resource Constraints
Brooks Algorithm — ACTIM
One of the available heuristic procedures is the Brooks Algorithm (BAG) presented in Chapter 6 of Bedworth . The algorithm presents a rule for determining which activities should receive limited resources first. The algorithm considers the single project, single resouce case but could be extended to the multi-resource case. This algorithm is best described by example. The example is taken from Bedworth .
The steps required to assign the single resource with BAG are as follows (Table 1 gives the tabular results of these steps for Sample Network 1 in Figure 1 with three resources available):
Sample Network 1
1. Develop the project network as with the critical path procedure identifying activities, their required times, and required resources.
Brooks' Algorithm Solution To Network #1
With Three Units of Resource
2. Determine for each activity the maximum time it controls through the network on any one path. This is equivalent to the critical path time minus the latest start time of the starting node of each activity. These times are then scaled from 0 to 100. This scaled control time is designated ACTIM.
3. Rank these in decreasing ACTIM sequence, as in Table 1. The duration and resources required for each activity are those determined in the first step. The rows TEARL, TSCHED, TFIN and TNOW need explanation:
a. TEARL is the earliest start time of an activity determined by traditional critical path calculations.
b. TSCHED is the actual scheduled starting time of an activity as determined by BAG.
c. TFIN is the completion time of each activity.
d. TNOW is the time at which resource assignments are now being considered.
4. Set TNOW at 0. The allowable activities (ACT. ALLOW.) to be considered for scheduling at TNOW of zero are those activities with TEARL of 0. These are 1-2, 1-3, 1-5. These are placed in the ACT. ALLOW, row in decreasing ACTIM order. Ties are scheduled by establishing the activity of longest duration first. The number of resources initially available, 3, are placed in the resources available column.
5. Determine if the first activity in ACT. ALLOW., 1-5, can be assigned. Activity 1-5 requires only one resource and three are available, so 1-5 can be assigned. A line is struck through 1-5 to indicate Table 1 assignment and the number of resources available is decreased by one. TSCHED and TFIN are then set for activity 1-5. This same process is repeated for the remainder of the ACT. ALLOW, activities until the resources available are depleted.
6. TNOW is raised to the next TFIN time of 5 which occurs at the completion of both activities 1-2 and 1-3. The resources available are now 2. ACT. ALLOW, includes those activities not assigned at the previous TNOW (in this case, none) and those new activities whose predecessors have been completed (2-4, 3-4, 3-5).
7. Repeat this assignment process until all activities have been scheduled. The latest TFIN gives the duration of the project, which is 17 days for this example.
ACTRES and TIMBRES
The Brooks Algorithm could be used with any number of criteria other than ACTIM. Bedworth  presents two other possible decision criteria, ACTRES and TIMBRES.
ACTRES incorporates both activity time and resource level in the control criteria. ACTRES is computed by taking the value of the activity time multiplied by the number of resource units for an activity plus the maximum of the ACTRES values following this activity. Again, after the ACTRES value is calculated for all of the network's activities, they are appropriately scaled from 0 to 100.
The TIMBRES criteria suggested by Bedworth are a combination of ACTIM and ACTRES. Therefore, ACTIM and ACTRES are given equal weight in the TIMBRES criteria. (To keep TIMBRES on the 0-100 scale, TIMBRES is calculated 0.5 (ACTIM) + 0.5 (ACTRES)).
GENRES - A Modification of the TIMBRES
Whitehouse  observed that ACTIM, ACTRES, and TIMBRES can each give a different activity sequence which will result in three possible project schedules. This is especially true for larger networks. The best project schedule is chosen as the one resulting in the least total project duration. The premise of GENRES is that further project schedules can be generated using combinations of ACTIM and ACTRES which are not equally weighted. Various weightings are tried and the best project schedule is selected as before. This search technique lends itself to computer application. A flow chart of the GENRES search model is presented in Figure 2. A computer program was developed using this model. Promising results of the rise of this model were reported by Whitehouse .
Flow Chart of GENRES Search Model.
COMSOAL – A Random Sampling Approach
Whitehouse modified the COMSOAL approach for the assembly line balancing problem to the resource allocation problem. We might characterize COMSOAL  as a method by which a fairly large number of feasible solutions are generated rapidly by a biased sampling method. The best solutions in the set become alternate solutions to the system. The universe from which we are sampling is, of course, all of the possible feasible solutions to the particular problem, and there is a finite probability that we can turn up optimal solutions in this fashion, a slightly larger probability of turning up the next best solutions, and so on. The probability of developing excellent solutions is, of course, related to the size of the sample generated. Obviously, the trick will be in generating feasible solutions rapidly and biasing the generation of these solutions toward the better ones rather than simply generating feasible solutions at random.
The COMSOAL approach for generating feasible solutions to the resource allocation problem would be as follows:
STEP 1: Determine a list of all tasks that could be scheduled at a point in time (Starting at time = 0). A task can be scheduled if: 1) all of its preceeding tasks have been scheduled and completed; and 2) there are enough resources of each kind available to schedule the task. (This list will be referred to as the AVAILABLE LIST.)
STEP 2: In the simplest form of COMSOAL an assignment is now made by selecting at random from the AVAILABLE LIST to determine the next task to be scheduled.
STEP 3: For the task selected, the scheduled completion time is calculated and the number of units of resources available are reduced by the number of units needed for the task. This is done for each of the various resources.
STEP 4: A new AVAILABLE LIST is developed and the procedure continues until the AVAILABLE LIST becomes empty, meaning that there are no tasks that can be scheduled, the reason being that there are insufficient available resources or no task has all of its predecessors completed. The clock is advanced to the completion of the next task to be completed.
STEP 5: The procedure continues until all tasks in the system have been scheduled and the final completion time for an interaction is determined.
Sample Network 2
In the experimentation this simplest form of COMSOAL was used, realizing that the results would probably be improved with more sophisticated sampling strategies.
A Sample Network
A number of networks were analyzed and the results were typical of results for the Sample Network 2 shown in Figure 3. This network was analyzed for various levels of resource availability. For the case of 7 resource units, the following results were obtained:
The results for COMSOAL are stochastic and a function of the sample size is considered. The best COMSOAL schedule found was 152 days.
Table 2 shows typical COMSOAL results for this network. The results look promising but work must be continued to determine appropriate sample sizes and to determine the appropriate confidence intervals for the answers obtained.
|Resource Level||# Iterations||Seed||Best Time|
Consider the following results of 20 runs of COMSOAL with 25 interactions on this network:
The results show a reasonable degree of stability considering the crudest form of sampling is being utilized. Much more stability would be expected with more sophisticated forms of COMSOAL sampling.
The COMSOAL approach to the resource allocation problem seems to show promise and inconsistently gave better results (for large sample sizes) than traditional heuristics used to schedule networks with limited resources. Much experimentation is necessary to develop confidence in these results and to determine the appropriate sample size to be used.
Alternate sampling strategies presently being considered include:
RULE 1: Weight tasks that fit in proportion to task time. The effect of this weighting is to give large tasks a greater probability of being assigned than small ones.
RULE 2: Weight tasks that fit by l/X ', where X ' is equal to the total number of unassigned tasks minus 1 less the number of all the tasks that follow the task being considered. The effect of RULE 2 is to give those tasks that have a large number of followers a greater probability of being assigned than tasks with a small number of followers.
RULE 3: Weight tasks that fit by the total number of all following tasks plus 1. The effect of this rule is to prefer tasks which, when selected, will be replaced and, therefore, expand the available list.
RULE 4: Weight tasks that fit by the times of the task and of all following tasks. The effect of this rule is to combine the advantages of RULES 1 and 3 by selecting large tasks early at each station in the entire sequence or, alternatively, by preferring tasks which, although small, tend to expand the available list.
RULE 5: Weight tasks that fit by the total number of following tasks plus 1, divided by the number of levels which those following tasks occupy plus 1. The effect of this weight is to give work elements in the longest chains the greatest probability of being assigned first.
1. Bedworth, D.D. Industrial Systems: Planning, Analysis and Control. New York: The Ronald Press Co., 1973.
2. Buffa, E.S. & Taubert, W.H. Production – Inventory Systems: Planning and Control, Homewood, IL: Richard D. Irwin, 1972.
3. Davis, E.W. Resource Allocation irf Project Network Models – A Survey. Journal of Industrial Engineering, 1966, 177-188.
4. Davis, E.W. Project Scheduling Under Resource Constraints – Historical Review and Categorization of Procedures. AIIE Transactions, 1973.
5. Davis, E.W. PROJECT MANAGEMENT: Techniques, Applications and Managerial Issues, Norcross, Georgia: AIIE, Inc., 1976.
6. Elsayed, E.A., Algorithms for Project Scheduling With Resource Constraints, International Journal of Research, 19, 1982.
7. Moder, J. & Phillips, C.R. Project Management With CPM and PERT, New York: Van Nostrand Reinhold Co., 1970.
8. Whitehouse, G.E. & Brown, J.R. GENRES: An Extension of Brooks Algorithm for Project Scheduling with Resource Constraints. Computers and Industrial Engineering, 1979.
9. Whitehouse, G.E. Systems Analysis and Design Using Network Techniques, Englewood Cliffs, NJ: Prentice Hall, Inc. 1973.
10. Whitehouse, G.E. & Tidwell, D. Practical Computer Search Approaches to Project Management with Resource Constraints, Proceedings of the 1980 AIIE Spring Conference, 1980.
Dr. Gary E. Whitehouse, P.E., is associated with the University of Central Florida in the Department of Industrial Engineering and Management Systems in Orlando, Florida.