IEEE TRANSACTIONS ON ENGINEERING MANAGEMENT, VOL. 43, NO.

4, NOVEMBER 1996

411

Time-Resource Tradeoff Problem

P. Simin Pulat and Steven J. Horn
of the project completion time. In order to solve the more general problem defined [l] by our technique, one needs to define the objective concerning the minimization of the realization time of node k in terms of activity realization times. They have suggested the use of ADBASE [9], a multiple objective linear programming (MOLP) code, to solve the problem. Other researchers [3], [5]-[7] have suggested goal programming formulations for the project scheduling problem. Rahman [8] describes another methodology for the time-resource tradeoff problem which deals with the efficient solutions in the objective space rather than the decision space. The algorithm is limited to planar project networks since it uses the dual network of a given project network. Reference [SI also introduces the concept of an efficient cut. While Rahmans algorithm is much faster than ADBASE it is much slower than the algorithm presented in our paper. Section V discusses the computational comparisons of the two techniques. The computational time required by our method on a 100-node problem is only 5 s. In this paper, we present the time-resource tradeoff problem with two resources or two groups of resources. The MOLP model of the problem has three objective functions, 21, 2 2 , z3 which are the minimization of the total cost of resource consumption for each resource and the minimization of project duration, t,,, respectively. The project completion time t, varies between t,,(normal) and t,(min), which are the normal and the minimum project completion times, respectively. Let z = (zl,2 , z3) represent the objective function vector. 2 The utility function U ( z l , 2 2 , ) : R2 + R1 is assumed to be linear and hence defined by U ( z 1 , z 2 ) = Xzl (I X)zz with unknown parameters X and (1 - A) values, 0 5 X 5 1 for each z:j = t,. A methodology that utilizes Geoffrions P(X) approach [4] to determine the set of efficient solutions for t,(min) 5 t,rL t,(normal) for 0 5 X 5 1 is 5 presented. An interactive version of the methodology is also discussed. Computational results demonstrate the efficiency of both enumerative and interactive methods. Section I1 introduces the time-resource tradeoff model and the methodology used to determine all efficient solutions to the problem. An illustrative example is given in Section 111. Section IV describes an interactive version of the methodology followed by computational results and comparisons in Section V. Conclusions are given in Section VI.
Abstruct- Given a project network with a set of tasks to be completed according to some precedence relationship, the objective is to determine efficient project schedules for a range of project realization times. This problem is referred to as the time-resource tradeoff problem. Associated with each task are its normal duration, maximum allowable crash range, and resource cost per time unit for each resource. A multiple objective linear programming (MOLP) model is presented. The time-cost tradeoff technique is extended to solve the time-resource tradeoff problem. The methodology assumes that the project managers (the decision maker) utility function over the resource consumption costs is linear with unknown weights for each resource. Enumerative and interactive algorithms utilizing Geoffrions P(A) approach, are presented as solution techniques. It is demonstrated that both versions have desirable computational times.

1. INTRODUCTION

ROJECT scheduling deals with the determination of activity (task) realization times in a way which minimizes the project completion cost. The cost of completing an activity of a project is actually an aggregated cost of usage of several resources required to perform the task. A time-cost tradeoff problem generates minimum cost project schedules as a function of project realization times. It provides the decision maker with information on the minimum achievable increase in project cost when the project realization time is decreased by one time unit. Generally, the minimization of the project cost is not the only desired objective. There will be some critical resources for which it is desirable to minimize the amount of consumption. A time-resource tradeoff problem provides project managers with information on how much each resources consumption (or its cost) will be increased if project duration is decreased by one time unit. Instead of generating a single time-cost tradeoff curve, one has to generate an efficient set of time-resource tradeoff curves for the project manager. Each time-resource tradeoff curve corresponds to the optimal curve for the time-cost tradeoff problem with the cost defined as the weighted sum of the resource usage costs for each activity for each resource. A multi-objective linear programming approach for the project scheduling model is also discussed [I]. The example given in the paper involved three objectives: 1) minimization of project cost, 2) minimization of project duration, and 3) minimization of realization time of a specific node (node k ) . The time-resource tradeoff problem defined in our paper assumes that the set of objectives is comprised of: 1) minimization of resource cost for each activity and 2) minimization
Manuscript received August 22, 1995; revised January 1996. Review of this manuscript was arranged by Editor-in-Chief D. F. Kocaoglu. P. S. Pulat is with the School of Industrial Engineering, University of Oklahoma, Norman, OK 73019 USA. S. J. Horn is with MPSI Systems, Inc., Tulsa, OK 74133 USA. Publisher Item Identifier S 00 I8-9391(96)08823-X.

TI. TIME-RESOURCE TRADEOFF MODEI A project network of a given project consists of a set of nodes indicating realizations of certain milestoncs 1, 2; and a set of arcs, A, referring to the tasks to be performed ) in the project. Each arc ( i , j E A refers to a unique task (activity). The project network is drawn so that all precedence relationships among tasks are observed.

0018-Y391/96$0S.00 0 1996 IEEE

412

IEEE TRANSACTIONS ON ENGINEERING MANAGEMENT, VOL. 41, NO. 4, NOVEMBER 1996

Activity(ij)

1 a;i

&

Fig. I .

An example CPS

The resource cost and the project duration are assumed to have a linear relationship. Each task (i, j ) E A has associated with it a normal duration Mi3 and an allowable crash range Si,. The objective is to determine the set of efficient project schedules for t,, where t,,(min) 5 t,r, 5 t,(normal). A project schedule is efficient if there does not exist any other project schedule Tor the same t,, with a better resource cost for all resources for a given range of values of A. The MOLP model for the time-resource tradeoff problem for k resources can be written as follows: Minzl =
( 2 , ~

~:~yi,

1E 4
~?~y;j

Min zg =
(",7)A

Fig. 2.

The resource cost plots as a function of A.

Min Z I ~ =
( i , i)E-4

a{:yi,

Min zK+l = t , subject to

tj
-

ti

+ gig 2 Mfj
yl,

5S ,
20

for all for all for all for all

(i, j )
(2,

j)EA

ti 2 0
Yij

i =l...-,n (i,j ) t A

where

t t,
M3 7

4;
Pi3

a73 ! .
A
71

realization time of milestone (node) i ; normal duration of activity (i, j ) ; allowable crash on activity ( 2 , j ) ; amount that activity (i; ,J') is crashed; cost of additional unit of resource k required to crash activity (i, j ) by one unit, k = I? 2 , . " , K.; set of activities in the network; number of nodes in the network.

that is, it varies the value of t , from t,(normal) to t,(min), and generates the set of efficient solutions corresponding to each t,. The variation of Z K + I from t,,(normal) to t,(min) follows the same process as in time-cost tradeoff approach. That is, cheapest set of activities are determined and crashed to their limit, which in turn reduces the project completion time. The constraints preserve the precedence relationships between activities and assure that activities will not be crashed beyond their limits. The minimum project completion time is reached when all activities on a path from node one to node n. have reached their allowable crash times. Let {uij; (,L; j ) E A } be a solution to the above MOLP problem with fixed t r LThen z k = C(i,j)tAnfl,y~jfor all k . . If the project manager's utility function is defined by

k=l

where

CXk=l

k=l Objective functions 21, . . , z~ minimize the cost of consuming resources 1 through K while Z K + ~ minimizes the then given { A k ; k = 1, . . . . K } one can determine the optimal duration of the project. The procedure enumerates on z ~ + 1 , schedule for the project manager. However, X k ' s are generally

PULAT AND HORN. TIMk. RESOURCh TRADEOR PROBLEM

413

(4-A

2)

( 4
Fig. 3. Labeling and residual capacity illustrations.

Fig. 4. An example project network.

not known in advance. Then, one either generates a set of all efficient solutions for 0 5 XI, 5 1 for all k , or develops an interactive procedure where the utility function of the project manager is implicitly refined as he/she is iteratively asked to indicate preference between schedule pairs. The solution approach uses Geoffrions P(X) method [4]. The time-cost tradeoff algorithm is discussed in detail by [2]. One can also refer to Fulkersons work 11 I ] for the development of the technique. We will assume familiarity with the time-cost tradeoff problem and extend it to the time-resource tradeoff problem with two resources. Further extension to K resources can be carried out by using interactive techniques to refine the A-space. The utility function for the decision maker for the two resource time-resource tradeoff problem is given by

U ( X l ,x 2 ) = X X l

+ (I

X)zz

where 0 5 X 5 1. The third objective function is X J = t,. Initially, all activity durations are set at normal levels and t,(normal) is computed. This schedule corresponding to t,, = t, (normal) is optimal for 0 5 X 5 1 with z1 = 0 and 252 = 0. The activity crash cost for activity (i, j ) is given by the function:

a) &

= Xa$

+ (1

Once the critical path subnetwork (CPS) is determined, one can use the maximum flow algorithm with uij(A) as the arc capacity for ( i , j ) in order to find the cheapest set of arcs to crash which will reduce t , by one unit. The cheapest set of arcs to crash will be different for different X ranges. For example, suppose Fig. 1 represents the CPS for a given project network. The plots of ai3(A) are given in Fig. 2. Using these plots, one can use the labeling procedure and determine the flow augmentings paths. After checking the arc capacities as a function of A on Fig. 2, it is concluded that the two A-ranges which need to be considered are 0 5 X 5 and 5 X 5 1. For 0 5 X 5 the node labels and the updated arc capacities are shown in Fig. 3(a) and (b), respectively. The node label for node j is given as (y3; where q.j is the maximum flow that can be delivered to node j from node one and is the immediate predecessor node from which node j received its label. ( 3 A) units of flow are augmented along thc path 1-23-4 which saturates arc (3, 4). The labeling procedure on the network of Fig. 3(b) leads to a flow of (3 - 4X) units along the path 1-2-4. Further labeling results in a nonbreakthrough, indicating that arcs (2, 4) and (3, 4) are the cheapest set of critical arcs to crash in order to expedite the project completion time. Similarly, the procedure can be carried out for 5 X 5 1

JJ=70L
~

/[4,71

\r

i,

c)

414

IEEE TRANSACTIONS ON ENGINEERING MANAGEMENT, VOL. 43, NO. 4, NOVEMBER 1996

(92,j3,8)
Fig. 5. Efficient solutions for the time-resource tradeoff problem

which will lead to arc (1, 2) being the cheapest arc to crash. The calculations which determine the amount by which to crash the selected arcs are the same as the calculations for the time-cost tradeoff technique described in [2]. The algorithm to determine the efficient time-resource tradet,, t,(normal) off curves as a function of X for t,(min) is explained next. Algorithm 1-Enumeration: Step 0: Initialization step. Determine t,(normal), t,(min). Set all activity durations to normal durations. Set t,, = t,(norinal), A m i n = 0,,,A , , = 1.

<

<

j), Step 4: For each (2; j), set t,, = tT,(i; Xrnitl = X i and ,,,A ,, = X j . Process steps 1 recursively for each 4 (2; j ) individually (i.e., the A-ranges defined by each ( i , j ) pair may each be broken down into several ranges of A, and each of those ranges broken down further, in tum, until t,(min) is reached for each final individual A-range). End while. Step 5 : Stop. The time-resource tradeoff curves for t,,(min) 5 t,rL t,, (normal) for all 0 5 X 5 1 have been found.

<

While

f,,

> t,,(min) for any X range

111. AN EXAMPLE Consider the project network shown in Fig. 4. For each activity ( i , j ) , the normal duration Mij, the minimum duration Mij - hi;, and the crash costs for resource types 1 and 2, u:; and a , respectively, are indicated on the figure. The normal :, and minimum project completion times are ts(norma1) = 17 and ts(rriin) = 8, respectively. The critical path is 1-2-3-5. For 0 5 A 5 0.5, arc (3, 5 ) is the cheapest to crash. For 0.5 5 X 1, arc (2, 3) is the cheapest arc to crash. Arc (3, 5 ) is crashed by one unit since path 1-4-5 then also becomes critical. The project completion time is t,, = 16. Similarly, arc (2, 3) is crashed by one unit before path 1-2-4 becomes

Step 1: Determine the CPS. Step 2: Using labeling procedure, determine the cheapest set of arcs to crash on the CPS for each A-range. Let AI < A2 < X3 < . . . < A, and define the A-ranges Let Ajj define the with X I = Amin and A, = A,,,. set of cheapest arcs to crash for Ai < X < A,. j), Step 3: For each ( i > use A,, to determine the maximum crash amount for t , and let & ( 2 , j) denote this amount. Crash the activities in A,, by that amount. Determine the new value for t,,, tn(2,j) = t , St,(i, j), and the corresponding z l ( 2 ) and z z ( 2 ) values.
~

<

PULAT AND HORN: TIME-RESOURCE TRADEOFF PROBLEM

415

seconds

- -RahmansMethod I

Algorithm 1 (Enumerative Method)

Set
Fig. 6. Computational time comparisons.

TABLE I DESCRIPTION TESTPROBLEMS OF Data Set 1 2 3 4 5 6 7 Number of Nodes

TABLE I1 CPU TIME(IN SECONDS)

5
6 7 7 8 11 11 15 20 30 40 50

Number of Arcs 8 10 11 12 15 15 23 25 35 65 100 100

Sample S i x 10

8 9 10 II 12

10 10

Data Set 1 2 3 4 5 6 7 8 9 10 11 12

Enumc tive Method Mean Std. Deviation 0.007 0.062 0.009 0.068 0.010 0.072 0.063 0.012 0.077 0.016 0.006 0.090 0.084 0.017 0.234 0.086 0.453 0.223 0.65 1 1.819 1.497 4.687 1.623 4.969

Interactive Method Std. Deviation Mean 0.006 0.114 0.115 0.007 0.1 16 0.006 0.118 0.009 0.007 0.120 0.005 0.121 0.008 0.125 0.007 0.126 0.007 0.126 0.010 0.141 0.009 0.156 0.045 0.184

critical. One continues in this fashion until t, = 8. Fig. 5 summarizes the iterations in a tree diagram. Once x1, 2 2 , x3 values are determined for all efficient solutions at xg = t, , one can check to see if the same solution was generated more than once. If that is the case, the two solutions can be merged by taking the union of ihe individual A-ranges as shown in Fig. 5.

(or t , > t,, (desired) if the project managers desired time is greater than the minimum achievable). Step 3 is still inserted after Step 3 and Step 4 still replaces Step 4. Step 3: Ask the project manager to select one of the two solutions defined by [ 1 1 ,z ( ) 231 for A 1 < z() zl, A < A2 and [ z l ( r - l ) ,Z ~ ( T l ) , 231 for A,I < A < A,. using t , = niax[t,(I, 2). t l L ( ~1, r ) ] . IV. AN INTERACTIVE TIME-RESOURCE TRADE-OFF METHOD If T > 3, recursively ask the project manager to select the preferred schedule by moving the XThe interactive version also allows the project manager to range not selected inward one step, i.e., if the first input a de5ired completion time since he/she may not want is selected, test it against [ z ~ ( - 2), zz(r - 2 ) ; z3] T to incur the cost of reduction to the minimum. This version for X,-z < A < ATP1 until only one A-range of Algorithm 1 presents the project manager two efficient remains. Let A i < A < A, be the selected range. solutions for the same t , and asks himher for the preference. , = A?. Step 4: Set t , = Ln(i,j ) , X m i n = X i and , ,A Assuming that the project manager is a rational person and Return to Step 1. makes consistent decisions, one can refine the A-range based Using the previous example, suppose the project manager on the given answer. The modification over the previous algorithm is that the While loop is only for t,, > t , (rnin) is presented with the two solutions (6, 2, 16) and (4, 4,

416

IEEE TRANSACTIONS ON ENGINEERING MANAGEMENT, VOL. 41, NO. 4, NOVEMBER 1996

16) and the solution (4, 4, 16) is selected. Then the project manager is given two more solutions (44, 20, 12) and (40, 32, 12). Suppose (40, 20, 12) is preferred. The procedure will then generate (56, 31, 11) and (92, 73, 8) without interacting with the project manager. If the project manager has input a completion time greater than t,(min), the procedure will halt at that time value. For example, say the desired completion time was t,, = 10. The procedure would generate a solution of (68, 45, 10). V. COMPUTATIONAL RESULTS Both the enumerative and interactive approaches were programmed in FORTRAN. Both approaches assumed only two resources. Random project networks were generated by a random network generator code developed at the University of Oklahoma. Twelve different data sets containing ten networks in each set were tested by the two codes. Table I describes the data sets. The activity parameters were randomly generated as follows: MiJ is drawn from a uniform distribution defined , between [ 1, lo]; 6 is drawn from uniform [l, Mij] and the are drawn from uniform [I, 101. resource costs at, and Each data set was solved using the two codes on a Multimax 320. Table I1 shows the average CPU time (in seconds) and its standard deviation for each data set. Similar size problems were run by Rahman [81 and compared to ADBASE [9] solution times in the report. Fig. 6 shows a drastic difference in performance between Algorithm 1 (enumerative method) and Rahmans Method. The largest network size tested by Rahman had 41 nodes and 87 arcs. As shown by Fig. 6, the CPU time for Algorithm 1 does not rapidly increase as network size increases. For data sets 8- 12, the interactive method indicated tremendous savings over the enumerative method. This can be attributed to the increased number of efficient solutions existing for larger project networks. Since the interactive method only finds a subset of the total found in the enumerative method, one would expect the time requirement to be much less. Table I11 gives the mean number of efficient solutions for each data set along with the relative standard deviations. Each problem was also solved by ADBASE to assure that, in fact, all efficient solutions are generated by the enumerative method. VI. CONCLUSIONS Enumerative and interactive algorithms are presented for the time-resource tradeoff problem with two resources. It is assumed that the project managers preference function on the two resources is linear. Geoffrions P ( A ) approach [4] for bicriteria linear programming problems and the time-cost tradeoff technique which is an application of the primaldual algorithm of linear programming to project networks are integrated to solve the time-resource tradeoff problem. Computational results indicate the superiority of both methods over existing solution approaches. One can also deal with resource limitations by defining the objective functions z and zz as total amount of resource 1

Data Set
~

1 2 3 4 5 6 7

8
9 10

I1
12

Number of Efficient Solutions Mean Standard Deviation 6.9 2.2 10.9 3.8 15.7 4.6 14.6 5.9 23.3 9.0 41.3 12.3 35.7 15.4 54.5 18.4 87.7 28.5 267.2 79.7 447. I 133.9 463.4 151.7

one and resource two to be used by the project, respectively. The efficient solution tree can then be pruned when the total consumption of a resource reaches its limitation. The maximum flow procedure used to determine the cheapest set of activities to crash on the critical subnetwork always determines the first cheapest subset encountered to be the set of activities to crash. There may be alternate optimal solutions (that is other subsets of activities with equivalent costs). This will not pose any complications when project duration is further crashed since those subsets will ultimately be selected. One can detect alternate optima from the efficient solution tree by locating two successive branches on the tree with the same incremental cost per unit time for the respective resource. The methodology presented in this paper can be further extended to solve the general time-resource problem with K resources. Other utility functions can also be considered to represent the project managers preference on resource costs.

REFERENCES
R. F. Deckro and J. E. Hebert, A multiple objective programming framework for trdde-offs in project scheduling, Eng. Costs Prod. Econ., vol. 18, pp. 255-264, 1990. S. E. Elmaghraby, Activity Networks: Project Planning and Control by Network Models. New York: Wiley, 1977. E. L. Hannan, The application of goal programming techniques to the CPM problem, Socio-Econ. Plan. Sci., vol. 12, pp. 267-270, 1978. A. M. Gcoffrion, Solving bicriterion mathematical programs, Operut.
Res., vol. IS, no. 1, pp. 39-54, 1967. S . M. Lee and D. L. Olson, Project scheduling for multiple objectives,

i n Project Munayement: Methods and Studies. Amsterdam: Elsevier, 1985, pp. 123-137. L. J. Moore, B. W. Taylor, E. R. Clayton, and S. M. Lee, Analysis of a multiple critcria project crashing model, AIIE Trans., vol. 10, no. 2, pp. 163-169, 1978. P. Vrat and C. Krierigkrairut, A goal programming model for project crashing with piecewise linear time-cost trade-off, Eng. Cosr.vProd. Econ., vol. IO, pp. 161-172, 1986. A. Rahman, Multiple objective time-resource trade-off problem, unpublished Ph.D. dissertation, Univ. Oklahoma-Norman, 1992. S. E. Steuer, ADBASE-Multiple Objective Linear Programming Code. Atlanta: Univ. Georgia, 1991. - Multiple Criteria Optimization-Theory, Computation, and A p , plication. Malabar, FL: Krieger, 1989. D. R. Fulkerson, A network flow computation for project cost curves, Manage. Sci., vol. 7, no. 2, pp. 167-178, 1961.

PULAT AND HORN: TIME-RESOURCE TRADEOFF PROBLEM

417

P. Simin Pulat received the B.S. dcgree in industrial

engineering from the Middle East Technical University, Ankara, Turkey, and the M.S. and Ph.D. degrees in operations research from North Carolina State University, Raleigh. She is currently an Associate Professor of Industrial Engineering at the University of Oklahoma, Norman. Her research interests have included network optimization, multiple criteria decision making, combinatorial optimization, and application of operations research models to engineering . - problems. Her current research involves application of tabu search technique to facility layout and continuous optimization problems. Dr. Pulat is a member of Institute of Industrial Engineers and the Institute of Opcrations Research and Management Scicnce.

Steven J. Horn recieved the B.S. and M.S. degrees in industrial engineering from the university of Oklahoma, Norman. He is currently a modeling analyst at MPSI Systems, Inc., in Tulsa, OK. His work involves modeling and statistical analysis of the retail petroleum industry. His current research interests are in multiplicative competitive interaction marketing models and neural networks Mr. Horn is a member of Institute of Industrial Eneineers and the Institute of Operations Research and Management Science.
I