Əsas səhifə
A I I E Transactions Scheduling a Project Under Multiple Resource Constraints: A ZeroOne Programming Approach
Scheduling a Project Under Multiple Resource Constraints: A ZeroOne Programming Approach
Patterson, James H., Roth, Glenn W.Bu kitabı nə dərəcədə bəyəndiniz?
Yüklənmiş faylın keyfiyyəti necədir?
Kitabın keyfiyyətini qiymətləndirə bilmək üçün onu yükləyin
Yüklənmiş faylların keyfiyyəti necədir?
Tom:
8
Dil:
english
Jurnal:
A I I E Transactions
DOI:
10.1080/05695557608975107
Date:
December, 1976
Fayl:
PDF, 608 KB
Sizin teqləriniz:
 Əvvəlcə öz hesabınıza daxil olmağınız xahiş olunur

Kömək lazımdır? Kitabı kindleyə necə göndərməli qısa təlimatını oxumağınız xahiş olunur
15 dəqiqə ərzində epoçtunuz bərpa olunacadır.
15 dəqiqə ərzində Kindle hesabınız bərpa olunacadır.
Qeyd: Kindleyə göndərdiyiniz hər bir kitabı verifikasiya etməlisiniz. Amazon Kindle Supportdan məktub alıbalmadığınıza dair elektron poçt ünvanınızı yoxlayın.
Qeyd: Kindleyə göndərdiyiniz hər bir kitabı verifikasiya etməlisiniz. Amazon Kindle Supportdan məktub alıbalmadığınıza dair elektron poçt ünvanınızı yoxlayın.
Əlaqəli Kitab siyahıları
0 comments
Kitab haqqında rəy bildirə və öz təcrübənizi bölüşə bilərsiniz. Digər oxuculara Sizin oxuduğunuz kitablar haqqında fikrinizi bilmək maraqlıdır. Kitabın ürəyinizcə olubolmamasından asılı olmayaraq, bu barədə dürüst və ətraflı məlumat versəniz, insanlar onlar üçün maraqlı olan yeni kitablar tapa bilərlər.
1

2

This article was downloaded by: [North Carolina State University] On: 11 August 2013, At: 12:06 Publisher: Taylor & Francis Informa Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House, 3741 Mortimer Street, London W1T 3JH, UK A I I E Transactions Publication details, including instructions for authors and subscription information: http://www.tandfonline.com/loi/uiie19 Scheduling a Project Under Multiple Resource Constraints: A ZeroOne Programming Approach a James H. Patterson & Glenn W. Roth a b The Pennsylvania State University, University Park, PA, 16802 b CarnegieMellon University, Pittsburgh, PA, 15213 Published online: 09 Jul 2007. To cite this article: James H. Patterson & Glenn W. Roth (1976) Scheduling a Project Under Multiple Resource Constraints: A ZeroOne Programming Approach, A I I E Transactions, 8:4, 449455, DOI: 10.1080/05695557608975107 To link to this article: http://dx.doi.org/10.1080/05695557608975107 PLEASE SCROLL DOWN FOR ARTICLE Taylor & Francis makes every effort to ensure the accuracy of all the information (the “Content”) contained in the publications on our platform. However, Taylor & Francis, our agents, and our licensors make no representations or warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of the Content. Any opinions and views expressed in this publication are the opinions and views of the authors, and are not the views of or endorsed by Taylor & Francis. The accuracy of the Content should not be relied upon and should be independently verified with primary sources of information. Taylor and Francis shall not be liable for any losses, actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoever or howsoever caused arising directly or indirectly in connection with, in relation to or arising out of the use of the Content. This article may be used for research, teaching, and private study purposes. Any substantial or sys; tematic reproduction, redistribution, reselling, loan, sublicensing, systematic supply, or distribution in any form to anyone is expressly forbidden. Terms & Conditions of access and use can be found at http:// www.tandfonline.com/page/termsandconditions Scheduling a Project Under Multiple Resource Constraints: A ZeroOne Programming Approach JAMES H. PATTERSON The Pennsylvania State University University Park, PA 16802 Downloaded by [North Carolina State University] at 12:06 11 August 2013 GLENN W. ROTH I I CarnegieMellonUmversity Pittsburgh, PA 1521 3 Abstract: An implicit enumeration (zeroone programming) algorithm is described for solving the multipleconstrained resource, project scheduling problem. The algorithm developed takes special advantage of the structure of the zeroone formulation, resulting in a significant decrease in the amount of computation time required t o solve a given multiresource problem. A description of the computer program for implementing the procedures developed is provided, as are detailed computation results. Because the multipleconstrained resource, project scheduling problem subsumes the jobshop scheduling and other related sequencing problems, extensions of our approach to the machine sequencing problem (along with limited computation results) are also reported. Davis [5] , in his second excellent survey paper on constrained project scheduling, notes the lack of computational experience in solving the multiresource, project scheduling problem. With regard to many of the procedures developed for solving the jobshop scheduling problem and which appear as if they can be extended to the multiresource category, Davis notes that: "His procedures have been computer programmed, but no guides as to possible limiting factors are suggested, although promising computational results have been reported for the jobshop type problem" [5, p. 3071 ;"Johnson discussed possible ways of extending his approach to handle the multiresource problem and guessed that the increase in computation time would be less than linear with the added data handling requirements" 15, p. 3081 ; "An approach for multiple resource types was also discussed, but not demonstrated [5, p. 3061 ; "Patton pointed out that his approach could be utilized with slight modifications on the multiresource problem, but that optimal results could not then be guaranteed" (5, p. 3081 ; etc. (Our own italics provided.) We find this lack of attention to the multiresource category of problem puzzling in light of the number of scheduling environments in which resources are dualconstrained (e.g., laborlimited job shops) or are multiconstrained. Perhaps this lack of computational experience Received January 1976; revised May 19'76. December 197 6, AIIE TRANSACTIONS stems from the difficulty in extending approaches for the traditional jobshop problem to the multiresource problem. For example, Balas' disjunctive graph approach for the machine sequencing problem [2] is difficult to extend to the multiresource problem "since there may be more than one unit of each resource available and several activities requiring the same resource may overlap in a feasible schedule. For a given problem with three machine types and five tasks per machine, for example, the number of possible resolutions is 230 (for the machine sequencing problem) and 33 (for the multiresource problem). Thus, there are only (2/3)30, or about 112060 as many possible solutions to the two state (machine sequencing) problem, which gives an indication of added complexity of the combinatorial aspect of the three state (multiresource) problem" [3] . Also, numerous of the partial schedule generation routines (branchandbound variety) exhibit large increases in computation time when generalized to the multiresource category. Davis' general conclusion is that "comparatively little computational experience has been developed with the more promising implicit enumeration techniques on the multiresource category of problem." This, coupled with *The authors would like to acknowledge the helpful comments made by an anonymous referee and by F. Brian Talbot of the University of Michigan in the preparation of this paper. 449 Downloaded by [North Carolina State University] at 12:06 11 August 2013 recent success in solving the assembly line balancing problem (ALB) using implicit enumeration [16], warrants a reexamination of the multiresource problem using implicit enumeration techniques. Among the advantages of the approach are the reduced amount of computer storage required for a given problem size, or a decrease in computer system "resource units" when primary memory is exceeded and auxiliary storage devices must be used. Computation results to date with the implicit enumeration algorithm developed are quite good, often producing solution times which are on the order of twenty times faster than a similar approach which does not take advantage of special problem structures [12]. Extensions of our approach to the machine sequencing problem are equally encouraging. In the next section, the notation used throughout the remainder of the paper and the formulation which we exploit is described. Section three presents the special procedures used in exploiting the structure of the multiresource sequencing problem, and the fourth section describes the computer program written to implement the procedures of section three. We also describe the extensive use made of indexing arrays in limiting computer storage requirements. The next section then gives detailed computational experience with the algorithm in solving multiresource problems, and finally the last section describes extensions of our approach to the jobshop scheduling problem and gives some (albeit limited) computation results for the jobshop problem. In the concluding section, we compare our approach to existing approaches. the one described. This in turn results in a substantial increase in computation time required to solve a given sequencing problem. Thus, variable definition is as important as it relates to the resultant problem structure as it is t o the "size" of the zeroone problem (measured by the number of zeroone variables and/or constraints required). Actually, resulting structure can be much more important than problem size depending upon the availability of special purpose procedures for solving the problem which results. We have chosen to adopt Elmaghraby's variable specification wherein a zeroone variable is used to indicate whether a job (activity) is begun in a specific period. This definition leads to a formulation which is easily exploited in the procedure described, and aids in the indexing procedure used in the solution algorithm. Before describing this formulation we shall make the following general assumptions. First, we assume without loss of generality that the project to be scheduled is represented by the directed. acyclic graph G. G is comprised of N nodes representing jobs (activities) to be scheduled, and P arcs corresponding to precedence relationships between jobs. N and P will denote, respectively, the set of jobs to be scheduled and the set of immediate precedence relationships (m << n) where job n is immediately preceded by job m. We further assume that the unique node with no predecessors is labeled node 1, that the unique node with no successors is labeled node N, and that m << n implies m is less than n. Any acyclic graph can be relabeled or a unique beginning or ending node can be inserted to conform to these assumptions. Definition of Problem Variables and ZeroOne Formulation Definitions Pritsker et al. 1141 suggest that "an efficient formulation [of the sequencing problem] will depend upon a judicious choice of definition for the variables." Several definitions of activity variables which have been used previously include Wiest's [I71 use of a zeroone variable to indicate whether a job is being processed in each scheduling period over the scheduling horizon, Pritsker et al.'s [I41 use of a zeroone variable to indicate whether a job is completed in a specific period, and Elmaghraby's [3, Section 2.11 use of a zeroone variable to indicate whether a job is started in a specific period. Other definitions exist. A "judicious" choice of variable definition will lead to a formulation of the sequencing problem which is readily solvable, whereas an "efficient" formulation may result in the fewest number of zeroone variables or the fewest number of constraints being required to represent a given sequencing problem. The "efficient" formulation may not be the formulation which predicates a solution algorithm yielding minimum computation times. Indeed, it is possible to eliminate the final (or any one other) zeroone variable for each job to be scheduled in the formulation which follows, reducing the number of zeroone variables required by the number of activities in a network. Such variable elimination, however, which appears to result in a more "efficient" formulation, results m a problem structure which is less easily exploited than CP= the critical path length of the project (in time periods, t ) HP = an upper limit on the length of a schedule (usually determined by heuristic means) dj = duration of activity (or job) j ej(Pj)= the earliest (latest) possible period in which activity j can begin (by virtue of activity precedence constraints and due date, HP). ej is the critical path analysis determined early start time Qj = L S q + (HP  CP) where L S q is the critical path analysis determined late start time of activity j JI = { x j t : t = ej, ej + . . . , Pi) denotes the set of 0  1 variables corresponding to feasible start times for activity j nj = number of elements in Ji rjk = per period demand for resource k by activity j Rkt = availability of resource k in period t, t = 1 , 2 , . . . , HP Sj = set of all tasks which immediately succeed (>>) activity j = set of all tasks which immediately precede (<<) activity j 1 if activity j begins in period t Pi Xjt = 0 otherwise. AIIE TRANSACTIONS, Volume 8, No. 4 I C t x ~ t t=e~ x Qj Subject to: Xjt = 1 j = 1,2, . . . ,N (activity t=ej t= em ,+,, 9 QN Minimize: Downloaded by [North Carolina State University] at 12:06 11 August 2013 1 Given the variable definitions described, the formulation of the multiresource sequencing problem becomes: to 0 and underlined. AU nonunderlined variables become free at each improved solution, and the search for a shorter duration solution begins by considering activity start times for activity 1. Because variables are arrayed (hence, considered for augmentation) in the order XI,, , x l e ..., . XlQ,;x2e2, X2e2+19 .. X2Q2;.  .;XNeN' XNeN+I . . XN,, (recall that G is restructured if necessary), feasibility is attained whenever xlvt % is set equal to 1. Restructuring G and backtracking in this manner alleviates the need for a specific test for improvement with the incumbent solution since whenever a variable x ~ is tset to 1, a better (shorter duration) feasible solution has been found. Optimality is then established in the traditional sense of implicit enumeration, whenever the leftmost variable is complemented and underlined [9] . The P precedence constraints exhibit a coefficient structure depicted in Table 1. That is, only two variable sets Jm and Jnhave nonzero coefficients in any one precedence constraint. Further, the coefficients in these constraints are given by a decreasing sequence of negative integers, each differing from its adjacent right occurrence time variable by (2) start constraints) t=e, all (m,n) E P (sequencing constraints) t= 1,2,...,HP (resource constraints) Constraint set (2) insures each activity will be scheduled to begin in one and only in one time period. Constraint set (3) insures precedence restrictions will not be violated, and constraint set (4) insures limitations on resources will not be exceeded during any period of the schedule span. Implementation of constraint (4) requires that we recognize predetermined values of xjq; that is, xiq 0 for q < ej and for q > Qj . Implicit Enumeration Procedure Several steps in the implicit enumeration procedure (Balasian algorithm) can be eliminated or strengthened (in the sense of fathoming a given partial solution) by exploiting the special structure given by (1) through (4). We will now describe these modifications to the implicit enumeration procedure in detail using Geoffrion's [9] notation for the 01 solution procedure. The N activity completion constraints (2) can be treated implicitly by using the following procedure. In the augmentation phase of the algorithm, we set to 0 variables xit Wj, &to, when xjto is set to 1. This insures that at most one xjtWj is set to 1 in any partial solution, and augments nj variables when elevating variable j to 1. (This procedure is similar to that used by Thangavelu and Shetty [16] in their examination of the assembly line balancing problem). In backtracking, all nonunderlined variablesxjtWj become free whenever xjto is underlined and complemented to 0 [9]. Also in backtracking, all variables xlvt to the right of xNt* = 1 (if any exist) are set to 0 and underlined since these variables correspond to schedule durations greater than t q and the (HPt*) rightmost variables in each job s e t 4 are set December 1976, AlIE TRANSACTIONS I I Table 1: Coefficients of variables in each precedence constraint. Predecessor. J , amt <O (negative) I Successor. J, I I ant > 0 (positive) 1 for the predecessor task variables (J,), and are given by an increasing sequence of positive integers, each differing from its adjacent right occurrence time variable by +1 for the successor task variables (J,) in each precedence constraint. Therefore, whenever considering a variable from the set Jn to elevate to 1, a l l variables xnt to the left of xnto, to = rninmEpn {amt : xmt= 11, are set to 0. This insures that the precedence constraints are feasible whenever the variable xnt is set to one, and that explicit examination of the precedence constraints is, therefore, not required. (An alternative to the above procedure would be to set to 0 all variables xnt, n S m , to the left of xnto, to = a m t , whenever xmt is set to 1. This procedure would then be the same as that used by Thangavelu and Shetty [16] . However, often a partial solution is fathomed by establishing there is no feasible completion to the incumbent partial solution because there exists no variable xit Wi, m < i < n , that can be set to 1 due to resource constraint violation. The process of not setting to 0 those variables xnt, n€S,,,, when a variable xmt is set to 1 reduces by about 20% the computation time required to solve the problems quoted in the fifth section over what would be required had this alternative procedure for treating the precedence constraints been invoked.)   With the resource constraints expressed as less than or equal to inequalities, all coefficients representing resource requirements of an activity are positive, as are the resource availabilitiesRkt. The check on resource feasibility forxjt=l involves the simple comparison of rjk with R k t at partial solutions (the latter denoted R i t ) for all k and for all t such that xjt is a free variable and the comparison is made for t, t + l , . . . , t + dj1. The quantity R:, thus denotes the remaining availability of resource k intime period t for assignment to nonscheduled activities. Let the t for whichactivity j is currently being considered to begin be denoted by t b . Then if rjk for k = 1,2,3, . . . ,K and for t = t b , tb+l , . . . , tb+djl, the specification xjtb = 1 is resource feasible and xjtb is set equal to 1. R i t is then decreased by rjk for all k and for allt, tb < t < tb+&1 1f rjk > R i t for any k and Downloaded by [North Carolina State University] at 12:06 11 August 2013 < ~ i ~ any te{tb, tb+l, . . . , tb+djl 1,thenxjtb = 1 is resource infeasible; hence, xjtb must be set equal t o 0 in anyfeasible completion of partial solution s. Let the first t for which rjk > R i t be denoted by tf. Then the search for a feasible set equal to zero. If a schedule of length T is found which is tr periods shorter than the heuristic schedule span HP provided to the 0  1 program, the tr right most variables in each variable set 4 are examined and if not set to 0 and underlined, are set to 0 and underlined. The algorithm then begins with job 1 and a null solution and attempts to find a specification of N activity variables at level 1, with a schedule duration of HP  t, periods or shorter. This "restarting" scheme is equivalent to the one of (12), except that ( I ) a "new" zeroone program is not formulated at each improved solution, and (2) specific advantage is taken of the structure of the zeroone program in reducing the time required for 'Onvergence. Description of the Computer Program for Implementing the Implicit Enumeration Algorithm and Preconditioning Project Data for Input completion to the partial solution can begin with Xjtf+l since the completion with xit = 1 for any t, tb < t < tf, is infeasible. Depending upon the ratio (Qjej)/dj, and the proximity of tb to ei, the process of considering only those activity start time variables xjt to the right of tf can significantly reduce the number of activity start time variables which would otherwise be examined in the enumeration process. An advantage of this particular formulation with the coefficients in the precedence constraints (3) of a successor task given by t = en, en + . . . , 11, is the following. Suppose the sequencing constraints involving task j as a successor activity are examined and all xjt for which t would represent an infeasible completion (considering only the precedence constraints) are set to 0 using the procedure described. Let the leftmost t for which xit could be elevated to 1 without violating the precedence constraints be denoted by t*. Then the only constraints which must be examined for resource feasibility are the K t*  I through the K (t* + dj  1) resource constraints. In general, only those resource constraints numbered K t  1 through K (t + dj  1) need be explicitly examined for resource feasibility, and the numeric value of t is provided by the coefficient ajt of xjt in the precedence constraints. (For the unique task with no predecessors, an auxiliary array is constructed containing the integers 1 , 2 , . . . , 11, indicating the K 11, resource constraints to examine for resource feasibility.) Examining K dj resource constraints for feasibility at each step (as opposed to K HP resource constraints) significantly reduces the amount of computation time required to solve a given problem. The implicit enumeration procedure begins by setting to 0 and underlining the rightmost variable in each activity set Jj. Starting from a null solution, variables xj, are elevated to 1 in sequence (j= 1, 2, . . . ,N) until a variable XNT E JNis set equal to 1 or it is determined there is no feasible solution with the right most activity variable in each variable set ,, A computer program was written in FORTRAN V for the IBM 3701168 computer to implement the procedure described in the previous section within the general framework of implicit enumeration. The program readsin data for each activity delineating activity number, duration, successors, and resource requirements. It then constructs the project network from the activity data provided, and restructures G (if necessary) to conform to the assumptions specified. Resource requirements per activity and resource availabilities are then sorted in decreasing order of work content, where "resource1" has the highest work content, "resource2" has the next highest work content, etc., where resource work content is given by . . . . Sorting and reordering resources by highest work content leads to the discovery of infeasible solutions rapidly since that resource which is highest in demand when compared to availability is considered first in the test for resource feasibility in the augmentation phase of the algorithm. A heuristic schedule span (project length) is then computed using the least total float priority dispatch scheduling rule. From this, ej and Qj are determined for each activity and the activities of G are further relabeled such that if !2j < Rjl, j < jl. While seemingly an inocuous change, it is tantamount to considering activities for elevation to 1 in the order of least total slack time for the activity, a rule which has been found effective elsewhere [7]. The program then constructs constraint sets (3) and (4) in the manner indicated below from the data provided. AIIE TRANSACTIONS, Volume 8, No. 4 Downloaded by [North Carolina State University] at 12:06 11 August 2013 The precedence constraints (3) are basically left intact by our procedure, although it is possible to reduce considerably the amount of storage required in handling these precedence restrictions. The precedence constraints were left intact because the amount of primary storage available was not a limiting factor in our experiments due to a very significant reduction in the amount of storage required to represent resource restrictions. The array containing the precedence coefficients, however, is appended by an array which indicates for each job j, j = 1,2, . . . ,N the numbers of the precedence constraints in which the job (activity) appears as a successor activity, and for such constraints, the beginning location of the negative coefficient for the predecessor task variable. This indexing procedure accelerates the search for to = minm ,pn (amt : xm =l ) so that infeasible precedence completions of activity variables are eliminated from consideration as described. matrix denoting the resource The (KHP) X (~f!= requirements for each activity for each of its scheduled occurrence times t is reduced to a K X HP and a K X N array by the following scheme. Coefficients in the K X HP "resources remaining" array are initialized at their Rkt values. Then, as variables xit are elevated to 1, corresponding resource requirements are subtracted from the availabilities in this K X HP array. Coefficients akt in this array thus represent the remaining availability of resource k in period t at any partial solution. The K X Nresource requirement array stores the resource requirement quantities for each task j, j = 1,2, . . .N for all resources k, k = 1, 2, . . . K. Recall that precedence constraints are examined to determine when activity j canbegin (tb) and not violate precedence restrictions at any partial solution. The variable xitb thus provides the index j to the resource requirements array to determine resource requirements for the variable considered for elevation to 1, and provides the index t b (which is stored in the precedence constraints array) for comparing requirements with availabilities for periods t through t + dj  1. To gauge the savings in computer storage with this procedure, consider the following example taken from one of the problems given in the following section. A 27 activity network with a heuristic schedule span (HP) of 46 time units and involving three resource types is to be scheduled. The total number of job start variables xit is 297. Without the above procedure, it would be necessary to somehow store a (3.46) X 298 or a 41,124 word array in the formulation of the resource constraints [4] .With the indexing procedure described, the array storage for these same constraints is reduced to 246 words. Depending upon the availability of computer primary storage, this savings can be significant. The amount of CPU time required on the IBM 3701168 computer to formulate the problems from the specification of activity data given, determine a heuristic schedule span using the least total float sequencing rule, and setup the indexing arrays for implementing the procedures described, is on the order of 0.6 seconds for those problems described in the following section. December 1976, AIIE TRANSAC~IONS Experimental ResultsMultiResource Problems Twelve problems representing variations of seven different project networks were solved using the described procedure and a comparison was made with solution times required to solve this same set of problems using the HorizonVarying, ZeroOne approach of reference [12]. These problems involve project networks with five to twenty activities, and one to three different resource types per project. As shown in Table 2 the present procedure is approximately twenty times faster on the average in solving these problems than the similar approach which takes no special advantage of problem structure. / Table 2: Computation time required to solve problems from Reference [12]. Problem I HorizonVarying Minimum Bound, Improved Solution Tim@ Procedure Brand, Meyer, & Shaffer 0.762 0.1 37 1.427 0.240 0.710 2.350 0.162 0.413 0.657 0.052 1.591 0.773 Davis, p. 52 Davis, p. 1 14 Davis, p. 200b Moodie & ~andevilleb Martino Shaffer, Ritter, & ~ e y & Average Solution Ti& 0.198 0.006 0.054 0.003 0.014 0.043 0.006 0.029 0.014 0.004 0.043 0.038 QlBM 3701168 CPU time, in seconds. b~ariationsof the problem solved can be found in [I21 . A group of fifty larger problems involving networks with 22 and 27 activities each and three different resource types per problem were then scheduled with the procedure described. These problems are more fully described in [4], [5] , and in [7] , and basically represent the most extensive set of "test" problems generally available. Table 3 gives pertinent scheduling results for these problems using the implicit enumeration algorithm. Table 3:Computation times required to solve problemsof Davis [41. Average . No.of No. of No. of Constraints Solution problems activities No. of Variables in 01formulation in 01formulation tin@ (jobs) 22 n 28 27 209 241 161 175 36.358 23.453 "IBM 3701168 CPU time, in seconds. As shown in Table 3, just under onehalf minute of CPU time (on the average) is required t o solve each of these problems. Also evident from this table is the fact that average solution time is not a function of problem size (as measured by the number of activities to be scheduled or by the resulting zeroone formulation) alone. Indeed, the group of 21 activity networks which in general required the fewer number of zeroone variables and constraints required on the average 55% more CPU time to solve than did the larger 27 activity networks. Thus variables other than problem size alone influence the amount of computation time required to solve a given problem with the enumeration procedure. Taken as a whole, however, the results reported in Table 3 appear quite encouraging for these "larger" problems. I Table 4: Computation times required to solve jobshop scheduling problems with revised procedure. No. of 01 Variables No. of Constraints 1 a) b) 302 577 246 290 0.007 0.010 2 a) b) 657 812 287 307 0.013 0.017 Problem Solution Time 'lBM 370/168 CPU time, in seconds. Downloaded by [North Carolina State University] at 12:06 11 August 2013 Conclusion Extensions to the Machine Sequencing (Job Shop Scheduling) Problem An obvious extension of our approach to jobshop type problems (in which each activity or job demands one unit of one and only one resource and resources are available in one unit amounts) deals with a further refinement for treating the resource constraints. The resource availability matrix is initialized with all elements set equal to 1. The resource requirements array which is 1XN is initialized with the number k of the resource (machine) required by job j, j = 1,2, . . .N. Then, the check for resource feasibility is made by testing whether the kth row of the resource availability matrix contains l's in the locations (columns) t, t+l, . . . ,t + di  1,where t represents a precedence feasible start time for job j . If 1's exist, the assignment is feasible, and the resource availability matrix elements are decrimented accordingly. If di consecutive (1's) do not exist, the assignment xjt = 1 is not feasible, and another variable xito, to > t must be examined for elevation t o 1. A job shop scheduling problem from El 1] consisting of 36 jobs was scheduled using this revised procedure. The problem was setup as a network of activities with the objective of minimizing makespan, or the time required to complete all jobs, and was modified similar to Fischer [8] for these experiments. That is, for problem 1, jobs 5 and 6 and resources 5 and 6 were eliminated, and for problem 2, job 6 and resources 5 and 6 were eliminated. Variations a and b sf these two problems were obtained by ftrst obtaining a heuristic schedule span using the least total float priority discipline (a), and then using the shortest imminent operation discipline (b) found effective in scheduling jobshop activity. These results are summarized in Tablie 4. The largest problem solved (as measured by the number of binary variables required) involved 812 variables and was solved in the maximum time for all problems of 0.017 seconds. These results, although limited, suggest the comparative computational difficulty in solving the multiresource version of this problem, and may account for the lack of computational experience in solving it as noted by Davis. Due to the lack of computational experience in solving multiresource, project duration minimization problems, it is difficult to speculate on the general efficacy of our approach in relation to other known approaches for solving this same class of problems. Because we were able to compare our approach to the HorizonVarying Approach of [12] using the same computer system, we can state that the implicit enumeration procedure described is clearly superior to that procedure for the problems examiped. With regard to Davis' bounded enumeration procedure [4] we are able to say much less regarding the comparative efficacy of our approaches. Davis used a far different computer than the IBM 3701168, his procedure required the use of auxiliary storage, etc., making a meaningful comparison between approaches difficult. We can state that our approach appears to be as fast or possibly faster than Davis' approach for solving similar problems, but can state no more. Perhaps this suggests the need for a "clearinghouse" of test problems and solution procedures so that meaningful comparisons can be made. Computer CPU time in and of itself can often be a misleading indicator of algorithm efficacy. If auxiliary storage devices are required, for example, then system resource units are being tied up and these costs should be accounted for accordingly. Many of the partial schedule generation routines which deal with the statement of the jobshop scheduling or the multiresource problem directly require either computers with massive amounts of central memory or else the use of auxiliary storage devices because of the large number of partial schedules which must be retained. Recent encouraging work by Stinson [IS] on the multiresource version of this problem is indicative of both the rapid solution times (CPU) on selected problems and the large amounts of memory required to implement the branch and bound approach. Any comparison of existing approaches should reflect the costs of the addition resource (memory) units required. We can thus offer the following general remarks regarding the implicit enumeration procedure described. The procedure is a reliable optimization technique for scheduling multipleresource projects involving up to 30 activities. (A "problem generator" is currently under development for testing the procedure on networks involving more than 30 AIIE TRANSACTIONS, Volume 8,No, 4  I I ~ activities, but this information is not currently available.) The procedure appears to be as fast (CPUwise) as other solution approaches for the same category of problem, and offers the advantage over some of the branchandbound approaches for solving related sequencing problems in not requiring excessive amounts of computer storage. For a given computer "size," this could be a very substantial advantage of our approach. And finally, the approach appears to be quite suitable when compared to existing approaches for solving the jobshop version of this sequencing problem when the further refinements introduced are incorporated into the solution procedure. Downloaded by [North Carolina State University] at 12:06 11 August 2013 References Balas, E., "An Additive Algorithm for Solving Linear Programs with ZeroOne Variables," Operations Research, 13 4, pp. 517546 (JulyAugust 1965). Balas, E., "Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm" Operations Research, 17 6 , pp. 941957 (NovemberDecember 1969). Bennington, G. E. and L. F. McGinnis, "A Critique of Project Planning with Constrained Resources," Report No. 81, Operations Research, North Carolina State University at Raleigh (May 15, 1972). Davis, E. W., "An Exact Algorithm for the Multiple ConstrainedResource Project Scheduling Problem," unpublished PhD thesis, Yale University (1969). Davis, E. W., "Project Scheduling Under Resource ConStrii&ts Historical Review and Categorization of Procedures," AZZE Transactions, 5 4, pp. 297313 (December 1973). Davis, E. W. and G. E. Heidorn, "An Algorithm foroptimal Project Scheduling Under Multiple Resource Constraints," Management Science, 17 12, pp. B803816 (August 1971). Davis, E. W. and J. H. Patterson, "A Comparison of Heuristic and Optimum Solutions in ResourceConstrained, Project Scheduling," Management Science, 2'0 8, pp. 944955 (April 1975). Fischer, Marshall L., "Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I," Operations Research, 21 5 , pp. 11141127 (SeptemberOctober 1973). December 1976, AIIE TRANSAC~IONS Geoffrion, A. M., "Integer Programming by Implicit Enumeration and Balas' Method," SZAM Review, 9 2 , pp. 178190 (April 1967). Geoffrion, A. M. and A. B. Nelson, "User's Instructions for 01 Integer Linear Programming Code RIP30C," Memorandum RM5657PT, The RAND Corporation (May 1968). Muth, J. F. and G. L. Thompson, Industrial Scheduling, PrenticeHall, Inc., Englewood Cliffs, New Jersey (1963). Patterson, J. H. and Walter D. Huber, "A HorizoaVarying, ZeroOne Approach to Project Scheduling," Management Science, 20 6, pp. 990998 (February 1974). Patterson, J. H. and Joseph J. Albracht, "Assembly Line Balancing: ZeroOne Programming with Fibonacci Search," Operations Research, 23 1, pp. 166172 (JanuaryFebruary 1975). Pritsker, A. A. B., L. J. Watters, and P. M. Wolfe, "MultiProject Scheduling with Limited Resources: A ZeroOne Programming Approach,"Management Science, 16 4 , pp. 93109 (September 1969). Stinson, Joel P., "A Branch and Bound Algorithm for a General Class of ResourceConstrained Scheduling Problems," Proceedings, 1975 Systems Engineering Conference (AZZE), Las Vegas, Nevada, pp. 337342. Thangavelu, S. R. and C. M. Shetty, "Assembly Line Balancing by 01 Integer Programming," AIZE Transactions, 3 1, pp. 6469 (March 1971). Wiest, J. D., The Scheduling of Large PTojects with Limited Resources, unpublished PhD Thesis, Carnegie Institute of Technology, Pittsburgh, Pa (1963). Dr. James H. Patterson is an Associate Professor of Management Science, Penn State University at University Park. His research interests are in the areas of heuristic and integer programming, sequencing theory, and implicit enumeration. He holds a BS degree from the University of Colorado and a DBA from Indiana University. Dr. Patterson is a member of TIMS, ORSA, and AAAS. Mr. Roth holds a BS degree (with honors) from Penn State University, and is currently a candidate for the MSIA degree at CarnegieMellon University. Mr. Roth's research interests are in the general areas of production planning and control, with emphasis on the financial aspects of production planning (constrained optimization). 455