SCREAM--scarce resource allocation to multi-projects
Technion – Israel Institute of Technology
This study deals with the development of a computerized model for the scheduling of multi-projects. The model, named SCREAM, assigns activities which utilize scarce and costly resources according to the least total penalty cost obtained from project tardiness, idle scarce resources, activity splitting and overtime work. User fixed variables enable efficient control of project tardiness without causing significant changes in resource utilization. A computer interactive feature is included which encourages the operator to improve schedule quality when schedules, identified as being inefficient, are generated.
Multi-project scheduling with limited resources can be defined as follows: “Several independent projects, each having its own arrival and due date, enter a scheduling system. The available resources, some of which are scarce, must be allocated to activities belonging to different projects in order to meet the objectives of the system.”
While multi-project scheduling can be seen as an extension of the single project resource allocation problem its combinational nature is far more complex since activities belonging to several projects are scheduled simultaneously.
The few studies reported on the subject can be divided into analytical (11) and heuristic approaches, with only the latter being able to cope with industrial applications.
The heuristic studies can be classified into:
(i) Those concerned with testing the efficiency of well known single scheduling rules.
(ii) Those dealing with composite scheduling rules.
Conclusions from the first category (5, 6, 9, 10) indicate that no single heuristic rule ranked best on all the possible objectives of the multi-project scheduling problem, so that for example, due date oriented scheduling rules like ‘minimum slack,’ favor due date oriented objectives at the expense of efficient resource utilization and vice versa.
The second category includes models like RAMPS (7, 8, 15) and PROJACS (12). These were developed for propriety usage and little is known about their operating details or efficiency, except that they do work for industrial applications.
Criteria for an Effective Multi-Project Scheduling Model
An effective multi-project scheduling model should meet the following criteria:
(1) Applicability — Ability to economically handle industrial sized multi-projects.
(2) Realistic objective function — The model should utilize a realistic objective function which incorporates all major factors of multiproject scheduling.
(3) Scarce and costly resources — The model should distinguish between scarce and unlimited resources since the former can influence project completion dates. On the other hand, costly but unlimited resources have a major influence on total costs, but do not influence project completion dates.
(4) Alternative resource combinations (ARC’s) (2, 14) — It is usually possible to execute an activity in several ways, each one requiring a different resource combination and duration. The model should be capable of selection between alternative resource combinations (ARC’s).
(5) Activity splitting — Emergency conditions usually require some activity splitting. Hence activity splitting is an option which every effective model should incorporate.
(6) Expediting projects — The model should incorporate the means of expediting projects when the need arises.
(7) Flexibility — The model should adapt itself to different situations during the scheduling process, e.g. emphasizing resource utilization when no urgent projects are involved in the scheduling process.
(8) Practical input and clear output formats — The input data should be in a form which is readily available and the output should be in an easily understood and useful form.
(9) Control and updating the model is an essential requirement.
Objective Function of the Model
The underlying assumption made in this study is that the schedule quality is basically determined by a limited number of factors. Consequently, only the relative effect of these factors need be considered for evaluating the schedule quality.
Whereas the total costs involved in the execution of multi-projects include many hundreds of items, it is claimed that only a few of these actually influence project tardiness and total costs to any great extent. Hence, the objective function of the model developed in this paper aims at minimizing the relative total (i.e. only the cost of these major factors), cost of executing the multi-projects. The following factors are considered as having a major influence on the objective function:
(a) Total cost of resources.
(b) Total cost of activity splitting.
(c) Total cost of overtime work.
(d) Total cost of project tardiness.
The total relative system cost is then optimized by periodic minimization of an objective function, DELTA(t), which expresses these factors as penalties:
(a) Total cost of idle resources (TCIR(t) ).
(b) Total activity splitting penalties (TSPEN(t) ).
(c) Penalty cost of overtime work (TCOT(t) ).
(d) Total project lateness penalties (TLPEN(t) ).
DELTA(t) is the algebraic sum of these four components and the schedule at time t which yields the lowest DELTA (t) value is taken as the “best” schedule.
A discussion of DELTA(t) components now follows:
(a) Total Cost of Idle Resources: Since only scarce (or limited) resources affect project tardiness and costly resources affect project costs (i.e. idle time costs), only scarce and costly resources are assumed to influence the overall relative system cost. For the remainder of this paper, the term “resources” refers only to scarce and costly resources.
The model assumes that the availability of resources is fixed for a given period of time. Minimizing the cost of idle resources means maximizing the monetary utilization of these resources. The total cost of idle resources is then equal to the sum of idle units of each resource type multiplied by its unit cost.
(b) Activity Splitting Penalty. It may be necessary at times to interrupt the work on one activity and transfer some, or all its resources to another more urgent activity. Returning to the original, incomplete activity will entail either, or both, set-up and transportation costs whose values will depend on the resources needed.
(c) Incremental Cost of Overtime Work: While the availability level of resources are fixed for a given period, it is always possible to increase them by working overtime. Thus the incremental cost of overtime work is included in the DELTA (t) function.
The incremental cost of overtime work can be negative for example with machinery and equipment, since the overhead costs per time unit decreases.
(d) Project Lateness Penalties: Each project has a due date and tardiness cost is incurred if a project is delayed beyond this date. It may involve the following factors:
(1) A penalty clause for delays written into the contract.
(2) Losses due to delays in final payments.
(3) Losses due to additional overhead cost incurred.
(4) Damage to company’s goodwill.
Factors (1) and (2) are clearly measurable whereas the last two factors are difficult to translate into monetary terms and are neglected.
Project tardiness occurs when an activity is delayed beyond its Late Start date (LS). Therefore an activity becomes critical if its start is delayed up to, or beyond, its LS date. To raise the scheduling priority of a critical activity, a “lateness penalty” is charged if the activity is delayed beyond its LS date. If more than one critical activity belongs to the same project, then lateness penalty is charged for the activity having the maximum tardiness since it alone determines project tardiness.
If at time t, there are N (t) projects being executed and gj(t) is the greatest delay (beyond LS) for any activity in project j, then the total lateness penalty (TLPEN (t) ) is given by:
Lateness penalty can be fixed according to various functions, several of which are illustrated in Figure 1.
Figure. 1 Illustrating lateness penalty functions
The Scheduling Rule
The purpose of charging a lateness penalty is to avoid project tardiness. But this penalty applies only after an activity is already late and project tardiness is inevitable. In order to increase the effectiveness of the lateness penalty, the concept of Critical Slack (CS) is introduced. An activity is considered as being late CS time units before it is really late. Thus, at time t, if an activity in project j is gj(t). (LP cost function)j will apply.
The value of CS is fixed by the user and its influence on a linear lateness penalty function is illustrated in Figure 2.
Figure. 2 Influence of critical slack on the lateness penalty function
Thus for scheduling purposes, the DELTA(t) value defined in equation 1, could be increased artificially by using a critical slack greater than zero (i.e. CS > 0). Call this new value DELTA*(t), where
Scheduling is done on a periodic (e.g. daily, weekly) basis. At each period all possible combinations of assignable activities are generated using the binary enumeration technique 2 .
The value of DELTA*(t) is calculated for all feasible combinations of resources and the one yielding the lowest value is chosen to be scheduled on that period.
Interacting with the Computer
The model is equipped with a monitoring function which stops the scheduling process when the DELTA(t) value of the schedule rises above a defined level. The computer system then enters an interactive mode and the scheduler is then encouraged to improve the schedule by trying out others for specific activities identified by the computer. Thus, when the current minimum DELTA(t) value exceeds some user defined limit, the scheduler is encouraged to try out new ARC’s for any of the activities identified by the computer as being the likely cause of the high DELTA(t) value.
The upper control limits (UCL) can be determined as follows:
where X is the updated average of minimum DELTA(t) values.
σ is the updated standard deviation DELTA(t) values.
M is a user selected number 0 >M >3.
At each scheduling period the average and standard deviation of the minimum DELTA(t) values are calculated. The value of M determines the frequency of warnings given, the greater its value, the less the number of warnings. With each warning the program may enter an interactive phase with the scheduler, who, through trial and error, will attempt to find an ARC that lowers the current minimum DELTA(t) value to within the acceptable limits.
The Model — “SCREAM”
Fig. 3 gives the flow chart for solving the multi-project scheduling problem. The program is written in FORTRAN IV and a computer listing will be made available from the authors on request.
The model is called “SCREAM.”
Figure. 3 Basic Flow Chart for SCREAM.
1) The inputs:
(i) The arrival and due dates of every project.
(ii) Lateness penalty and critical slack (user fixed).
(iii) The total number of activities in each project and the set of immediate followers for each activity.
(iv) The ARC’s and their durations.
(v) The unit cost of each resource.
(vii) The resource availability levels.
(viii) Factors that determine the incremental cost for the overtime use of each resource.
(ix) Splitting penalties associated with each resource.
(x) The value of M (user fixed).
(i) Candidate activities for each project.
(ii) Activities to be performed on the stated date.
(iii) Cost of idle scare/costly resources (TCIR(t) ), cost of activity splitting (TSPEN(t) ), cost of project tardiness (TLPEN(t) ), cost of overtime work (TCOT(t) ), and values of DELTA(t) and DELTA*(t)
(iv) Resource types which work overtime.
(v) Project completion (if this occurs).
This output enables the project manager to plan and control the current projects at each period. A short section of the output is illustrated in Figure 4. It’s format, designed for the investigation, should be redesigned to meet the real-life needs of the projects manager.
Testing the Model
Two experiments were used with SCREAM. The first, a preliminary study, was used in identifying the important variables. The second, a factorial experiment, was used for investigating the model behaviour for different values of the design variables. The two experiments are fully described in (1).
The preliminary study led to the conclusion that the following variables had an important influence on both the total relative cost and schedule performance.
• Lateness Penalty
• Critical Slack
• Unit Cost of Resources
The two remaining components of DELTA(t) (i.e. penalties for activity splitting and overtime) had a negligible influence on the schedule performance and were consequently given fixed values in the main investigations.
Six projects having the characteristics listed in Table 1 were included in the main investigation. Five ’scarce/costly’ resources were utilized and project 4 was chosen as the test project since it was least influenced by boundary conditions.
Figure. 4 The Output Format
Table 1. Summary of Project Characteristics.
|Project No.||No. of Activities||Arrival Date||Due Date||Project Slack||F-Ratio*|
* F-Ratio is a measure of the network order strength, and equals (no. of zeros in the min. matric representing the network)/(number of cells in the minimum matrix)
Table 2 summarizes the levels at which each factor was tested.
Table 2. Summary of Level Values of Variables Used in the Factorial Experiment.
|FACTOR||LEVEL 0||LEVEL 1||LEVEL 2|
|C||Unit cost of resources||200,250 |
* The three levels of lateness penalty were determined for projects worth 1 million, 2, 5 million and 4 million, respectively. It was calculated on the assumption that the final payment, taken as 20% of the project worth, is withheld until the project is completed.
** The three levels of critical slack correspond to 0%, 10% and 20% of the expected duration (i.e. due date – arrival date) of project 4.
The main results of the study were as follows:
• Most schedules were approximately equal in quality, i.e. the DELTA(t) remained fairly constant — changes in critical slack and lateness penalty simply leads to compensating changes in the other terms in DELTA(t).
• Lateness penalty and critical slack had a major influence on project tardiness. The critical slack is especially important since it is a user fixed parameter.
• The best overall schedules were obtained when the critical slack was fixed at 10% of the expected project duration. A 20% value resulted in project 4 being heavily expedited.
Other observations from the experiments were as follows:
(i) Resource utilizations were high — falling in the range of 86 to 91%.
(ii) The two main components of Σ (minimum DELTA) were idle — cost of resources and total project lateness penalties. These two factors add up to 80-85% of its total value.
(iii) Computation costs were not a significant factor. The experiments were run on an IBM 370/168 with an average CPU time of 3.5 minutes.
SCREAM is expected to simultaneously handle an average of 10 moderately sized projects having up to 20 resource types using a reasonable amount of computation time. But more work is being done in preparing the model for industrial use.
This paper describes the successful development of a multi-project scheduling model designed to meet the requirements of an effective computer model. Its objective function considers all the major components involved, project tardiness, resource utilization, activity splitting and overtime work.
Indications are that the scheduler can control project tardiness through the choice of critical slack without affecting total system costs. The schedule, generated on a periodic basis, results in high utilization values for all resources used in the experiments. The scheduler may interact with the computer in order to improve the quality of schedules it generates.
Input data takes a practical form and changes, updating and control activities are readily accomplished. Computation costs were found to be unimportant.
1. Behmoaram, A., “Multi-project scheduling with limited resources,” Unpublished M.Sc. thesis, Technion — I.I.T., Haifa, October 1976.
2. Dar-El, E.M. and Tur, Y., “A multi-resource project scheduling algorithm,” Operations Research, Statistics and Economics Mimeograph Series 168, Technion — I.I T., 1975.
3. Davis, E.W., “Resource allocation in project network models — A survey,” Journal of Industrial Eng., Vol. 17, No. 4, pp. 177-188, 1966.
4. Davis, E.W., “Project scheduling under resource constraints, historical review and categorization of procedures,” AIIE Transactions, Vol. 5, No. 4, pp. 297-313, 1973.
5. Fendley, L., “Towards the development of a complete multi-project scheduling system,” J. of Industrial Eng., Vol. 19, No. 10, pp. 505-515, 1968.
6. Gonguet, L., “Comparison of three heuristic procedures for allocating resources and producing schedules,” in: Project Planning and Network Analysis, Lombaers (Ed.), pp. 249-255, North Holland, Amsterdam, 1969.
7. Lambourne, S., “RAMPS — A new tool in planning and control,” The Computer Journal, Vol. 5, pp. 300-304, 1963.
8. Moshman, M., Johnson, I., Larsen, M., “RAMPS — A technique for resource allocation and multi-project scheduling,” Proceedings Spring Joint Computer Conference, 1963.
9. Pascoe, T. L., “An experimental comparison of heuristic methods for allocating resources,” Unpublished Ph.D. dissertation, Cambridge University, 1965.
10. Patterson, J.H., “Alternate methods of project scheduling with limited resources,” Naval Research Logistic Quarterly, Vol. 20, pp. 767-784, December 1973.
11. Pritsker, A.A.B., Walters, L.J., Wolfe, P.M., “Multi-project scheduling — A zero-one programming approach,” Management Science, Vol. 16, No. 1, pp. 93-109, 1969.
12. Projacs, “Project Analysis and Control System,” IBM Program No. 5746-XP1, IBM Inc., New York.
13. Tur, Y., “Optimizing resource costs when specifying the project completion date,” Ph.D. dissertation, Technion — I.I.T., Haifa, Israel, 1975.
14. Wiest, J.D., “A heuristic model for scheduling large projects with limited resources,” Management Science, Vol. 13, No. 6, pp. 359-337, 1967.
15. Wiest, J.D., “A heuristic scheduling and resource allocation model for evaluating alternative weapon system programs,” The Rand Corporation, Memorandum Rm-5769-PR, August 1969.