Cost minimization of m simultaneous projects that require the same scarce resource Mary N. TRYPIA
the project's total duration) and those time periods during which the resource K will be used in every project, so that the sum of total costs of all m projects is minimized. The total project cost consists of the direct performance cost and the indirect cost which refers to overheads, penalties etc. [ 1 - 3 ] . The total project cost among other exogenous and uncontrolable factors, also depends on the total duration of the project. Usually, if the duration of a project is increased, the project's direct cost decreases while its indirect cost increases. Here, we want to find those total durations of the m projects that will not exceed the availability of resource K in any time period, and will lead to the minimization of the sum of total costs of the m projects. We assume that a CPM network [ 1 - 3 ] has been constructed for each project and we have found for each project i (i = 1, .... m) the total cost Cii that corresponds to every possible total duration D # , i.e., if I i is the number of possible total durations of project i, we have found the pairs (Cil - D i l ) , (Ci2 - Di2), ..., ( f i t i - Dill). In the example that we will present the relationship between the project's cost and project's duration will be clarified. Here, we consider that the total duration of a project is expressed in weeks. Any other time unit could have been considered. The analysis of the CPM network should have also given
The Athens Graduate School o f Economics and Business Science, Athens, Greece
Received May 1979 Revised September 1979 A company is responsible for m projects which are carried out concurrently. All m projects require the use of the same scarce resource for some time periods. An Integer Programming model is here presented to solve the problem of optimally allocating the scarce resource to *.bem projects so that the sum of total costs of carrying out the m projects is minimized.
1. Introduction In many real-life situations, the problem of optimally allocating a scarce resource to different projects is very important. There exist many methods [ 1,2,4] which have solved the problem of multiproject resource allocation, but most of these methods are heuristic not always giving the best solution. Here, a 0 - I Integer Progiamming [ 5 - 7 ] model is presented which attempts to give the optimal answer to the problem of multiproject resource allocation, when the resource is of a discrete nature. In case there is more than one critical resource, the model we will present .can be adjusted to take account of the multiplicity of critical resources, as it will be shown. Let a company be responsible for the simultaneous performance of m projects. The m projects can start in different time periods but at some point of their performance all m projects are simultaneously carried out. All m projects require the use of the same scarce resource in different amounts during some time periods of their performance. The scarce resource K, whose optimal allocation to the m projects we are seeking, is of a discrete nature e.g., human personnel, machinery. The problem is tb determine the "usage level" of resource K in each project (as a function of
Table 1 Requkements of the resource K by project i Total dr)ration (weeks) a
ri I 1
ril i 1
a n is the number of weeks required for the completion of the longest project.
to North-Holland Publishing Company European Journal of Operational Research 5 (1980) 235-238 235
M.N. Trypia / Cost minimization of m simultaneeus projects
us the units ri/p of resource K, that should be allocated in project i in week p, when the total duration of project i is Dii weeks, the units rikp that will be required in week p by project i, when the total duration of project i is Dik weeks, etc. Thus, for every project i, (i = 1, ..., m), a table can be constructed as shown in Table 1. A 0 - I integer Programming model [ 5 - 7 ] , will be presented here whose objective is the minimization of the sum of total costs of the m projects, under the condition that the demands of the m projects in resource K will never exceed its availability in any week•
each project: Project l ' x z z +xz2 + ' " +xls t = 1 Project2:x21 +x22 +
Project m: Xm~ + Xm2 + "'" + Xrnl m = 1 (2) The demand of resource K by all the m projects should never exceed its availability in any week• Thus, n constraints of this type are introduced, where n is the duration in weeks of the longest project: m
2. The model
Variables. Let the 0-1 variable xq signify the following: (a) ifxij = 1 the total duration of the project is Dij, (b) ifxq = 0 the total duration of the project is not Dq.
m(ll + 12 + ... +lm) 0-1 variables of this nature are introduced in the model. Ob/ective function. The objective function represents the minimization of the sum of the total costs of the m projects: m
min G G
= C l l X l l +C!2x12 + ' " + C I I I X I ! 1 + C21x21 + C22X22 + ... ~- C212x2l 2
+ ... + C m l X m l + C m 2 x m 2 + ... + C m l m X m l m ,
where l i is the number of possible total durations of project i, Cq is the total cost of project i that corresponds to its total duration Dq.
Constraints. (1) Among the possible total durations of a project only one will m; ~rialize' li
x~i = 1.
m constraiwts of this type are introduced, one for
+ x2t2 = 1
xijrijp <~ b p ,
where bp is the availability of resource k in week p. If there exist more than one critical resources which are needed in some projects, we simply add a second, third, set of constraints of the above form (3), assuming of course that these resources K, L, T, ... are "autonomous" i.e., that they can be used at different time periods in the performance of any project. If this is not so, and all critical resources K, L, T ... should be used concurrently in a project, we simply consider one critical resource which is a weighted form of the critical resources K, L, T, .... Example. Let a company be; responsible for 3 projects which are performed simultaneously for some time periods and all the 3 projects require the use of the same machinery K. Projects 1 and 2 start in week 1 while project 3 s~:arts in week 5. Before any project starts, the firm is doing the following preliminary analysis.
Preliminary analysis for project 1. Let the network and data related to project 1 be the network of Fig. 1 and Table 2. Analysing the network we have: (a) Total project duration when activities are performed in normal time, D~ = 17 weeks• The corresponding total direct cost is C~ = 19 m.u. (b) The minimum project duration when all activities except activities (2-5), ( 1 - 2 ) are performed in their crash time is D4 = 11 weeks• The corresponding total direct cost is C4 = 25 m.u. after intelligently using the float of activities (1-2), (2-5). As it is analysed in (1), (3), by using intelligently the floats of the activities, we determine the follow. ing pairs (Duration-Cost) of the project: D2 = 13 weeks D 3 = 12 weeks
C2 = 22 m.u. C3 = 23 m.u•
M.N. Trypia / Cost minimization of m simultaneous projects
Fig. 1. Table 2 Activities
I-2 1-3 1-4 2-5 3-5 4-6 5-6
Normal time d (weeks)
3 4 5 2 6 7 7
Cost of performing the activity in time d, ca m.u.
Crash time d' (weeks)
Cost of performing the activity in time d', cd' m.u.
3 3 4 5 2 1 1 19
2 2 4 1 6 7 3
4 5 5 8 2 1 4
Dlt D12 DI3 DI4
= = = =
Cll Ct2 Ci 3 Cl4
17 13 12 11
= = = =
19 22 23 25
+ + + +
1.7 1.3 1.2 1.1
= = -=
20.7 23.3 24.2 26.1
Table 3 is associated with the requirements of machinery K, depending on the total duration o f the project.
Prelimhzary analysis for pro/ect 2. Similarly, the analysis of project 2 has concluded the following:
Table 3 Weeks
Let the project's indirect cost be linear o f the form 0.1t, where t is the duration of the project. Thus, the final pairs ( d u r a t i o n - t o t a l cost) o f project 1 are:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1
2 1 0 0 0 0 0 1 2 1 1 1
2 1 0 0 0 0 0 2 2 0 2
Total Cost C2 t = 6 m.u. C22 - 8 m.u. (723 = 14 m.u.
Duration Dz i = 12 weeks D22 = 10 weeks D23 = 9 weeks.
Table 4 shows the requirements of machinery K.
Project 3. There are 2 possible total durations for project 3 C31 = 1 m.u. C32 = 2.6 m.u.
D3i = 3 weeks D32 = 1 week.
Table 5 shows the requirements of machinery K. The model that was here presented is formulated as follows: m
~- (20.7Xll + 23.3X12 + 24.~X'13 + 26.1X14) + (6X21 + 8X22 + 14X23)+ (1 "X31 + 2 • 6X32).
M.N. Trypia / Cost minimization o f m simultaneous pro/eets
Table 4 Weeks
~_ 2 3 4 5 6 7 8 9 10 11 12
Duration D21 = 12 weeks
D22 = 10 weeks
D23 = 9 weeks
0 0 0 1 1 0 0 1 0 1 1 1
0 1 1 1 0 0 1 0 0 2 -
0 1 2 1 1 0 2 1 2 -
Subject to Xll +Xl2 + X I 3 +X14 = 1, X21 +X22 +X23 = l, X31 +X32 = 1,
5 6 7
Duration D31 = 3 weeks
D32 = 1 week
1 1 1
Conclusion The basic form of a 0 - 1 Integer Programming model has been presented here, to solve the problem of optimally allocating a critical resource of a discrete nature, to m projects which are performed simultaneously. Another definition of the problem could be the following: Find the total durations of the m projects so that the sum of their total costs is minimized and the availability of the critical resource is never exceeded in any time period. As conditions affecting the performance of projects can change while they are performed, it has to be added here that the same model with different parameters, can be adapted to the new prevailing conditions.
")fll +2X12 + 2 X 1 3 + 3X14)+ 0 + (1 "X3t + 3X32) ~< b l ,
(1 " x l t + 2xt2 + 2x13 + 3x14) + (1 "x22 + 1 - x 2 3 ) ~ b 2 , (1 " x t l + 1 " x l 2 + 1 " x l 3 ) + (1 "x22 + 2X23 ) < b3, (1 " X l l ) + (1 "X2t + 1 "X22 + 1 " x 2 3 ) ~ b 4 , (1 "x21 + 1 - x 2 3 ) + ( 1
.x31 + 3 x 3 2 ) ~ b s ,
(1 "X31)~< b6, (1 "x22 + 2 X 2 3 ) + ( 1
where bl .... , b 7 is the available number of machines in weeks 1, ..., 7. Similarly, we write the constraints of resource availability for the weeks 8, 9, ..., 17.
[ 1 ] J.J. Moder and ~2.R. Philips, Project Management with CPM and PERT (Van Nostrand, 1964). [21 J.M. Antill and R.W. Woodhead, Critical Path Methods in Construction Practice (John Wiley, 1970). [ 3] M.N. Trypia, Project Planning (Papazissis Press, Athens, 1977).  S. Lambourn, Resource Allocation and Multiproject Scheduling, The Computer Journal Vol. 5, no. 4 (1963) 300. [5 ] M.N. Trypia, Methods for Integer Programming, Ph.D. Thesis, Imperial College, London 1975.  M.N. Trypia, A Non Binary Tree Search Method for the 0 - 1 Linear Programming Problem, N.Z. Operational Research, Vol. 5 (1977) 35. [ 7] A. Land and S. Powell, Computer Codes for Problems of Integer Programming, Paper presented in the Vancouver Conference on Discrete Optimization, August 1977. (To be published in Discrete Mathematics, 1979).