Division of Research Graduate School of Business Administration The University of Michigan January 1980 PROJECT SCHEDULING WITH RESOURCE-DURATION INTERACTIONS: THE NONPREEMPTIVE CASE Working Paper No. 200 F. Brian Talbot The University of Michigan FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the express permission of the Division of Research.

I I I I i~~~~~~~~~~~~~~~~^ I~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~- '

ABSTRACT This paper introduces methods for formulating and solving a general class of nonpreemptive resource-constrained project scheduling problems in which the duration of each job is a function of the resources committed to it. The approach is broad enough to permit the evaluation of numerous time or resource-based objective functions, while simultaneously taking into account a variety of constraint types. In particular, techniques are presented for solving the time-cost tradeoff problem under multiple resource constraints, and the problem of finding the minimum project completion time under multiple resource constraints when resource allocations affect job performance times. Computational results indicate the the procedures provide cost-effective optimal solutions for small problems and good heuristic solutions for larger problems. The programmed solution algorithms are relatively simple and require only modest computing facilities, which permits them to be potentially useful scheduling tools for organizations having small computer systems.

ff

INTRODUCTION Over the past decade attempts to solve multiple resourceconstrained project scheduling problems of either the preemptive [10] or nonpreemptive [1, 3, 4, 8, and 9] varieties have been restricted to certain cases. These were cases in which each job was characterized by a unique duration and by a singular complement of resource requirements that had to be met in each time period the job was in process. Formulations of the more general model which permit jobs to be accomplished using one of several complements of resources have been known since at least 1969 [5]. But researchers have generally been dissuaded from developing optimizing codes for these models because of the formidable computational problems involved in implementing the formulations. Only recently has there been a serious effort to solve the general time-resource tradeoff problem for the preemptive case [6], while still very little computational experience has been reported for the nonpreemptive case [2, pp. 173 -183]. It is the purpose of this paper to introduce a relatively simple yet effective procedure for optimally or heuristically solving nonpreemptive scheduling problems. The paper will focus on two variations of the time-resource tradeoff problem: finding the schedule of jobs that minimizes project completion time, and determining the schedule of jobs that minimizes overall project costs. The first model was selected because it is the natural generalization of previous nonpreemptive resource-constrained project scheduling research [1, 3, 4, 8, 9]. The resource-constrained time-cost tradeoff problem was selected because it bridges an important gap in the project management literature: the gap between time-cost tradeoff scheduling techniques and methods for scheduling

-3 - under resource constraints. Time-cost tradeoff methods have been based on the assumption that resources are available in unlimited quantities. Resource-constrained models, on the other hand, have not been developed to explicitly treat cost or profit as a scheduling objective while simultaneously permitting job durations to be affected by resource allocations. The proposed formulation and solution algorithm remove the above restrictions. The nature of the time-resource tradeoff problem will first be described and formally defined using a zero-one integer programming approach. Next, an implicit enumeration solution technique will be introduced for finding the schedule of jobs that minimizes project completion time. Modifications to this algorithm are subsequently described for solving the problem given monetary-related objective functions. Illustrations of these ideas follow, with solved examples for the objectives of minimizing project completion time and minimizing total project cost within the framework of a resource-constained time-cost tradeoff problem. The last section of the paper presents computationalresults for a series of test problems. FORMULATION OF THE PROJECT COMPLETION TIME MINIMIZATION PROBLEM One can assume without loss of generality that a project can be depicted by an acyclic activity-on-node graph where activities, or jobs, are numerically labeled such that successor jobs always have higher numbers (labels) than all their predecessors. Associated with each job is a set of possible durations and the corresponding resource requirements which would permit the job to be completed in the stated durations. Each duration-resource combination is called a "job-operating mode" or simply a "mode."

-4 -In keeping with the general nature of the model, three resource categories are included. Using the terminology introduced by Weglarz [12], and Slowinski [6, 7], these resources are defined as renewable, nonrenewable or doubly constrained. If resources are available in limited quantities each time period, the resources are considered renewable. An example of such a resource would be skilled labor: the number of skilled laborers available to work on the project each day is limited, although no constraint is placed on the number of days skilled labor may be used. Thus, the resource labor is renewed each period to a predetermined level, where the level may differ from one period to the next. If the total consumption of a resource over the life or part of the life of the project is constrained, it is called nonrenewable. Money is perhaps the best example of a nonrenewable resource: overall project costs are frequently limited to a fixed predetermined contract price. Also, cash flows within a project may be pegged to the attainment of milestones by particular dates. If the budgeted capital is not used before a specific time after which it is no longer available, it is a nonrenewable resource. Finally, resources are defined as doubly constrained if both their per-period and total availability are limited. Money is again probably the best example of a doubly constrained resource: cash flows per day as well as total cash expended on a project are often restricted. These three resource categories will be included in the model because a variety of time and resource-based objective functions, as well as constraint forms, may then be considered. This has been very ably demonstrated by Weglarz [11] and Slowinski [6, 7] for many different scheduling problems, but especially for the preemptive scheduling problem.

-5 -The general time-resource tradeoff problem can be formulated as an integer programming problem in which a zero-one integer variable xtm = 1 if job j operating in mode m (1 < m < Mj) is assigned a completion time in period t; otherwise, xjtm = 0. Jobs are labeled from 1 to N, with job N being the unique terminal task without successors. If such a job N does not naturally exist, then a dummy job N having one mode with zero duration and zero resource requirements is appended. Associated with each job j are its critical path determined early finish time, Ej, and late finish time, L.. Both E. and L. are calculated in the usual way but using J I J the set of minimum duration modes for all jobs. In determining the L., L is set equal to a known heuristic project completion time H, j N or, if H is not known, LN is set equal to the sum of all maximum job durations. Equations (1) to (5) define the problem when the objective is to minimize project completion time. Occurrence constraint set (2) insures that each job is completed exactly once. Constraint set (3) insures that precedence relationships are maintained. Here P is the set of all pairs of immediate predecessor jobs and d. is the duration of job j operating in mode m. Renewable resource restrictions are enforced by constraints (4). Resource k is available in Rkt units in time period t. Job j requires the use of rjkm units of renewable resource k when operating in mode m. Nonrenewable resource limitations are imposed by (5). Here W. is the amount of nonrenewable resource i available for the project, and w.. is the amount of resource i jim consumed by job j in mode m. Doubly constrained resources would appear in both (4) and (5). For example, for a given job and mode we could set rjk = w. i/dj where k and i refer to the same resource type. jkm jkm j jm

-6 - The resource requirement rjkm can now be considered the rate at which resource i is consumed by job j; thus both the rate and total usage of resource k are constrained. Minimize m= 1 LN t = tNtm (1) EN Subject to M. m = 1 m-l L. t = Xjtm = 1 for j = 1,...N (2) E j M a m - L a t = Mb txatm + m = Lb ( ft-d x > 0O t/ = tbm btm - t = Eb b (3) 1 E a 1 for all (a,b)eP N j = 1 M; m = 1 - t + d. -1 jm q = t r xjqm < R jkm jqm - kt (4) for k = 1,...,K t = 1,...,H w.. x < W. jim jtm- N j = 1 M. m = 1 Lt t = E. ] (5) -. — j,, -. - -- -

-7 - FORMULATION OF PROBLEMS WITH MONETARY OBJECTIVE FUNCTIONS The presented model permits one to consider several alternative objective functions in addition to simply minimizing project duration. In particular, least cost schedules can be obtained, if the first term in (6) becomes the objective function, and (7) replaces (5). Given an arbitrarily large project completion time T, the global minimum cost solution can be found. Otherwise, the least cost solution will be obtained such that project completion time is less than or equal to the desired completion time T. Of course, the resource c in (6), which we are calling cost, may be any nonrenewable or doubly constrained resource. N M. Lj LN Min 7 + 5 jcm tmS XNtm (6) j = 1 m = 1 t = Ejm = 1 t = EN M LN tX Ntm < T (7) m = 1 t = EN m=l t=EN By adding the second sum to (6) and dropping the constraint set (7), the problem becomes a resource-constrained version of the classical CPM time-cost tradeoff problem. Here St, which is usually approximated by a constant for all t, represents project overhead per period. By making St a function of time, however, performance penalties or bonuses may be considered explicitly. If the project's time horizon is long, then the present value of cash flows rather than the absolute cost of the project may

-8 -dominate in importance. In this case, the objective function would be to minimize the present value of expenditures of resource c as given by (8). Here, vjtm is the present value of expenditures of resource c for job j operating in mode m if it finishes in time period t. Of course (8) can be replaced with a "maximize net present value" objective function if revenues are also taken into account. N M. Lj J _ -Min v jtm xj tm (8) j=l m=l t = E. Other objective functions and constraints can be incorporated into the model and solved using the proposed algorithm. The inclusion of lateness penalties and due dates or job performance constraints, such as concurrency requirements, are some of these possibilities. Since these variations have been considered in [5] and could easily be included in the algorithm, we will not repeat them here. It is of interest, however, to note that an important' problem bridging the gap between the capital budgeting problem and the general time-resource tradeoff problem can be effectively formulated with our procedure. A brief comment on this situation is in order, because it is a frequently encountered problem that has not been adequately treated in the literature, and because it requires a new interpretation of what have been called nonrenewable resources. To motivate this discussion, consider the general multiproject scheduling problem restricted by renewable, nonrenewable, and doubly constrained resources. Assume that the objective is to schedule jobs in order to maximize the net present value of all projects, where all projects must be completed. Further assume that money is a nonrenewable

-9 - or doubly constrained resource and that the completion of certain jobs (or projects) results in a positive cash flow. In this case, the performance of certain jobs increases or renews the nonrenewable resource money. This resource dependency between jobs poses no formulation problems: positive resource flows are simply indicated by negative coefficients for appropriate variables in (5) or in (8). However, the nomenclature "nonrenewable" somewhat disguises the broader interpretation of constraint set (5). SOLUTION METHODOLOGY FOR THE PROJECT COMPLETION TIME MINIMIZATION PROBLEM A two-stage solution methodology is developed which builds upon ideas presented earlier [9] for the basic resource-constrained scheduling problem. A specialized algorithm of this type was selected because of the inability of general purpose 0-1 computer codes to efficiently store and solve problems of the size we are considering. Stage one defines the problem as a compact integer programming problem, and stage two searches for the optimal solution using an implicit enumeration scheme that systematically improves upon generated heuristic solutions. Conceptually the problems are given by (1) to (8), but operationally no constraints or objective functions are explicitly formulated in our procedures. Rather, all resource and precedence data are stored in compact arrays that are interrogated during enumeration to insure solution feasibility. This results in a very efficient use of computer storage and also in a reduction of computational time. Stage One In stage one the network is first relabeled using one of the heuristic scheduling rules listed in Table 1. This process is similar to that successfully used in [9], although the rules

-10 - TABLE 1 Node Relabeling Rules Rule Formula Description 1. MAX ADUR. 3 M. m=l maximum average job duration 2. MAX DUR. I Max {d jmm = 1,..., maximum job duration 3. MIN L. J L 3 minimum late finish time 4. MAX RD 3 M. jm 1m=l K k=l M. r jk/ (Msk) nr-^kn maximum resource demand 5. MIN E ] E. I minimum early finish time 6. MIN(L-D)j Min [L. - min {d jmm=l,...M.}] j ~ ~ jm'''j minimum (late finish time reduced by smallest duration) 7. RAN. 3 nodes renumbered randomly 8. MIN(L-D) j M. Min {L. - m=l djm/Mj } minimum (late finish time reduced by average duration)

-11 - are calculated differently. The effect of this relabeling procedure is to specify the order in which jobs will be considered for assignment (scheduled) during stage two of the algorithm. Resources and modes are also sorted for each job in stage one. Renewable resources are sorted such that the resource having the maximum frequency of highest per-period requirement relative to resource availablity has the smallest numerical label. Specifically, for each resource and job mode an index (9) is calculated. Index jkm= d. for the k which maximizes rjkm/Rk (9) Otherwise, Index =0, jkm where L. Rk = Rkt/(L. - E.+l) t=E. 3 These indices are summed over all jobs and modes, then the resources are sorted in decreasing order of summed indices. The effect of this sort during the enumeration procedure is to identify resource infeasibility as early as possible. This sorting procedure can markedly reduce computational time when the number of renewable resources exceeds two. Depending on the objective function selected, one of several mode sorts is used. For example, if the objective is to minimize project duration, modes are sorted by increasing duration. If the objective is to minimize project cost, then modes are sorted according to increasing total cost. Mode sorting procedures typically have a significantly far greater effect on computational time than resource sorting. The primary reason is that the order in which modes are sorted determines, -I-I. ---- — ----~ --- —----- ---------------------------------------- I"-I- - --- -

-12 -along with job labeling, the initial heuristic project completion time found by the enumeration procedure, and hence, the initial bounds L.. Stage Two Once a problem has been prepared for analysis, the algorithm passes to stage two. Here an implicit enumeration algorithm builds always feasible partial solutions into complete schedules by considering jobs for assignment in increasing numerical order. Since in stage one jobs were labeled according to modified priority dispatch scheduling rules (from Table 1), the effect of this predetermined enumeration scheme is to apply successively the heuristic to the problem defined by the unscheduled jobs. Optimality is assured by either bounding the solution, or by implicitly or explicitly enumerating all possibilities. The discussion which follows will begin by considering the enumeration procedure for the objective of minimizing project completion time as given by (1) to (5). A demonstration of how the procedure can be modified to take into account other objective functions will follow. Associated with each job j are integer variables Y. and U., where Y. = t and U. = m, if mode m of job j is assigned a completion time of J 3 t. Otherwise, Y. and U. are both unspecified (since partial schedules are always feasible). Enumeration begins by assigning mode 1 of job 1 to its earliest possible completion time. Renewable resources required, rlkl, are subtracted from resources available, Rkt, for k=l,...,K and t=l,...,Y. Similarly, nonrenewable resources consumed, wlim, are subtracted from W. for i=l,...,I. Beginning with job 2 and continuing to job N, an attempt is made to assign the first mode of each job to its earliest precedent and resource-feasible completion time. Precedence and resource con straints are maintained by first finding t* = max {Y plpeP*} p 3.

-13 - where P* is the set of immediate predecessors.of j. To insure that j nonrenewable resources are not overconsumed, availability array W. is interrogated to determine whether w.. < W.. Then the resource jim - 1 availability array Rkt is scanned for k=l,...,K and from t* +1 to L. for the earliest contiguous interval d. units in length where rjkm < Rkt. Suppose that interval begins at t* + A; j then ends at t' = t* + + d. -1. Consequently, we would set Y.=t', U.=m, and adjust resource availability arrays accordingly. Rkt would be reduced rjkm units from t = t*+A to t' for k=l,...,K, and w. would 3 z~~~~~~km~~an 1 be reduced by w.. for i = 1,,I. Borrowing a term from 0-1 integer programming, the process of assigning a completion time to job j is called augmenting variable Y. to t'. If augmentation of mode m of job j is prevented because of either type of resource infeasibility, modes m+l, m+2,...,M. are considered for augmentation. If none of the modes of j is resource feasible, then the algorithm backtracks to job j-1. Mode m=U.j of job j-1 is removed from solution. Array Rkt is increased by rjlkm units for k=l,...,K and t=t", t"+l,...,Y._1 where t"=Y l+l-dj m ''' ' ''''' j-l' j-1m W. is increased by j-lim for i=l,...,I. An attempt is now made to reassign job j-l mode m to the earliest feasible completion time after Yj-i. That is, Rkt is scanned from t=t"+l to L. for the earliest contiguous interval djlm units in length where rjlkm < Rkt, for k=l,...,K. If such an interval is found, then Yjl is set equal to the new completion time, resource arrays are adjusted, and so on. If no such interval is found, an attempt is made to assign mode m+l, m+2, etc. This process of augmentation and backtracking continues until job N is assigned a completion time, or until an attempt is made to backtrack below job 1. In the former case an improved (reduced) completion

-14 -time for the project is found. In the latter, the incumbent best solution is optimal. When an improved solution with a reduced project completion time T* is found, it replaces the incumbent solution (if any) in the vectors B and Z, where B. contains the completion time of job j and Z. the mode of j actually assigned. If BN equals a known lower bound on the solution, such as the critical path early completion time EN, then B contains the optimal schedule. If BN exceeds the best known bound, the late finish times L. are reduced by the quantity LN - (BN +1) and the augmentation process starts anew with job 1 mode 1. Again, optimality is assured when either an attempt is made to backtrack below job 1, or a project completion time is found that is equal to a known lower bound. ALGORITHM MODIFICATIONS NEEDED FOR PROBLEMS WITH COST RELATED OBJECTIVE FUNCTIONS The above discussion has been restricted to the case il which (1) is the objective function. If (6) or (8) were the objective function and constraints (7) were appended to the model, the above algorithm could still be used after incorporating the following minor modifications. In stage one during the calculation of Lj, the desired project completion time T replaces H, a known heuristic completion time for the project. In stage two, several changes in the solution procedure are made. First, the late finish times L. are not updated when a new completion time is found for job N. But the cost C of the incumbent solution (if one exists) is replaced by the cost, as represented by (6) or (8), of the improved solution. The incumbent cost C then becomes a new upper bound on the solution. This upper bound is used in two ways. During augmentation, when mode m of job j is about to be evaluated for resource feasibility, a check is made to insure

-15 - that the actual cost of the current partial solution for jobs 1 to j-1 plus the cost of job j does not exceed C. Unfortunately, this is a weak test that guarantees feasibility but it does not exclude the explicit evaluation of many other nearly good solutions. Given the strong ordering scheme used for augmenting variables in the algorithm, it is possible to construct the following tighter cost bounds. Define a vector D with elements D. given by (10). D. is thus 3 3 N D. = 7 min {w mm=l,...,M} (10) g=j the cumulative minimum cost of all -unassigned jobs when job j is being considered for assignment, where the nonrenewable resource c is cost. This cost bound is implemented before precedence restrictions are evaluated.,If the actual cost of the partial solution of jobs 1 to j-1 plus D. is greater than or equal to C, 3 then backtracking to j-l commences immediately. GENERAL OBSERVATIONS ON COMPUTATIONAL STRATEGIES In this paper as in [9], the general approach to the minimum project completion time problem is to start with a heuristic solution and to improve upon it systematically until the optimal is found. The attractiveness of this strategy is that the procedure may be stopped before reaching optimality when the tradeoff between computational time and potential solution improvement becomes unfavorable, yet a good heuristic solution to the problem will still be available. Very often, however, this is not the favored approach from a strictly computational point of view when an optimal solution is desired. If the initial heuristic solution greatly exceeds the optimal solution,

-16 - then a fair amount of time may be expended in generating improved but nonoptimal solutions. An alternative strategy in this case, found to be useful in a zero-one approach to minimum duration project scheduling [3], is to search over a varying completion time horizon. Although it has not been implemented, the proposed algorithm could easily be modified to accomodate this approach. Regardless of the horizon strategy used, however, a successful application of this technique relies very heavily on heuristics —heuristics to obtain a good starting solution for bounding purposes (e.g., calculating Lj) and good heuristics to use in mode relabeling and resource and modesorting schemes. The computational section will report on results using the heuristics listed in Table 1. SOLVED EXAMPLES The following example, adopted from Elmaghraby's excellent text on networks [2], illustrates the foregoing discussion. In Figure 1, the project is shown to consist of six jobs, each of which may be accomplished in one of two modes. Five renewable resources are required by each job. Resource one represents a higher level of skill than resource two, which is reflected in reduced durations for those modes using resource one. The resources available in each period of the project's duration are 1, 2, 6, and 8 for resources one, two, three, and four respectively. Resource five will be discussed momentarily. The scheduling problem Elmaghraby considers is to find that combination of modes and job starting times which will minimize project completion time given these four resource restrictions. This problem is specified by (1) to (4), and the optimal solution is given in Figure 2.

-17 - ~' Renewable (Per Period) Resource Requirements 1 2 3 4 5 Job Number 1 Mode 1 2o 2 1 2 3 1 2 Duration 2 3 1 3 3 4 5 7 4 6 1 4 0 Total Cost 1 0 2 1 135 0 1 2 1 65 1 0 3 2 160 0 1 3 2 90 1 0 1 4 170 0 1 1 4 100 i60 270 510 400 $270 195 - 4 1 2 1 0 0 1 3 155 1 1 3 85 775 595 5 1 2 6 1 2 1 1 0 2 2 150 0 1 2 2 80 1 0 3 4 190 0 1 3 4 120 0 0 0.0 0 1 2 6 8 300 190 480 0 600 480 7 Resources Available Each Period Figure 1 A Six-Job Project

Job Schedule J rob Mode 1 2 XXX 2 2 XXX 3 1 X 4 1 XXXXX 5 2 XXXXXX 6 1 X 123456789 Time Resource Profile Time Period 1 2 3 4 5 6 7. 8 9 Resources. Consumed I2 2 3 4,. 1 2 1 2 1 2 1 1 1' 1 1 1 1 1 1 1 1 1 6 7 6 7 67 3 5 35 35 3 5 3 5 5 6 Figure 2 Minimum Duration Solution to Sample Problem

-19 - In order to illustrate the notion of renewable and doubly constrained resources, we have modified Elmaghraby's problem by appending to each mode its per period and total costs of operation. Assuming that the resources are valued at $100, $30, $10, and $15 per period, the period cost of job 1 mode 1, for example, would be $135 = [1(100) + 0(30) + 2(10) + 1(15)], and its total cost would be $270 = 2(135). If only total cost is constrained, cost would be a nonrenewable resource. If resource five, cost per period, and total cost are constrained, then cost becomes a doubly constrained resource. Figure 3 illustrates the minimum duration solution to the sample problem after restrictions have been placed on per-period and total cash expenditures. This problem is. depicted by (1) to (5) where maximum per period cash flow R5t = $300, and maximum project cost W $2,020. Figure 4 shows the minimum cost solution to the sample problem represented by (2) to (6), where the latest acceptable project completion time is T = 10, and the maximum per period cash flow R5t = $300. Here, St = 0 for all t. Perhaps the most interesting case, however, is when St 0, since this casts the problem as a resource-constrained project scheduling time-cost tradeoff problem. For example, if the per period overhead cost of the sample problem is S = $250 for all t, the overall minimum cost schedule is given in Figure 4. This can be verified quite readily by noticing that if the project were extended one period as given in Figure 3, then the marginal cost of overhead, $250, would exceed the marginal reduction in scheduling costs, $180 = 2200-2020. LE -W;. — ~~~~~~~~~~~~~~~ - " -~~~~~~~~~ s - -I — -

t, -20 - Job 1 2 3 4 5 6 ModE 2 1 2 2 2 1 Job Schedule XXX XXXXX x xxxx xxxxxxx xxxxxx 12345678901 Time Resource Profile Job Cost $195 160 400 595 480 190 $2020 Time o Period 1 2 3 4 5 6 7 8 9 - 10 11 Resources Consumed 1 2 3 4 5 (Cash Flow) 023 02 3 023 02 2 1 1 4 023 023 023 023 023 1 1 5 5 165 5 165 5 165 7 185 5 245 5 165 5 165 5 165 5 165 5 165 6 270 Figure 3 Minimum Duration and Minimum Cost Solution to Sample Problem with Money a Doubly Constrained Resource

b -21 -Job Schedule Job Job Mode Cost 1 2 XXX $195 2 1 X 160 3 2 XXXX 400 4 1 XXXXX 775 5 2 XXXXXX 480 6 1 X 190 1234567890 $2200 Time Resource Profile Time Resources Consumed Period _1 2 3 4 5(Cash Flow) 1 0 2 3.5 165 2 0 2-3- 5 165 3 0.2.3 5165 4 1 1 2 7 255 5 1 1 3 5 235 6 1 1 3 5 235 7 1 1 3 5 235 8 1 1 3 5 235 9 1 1 5 4 240 10 1 1 5 6 270 Figure 4 Minimum Duration Solution to Sample Problem with Project Completion Time Less Than 11.. - - ------ -- - -- IIILICIC

.-22 - COMPUTATIONAL RESULTS To test the efficacy of this approach the enumeration procedure which solves the minimum project completion time problem was programmed in FORTRAN. This basic program was then modified, as described previously, to solve problems with cost-related objective functions. No special programming effort was exercised to optimize either the storage of data or program-running efficiency, since tle basic approach already does a reasonably good job in both respects. Although for testing purposes two separate programs were developed (the basic and the modified program),with very little effort one program could be written to solve all the various problems discussed in this paper. Such a program could easily be written to run in less than 32k Bytes for problems containing approximately thirty jobs with three modes each, and six renewable and ten nonrenewable resources over a planning horizon of 100 time periods.' This efficient use of computer storage permits the approach to be adopted by potential users with only modest computer hardware. A preliminary evaluation of the heuristic rules shown in Table 1 was accomplished by solving 100 10-job problems as project completion time minimization problems with each heuristic used as a node-numbering rule. Detailed descriptions of these problems will not be given here since they are completely listed in Appendix A. Briefly, jobs in each problem had from one to three modes of operation and each mode was constrained by three renewable resources. The total number of modes in each project ranged from eighteen to thirty. Network complexity (the ratio of the number of precedence relationships to the number of jobs) ranged from 1.0 to 1.6. Critical path early _i;,[. _ $,,X _ ___

-23 - finish times EN ranged from 10 to 27, and optimal project completion times ranged from 12 to 32. Table 2 contains five summary.measures of heuristic performance for the minimum duration problem. "Best" refers to the smallest project completion time found by all heuristics. "Optimal" is the percentage of problems for which the rule obtained an optimal solution. "Worst" is the percentage of problems for which the rule yielded the largest project completion time. Measures d and e refer to the percentage of problems for which the enumeration algorithm found and verified the optimal solution when the jobs were numbered with the respective heuristics. Certainly no sweeping generalities can be inferred from an analysis of this small sample. It is interesting to note, however, that all rules outperformed the random rule number 7 on all measures except total time to optimality. Furthermore, the best overall rules; numbers 3, 6, and 8, are based on the minimum late finish time rule which has been found to be one of the best rules for the single-mode problem [9]. The minimum average time to find and verify the.optimal solution for all 100 problems was obtained with rule 8 at.392 seconds of CPU time for each problem on an AMDAHL 470 V/7 computer. The range of solution times for each problem using rule 8 was from.001' to 12.912 seconds with only two problems requiring more than 2 seconds. To evaluate the effectiveness of this approach on larger problems and with cost-related objective functions, ten 20-job and ten 30-job problems were solved under a variety of resource and cost conditions. '-r. - -~lrrt ~ I — T- - — _ - X.- yC - —. -, --

-24 - TABLE 2 Heuristic Solution Results for Minimum Duration Problems Rule* Percentage of Problems on which Rule Was 1 2 3 4 5 6 7 8 a. Best.72 73 83 73 76 77 57 76 b. Optimal 30 29 33 30 30 34 23 34 c. Worst 60 59 46 58 53 54 77 54 d. Fastest to optimal 37 41 52 49 37 58.37 55 e. Slowest to optimal 37 39 28 40 39 28 59 29 *Described in Table 1 --— I --— lr --- — - -- --- -, ---~ —~ — _-rrrrumrreB — _

-25 - It was not always possible to solve these problems optimally within 16 seconds of CPU time, which was the maximum time the program was permitted to run for a given problem. However, in all cases good heuristic solutions were found within two seconds by at least one of the eight renumbering heuristics listed in Table 1 when appropriate mode sorting was also used. SUMMARY AND CONCLUSIONS This paper has presented a computationally tractable integer programming approach for solving a large class of nonpreemptive resource-constrained project scheduling problems in which job performance time is a function of resource allocation. The approach is general enough to permit the solution of problems with time or monetary objective functions under a variety of resource restrictions. In particular, the paper introduces and discusses in detail the only solution algorithms thus far reported in the open literature for solving the nonpreemptive project completion time minimization problem and the discrete time-cost tradeoff problem with multiple resource constraints. Computational experience is reported for a series of test problems which indicates that the methodology can provide optimal solutionsto small problems'and good heuristic solutions to larger problems in a cost-effective manner. ACKNOWLEDGMENTS This work was supported by a grant from the Graduate School of Business Administration, the University of Michigan, during the Summer of 1979. The author wishes to thank Professor James Patterson, the University of Missouri-Columbia, for reading an -r-~mh; ZIIICIU,, ------- ________ ___ i C-l^~.CI~~~ ---L~rr —r-~I — 1-n~111 —-1 -----

-26 -early draft of this paper and for providing a number of valuable suggestions. The author also extends his appreciation to Professors Roman Slowinski and Jan Weglarz, both of the Technical University of Poznan, Poland, who introduced the author to new approaches for preemptive scheduling which in many ways influenced the current work. _- Gus. ~ ~rsz _ a_ ="I_ _

-27 - REFERENCES [l1] Davis, E.W.; and Heidorn, G.E. "An Algorithm for Optimal Scheduling Under Multiple Resource Constraints." Management Science, 17, no. 12 (August 1971); B-803-816. [2] Elmaghraby, Salah E. Activity Networks: Project Planning and Control by Network Models. New York: John Wiley & Sons, 1977. [3] Patterson, J.H.; and Huber, D. "A Horizon-Varying, Zero-One Approach to Project Scheduling." Management Science 20, no. 6 (February 1974): 990-998. [4] Patterson, J.H-T.; and Roth, G.W. "Scheduling a Project Under Multiple Resource Constraints: A Zero-One Programming Approach.' AIIE Transactions 8, no. 4 (December 1976): 449-455. [5] Pritsker, A.B.; Watters, L.J.;. and Wolfe, P.M. "Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach." Management Science 16, no. 1 (September 1969): 93-108. [6] Slowinski, Roman; "Two Approaches to Problems of Resource Allocation Among Project Activities —A Comparative Study." Preliminary Report, Institute of Control Engineering, Technical University of Poznan (January 1979). [7] Slowinski, R.; "Multiobjective Network Scheduling with Efficient Use of Renewable and Non-renewable Resources." European Journal of Operational Research (to appear). [8] Stinson, Joel; "A Branch and Bound Algorithm for a General Class of Resource-Constrained Scheduling Problems." AIIE Conference Proceedings, Las Vegas, Nevada, (1975), pp. 337-342. [9] Talbot, F.B.; and Patterson, J.H. "An Efficient Integer Programming Algorithm With Network Cuts For Solving Resource-Constrained Scheduling Problems." Management Science 24, no. 11 (July 1978): 1163-1174. [10] Weglarz, J.; Blazewicz, J.; Cellary, W.; and Slowinski, R. "An Automatic Revised Simplex Method for Constrained Resource Network Scheduling." ACM Transaction on Mathematical Software 3, no. 3 (September 1977): 295-300. [11] Weglarz, J. "On Certain Models of Resource Allocation Problems." Kybernetes (to appear).

-28 - Appendix A Ten-job Test Problems The one hundred ten-job time-resource tradeoff problems used to derive Table 2 in this paper are defined on the following pages. The problems were developed by taking all combinations of the ten precedence diagrams labeled P-l through P-10 and the ten time-resource listings labeled R-l through R-10. For example, the computer output illustrates the solution to problem number one (of one hundred) taken by combining P-l with R-1. The precedence diagrams and resource characteristics were created manually to depict a wide variety of project scheduling situations, but they are not intended to be a random sample in any statistically rigorous sense.

-29 - P-1 P-2

I U) 0 I U Ln

-31 - P-7 P-8 P-9 P-10

-32 - R a b c:1 2 '5 2-1 2 I t1i 2 9 I 10 4 4:1. 2 2 8 2 3:1. 4 ) 'I:1.:.3:1. 2 -2:.:t., 12 5 2 '..:1 2. 4:1. 6 2 4 9 2 7:.9 2 6:1.024 1.0:1. 2-' de f gh 4 2:1. 8 5 3:1. 6:1. 5 5 7 o 3 4 0 1 7 3 5 2 0 7:1:1. 3 2 5 2 A 0:f:: ".' 3 6 2 1 j 0 J.::',.1 '., C)..."4:2 2: 4 5 2. 5 5 3 2:f. 6 " —,;6 6 6:.:1.:1. '.3 4 5 0 0 '2:. 5 6.: 0 0 4 2,..-:1.:1. 5:1. A.. 4 i a b c d 1 2 6 5 2 14. A.1 R- 3 2 i 4 1 22 S. 2; "S ",:).6.: 3 4. 6:": 7 2 3 6. 0 " 955:10 1. 2 Al 0 f 2 A*1 7:1.:.. 2 4 0 7 0 ".: 0 3 1 6 0:I3 2 2 0 5 1 3 3:1. 2 4:1..: e f g 5 2.4 231 a::; " 3 2: 1. 5:1. 4 6 0 3 3:1. 3.:. *:...:1.: 1 1 3. 0, 'i." 7 ':-; li S35 4 6 0 0 1 3:1. 26 (02:1.:1 2 56 23 4 a t 3;4 00:1. I 0 02:1 0 0 2 0:1.:1.:1 1 0 0. 0 0 2:1.:1. 0:1.0 0 12:.[ "-': Key-: a- job number b- mode number c- duration d through i are renewable resource requirements (requirements per period) For purposes of Table 2, only resources d through f were used. Y-C ---~~~~~~~~~~~p+- ----- 4DI~~~~~~~~~~~~~~~~

-33 - I. a R-5 -:t.:1. *':.A...3 3 '3 4 4 4 5 5 6 6 A. 7 7 LI L../.. 8 9 10:1.0:10 b c d 3 5 2 4 9 1. 3:1. 0 3 2: "~ *1. 2:1.:1.: 2 33 ~I '26 6 2 3 42 3:-. 5 t 1 '5 1::1.:1. C). 2 2 3 2 '. 2:I. ". ~ ' 2 6 C):1. '3 8 I ' s. 2. i.$ I 4 8? ': ef '-a a::':1 S1 2:1.:1.1.:1. 2 A 0:1. 4:1. C) 0 0 2 3 J. I Ar:1. 3 I) 4 g hi 8 5 5 5 6.. a..:.:,j l.r.. a::'.:. 1::0 5 ) 0 3i. 0 40 2 Z S 5 1.:' '5 1 0:1. 0::1. 0 0 1 0 I:) ~')..- ) 4'?.. 5:1. '.. 4 8 0 2 13 2 2 1.. / 3 2 2 4. }S a R-6:1.:1.:1. 2 '.:: 'I 3 3 4 S 1.. '7 7 '7 t... 1 0.1. 0 b c 5 ' 33 23 '.3 3 6 2 6:I6 34 24.:1. s:1. 3. 1.3 27 C1) 7:'. 2.: '7 1 1 d.~.. 2 C') X.. 2 4 0 1..:1. 2 5 6 7 '.) 0 4 4 5 2 0:1. 1.l 0 e f g hI i 4.:1. 2 q 4 a: 13 r; 0 4' 0 4 a:; 4:1. 0 ' 2 2 4 I3 1. 2 4 1. 13:1. 4:2; ~~1 2 I (3 ' f " C):1: 3 4 7 af a::; 0 /:; ' ) 0 4 13 1 0 4 4 5 0 2 '.3 2:1. 4 0 2t 13:1. 01:i. 1.f 0i:1.:t 0 1I:1. 0 2 3 13 4 Q?.1 ~5:1..4 2 C) 4..... rI,_L_.... —

-34 - ab c d R-7:. 2 4 0:1. 1: 0 2 2 2.1. J. 3 2 4 4:1.:L.: 4 5 2 A 6 6 2 7.. 4 ' 'i 6:1. 3 6 7 2 6 6 7:. 5 6 1 2 4 5 ~.1 3 6 9:1. 4. J:: 2 4... — y1 —2 6 1~.:1.:. 5 4 2 '" 6 6 2:. 4.. "1: 3 A 4::, ":" 5 3 3 S 2 2 3 7 2 4 1 C7:) a::1. 0 2 2 4......:,: efg h i 1~t 4 0) a) 1: 2 1 3 ~~~4 5 4 4 ~4 ** 2 3 2 3:d 'a 2 ~i 4;f'a l I I 5 14 )~5 I a 2-9:1:1.:1. A.. 4 3 d.I 4 '5 6 7 A:! / 7 8 I.1 R-10:. t'lj o~...:..0 1.3 -:::4 4 5 '5 6 6 7 7 8 9:10:10:1.0) b.1.:.1b.1. 4.1.:1. (1.:. 1.1:1.:1.:1:1.:1:1. A:1:i 1 4:1:1. ':1. d e if g h i:1.:. 0:1.:. 0 0: 1.: 1.:1. 0 2:.:1. 2 0:1 1.:1.:1.:L 0: 1. 0 1 0 2. 4:1.::i.:1.,::1.40:1. 4. I.:1..,.. 0 0 04 0:1. Q " (4 1 0 0:1. o 3 3 0..:1. 3' I- ():1. 29.J.'.:4. J. 2 34 "~. ',;. i: '..o::; 6:1. 2:' 0 1:,:1. 1?:;:1.,.:3.2 4 3.5 21;?!: " 5 3 2 1 5 1_ ]

,.CS] 3 I..N 1.3'"1,'lHC.. I,:!" I.1 1- [i...;:'::::-..N 3:):. (N:(i) H J.. i:: N i -:.:.:I JsC)::11 i:1:!: '0:.: IiN f U }..[l" l...3N ' "Iv~i ";NICI:'I)3H...::1 C) H a: y I O.. "J. )N 3 i.... N::(I Nr rii.TsI: N o N.:Jr.. '!"J 0i N C "' C'" '.::t:IH.J.:i:S N f::i:..i l'l ) 3:33 -:1.1. '$3;':): NoC):2)31s ~00()^0;1.:i::) U.1.V iW:i~1 Cf nn::......i: s y "I S:: ~: '.Ef ' s: - O.:I: uc (:C 1:. I.. "'I [C) s3 H.:I.. $3 (1Niovv:33. 1 0..C o.::i ONii ':.1V:iW N4 23L...-::IV 01): ]o.:i f3.f1 I v- I No.r..1.0::; 2.%...ynQ'y xyw SI~~~~~~~~~~~~~:;in 3 I Nn ) 1;:~o:::ia.C J.i:. fI ' '" s::I Il.J.. Ci U: Y:t (1W 3311021::1 'i::':;'"I.....:i: N 3 -1 (;::ia': 3;::1t133'i S 31....3.::I::i;f. ll:(s,-i;.-..:':':.~ [ 't N 3'"t!":,':iii 3l~l... (') NISI).'y."i ['ata(::I n 8: N: i'M N::r;::! N 3 3:i3( Sw >!,.: H )t;oni:t:ifl N:3 tI..I.. 9 "SI No 1 I:. ''!: C T'i1:):" 1:i. 3 I!(:)s I"..:.:: "'1 "-1 I.. I;:I,) I I-... k) *I; 0 0 6 1 C 1'::: ' f.) (: ' " 'C:: (.f ~ ( S f C 'it 0 / 9 t '1: 6 '.:;'~~~~~ t;-;:':: 9 A '".J S. ".:' 0 0 '9: " " ~ 0 -. ~.. A ~, 0 0 ';-.::"'I '!.: I S:;: f.:,.:. 0 0 0 3 ) '1: ` 0 f-;:':':: I 0 "'..:'..F 0 I: NOT1IA~flQ LD3PO~d DN'tZTWINT JWYOdILO fll1: dI:.::,A.......;.V (.' <:;l.A^::|***lq~in.J.,~"' 6 " (t, 01: s: N i.,Id 0 't,.::, C,:..i. '."?yno.:::;':! I;;(::I.(.:;MI- Q~i os H.::! 3003 loa C b....: D T'. '!: (". ', 0 (f:)i'.~~~~( '!: v; '!:; v J e.": 0NOiLLVt~na l'tard: I: 9N~IZIWINIWI' JO0 WZIE[Otdlc,HT U{OJ I,,fcIT~O NI'IIT, IOD RrIcI,',IVXH SE

o I: <:;e ~C 1: ':": 'I: i:) ~~~~~~~~....~,~~~~~~~~~~~~~~~~~~~~~~~VC 'o~ 0 oi 1...... c.... o ~~..s. T C' f C "i~ 9.,".: T 'T ~i.,::,,:.: ~ '.: ~ ~:. T L~~~~~~~~~~~~~~~~~~~~~~~~~~~~~:..,.,. ~ ~S6 (;~': "' ~ff 0 0;': 1....::! 1: 8T61:,.2: 881": S *i: 8,'\.'..; 1I: 8'9 ~~~~~ 9 01:f'":I 9,: 'A -: ', C 1: ~~~~~~~~~~~~~~~~:.. -, o::1 i ' '...~~~~~~A A. ''.: " C, 8'1: 'f...901:.''.:1 r:, E. ~~~~~~~, '": i:.":' S 8:t: S'.".. 8 01: S~ 'S 86/ f:;;', A A x-..: A. *i: E: t;'7:; "I:..... i AA...A xxxr~ 'r:is o o: XX! 6 i5f I.-: = t. v kj: f~:IXXX.........:::.: 1 C!:t:;:: l:!;.: -J 1;1I:. "'~~~ XXXXX^ 9..~ /%./%_________________XXXX ~) 1: ':068/9 6::9* /%/%/%r I..! *i: 'ON a Of *-**** 01: l;I:::l""l..(.:l;..(. ir'taoyd:3Hi yoj ii~ivi-i;:) /\.'%/::...' " " t~', t..' %/ i"N./:~~~~ ~ ~ ~~~~ ~.'.::lI vvxxx I, ~ i~~~..:, /%/'....-.;~~~~~~~~~~~~~~~~~~'- 1:' ~ 1~~ ~~~~~~~~.... '1: ': 0 N:::.'( 0I i" '"'0: t~:;!:,i '"t... IE.L t"t:(:'::,::1: ~lH.~...;:10.:: ~..L;: 1 ~., I"1.... N! ~:? i)!... S ' I I ~I"..t. i

b If~N U J BS ~60 0O S '114130:51 S o "~:::: j.t I,.i..J 1! -....f P ' "4; N 1.,f. '";I;l 4: f i N;!t ': -J*-!.... k.J:I) -.i S "'""*-~^::,: blefi l I.i. tr l *- ' i Ia o -;"~ 5:: ~j J0[: 'I: X 1: ~ i ' '. 1. i t 8 ~ " j: s.S. f.' I. In j.''f.; j1:.;::t: * 'I-' ' * 1 *I,!." ' 1:9 *: 6 i: I..s::I.1, I: I. 1 I- C"-Is'. s ti l f. 9: '.... 9 1; 1:;,:.......I: J..!:,jI..3 3.t t' M;il... '-l; f f..' —: I;:;l:..- f' i -' 8'01"'r -LC