UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Solution for a class of combinatorial problems with emphasis on project sequencing in water resources… Tsou, C. Anthony 1972

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1972_A1 T86.pdf [ 5.5MB ]
Metadata
JSON: 831-1.0050547.json
JSON-LD: 831-1.0050547-ld.json
RDF/XML (Pretty): 831-1.0050547-rdf.xml
RDF/JSON: 831-1.0050547-rdf.json
Turtle: 831-1.0050547-turtle.txt
N-Triples: 831-1.0050547-rdf-ntriples.txt
Original Record: 831-1.0050547-source.json
Full Text
831-1.0050547-fulltext.txt
Citation
831-1.0050547.ris

Full Text

SOLUTION FOR A CLASS OF COMBINATORIAL PROBLEMS WITH EMPHASIS ON PROJECT SEQUENCING IN WATER RESOURCES PLANNING by C. ANTHONY TSOU B.A., Oxford U n i v e r s i t y , 1967 M.A., Oxford U n i v e r s i t y , 1971 M.A.Sc, U n i v e r s i t y of B r i t i s h Columbia, 1970 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY i n the Department of C i v i l Engineering We accept t h i s t h e s i s as conforming to the re q u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA A p r i l , 1972 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make i t freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the Head of my Department or by his representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of C i v i l Engineering The University of British Columbia Vancouver 8, Canada Date 9 March 1972 A B S T R A C T An algorithm i s presented to obtain the optimal permutation for a class of combinatorial optimization problems. Included i n the class of problems dealt with are the following: project construction sequenc-ing, the minimum tardiness job scheduling, and several sequential search and t e s t i n g problems. The algorithm i s based on a simple necessary con-d i t i o n for an optimal permutation incorporated i n t o a Branch-and-Bound s o l u t i o n method. In many cases, optimal permutations can be obtained, with very l i t t l e computational e f f o r t , by using only the necessary condition of op t i m a l i t y . For more complex problems, t h i s condition i s u t i l i z e d i n both branching and bounding operations, r e s u l t i n g i n a powerful mechanism to eliminate subsets of solutions from optimal permutation consideration. Optimization techniques for use i n water resources planning, where a series of developments w i l l be required to meet a growing demand, "should not only be e f f i c i e n t i n f i n d i n g the optimal s o l u t i o n but also o f f e r means to perform s e n s i t i v i t y a n a l y s i s . An approach is proposed i n t h i s thesis which w i l l not only i d e n t i f y the project that i s most l i k e l y to be the f i r s t element i n the optimal construction sequence, but also allow estimates to be made of the amount by which the cost of any other project would have to be changed before i t ' could occupy the f i r s t p o s i t i o n i i H i i n the o p t i m a l sequence. A combination of the methods f o r f i n d i n g the o p t i m a l sequence and the s e n s i t i v i t y a n a l y s i s r e p r e s e n t s a " p l a n n i n g t o o l " which should provide an o p p o r t u n i t y f o r an e f f e c t i v e p l a n n i n g s t r a t e g y which can be used i n many d i f f e r e n t s i t u a t i o n s . TABLE OF CONTENTS Page LIST OF TABLES • v i LIST OF FIGURES v i i CHAPTER 1. INTRODUCTION 1 2. GENERAL FORMULATION 5 3. PROJECT CONSTRUCTION SEQUENCING PROBLEM 15 3.1 N o t a t i o n • 16 3.2 O b j e c t i v e F u n c t i o n 17 3.3 Necessary C o n d i t i o n of O p t i m a l i t y 18 3.4 S u f f i c i e n t C o n d i t i o n of O p t i m a l i t y 19 3.5 Decomposition Theorem 24 3.6 P r e f e r e n c e M a t r i x 27 3.7 Stages and Nodes. 31 3.8 L o c a l Optimal Sequence 31 3.9 E l i m i n a t i o n Check 35 3.10 Upper Bound of the Optimal S o l u t i o n 38 3.11 Lower Bound Sequence and Lower Bound 39 3.12 Flow Chart 42 4. EXAMPLES OF THE PROJECT CONSTRUCTION SEQUENCING PROBLEM . . 44 4.1 Four P r o j e c t Sequencing Problem 44 4.2 Ten P r o j e c t Sequencing Problem 46 5. USE OF THE ALGORITHM IN WATER RESOURCES PLANNING 53 6. SCHEDULING AND SEQUENTIAL SEARCH PROBLEMS 58 6.1 Least Cost T e s t i n g Sequencing Problem 58 6.2 S e q u e n t i a l Search and T e s t i n g 60 6.3 P r o d u c t i o n Scheduling 62 iv V Page SUMMARY 72 REFERENCES 73 APPENDICES . . . . . . . . 76 Appendix A: Computer Programme L i s t i n g 77 Appendix B: Solution of the Four Project Sequencing Problem 100 LIST OF TABLES Table Page 1. S u f f i c i e n t C o n d i t i o n s of Optimal Permutation 24 2. P r e f e r e n c e M a t r i x f o r Four P r o j e c t Problem 29 3. P r e f e r e n c e M a t r i x f o r Subset of Four P r o j e c t Problem With P r o j e c t C F i r s t 3 0 v i LIST OF FIGURES F i g u r e Page 1. Flow Chart f o r the General A l g o r i t h m 14 2. Complete Tree Branches f o r Four P r o j e c t s 32 3. P r o j e c t Sequencing Problem — Flow Chart 43 4. I l l u s t r a t i o n of P r o j e c t Sequencing Procedure With Four P r o j e c t s 45 5. P r o j e c t Sequencing — Ten P r o j e c t s — Case I I 48 6. P r o j e c t Sequencing — Ten P r o j e c t s — Case I I I 51 7. Job Scheduling Example 69 v i i ACKNOWLEDGEMENT The author i s deeply g r a t e f u l to P r o f e s s o r L. G. M i t t e n whose guidance and teaching i n the past three years are i n v a l u a b l e . The author a l s o wishes to thank P r o f e s s o r S. 0. R u s s e l l f o r h i s guidance and encouragement d u r i n g the development of t h i s t h e s i s . T h i s study was supported by grants from the Ford Foundation and C e n t r a l Mortgage and Housing C o r p o r a t i o n . The author expresses h i s a p p r e c i a t i o n f o r t h e i r a s s i s t a n c e . v i i i CHAPTER 1 INTRODUCTION In the f i e l d of water r e s o u r c e s , planners and engineers a r e o f t e n faced w i t h the ta s k of e v a l u a t i n g a l a r g e number of a l t e r n a t i v e develop-ment plans and s e l e c t i n g the best scheme. For example, i n order t o meet a growing demand f o r e l e c t r i c energy or water s u p p l y , a s e r i e s o f developments may be r e q u i r e d which c o u l d i n v o l v e a number of engineer-i n g p r o j e c t s . The sequence i n which the p r o j e c t s are c o n s t r u c t e d are o f t e n based, at l e a s t i n the p r e l i m i n a r y a n a l y s i s , on a minimum present worth c o s t c r i t e r i o n . S e l e c t i o n of an o p t i m a l sequence a c c o r d i n g t o t h i s c r i t e r i o n w i l l be i n f l u e n c e d mainly by the f o l l o w i n g f a c t o r s : shape of the p r o j e c t e d f u t u r e demand curve, the dis c o u n t r a t e , r e l a t i v e c o s t s and output c a p a c i t i e s of these p r o j e c t s . To o b t a i n such an o p t i m a l p r o j e c t c o n s t r u c t i o n sequence one might eval u a t e the present worth c o s t s of a l l the p o s s i b l e sequences and then choose the cheapest one. T o t a l enumeration i s c o n c e i v a b l e f o r v e r y simple cases when there are on l y a few choices a v a i l a b l e f o r e v a l u a t i o n s . However, even f o r a moderate s i z e problem i n v o l v i n g 10 f e a s i b l e p r o j e c t s , there are 3,628,800 d i s -t i n c t sequences i n which they could be c o n s t r u c t e d . When such v a s t num-ber of a l t e r n a t i v e s are i n v o l v e d , i t i s not p o s s i b l e , without some e f f i -c i e n t a n a l y t i c a l s c r e e n i n g mechanism, f o r the planners to enumerate a l l the p o s s i b l e schemes even w i t h the a i d of modern h i g h speed d i g i t a l computers. 1 2 Although the prime concern of planners i s undoubtedly the immediate a c t i o n s which must be taken i n order to meet the growing demand, a charac-t e r i s t i c of water resources p l a n n i n g i s the n e c e s s i t y to c o n s i d e r a l o n g p l a n n i n g h o r i z o n , u s u a l l y of at l e a s t 20 or 30 y e a r s . T h i s i s because water resources p r o j e c t s normally have a l o n g l i f e and d u r i n g t h i s p e r i o d , economical, s o c i a l , p h y s i c a l and t e c h n o l o g i c a l changes are bound to occur. With a l o n g p l a n n i n g h o r i z o n i t would be p o s s i b l e to p r o v i d e o p t i o n s to accommodate such changes. Hence, to i n i t i a t e the f i r s t p r o j e c t i n a s e r -i e s of developments, planners must be reasonably sure t h a t i t does not c o n t r a d i c t the o b j e c t i v e s of the e n t i r e p l a n n i n g h o r i z o n . I n order t o reach a sound d e c i s i o n about the f i r s t p r o j e c t i n a s e r i e s of develop-ments one approach would be to o b t a i n d e t a i l e d i n f o r m a t i o n on a l l the p r o j e c t s and then to proceed w i t h the a n a l y s i s u s i n g these d a t a . T h i s of course would be h i g h l y d e s i r a b l e but r a t h e r u n p r a c t i c a l , s i n c e data a c q u i s i t i o n f o r water resources engineering p r o j e c t s i s very expensive and time consuming, w h i l e resources a v a i l a b l e f o r p l a n n i n g and design are u s u a l l y inadequate. Thus the amount of e f f o r t devoted to data a c q u i -s i t i o n , study and design of a p r o j e c t should be approximately p r o p o r t i o n -a l to the p r o b a b i l i t y of i t s being the f i r s t p r o j e c t i n a s e r i e s of develop-ments. One of the major d i f f i c u l t i e s i n water resources p l a n n i n g i s the need to e v a l u a t e a l a r g e number of a l t e r n a t i v e s and to determine, w i t h l i m i t e d r e s o u r c e s , a prudent course of immediate a c t i o n i n accordance w i t h the l o n g term o b j e c t i v e . As a step i n the development of s c i e n t i f i c d e c i s i o n methods f o r use i n the water resources p l a n n i n g p r o c e s s , t h i s t h e s i s presents an a l g o r i t h m 3 to o b t a i n the optimal p r o j e c t c o n s t r u c t i o n sequence based on a minimum discounted cost c r i t e r i o n . I t a l s o suggests a procedure f o r e l i m i n a t i n g p r o j e c t s i n a stepwise manner, thus p r o v i d i n g a r a t i o n a l way t o a l l o c a t e l i m i t e d c a p i t a l and t e c h n i c a l resources to each f e a s i b l e p r o j e c t i n p r o -p o r t i o n to i t s l i k e l i h o o d of bein g the f i r s t p r o j e c t i n a s e r i e s of deve-lopments . The computational d i f f i c u l t y i n obt i n i n g an o p t i m a l p r o j e c t con-s t r u c t i o n sequence i s mainly due to the v a s t number of p o s s i b l e permuta-t i o n s . This i s i n f a c t c h a r a c t e r i s t i c of c o m b i n a t o r i a l o p t i m i z a t i o n prob-lems which are n o t o r i o u s l y d i f f i c u l t t o s o l v e e f f i c i e n t l y . H i s t o r i c a l l y the f i r s t c o m b i n a t o r i a l o p t i m i z a t i o n problem was probably r a i s e d i n 1934 by H a s s l e r Whitney i n a seminar a t P r i n c e t o n U n i v e r s i t y . T h i s i s the now w e l l known " T r a v e l l i n g Salesman Problem," which i s to f i n d the s h o r t e s t (or cheapest) route f o r a t r a v e l l i n g salesman who has to v i s i t each of the N c i t i e s once, s t a r t i n g and ending a t c i t y 1. This problem has been under i n t e n s i v e i n v e s t i g a t i o n f o r a couple of decades and many approaches have been suggested, but t o date r.o s a t i s f a c t o r y method has yet been found when a l a r g e number of c i t i e s are i n v o l v e d . I n the f i e l d of I n d u s t r i a l E n g i n e e r i n g , problems known as produc-t i o n s c h e d u l i n g ( to minimize p r o d u c t i o n delays or machine completion time) and s e q u e n t i a l search and t e s t i n g ( to minimize the cost or time r e q u i r e d t o c a r r y out t e s t s t o l o c a t e f a u l t y components when complicated machinery breakdown occurs) are o f t e n encountered. E f f i c i e n t s o l u t i o n procedures have been obtained f o r t h i s k i n d of c o m b i n a t o r i a l o p t i m i z a t i o n problem, but no ge n e r a l f o r m u l a t i o n has y e t been proposed. Although the prime ob-4 j e c t i v e of t h i s t h e s i s i s to d e v i s e a method f o r use i n water resources p l a n n i n g , s i n c e the p r o j e c t c o n s t r u c t i o n sequencing problem i s r a t h e r s i m i l a r t o those problems i n I n d u s t r i a l E n g i n e e r i n g , a g e n e r a l formula-t i o n i s presented f o r f i n d i n g a permutation which minimizes an o b j e c t i v e f u n c t i o n of a s p e c i f i e d form. I t i s then shown that the p r o j e c t c o n s t r u c -t i o n sequencing problem i s a s p e c i a l case i n t h i s c l a s s of c o m b i n a t o r i a l o p t i m i z a t i o n problem. As such i t possesses some unique p r o p e r t i e s , which can be u t i l i z e d to develop an even more e f f i c i e n t s o l u t i o n procedure than t h a t proposed i n the gen e r a l f o r m u l a t i o n . I n the f o l l o w i n g chapters the g e n e r a l f o r m u l a t i o n i s f i r s t i n t r o -duced and then the s p e c i a l case o f the p r o j e c t c o n s t r u c t i o n sequencing problem i s given i n Chapter 3, some examples of which are presented i n Chapter 4. Chapter 5 cont a i n s suggestions f o r i n c o r p o r a t i n g t h i s t e c h -nique and i t s extensions i n a water resources p l a n n i n g p r o c e s s , and a p p l i -c a t i o n s of the g e n e r a l f o r m u l a t i o n to p r o d u c t i o n s c h e d u l i n g and s e q u e n t i a l search and t e s t i n g problems are presented i n Chapter 6. CHAPTER 2 GENERAL FORMULATION The gen e r a l f o r m u l a t i o n of a method f o r s o l v i n g a c l a s s of com-b i n a t o r i a l o p t i m i z a t i o n problems i s developed i n t h i s c hapter. The f o l l o w i n g n o t a t i o n i s used: a : a f i n i t e unordered s e t c o n t a i n i n g a l l the elements under i n v e s t i g a t i o n . P : a set of a l l permutations o f the elements i n a. : a subset of 0. P. : a s e t of a l l permutations of the elements of any non-empty set o*^ . P^, P^ etc are used to denote elements of P^. P^(j<k) : two d i s t i n c t elements j and k i n a permutation P^, where j e 0^ and k e o\ , i n which j immediately precedes k. P Q : a v o i d permutation, i . e . the permutation c o n t a i n i n g no element. I t i s assumed, f o r convenience, that P q i s the s o l e element of the set P^ when = 0. P. ( P . , P „ ) : the combination of two permutations P. e P. and P. e P. k v i ' y i ~ i j ~ j w i t h P ± f o l l o w e d by P ^ . : a subset of C^. I t co n t a i n s a l l the elements preceding the element j i n a permutation P^. P : a permutation of a l l the elements i n subset a ^ j • Hence 5 6 P = ( P , , j , P. ) . I f j i s the f i r s t element i n P then P = P o 2.1 O b j e c t i v e F u n c t i o n : A s s o c i a t e d w i t h each P^, there e x i s t s a r e a l v a l u e d f u n c t i o n C(P ) , such t h a t where i s a s p e c i f i e d p o s i t i v e r e a l v a l u e d f u n c t i o n f o r each j e a^. C(P^) may be considered as the c o s t of c a r r y i n g out a s e t of a c t i v i t i e s i n the order s p e c i f i e d by the permutation P^. For example, i n the p r o j e c t c o n s t r u c t i o n sequencing problem C(P^) i s the discounted c o s t of c o n s t r u c t i o n of those p r o j e c t s i n the se t where the order of c o n s t r u c t i o n i s s p e c i f i e d by the pe r -mutation P^. The o b j e c t i v e i n t h i s c l a s s of c o m b i n a t o r i a l o p t i m i z a t i o n problem i s to f i n d an o p t i m a l permutation P*, such t h a t (E2.1) C(P*) = min C(P) PEP ( E 2 . 2 ) 7 2.2 Branch-and-Bound Procedure; The Branch-and-Bound technique was developed i n the e a r l y 1960's and s i n c e then i t has proven a very u s e f u l method f o r s o l v i n g combina-t o r i a l o p t i m i z a t i o n problems. I t has been a p p l i e d to a v a r i e t y of im-por t a n t o p t i m i z a t i o n problems such as Integer Programming (1,2,3,4,5), n o n - l i n e a r assignment problems (6,7,8), s c h e d u l i n g problems (9,10,11), the t r a v e l l i n g salesman problem (12) , network problems (13) , the knap-sack problem (14), p l a n t l o c a t i o n problem (15), e t c . B a s i c a l l y , the Branch-and-Bound technique i n v o l v e s two o p e r a t i o n s : (a) Branching: which i s to d i v i d e the s o l u t i o n s e t i n t o a number of subsets; and (b) Bounding: which i s to e s t a b l i s h bounds on the va l u e of the o b j e c t i v e f u n c t i o n over the subsets of s o l u t i o n s . For example, i n a m i n i m i z a t i o n problem i f the lower bound a s s o c i a t e d w i t h a p a r t i c u l a r subset of s o l u t i o n s exceeds the upper bound of the o b j e c t i v e f u n c t i o n (which can be the best s o l u t i o n found so f a r ) , then that subset can be di s c a r d e d and need be gi v e n no f u r t h e r c o n s i d e r a t i o n i n the search f o r an o p t i m a l s o l u t i o n . The proof of t h i s s u f f i c i e n t c o n d i t i o n f o r e x c l u s i o n of sub-s e t s of s o l u t i o n s f o r o p t i m a l s o l u t i o n c o n s i d e r a t i o n i s q u i t e s t r a i g h t -forward as f o l l o w s : For any permutation P^, P^ e and a, l e t b^ be the lower bound of the values of sub-sequence P^, and B be an upper bound of the o b j e c t i v e f u n c t i o n . 8 C(P ) > b 4 (by d e f i n i t i o n of lower bound) and B > C(P*) (by d e f i n i t i o n of upper bound) Hence i f bj > B (C2.1) then C ( P ± ) > b± > B >_ C(P*) Since f u n c t i o n g i n Eq.(E2.1) i s non-negative, • • c ( p k > i l c < p i > > c< p*> where C ( P k ) - ( P i , P j ) (E2.3) Thus, when c o n d i t i o n (C2.1) i s s a t i s f i e d , P^ can not be a sub-sequence i n the o p t i m a l permutation P*. Therefore a l l subsets of s o l u t i o n s i n the form of Eq.(E2.3) can be excluded from f u r t h e r c o n s i d e r a t i o n s i n the search f o r the o p t i m a l s o l u t i o n . S u c c e s s f u l a p p l i c a t i o n s of the Branch-and-Bound technique to the s o l u t i o n of c o m b i n a t o r i a l o p t i m i z a t i o n problems depend mainly upon how e f f i c i e n t l y subsets of s o l u t i o n s can be d i s c a r d e d 9 from f u r t h e r c o n s i d e r a t i o n . T r a d i t i o n a l l y , the a r t i n u s i n g the Branch-and-Bound s o l u t i o n technique l i e s i n the development of e f f e c t i v e means f o r determining " t i g h t " bound v a l u e s such t h a t by comparisons of bound values, most subsets can be e l i m i n a t e d and o n l y a s m a l l p r o p o r t i o n of subsets of s o l u t i o n s need be r e -t a i n e d f o r f u r t h e r i n v e s t i g a t i o n . The s o l u t i o n method presented i n t h i s t h e s i s f o r the c l a s s 'of c o m b i n a t o r i a l o p t i m i z a t i o n problems s p e c i f i e d i n s e c t i o n 2.1 i s based on a m o d i f i e d Branch-and-Bound technique, where a second c o n d i t i o n f o r e x c l u s i o n of subsets of s o l u t i o n s i s o b t a i n e d by a p e r t u r b a t i o n c o n s i d e r a t i o n of two adjacent elements i n a permutation. I t w i l l be shown i n l a t e r chapters t h a t t h i s necessary c o n d i t i o n of o p t i m a l i t y r e p r e s e n t s an extremely powerful mechanism f o r d i s c a r d i n g a great number of subsets from f u r t h e r c o n s i d e r a t i o n , thus markedly enhancing the e f f e c t i v e n e s s of the Branch-and-Bound s o l u t i o n method. 2.3 Necessary C o n d i t i o n of O p t i m a l i t y by P e r t u r b a t i o n : T h i s c o n d i t i o n i s based on a p e r t u r b a t i o n of a permutation by i n t e r c h a n g i n g the order of two adjacent elements. The c o n d i t i o n i s s t a t e d i n the f o l l o w i n g theorem. Theorem 2.1 For P ± - ( P i j , j , k, P m ) and Pi - ( P j k , k, j , ) m where °ij = a i k and P m - P* m m A necessary c o n d i t i o n f o r permutation P^ to be e l i g i b l e f o r o p t i m a l s o l u t i o n c o n s i d e r a t i o n i s : Gj( 0 ± j . k ) < Gk( 0 ± 1 , J ) (C2.2) where G ( a , v ) = g ( a ) - g ( a , v ) u w ° u w °u w (E2.4) Proof: C C P ^ 1 S n ( ° i n > (by d e f i n i t i o n of Eq.E2, and P ± » ( P , j , k , P m ) C(P.) - C ( P ± J ) +g J(o 1 J) + 8 ^ ) + S i m i l a r l y , C(Pi) - C(P i k) + g k(a i k) + 8 ^ 0 ^ ) + . . . . . . * i j * i k C(Pj) - C ( P ± ) " { «k<°ik> + « j < ° i J ) } " { W + gk (V } - ( S ^ a y ) + gjCa^ , k) y - { g ^ . ) + , j ) > • { 8 k ( o i j > - s k ^ i j • J) > " | g j ^ ) - g / a ^ , k) } = G k ( a i j , i) - G.io±i , k) °k ( aij ' j ) > Gj (°ij ' k * ( b y h y P o t h e s i s ^ . . C(P[) > C(P ±) 12 Therefore P^ can not be a sub-sequence i n the o p t i m a l permuta-t i o n P* , and, as c l a i m e d , P^ ^ i s then e l i g i b l e f o r o p t i m a l s o l u t i o n c o n s i d e r a t i o n . A g e n e r a l a l g o r i t h m f o r s o l v i n g the c l a s s of c o m b i n a t o r i a l o p t i -m i z a t i o n problems d e f i n e d by Eqs. 2.1 and 2.2 i s presented i n the next s e c t i o n . This a l g o r i t h m i s a m o d i f i e d Branch-and-Bound technique, as i t not only uses the bounding c o n d i t i o n C2.1 to exclude subsets, but a l s o u t i l i z e s theorem 2.1 to d i s c a r d a l a r g e number of s u b s e t s . 2.4 The General A l g o r i t h m : The steps i n the g e n e r a l a l g o r i t h m are g i v e n below and i l l u s t r a t e d by the f l o w c h a r t i n F i g . l . Step 0 : I n i t i a l i z a t i o n . Step 1 : Branch - choose a p a r t i a l permutation from the c u r r e n t set of s o l u t i o n s and add one more element to i t . Step 2 : Test f o r o p t i m a l i t y - determine i f the new p a r t i a l permutation meets c o n d i t i o n C2.2. Step 3 : Bound computation - compute upper bound of the o b j e c t i v e f u n c t i o n and lower bound a s s o c i a t e d w i t h the new p a r t i a l permutation. Step 4 : Bound check - determine i f the bounds s a t i s f y c o n d i t i o n 2.1. 13 Step 5 : Stop check - determine whether an o p t i m a l s o l u t i o n has been o b t a i n e d . The a l g o r i t h m presented above i s g e n e r a l and the a c t u a l branching (step 1) and bounding (step 3) o p e r a t i o n s are not d e t a i l e d here, but are presented f o r the more s p e c i f i c problems i n v e s t i g a t e d i n l a t e r c h a p t e r s . The necessary c o n d i t i o n of o p t i m a l i t y by p e r t u r -b a t i o n c o n s i d e r a t i o n C2.2 i s o f t e n s u f f i c i e n t , by i t s e l f , to determine the o p t i m a l permutation, e.g. i n s e q u e n t i a l search and t e s t i n g problems. In more complicated problems of p r o j e c t c o n s t r u c t i o n sequencing, c o n d i t i o n C2.2 i s employed i n both branching and bounding o p e r a t i o n s as shown i n the next chapter. 14 o < Data Input I n i t i a l i z a t i o n V Branching V \ Yes ( Compute Upper 4 Lower Bounds <0 < V Discard This Subset Of Solutions F I G U R E 1 F L O W C H A R T F O R T H E G E N E R A L A L G O R I T H M CHAPTER 3 PROJECT CONSTRUCTION SEQUENCING PROBLEM In 1969 Butcher, Haimes and H a l l ( 1 6 ) suggested a Dynamic Programming a l g o r i t h m to f i n d an o p t i m a l sequence f o r the c o n s t r u c t i o n of p r o j e c t s to meet a growing demand based on a minimum discounted c o s t c r i t e r i o n . R e c e n t l y Morin and Esogbue(17) proposed another Dynamic Programming approach which b a s i c a l l y f o l l o w e d the f o r m u l a t i o n by Butcher e t a l , but w i t h m o d i f i c a t i o n s to reduce computational and storage requirements. I n both a l g o r i t h m s the d e c i s i o n v a r i a b l e f o r any s t a t e depends not o n l y on that s t a t e but a l s o on how t h a t s t a t e i s reached, namely i t i s c o n d i t i o n e d upon previous d e c i s i o n s . Dynamic Programming a l g o r i t h m s based on such f o r m u l a t i o n s can not i n g e n e r a l guarantee g l o b a l o p t i m a l s o l u t i o n s . Furthermore, even f o r a c o r r e c t l y formulated Dynamic Prog-ramming a l g o r i t h m the computational e f f o r t i s u s a u l l y q u i t e c o n s i d e -r a b l e and the o p t i m a l s o l u t i o n can not be obtained r e a d i l y under any circumstances. In c o n t r a s t the s o l u t i o n method proposed i n t h i s t h e s i s guarantees the convergence to the g l o b a l o p t i m a l s o l u t i o n and o f t e n i t enables the o p t i m a l permutation to be obtained immediately w i t h v e r y l i t t l e c omputational e f f o r t . A l s o i t i s b e l i e v e d that t h i s s o l u t i o n procedure lends i t s e l f e a s i l y to i n c o r p o r a t i o n i n a p l a n n i n g p r o c e s s . 15 16 3.1 N o t a t i o n : X ( t ) : p r o j e c t e d f u t u r e demand, a s i n g l e valued monotone i n c r e a s i n g p o s i t i v e f u n c t i o n w i t h X(t=0.0) = 0.0 t ( X ) : time, the i n v e r s e of the demand f u n c t i o n . Hence t ( X ) i s a l s o a s i n g l e valued monotone i n c r e a s i n g p o s i t i v e f u n c t i o n w i t h t(X=0.0) = 0.0 : estimated c o s t of p r o j e c t i X J L : output c a p a c i t y of p r o j e c t i a : 1.0 + I , where I i s the d i s c o u n t r a t e Y£ : aggragated output c a p a c i t i e s of a l l the p r o j e c t s i n se t a^, i . e . Y ± - L X j Z(a^j) : aggregated output c a p a c i t y of a l l the p r o j e c t s preceding p r o j e c t j i n a permutation P.^ . Z(a^) = 0.0 i f j i s the f i r s t element i n permutation P^ C(A,P^) : discounted c o s t of a sequence i n the order s p e c i f i e d by the permutation P^ when the f i r s t p r o j e c t i n t h i s sequence i s c o n s t r u c t e d w i t h a time d e l a y of t(A) where A > 0.0 17 3.2 O b j e c t i v e F u n c t i o n ; The o p t i m a l permutation P* i n the p r o j e c t c o n s t r u c t i o n sequencing problem i s d e f i n e d a s : C ( A» P*>A=0.0 = £ J C ( A' P )A=0.0 w i t h CCA.Pi) = C k l • f (A) + C k 2 • f (A+x k l) + + • f { A + Z ( O i k n ) } Z C k, • f{A+Z(o ± i)} where f ( y ) = a - t ^ y ) , a monotone decreasing p o s i t i v e f u n c t i o n w i t h f(y=0.0) = 1.0 By comparison w i t h Eq.2.1 i t can be seen t h a t the o b j e c t i v e f u n c t i o n of the p r o j e c t c o n s t r u c t i o n sequencing problem has the same form as t h a t s p e c i f i e d i n the ge n e r a l f o r m u l a t i o n , i . e . 8n(<W ' C n ' f{A+Z(0 m n)} (E3.1) 18 3.3 N e c e s s a r y C o n d i t i o n o f O p t i m a l i t y ; S i n c e t h e o b j e c t i v e f u n c t i o n o f t h e p r o j e c t c o n s t r u c t i o n s e q u e n c i n g p r o b l e m has t h e same fo r m as s p e c i f i e d by E q , 2.1, t h e n e c e s s a r y c o n d i t i o n o f o p t i m a l i t y C2.2 i s , o f c o u r s e , a p p l i c a b l e and i t c a n be w r i t t e n i n t h e f o l l o w i n g e x p r e s s i o n by s u b s t i t u t i n g E3.1 i n C2.2: S i n c e f i s a monotone d e c r e a s i n g p o s i t i v e f u n c t i o n , t h e r e f o r e Cj • f{A+z(a±j)} + C k • fU+zCa^j)} < C k • f{A+Z(ai:j)} + Cj • f{A+Z(ai;j,k)} (C3.1) Cj • { f(A+Z(a±j)) - f(A+Zfaij.k)) } < c k • {f(A+z(a±1)) - f(A+z(a i,,j)) } < 1 - f{A+z(ai.i,j)> f (A+ZCo-ij)} 1 f(A+Z(aij,k)} f U + Z (oY.)i i . e . RjCA+ZCOi,)} < R k(A+Z (0 i . ) } (C3.2) 19 where C n . R n ( y ) = (E3.2) f ( y + x n ) 1 f ( y ) E x p r e s s i o n C3.2 i s the necessary c o n d i t i o n f o r an o p t i m a l permutation i n the p r o j e c t c o n s t r u c t i o n sequencing problem. R e c a l l t h a t P A - ( P i : j , j , k , P m ) t h e r e f o r e , i n order f o r t h i s p a r t i a l sequence P^ to be e l i g i b l e f o r o p t i m a l s o l u t i o n c o n s i d e r a t i o n , i . e . p r o j e c t j immediately pre c e d i n g p r o j e c t k a t demand 1 e v e l of A+Z(o^j), c o n d i t i o n C3.2 must be s a t i s f i e d . Note t h a t the e x p r e s s i o n R d e f i n e d by Eq.3.2 f o r any . p r o j e c t depends o n l y on the constants a s s o c i a t e d w i t h t h a t p r o j e c t (namely c o s t and output c a p a c i t y ) and a parameter y which i s the aggregated output c a p a c i t y of a l l the p r o j e c t s preceding the one under c o n s i d e r a t i o n . . Although the necessary c o n d i t i o n of o p t i m a l i t y i s d e r i v e d s p e c i -f i c a l l y f o r two adjacent p r o j e c t s , a great d e a l of i n f o r m a t i o n can be obtained by t a b u l a t i n g the R v a l u e s of a l l the p r o j e c t s a t s p e c i -f i e d demand l e v e l s . T h i s w i l l be d e a l t w i t h i n d e t a i l i n s e c t i o n 3.5. 3.A S u f f i c i e n t C o n d i t i o n of O p t i m a l i t y : The necessary c o n d i t i o n of o p t i m a l i t y C3.2 may become a s u f f i -20 c i e n t c o n d i t i o n when the demand f u n c t i o n possesses c e r t a i n s p e c i a l f u n c t i o n a l p r o p e r t i e s . Since t ( X ) i s merely the i n v e r s e of the demand f u n c t i o n , one may c o n s i d e r the f u n c t i o n a l nature of t(X) i n s t e a d . CASE I . t( X ) i s a l i n e a r monotone i n c r e a s i n g p o s i t i v e f u n c t i o n : t( X ) = K • X f ( X ) = a" t ( X> -K-X a Therefore the e x p r e s s i o n of R d e f i n e d by Eq.3.2 becomes **(y) = K ^ r ~ (E3,3) 1 - a K X n Note t h a t the e x p r e s s i o n f o r R i n Eq. 3.3 depends only on the constants C nand x^, aid thus i t i s no longer dependent upon the argument. With t h i s s p e c i a l p r o p e r t y of the e x p r e s s i o n R, the o p t i m a l permutation S* can be obtained by a r r a n g i n g a l l the p r o j e c t s i n non-decreasing order of t h e i r R v a l u e s . T h i s i s because f o r any permutation S, S f S* , t h i s sequence S can be obtained from S by a s e r i e s of interchanges of adjacent elements. None of these interchanges w i l l decrease the v a l u e of C ( S * ) f t h e r e f o r e S* must be the o p t i m a l s o l u t i o n . 21 CASE I I . t ( X ) i s a n o n - l i n e a r monotone i n c r e a s i n g p o s i t i v e f u n c t i o n : When t(X) i s n o n - l i n e a r , the a n a l y s i s w i l l depend on the r e l a t i v e magnitudes of the c o s t s ; the f o l l o w i n g three s i t u a t i o n s are considered s e p a r a t e l y . (2A) Cj > C k : Expression C3.1 can be r e w r i t t e n i n the f o l l o w i n g form rt, C k (1 - - i ^ - ) • f{A+Z(Oij)} + • f { A + Z ( a i : j , j ) } Cj C j < f U + Z C O i j . k ) } (C3.3) I f f i s a concave d e c r e a s i n g p o s i t i v e f u n c t i o n , then by co n c a v i t y the L.H.S. of C 3 . 3 i s l e s s than the f o l l o w i n g q u a n t i t y c k c k f { ( l ) • (A+ZCo.,)) + (A+z(a i 1 fj))> f{A+Z(a ± j)+ x j } Since f i s a monotone dec r e a s i n g f u n c t i o n and Z ( O i j , k ) = Z ( a ^ j ) + x k , t h e r e f o r e when 22 c k A + z ( o ± j ) + XJ i l A + z(a 1 :j,k)-i . e . U j <^  u k where u i s the u n i t c o s t of a p r o j e c t then the ex p r e s s i o n C3.3 i s always tr u e and independent on the p a r a -meter A+Z(o^). Since by d e f i n i t i o n f ( X ) = a v ' t h e r e f o r e f i s a concave dec r e a s i n g p o s i t i v e f u n c t i o n i m p l i e s t h a t t i s a convex i n c r e a s i n g p o s i t i v e f u n c t i o n and d 2 t ( X ) d t ( x ) 0 { } • l o g . a f o r a l l X dX 2 dX ( 2 B ) Cj • C k : Ex p r e s s i o n C3.1 becomes f f A + Z f a i j . j ) } < f{A+Z(a i ; j,k)} Since f i s monotone d e c r e a s i n g , t h e r e f o r e e x p r e s s i o n C3.1 i s always t r u e i f X j > x k . Th i s c o n d i t i o n i s obvious, s i n c e the two p r o j e c t s have i d e n t i c a l c o s t s , the p r o j e c t w i t h l a r g e r output c a p a c i t y i s s u r e l y more economical one to add onto the e x i s t i n g system f i r s t . In f a c t t h i s c o n d i t i o n a p p l i e s to any demand f u n c t i o n . 23 (2C) Cj < Cfc : Exp r e s s i o n C3.1 can be r e w r i t t e n as (1 • ftA+zCa^)} + — ~ f { A + Z ( a i j , k ) } C k C k > f { A + Z ( a i j , j ) } (C3.4) I f f I s a convex dec r e a s i n g p o s i t i v e f u n c t i o n , then by c o n v e x i t y I t can be shown, i n a s i m i l a r l y manner as i n case 2A, t h a t e x p r e s s i o n C3.4 i s always t r u e i f F u n c t i o n f i s convex dec r e a s i n g p o s i t i v e i m p l i e s t h a t e i t h e r t i s a concave i n c r e a s i n g p o s i t i v e f u n c t i o n o r t i s a convex i n c -r e a s i n g p o s i t i v e f u n c t i o n and d 2 t ( X ) dt(X) _ < { . l o g a f o r a l l X dX 2 dX Table 1 summarizes the s u f f i c i e n t c o n d i t i o n s f o r p r o j e c t j immediately preceding p r o j e c t k i n an o p t i m a l sequence. 24 TABLE 1 SUFFICIENT CONDITIONS OF OPTIMAL PERMUTATION t(X) i s l i n e a r t ( X ) i s any f u n c t i o n t ( X ) i s convex t ( X ) i s concave t(X) i s convex For a p a r t i c u l a r demand f u n c t i o n which has the f u n c t i o n a l p r o p e r t i e s d e s c r i b e d i n Table 1, and should a l l the p r o j e c t s s a t i s f y the c o n d i t i o n s , then the o p t i m a l s o l u t i o n can be obtained r e a d i l y as i n d i c a t e d i n the case of the l i n e a r demand f u n c t i o n . In more general cases where the s u f f i c i e n t c o n d i t i o n s are not a p p l i c a b l e , the R v a l u e concept pro v i d e s a powerful e l i m i n a t i o n mechanism i n the m o d i f i e d Branch-and-Bound s o l u t i o n method. 3.5 Decomposition Theorem: Although the R v a l u e , as d e f i n e d by Eq.3.2, i s d e r i v e d from a p e r t u r -b a t i o n a n a l y s i s by i n t e r c h a n g i n g two adjacent elements i n permutation, a great d e a l of i n f o r m a t i o n can be obtained from the R v a l u e s by the use of Decomposition Theorem which i s as f o l l o w s : Suppose s e t 0 " k can be p a r t i t i o n e d i n t o two d i s j o i n t subsets and 0 j w i t h the property that R u ( y ) < R-^Cy) f o r a l l u e and v e O j , and f o r Rj < R k, where R i s d e f i n e d by Eq.3.3 Cj = C k and X j > x k d 2 t d t 2 C, > C i , , xi* < ui. and > { } ' l n a V X j k j - K dX 2 dX Cj < C k and U j < u k d t d t , C , < C k , u i < u k and < { -} «lna V X J J dX 2 dX 25 A k < y < A J + Y J + Y J where A K j> 0.0 . I f P ± = min C ( A k , P i ) P i e P i and P* = min C(Ak+Y±, P j ) , then P k = ( P* , P j ) minimizes 2 P J e P J C ( A k , P k ) over the s e t P k . P r o o f : L e t P k C P k be the subset c o n s i s t i n g of a l l the permutations of the form ( P ± , P j ) where P i £ P i and P j £ P j . L e t P k = min C ( A k , P k ) p k e * k Then P k £ P k , f o r otherwise there would e x i s t adjacent elements u £ and v £ 0 j such t h a t P k(v<u) . R u ( y ) < Rv(y) (by h y p o t h e s i s ) . . v < u v i o l a t e s the necessary c o n d i t i o n C3.2 , hence P k ( v < u) c o u l d not minimize C ( A k , P k ) • Therefore 26 P' = min C(A^ , P ) min C(A^ , P. ) min {cC^.Pi) + C(A k+Y i , P^) |p ± e T?± and P j e Pj} P i . P J min C ( A k , P ±) + min C(A+Y. , P.) P i e P i P J e P J C ( Ak • Pi> + C ( A k + Y i ' P1> = C ( A k , (P*,P*)} - C ( A k • Pk> The importance of the decomposition theorem r e s t s i n the f a c t t h a t , when the hypothesis i s s a t i s f i e d , the problem of f i n d i n g an o p t i m a l permutation of the elements i n set 0"k can be decomposed i n t o the two independent sub-problems of f i n d i n g o p t i m a l permutations of the elements of subsets and Oj . Such a decomposition w i l l drama-t i c a l l y reduce the number of permutations which need to be considered i n f i n d i n g the o p t i m a l s o l u t i o n . 27 In s o l v i n g a p r o j e c t c o n s t r u c t i o n sequencing problem of N p r o j e c t s , i t i s not uncommon that the o r i g i n a l problem can be t o t a l l y decomposed, namely the s e t a can be p a r t i t i o n e d i n t o N subsets which are m u t u a l l y e x c l u s i v e but c o l l e c t i v e l y e x h a u s t i v e . When a problem i s t o t a l l y de-composable, then the o p t i m a l s o l u t i o n i s apparent and no f u r t h e r com-p u t a t i o n s are necessary. In more complicated s i t u a t i o n s , decomposition can be a p p l i e d a t any stage i n the computations w i t h any subset of p r o j e c t s . The preference m a t r i x d e f i n e d i n the next s e c t i o n i s a u s e f u l t o o l f o r determining the decomposability of any set of p r o j e c t s . 3.6 Preference M a t r i x : A preference m a t r i x i s c o n s t r u c t e d u s i n g R v a l u e s , as d e f i n e d by Eq.3.2, computed f o r every element i n a s e t at c e r t a i n s p e c i f i e d demand l e v e l s . L e t s y ( k ^ » 'k^) be a row of N d i s t i n c t p r o j e c t s where N i s the number of elements i n s e t a k , and k^, i = 1, 2, , N , denotes the p r o j e c t occupying the i t h p o s i t i o n i n S y such t h a t R k ^ y ) < R k 2 ( y ) < < Rk N<y> The preference m a t r i x a s s o c i a t e d w i t h set o k i s composed of a whole s e r i e s of Sy's such t h a t the f i r s t row of t h i s m a t r i x i s equal to Syt=Ak where A^ i s a non-negative parameter r e p r e s e n t i n g the aggre-28 gated output c a p a c i t y of a l l the p r o j e c t s preceeding the set i n a permutation, and the l a s t row i s equal to S ? = Ak + Yk The f o l l o w i n g example i s used to i l l u s t r a t e the concept of the prefe r e n c e m a t r i x : PROJECT A B C D C O S T 700 600. 336. 114. OUTPUT 2000 1200 700 300 Discount r a t e i s 5%. Demand as shown i n Table 2. For the s p e c i f i e d demand f u n c t i o n , the preference m a t r i x a s s o c i a t e d w i t h the s e t c o n t a i n i n g a l l four p r o j e c t s i s shown i n Table 2. A v i s u a l i n s p e c -t i o n of t h i s m a t r i x c l e a r l y i n d i c a t e s t h a t no p a r t i t i o n s e x i s t ; thus no decomposition i s p o s s i b l e f o r t h i s s e t . Suppose that p r o j e c t C i s assumed to occupy the f i r s t p o s i t i o n i n a permutation of fo u r p r o j e c t s , then the p r e f e r e n c e m a t r i x a s s o c i a t e d w i t h the subset c o n t a i n i n g the r e s t of the p r o j e c t s , i . e . , A, B, and D, i s shown i n Table 3. This m a t r i x can be p a r t i t i o n e d i n t o two s u b s e t s , namely (D,A) and (B). This i s because the R v a l u e of element B i s g r e a t e r than those f o r D and A throughout the s p e c i f i e d demand i n t e r v a l , i . e . , 700 <_y <_4200. This l e a d s to the imme-d i a t e c o n c l u s i o n that i f p r o j e c t C i s the f i r s t element i n any permutation, •' then the e l i g i b l e candidates f o r o p t i m a l s o l u t i o n are C, A, D, B and C, D, A, B s i n c e both p r o j e c t s A and B must precede p r o j e c t D when p r o j e c t C i s the f i r s t i n the permutation. The number of permutations i n which p r o j e c t C i s the f i r s t element i s 31 = 6, but by using the decomposition theorem i t i s TABLE 2 PREFERENCE MATRIX FOR 4 PROJECT PROBLEM TIME DEMAND PREFERENCE MATRIX 0.0 0 D C A B i . 9 100 D c A B 2.7 200 D c A B 3.3 300 D c A B 3.8 400 D c A B 4.2 500 D A C B 4.6 , 600 D A C B 5.0 700 D A C B 5.3 800 D A C B 5.6- 900 D A C B 5.9 1000 D A C B 6.2 1100 D A C B 6.5 1200 D A C B 6.8 1300 D A C B 7.0 1400' D A C B 7.3 1500 D A C B 7.5 1600 D A C B 7.8 1700 D C A B 8.0 1800 D C A B 8.2 1900 D C. A B 8.4 '2000 D C A B 8.6 2100 D C A B 8.8 2200 D C A B 9.0 2300 D C A B 9.2 2400 D C A B 9.4 2500 D A C B 9.6 2600 D A C B 9.8 2700 D A C B 10.0 2800 D A C B 10.1 2900 D A C B 10.3 3000 A D 3 C 10.4 3100 A D B C 10.5 3200 A D B C 10.6 3300 A D B C 10.6 3400 A D B C 10.7 3500 A D B C 10.8 3600 A D B C 10.9 3700 A D B C 11.0 3800 A D B C 11.1 3900 A D B C 11.2 4000 A D B C 11.3 4100 A D C B 11.4 4200 A • D C B DATA PROJECT A B C D C O S T 700 600 336 114 OUTPUT 2000 1200 700 300 I n t e r e s t Rate 5% TABLE 3 PREFERENCE MATRIX FOR SUBSET OF 4 PROJECT PR03LEM WITH PROJECT C FIRST DEMAND PREFERENCE MATRIX 700 D A B 800 D A B 900 D A B 1000 D A B 1100 D A B 1200 D A B 1300 D A B 1400 D A B 1500 D A B 1600 D A B 1700 D A B 1800 D A B 1900 D A B 2000 D A B 2100 D A B 2200 D A B 2300 D A B 2400 D A B 2500 D A B 2600 D A B 2700 D A B 2800 D A B 2900 D A B 3000 A D B 3100 A D B 3200 A D B 3288 i B I 3500 A D B 3600 A . D - B 3700 A D B 3800 A D B 3900 A D B 4000 . A D B 4100 A D B 4200 A D B 31 c l e a r t h a t only two permutations are e l i g i b l e f o r o p t i m a l s o l u t i o n c o n s i d -e r a t i o n . T h i s example of the f o u r p r o j e c t sequencing problem w i l l be used throughout the r e s t of t h i s chapter to i l l u s t r a t e v a r i o u s aspects of the m o d i f i e d Branch-and-Bound a l g o r i t h m . A number of terms and concepts are e x p l a i n e d i n the f o l l o w i n g s e c t i o n s . 3.7 Stages and Nodes: A stage i s r e f e r r e d to the p o s i t i o n i n a permutation P, e.g., the f i r s t p o s i t i o n i n P i s c a l l e d the f i r s t s t a g e, the second p o s i -t i o n i n P i s c a l l e d stage 2, e t c . Hence permutation of N p r o j e c t s w i l l c o n s i s t of N stages. Nodes are i d e n t i f i e d a t every stage and they r e f e r to the i n d i -v i d u a l p r o j e c t s at that stage. For example, a complete t r e e branch of the f o u r p r o j e c t sequencing problem i s shown i n F i g u r e 2. There are four stage 1 nodes which are occupied by p r o j e c t s A, B, C, and D. There are three stage 2 nodes a s s o c i a t e d w i t h the branch where p r o j e c t A i s the node at stage 1, e t c . 3.8 L o c a l Optimal Sequence (L.O.S.): A s s o c i a t e d w i t h every node there may e x i s t a l o c a l o p t i m a l se-quence. The l o c a l o p t i m a l sequence f o r a node n at stage s i s denoted by = (k^, , k^) which c o n s i s t s of a l l the N p r o j e c t s i n the u n i v e r s a l s e t a. amd k., i = l , 2, N, denotes FIGURE 2 - C O M P L E T E T R E E B R A N C H E S F O R 4 P R O J E C T S 33 the p r o j e c t occupying the i t h p o s i t i o n i n the sequence Lg . Let the f i r s t to the s t h stage nodes on the branch l e a d i n g to stage s node n be occupied by p r o j e c t s d i , d 2 , > d s r e s p e c t i v e l y . L e t be a set c o n t a i n i n g a l l the p r o j e c t s except those a l r e a d y assigned to p o s i t i o n s k j , j = 1, 2, , i , i . e . i 8 k - a - Z k i j = l Le t Y kjL be a subset of such t h a t Y k c o n t a i n s a l l those elements u which s a t i s f y the c o n d i t i o n R k ± ( y ) < R u < y ) where i - 1 y a 1 x k i Then, the l o c a l o p t i m a l sequence L" i s obtained as f o l l o w s : k i = d i f o r i = 1, s R k <y> K i min R j ( y ) f o r i = s+1,* * *, N i - 1 where i - 1 Z xj j = l 34 A c c o r d i n g t o t h e above p r o c e d u r e , i n t h e 4 p r o j e c t s e q u e n c i n g p r o b l e m , t h e l o c a l o p t i m a l sequence f o r s t a g e 2 node C on t h e b r a n c h , where s t a g e 1 node i s o c c u p i e d by p r o j e c t D, i s r L2 = D, C, A, B T h i s i s b e c a u s e node C i s a t s t a g e 2 and t h e r e f o r e p r o j e c t s o c c u p y i n g r t h e f i r s t and second p o s i t i o n s i n L-2 a r e k n o w n , n a m e l y , p r o j e c t s D and C r e s p e c t i v e l y . The s e t 3, n i s t h e n c o n s i s t e d o f two p r o j e c t s , K2 =t> A and B. The e l i g i b l e c o n d i d a t e s f o r t h e t h i r d p o s i t i o n i n a r e i n t h e s e t y. , where y. i s i d e n t i c a l t o s e t 8, __ i n t h i s K-2=v^ 2~* 2~ c a s e . T h i s i s b e c a u s e t h e R v a l u e s o f b o t h p r o j e c t s A and B a r e g r e a t e r t h a n t h e R v a l u e o f p r o j e c t C computed a t a demand l e v e l o f y, where i - l E x k = x ^ = 300 The e l e m e n t , w i t h t h e s m a l l e s t R v a l u e computed a t a demand l e v e l o f y = x_j + x^, , i n t h e s e t _^ i s t h e n a s s i g n e d t o t h e t h i r d p o s i -t i o n i n t h e l o c a l o p t i m a l s e q u e n c e . I n t h i s c a s e t h e p r o j e c t c h o s e n i s A. A l o c a l o p t i m a l sequence c o n s t r u c t e d a c c o r d i n g t o t h e above p r o -c e d u r e i s a f e a s i b l e p e r m u t a t i o n w h i c h does n o t v i o l a t e t h e n e c e s s a r y c o n d i t i o n o f o p t i m a l i t y C3.2, i . e . , i n t e r c h a n g i n g any two a d j a c e n t e l e m e n t s i n a L.O.S. w i l l i n c r e a s e t h e d i s c o u n t e d c o s t . Hence, t h e 35 present worth cost of a L.O.S. rep r e s e n t s an upper bound of the o p t i m a l s o l u t i o n . In some cases a l o c a l o p t i m a l sequence cannot be s u c c e s s f u l l y c o n s t r u c t e d f o r any node. For example, the l o c a l o p t i m a l sequence f o r stage 1, node C i s incomplete and can have only three p r o j e c t s thus r e s u l t i n g i n o n l y a p a r t i a l sequence of C, A, B. This i s because the s e t Y, „ co n t a i n s no elements a t k3=B a l l . Hence i t i s not p o s s i b l e , by the l o c a l o p t i m a l sequence pro-cedure d e s c r i b e d above, to o b t a i n a f u l l sequence c o n t a i n i n g f o u r p r o j e c t s w i t h p r o j e c t C being the f i r s t element. For any node w i t h an incomplete l o c a l o p t i m a l sequence, a f u r t h e r e l i m i n a t i o n check must be performed to determine whether or not that node can be d i s -carded from the search f o r an o p t i m a l s o l u t i o n . 3.9 E l i m i n a t i o n Check; Suppose node n at stage s has an incomplete l o c a l o p t i m a l sequence, and the aggregated output c a p a c i t y of a l l the p r o j e c t s preceding and i n c l u d i n g node n on t h i s p a r t i c u l a r branch i s A n. s Then the e l i m i n a t i o n check procedure i s : (1) Let a be an a d m i s s i b l e s e t which c o n t a i n s , i n i t i a l l y , a l l the elements i n set y. ks d e f i n e d i n s e c t i o n 3.8. (2) Let B n s = An + £ x, s . i i e a (E3.4) 36 (3) For each val u e of y, which i n c r e a s e s i n c r e m e n t a l l y from A f i n d a corresponding p r o j e c t u such t h a t R ^ y ) o min R.(y) jea (4) Let set 6 c o n t a i n a l l the elements v such t h a t v e B g and R ^ y ) < R ^ y ) where y has the same s p e c i f i e d v a l u e as that i n Eq.3.5 (5) I f 6 _ a ( f o r s i m p l i c i t y , assume 0 c a) and y = B n , then t h i s s node can be e l i m i n a t e d . I f 6 C a , but y < B n then i n c r e a s e the v a l u e of y i n c r e m e n t a l l y s and go to step ( 3 ) . I f 6^ a and the number of elements i n set 6 i s equal to (N-s-1), then t h i s node can not be e l i m i n a t e d . I f 6 a and the number of elements i n set 6 i s l e s s than (N-s-1), then l e t a = 6 U u and r e s e t the v a l u e of B™ a c c o r d i n g to Eq.3.4. Increase the v a l u e of y i n c r e m e n t a l l y before going to step ( 3 ) . T h i s e l i m i n a t i o n check b a s i c a l l y c o n s t i t u t e s a s u f f i c i e n t c o n d i t i o n f o r e x c l u s i o n of s o l u t i o n subsets from o p t i m a l c o n s i d e r a t i o n . T h i s i s because the s e t a i n i t i a l i z e d i n step (1) c o n t a i n s a l l the a d m i s s i b l e elements e l i g i b l e ( i . e . not v i o l a t i n g the necessary c o n d i t i o n of o p t i m a l i t y to B n , (E3.5) 37 C3.2) and a v a i l a b l e ( i . e . not y e t assigned to e x i s t i n g nodes on a branch) to occupy the ( s + l ) t h to the Nth p o s i t i o n s i n a permutation l e a d i n g on from that node. The constant and the parameter i n d i c a t e the s t a r t i n g and ending demand l e v e l s the p r o j e c t s i n s e t a are r e q u i r e d to meet. The procedure to r e s e t the parameter and the s e t a i n step (5) provides the maximum o p p o r t u n i t y to enlarge the s e t a and to i n c r e a s e the v a l u e of B n Hence when the v a l u e s . of y reaches B n and the number of elements i n s e t a i s l e s s than s (N-s), i n order to form a sequence of N p r o j e c t s , some other p r o j e c t s not i n set a must be assigned to p o s i t i o n ( s ) a f t e r the s t h . Since the R v a l u e ( s ) of such p r o j e c t ( s ) i s s m a l l e r than the R v a l u e s asso-c i a t e d w i t h those p r o j e c t s i n set a at a p p r o p r i a t e demand l e v e l s , the necessary c o n d i t i o n of o p t i m a l i t y C3.2 i s v i o l a t e d , and t h e r e f o r e such a sequence can not be the o p t i m a l permutation. To i l l u s t r a t e the procedures i n v o l v e d i n t h i s e l i m i n a t i o n check, l e t us c o n s i d e r the stage 1 nodes C and A i n the 4 p r o j e c t sequencing problem. Both of these nodes have incomplete l o c a l o p t i m a l sequences C,A,B and A,B r e s p e c t i v e l y . For node C, the e l i m i n a t i o n check i s as f o l l o w s : A J = X (, = 700 a ». ( A, B ) B i = 700 + (2000+1200) - 3900 For 700 < y < 2900 , the element u i s equal to p r o j e c t A and the s e t 6 = (B) , namely 6 c a . But when y = 3000 , u = A and 6 = ( D, B ). Since 6 ^  a and y = 3000 < B G = 3900 , r e s e t 38 a = 6 U u , i . e . a = ( D, B, A ). The number of elements i n se t a i s now equal to (N-s) , namely, 4-1=3, and t h e r e f o r e node C can not be e l i m i n a t e d . On the c o n t r a r y , node A can be d i s c a r d e d , t h i s i s because: AV = x = 2000 1 A a = (B) B^ = 2000 + 1200 = 3200 For 2000 < y £ 2900 , 6 = 0; but when y = 3000, u = B and 6 = (C). Since 6^ a and y = 3000 < B^ = 3200 , r e s e t a = 6 U u = ( C, B ) and B^ - 2000 + (700+1200) = 3900 . Throughout the f u r t h e r m a n i p u l a t i o n s v i a i n c r e a s i n g y v a l u e s , i t i s seen t h a t 6 <z a. and the set a c o n t a i n s l e s s than 3 elements, hence stage 1 node A can be e l i m i n a t e d from f u r t h e r c o n s i d e r a t i o n i n the search f o r an o p t i m a l s o l u t i o n . 3.10 Upper Bound of the Optimal S o l u t i o n (U.B.): As e x p l a i n e d i n s e c t i o n 3.8, the l o c a l o p t i m a l sequence of a node rep r e s e n t s a condidate f o r the o p t i m a l s o l u t i o n . Since a t any stage there may e x i s t a number of nodes w i t h complete l o c a l o p t i m a l sequences, the upper bound on the o p t i m a l s o l u t i o n a t any stage i s then d e f i n e d to be the minimum discounted c o s t of a l l the complete l o c a l o p t i m a l sequences a t t h a t stage. 39 3.11 Lower Bound Sequence (L.B.S.) and Lower Bound ( L . B . ) : There i s a lower bound sequence a s s o c i a t e d w i t h each node at every stage. I t i s an a r t i f i c i a l sequence w i t h a discounted c o s t which i s lower than that of any r e a l sequence. The discounted c o s t of t h i s a r t i -f i c i a l sequence i s c a l l e d the lower bound. Suppose node n at stage s i s under i n v e s t i g a t i o n . L e t d^ , i = 1, 2, , s , be the p r o j e c t occupying the i t h node on t h a t p a r t i c u l a r branch. L e t 3 S be a s e t c o n t a i n a l l the remaining p r o j e c t s , i . e . 3 S = a - ! d ± i = l The lower bound sequence f o r node n i s composed of a r t i f i c i a l p r o j e c t s which are obtained by a r r a n g i n g the c o s t s and output c a p a c i t i e s of a l l the p r o j e c t s i n s e t 8 g such t h a t the h i g h e s t output i s assigned the lowerest c o s t and so on. These a r t i f i c i a l p r o j e c t s are then arranged i n d e c r e a s i n g order of t h e i r output c a p a c i t i e s (or i n c r e a s i n g order of t h e i r c o s t s ) to form the lower bound sequence. The proof i s as f o l l o w s : L e t n be the number of elements i n set 8_. L e t S'(bj , b2, > b n ) be any r e a l sequence c o n t a i n i n g a l l the elements i n s e t 8S. Let S ( k i , , k n ) be the lower bound sequence, i . e . the c o s t s of k! s are i n i n c r e a s i n g order of the elements i n s e t 8 S and the I 40 output c a p a c i t i e s of k±'s are i n descending order of the elements i n set 3S« C(A,S) = Z C k m • fCA+X^) m=l and C(A,S') = Z C b m • f ( A + X b m ) m=l x k m 1 X b m f o r a l l m and f u n c t i o n f i s monotore decreasing tn= 1 m= 1 L e t i E i = 1 Ckm w i t h E ° = 0 , 0 m=l and i F± = £ w i t h F Q = 0.0 m= 1 Then C b m - F m - F r a_! 41 ? C k m • f ( A + X b m ) = Z ( - E ^ ) • f ( A + X b n ) m=l ra=l n n E • f ( A + X b m ) - I E m _ 1 ' f ( A + X b m ) m= 1 m=l " Em * f < A + X b m > " ^ Em ' f ( A + X b n H - l > m=1 m=1 n-1 Z ^ ' { f ( A + X b m ) - f (A+X^. ) } + m=l 1 E n ' f < A + X b n > S i m i l a r l y , n n-1 Z C b m • f(A+X b ) = Z F m • { fCA+X^) - f ( A + X b m f l ) } + m= 1 m m=l ?n * f ( A + X b n ) Y± >_ E± f o r a l l i ? C k m • f ( A + X b n ) < ? C b m ' f ( A + X b m ) m=l m=l Therefore n n Z CV * f(A+X k ) < Z Ch ' f(A+X b ) , *m Km — , m °m m=l m= i 42 In the preceding s e c t i o n s , the upper bound of the o b j e c t i v e f u n c t i o n and the lower bounds a s s o c i a t e d w i t h a l l the nodes at a stage have been e s t a b l i s h e d . As i n d i c a t e d i n s e c t i o n 2.2, i f the lower bound of a node exceeds the upper bound of the o b j e c t i v e f u n c t i o n at that stage, then a l l the subsets of s o l u t i o n s l e a d i n g down from that node cannot c o n t a i n the o p t i m a l permutation P , and they can be d i s c a r d e d from f u r t h e r c o n s i d e r a t i o n . 3.12 Flow Chart: The r a t i o n a l e of the a l g o r i t h m f o r the p r o j e c t c o n s t r u c t i o n se-quencing problem i s the same as t h a t given i n s e c t i o n 2.4 f o r the general c o m b i n a t o r i a l o p t i m i z a t i o n problem. However, i t s s p e c i a l pro-p e r t i e s can be f u l l y u t i l i z e d to enhance the e f f e c t i v e n e s s of the g e n e r a l a l g o r i t h m . The a l g o r i t h m i s coded i n F o r t r a n f o r e x e c u t i o n on an IBM 360-67 computer and the average CPU time r e q u i r e d to s o l v e a ten p r o j e c t sequencing problem i s 8 seconds. A f l o w c h a r t i n shown i n F i g u r e 3 and a programme l i s t i n g i s given i n Appedix A. To i l l u -s t r a t e the use of the a l g o r i t h m , a number of examples are presented i n the next chapter. V O A T A 7 \ I N P U T / C O M P U T E R V A L U E S . C O N S T R U C T a STORE P R E F E R E N C E M A T R I X 43 INITIAL D E C O M P O S I T I O N ( I N I T I A L I Z A T I O N ' L E T Ufl ' m T A K E O N E B L O C K AT A T I M E F R O M D E C O M P O S I T I O N R E S U L T S ITS POS IT ION IN O P T I O N A L S E Q U E N C E IS K N O W N BRANCH ING 1 BY A S S I G N I N G A L L T H E P R O J E C T S IN T H I S B L O C K T O IT H S T A G E N O D E S T A K E O N E N O D E A T A T I M E C O N S T R U C T L O C A L O P T I M A L S E Q U E N C E FOR T H A T N O O E B O U N D C H E C K • E L I M I N A T E A L L T H O S E N O D E S W H O S E L B > U 8 F I N O P.W.OF THIS S E Q U E N C E . H E N C E THIS IS T H E L O W E R B O U N D O F T H I S N O D E N U M 8 E F ' O F P R O J E C T S IN T H A T B L O C K ? " J . » . F I N A L S T A G E F O R ^ J T H I S B L O C K IS, R E A C H E D ? YES ( N O 1 P O S I T I O N S O F A L L T H E P R O J E C T S ON E A C H B R A N C H IN T H E O P T I M A L S E Q U E N C E . A R E K N O W N P O S I T I O N S O F A L L T H E P R O J E C T S ON T H I S B R A N C H IN T H E O P T I M A L S E Q U E N C E IS K N O W N I A P P L Y D E C O M P O S I T I O N T O A L L T H E REMA IN ING P R O J E C T S E X C L U O I N G T H O S E A L R E A D Y IN T H E OPT IMAL S E Q U E N C E F U R T H E R B R A N C H I N G FOR A L L T H E B R A N C H E S • BY A S S I G N I N G A L L T H E P R O J E C T S IN T H I S B L O C K N O T Y E T O N A N Y P A R T I C U L A R B R A N C H T O T H E I ' M S T A Q E N O O E S O F T H I S B R A N C H ' Fig. 3 PROJECT SEQUENCING PROBLEM - FLOW CHART. CHAPTER 4 EXAMPLES OF THE PROJECT CONSTRUCTION SEQUENCING PROBLEM The various concepts and terminologies introduced in the pre-ceeding chapter will be used first to solve the four project sequenc-ing problem, after which three further examples involving 10 projects will be presented. The following symbols are used to show the various steps performed in the algorithm: node with a complete local optimal sequence. node with an incomplete local optimal sequence. node with an incomplete local optimal sequence which is discarded by the elimination check. node eliminated by bound check, i.e., the lower bound of this node exceeds the upper bound of the objective function. node eliminated by branching operation, i.e., no projects can be placed immediately after this node without violating the necessary condition of optimality C3.2. • V x © 4.1 Four Project Sequencing Problem PROJECT A B C D C O S T 700 600 336 114 O U T P U T 2000 1200 700 300 44 STAGE I 10 o 2 0> CL E o o CO d J o c 3 o CD D - S -c -STAGE 2 Q> Q. £ o u to G> "O O Z CO J JUL U O x: o c 3 o CO - c - S -- X . 45 STAGE 3 CO o O N o t e s 8 1 For p r e f e r en ce m a t r i x see Tab l e 1 . 2 P ro j e c t B cou ld not come f i rst without v io la t ing the n e c e s s a r y c o n d i t i o n . D E M A N D C U R V E 3 Op t ima l s e q u e n c e is D, C, A, B . 4 0 0 0 r Time ILLUSTRATION OF PROJECT SEQUENCING PROCEDURE WITH 4 PROJECTS. 46 Discount r a t e = 5% P r o j e c t e d f u t u r e demand f u n c t i o n i s :(t) = / 28.28 • t ' 0 < t < 10.3 10 f 12.5 • ( t - 9.2) 10.3 < t < 11.4 S o l u t i o n : The preference m a t r i x i s shown i n Table 1 from which i t i s seen that decomposition i s not p o s s i b l e . Since a t a zero demand l e v e l the R v a l u e of p r o j e c t B i s the l a r g e s t , t h i s leads to the immediate c o n c l u s i o n that the f i r s t p o s i t i o n i n the o p t i m a l permutation i s not occupied by p r o j e c t B. This i s because any sequence w i t h p r o j e c t B being the f i r s t element v i o l a t e s c o n d i t i o n 2.2. Therefore there are o n l y 3 stage 1 nodes namely D, C, and A. The complete s o l u t i o n pro-cedure i s shown s c h e m a t i c a l l y i n F i g u r e 4 and a computer p r i n t out i s given i s Appendix B. 4.2 Ten P r o j e c t Sequencing Problem: The f o l l o w i n g data are used f o r three d i f f e r e n t f u t u r e demand f u n c t i o n s to f i n d the minimum discounted cost sequences: 47 PROJECT A B C D E F G H I J COST 700 646 559 600 490 414 336 210 148 114 OUTPUT 2000 1700 1300 1200 1000 900 700 500 400 300 Discount r a t e = 5% CASE 1. Convex demand f u n c t i o n : X ( t ) = 3000 • (1.07* - 1.0) This f u n c t i o n corresponds to a demand i n c r e a s i n g a t an annual r a t e of 7% from a s t a r t i n g l e v e l of 3000 u n i t s . From the preference m a t r i x f o r t h i s example, i t was found t h a t t o t a l decomposition was p o s s i b l e . Hence the o r i g i n a l problem of f i n d i n g an o p t i m a l 10 p r o j e c t permutation i s decomposed i n t o 10 sub-problems, each of which c o n t a i n s one p r o j e c t . Thus the o p t i m a l sequence i s obtained immediately, i . e . P* = I J H A B C F G E D and C(P*) = 2383.6 CASE I I . Concave demand f u n c t i o n : X ( t ) = 2150 • / t STAGE I tn <D o Z O O '•^  <u O J= 1- (J CO -o -a • tn £ O c ~ . o o -JO CD y B C y -F — x H i x STAGE 2 •o o Z C I f-o c o o u . -o 00 w 9 § J O y -y -y . h F X I — x J X r F X H X I X J • X h H X I X h J X - H X - I X I X u a> JZ o T> C o CO STAGE 3 O.K. 48 Optimal sequence is A B I 3 CHFGED T i m e F ig .5 PROJECT SEQUENCING - 10 PROJECTS - C A S E IL . 49 The r e s u l t s of the e l i m i n a t i o n processes are shown schemati-c a l l y i n F i g u r e 5. The o p t i m a l sequence is P * - A B I J C H F G E D and the cost is C(P*) = 3141.2 The e f f e c t i v e n e s s of the e l i m i n a t i o n mechanisms i n the m o d i f i e d Branch-and-Bound a l g o r i t h m i s demonstrated i n t h i s example. For a 10 p r o j e c t sequencing problem, there are 10 stage 1 nodes each of which can be f u r t h e r branched i n t o 9 stage 2 nodes, g i v i n g a t o t a l of 90 stage 2 nodes. I f none were e l i m i n a t e d there would be 3,628,800 stage 10 nodes f o r e v a l u a t i o n by exhaustive enumeration. By the a l g o r -ithm proposed i n t h i s t h e s i s , i t i s seen from F i g u r e 5 that there are n i n e stage 1 nodes, one of which i s d i s c a r d e d v i a L.O.S. c o n s i d e r a t i o n and the e l i m i n a t i o n check. Two more nodes are e l i m i n a t e d by the bound check, thus l e a v i n g only s i x nodes. From these s i x stage 1 nodes there c o u l d be a t o t a l of 54 stage 2 nodes (nine branches from each stage 1 node), but by u s i n g the necessary c o n d i t i o n of o p t i m a l i t y C3.2 there are i n f a c t o n l y 17 stage 2 nodes. By L.O.S. c o n s i d e r a t i o n and e l i m i -n a t i o n check, 14 of these nodes can be d i s c a r d e d and two more nodes are e l i m i n a t e d by bound check, l e a v i n g only one node. An immediate c o n c l u s i o n can be drawn that the p r o j e c t s occupying the f i r s t and second 50 p o s i t i o n s i n the opt i m a l sequence are known, i . e . p r o j e c t A and p r o j e c t B r e s p e c t i v e l y . For the remaining 8 p r o j e c t s , i t i s seen that t o t a l decomposition i s p o s s i b l e , and thus the op t i m a l permutation c o n s i s t i n g 10 p r o j e c t s i s obtained by c o n s i d e r -i n g only a t i n y f r a c t i o n of the p o s s i b l e a l t e r n a t i v e s . CASE I I I . General monotone i n c r e a s i n g f u n c t i o n : X ( t ) = 28.28 • t 2 / 10* . ( J 12.5 t - 9.2) 0 < t < 10.3 10.3 < t F i g u r e 6 shows s c h e m a t i c a l l y the e l i m i n a t i o n processes. The opti m a l permutation i s P* = J I H A B C F G E D and the co s t i s C(P*) = 2431.5 From the above three examples i t i s i n t e r e s t i n g to note that (1) Of the three demand f u n c t i o n s , Case I i s probably the most t y p i c a l and i t was the e a s i e s t to s o l v e . S T A G E I in a) o c o (U •o J U c o m o <D x: y S T A G E 2 H C B A y y y y y y X to o H G H c o • -a to-j} 9§ -JO Opt imal sequence is N 01 HA B C F G E D y y y y X X X y y y X X X 5f X X X X > X xs X X X X •a c 3 O CD o a> x: O S T A G E 3 01 a) o 2 H G F A I F A B c o CO q § _ i c_> s/ X X V X X X (A X J c 3 o CO O a> x: O y — * X X — A — y~ * B B A A F B B y— X X 0 B B — x 10 000 S T A G E 4 O A B c o •o CO w J U y y B T i m e F i g . 6 P R O J E C T S E Q U E N C I N G - 1 0 P R O J E C T S - C A S E JU (2) For each example, the g l o b a l o p t i m a l permutation i s i n v a r i a b l y e q u i v a l e n t to the l o c a l o p t i m a l sequence of a l l the p r o j e c t s . (3) A sequence i n i n c r e a s i n g order of u n i t c o s t s i s : A I B J H C F G E D . None of the o p t i m a l permutations i s equal to t h i s sequence showing t h a t the t r a d i t i o n a l approach of r a n k i n g p r o j e c t s by t h e i r u n i t c o s t s does not r e s u l t i n a sequence which has the minimum discounted c o s t . CHAPTER 5 USE OF THE ALGORITHM IN WATER RESOURCES PLANNING Although a long p l a n n i n g h o r i z o n i s necessary i n water resources development s t u d i e s , the prime concern of planners i s undoubtedly the immediate a c t i o n which must be taken i n order to meet a growing demand. For example, a s e r i e s of developments may be r e q u i r e d to meet a growing demand of e l e c t r i c energy which i s p r o j e c t e d 30 or 40 years i n t o the f u t u r e . However, the f u r t h e r i n t o the f u t u r e t h a t c o s t , i n t e r e s t r a t e and demand are p r o j e c t e d , the l e s s accurate they are l i k e l y to be. A l s o , c o n d i t i o n s change and i n a few years time p r i o r i t i e s may be q u i t e d i f -f e r e n t from what they are now. Therefore, what i s r e a l l y r e q u i r e d a t present i s t o make a prudent d e c i s i o n on the imrne d i a t e a c t i o n namely which p r o j e c t i s to be c o n s t r u c t e d now. Once the f i r s t p r o j e c t i s b u i l t i t w i l l meet the i n c r e a s i n g demand f o r a few y e a r s , and by then a d e c i s i o n on the second p r o j e c t i n the s e r i e s of developments can be made u s i n g the i n f o r m a t i o n a v a i l a b l e at that time. Thus, water resources p l a n n i n g (and indeed a l l l a r g e s c a l e planning) should be a c o n t i n u i n g process w i t h the plans s u b j e c t to change i n the l i g h t of the l a t e s t a v a i l a b l e i n f o r m a t i o n . However, the d e c i s i o n of the f i r s t p r o j e c t must not c o n t r a -d i c t the o b j e c t i v e of the e n t i r e p l a n n i n g h o r i z o n , s i n c e once a p r o j e c t i s c o n s t r u c t e d , c e r t a i n o p t i o n s i n the f u t u r e w i l l i n e v i t a b l y be c l o s e d o f f . Furthermore, data a c q u i s i t i o n and p r e l i m i n a r y design of water resources engineering p r o j e c t s are both time consuming and expensive, 53 54 therefore e f f o r t s devoted to the study of a p r o j e c t should be approxi-mately i n proportion to i t s l i k e l i h o o d of being the f i r s t one i n the s e r i e s of developments. The s o l u t i o n algorithm for p r o j e c t c o n s t r u c t i o n sequencing problem formulated i n Chapter 3, guarantees the convergence to the g l o b a l optimal sequence which has the minimum discounted cost f o r the e n t i r e development s e r i e s . I f the input data such as costs and output c a p a c i t i e s of a l l the p r o j e c t s are p e r f e c t l y accurate, then there i s no doubt at a l l which p r o j e c t has to be constructed f i r s t . To obtain an accurate cost of a p r o j e c t , i t would r e q u i r e , f o r instance i n hydro development, d r i l l i n g at r e s e r v o i r s i t e and performing d e t a i l e d design of the dam e t c . There-fore i n the preliminary planning phase, costs of the p r o j e c t s are only estimates and they are of varying degrees of accuracy depending on the information a v a i l a b l e on each p r o j e c t . Hence i t i s extremely important to assess the i n f l u e n c e of varying degrees of cost estimate accuracy on the optimal sequence. I t was noted i n the l a s t chapter that, for example, the g l o b a l optimal sequence i s i d e n t i c a l to the l o c a l optimal sequence i n v o l v i n g a l l the p r o j e c t s , namely the l o c a l optimal sequence at stage zero. Twenty four te s t cases were conducted by using various demand functions and a l l kinds of u n i t cost spectrums. In every cas2, the g l o b a l optimal sequence i s i n v a r i a b l e i d e n t i c a l to the associated stage zero l o c a l optimal sequence. Although t h e o r e t i c a l l y t h i s i d e n t i t y can not be proved, i t does i n d i c a t e pragmatically an approach to i d e n t i f y the f i r s t p r oject i n the optimal 55 sequence by merely finding the project with the minimum R value computed at a zero demand level. Sensitivity analysis of allowable errors in cost estimates can then be readily performed as follows: Since R n(y) Cn i •- f ( y + x n ) f(y) For zero demand level , Rn(y=o) c n 1 - HxJ where f(x) = ( 1.0 + I ) ~ t ( x ) Let u be the project such that R u(y=0) = min Ri(y=0) iea Therefore project u i s extremely l i k e l y to occupy the f i r s t position in the global optimal sequence. However, i f the cost of another project i is reduced such that 56 R u(y=o) > Ri(y=0) f o r i e a - u Then p r o j e c t i , r a t h e r than p r o j e c t u, w i l l be the most l i k e l y candidate f o r the f i r s t p o s i t i o n i n the g l o b a l o p t i m a l sequence. Hence a c o s t f o r p r o j e c t i can be determined such t h a t Unless the co s t of p r o j e c t i i s reduced to the value given by E5.1, p r o j e c t i i s very u n l i k e l y to be the f i r s t one i n the s e r i e s of develop-ments. I f the r e d u c t i o n i n co s t i s s u b s t a n t i a l and the planners are q u i t e c o n f i d e n t that the a c t u a l c o s t of p r o j e c t i can not be as low as t h a t , then p r o j e c t i can be s a f e l y d i s c a r d e d from f i r s t p o s i t i o n c o n s i d e r a t i o n . On the other hand, i f such a reduced c o s t of p r o j e c t i i s p o s s i b l e , then i t should be r e t a i n e d , and a more r e f i n e d c o s t estimate (which would i n v o l v e more e f f o r t s and t e c h n i c a l resources) should be prepared. When r n 0 r e accurate c o s t data are ob t a i n e d , the new R valu e s based on the l a t e s t i n f o r m a t i o n can then be computed and the next round of a n a l y s i s can be performed. S e n s i t i v i t y a n a l y s i s f o r the 4 p r o j e c t sequencing example i s shown i n Appendix B. The above s e n s i t i v i t y a n a l y s i s procedure i s not r i g o r o u s , s i n c e the p r o j e c t w i t h the minimum R value computed at a zero demand l e v e l can not be t h e o r e t i c a l l y guaranteed to occupy the f i r s t p o s i t i o n i n the g l o b a l o p t i m a l sequence. However, cost estimates are never comp-l e t e l y a ccurate and hence the c o s t s of a l l the p r o j e c t s are s u b j e c t = Ru(y=0) * { 1.0 - f ( X i ) } (E5.1) 57 to e r r o r ; i n these circumstances a s i m p l e , r e l i a b l e i f not t h e o r e t i c a l l y r i g o r o u s procedure f o r f i n d i n g the a l l o w a b l e e r r o r i n the cost estimate of each p r o j e c t i s b e l i e v e d to be a u s e f u l p l a n n i n g t o o l . CHAPTER 6 SCHEDULING & SEQUENTIAL SEARCH PROBLEMS In the f i e l d of I n d u s t r i a l E n g i neering c o m b i n a t o r i a l o p t i m i z a t i o n problems are o f t e n encountered i n p r o d u c t i o n s c h e d u l i n g and s e q u e n t i a l search and t e s t i n g . In t h i s chapter i t i s shown that these problems have o b j e c t i v e f u n c t i o n s d e f i n e d by Eqs. 2.1 and 2.2 and th a t they can be so l v e d e a s i l y by a p p l y i n g the necessary c o n d i t i o n of o p t i m a l i t y C2.2. 6.1 Least Cost T e s t i n g Sequencing Problem; This problem was suggested by P r i c e ( 1 8 ) as f o l l o w s ; An item i s to be subjected to N d i f f e r e n t t e s t s , say t e s t s a ( l e n g t h ) , b (hardness), c (diameter), and so on. A s s o c i a t e d w i t h the j t h t e s t there are two c o n s t a n t s : Cj and Rj where Cj i s the c o s t per item of conducting the j t h t e s t and Rj i s the p r o b a b i l i t y of r e j e c t i n g the item on the j t h t e s t . The t e s t s are independent i n the sense t h a t they may be performed i n any order whatsoever and the constants Cj and Rj are taken to be independent of the order i n which the t e s t s are c a r r i e d out. A sequence of t e s t s , say S = ( a , b, » p) , i s s e t up and each item i s subjected to each t e s t i n the sequence S as long as i t continues to pass the t e s t s . I f the item f a i l s a t e s t , i t i s r e j e c t e d and no f u r t h e r t e s t s are performed on i t . I t i s r e q u i r e d 58 59 to f i n d the t e s t sequence S* such that the expected c o s t of performing the t e s t s i n the order s p e c i f i e d by S i s a minimum. An elegant a n a l y t i c a l s o l u t i o n to t h i s problem i s g i v e n by M i t t e n (19). The o p t i m a l sequence S* i s obtained by a r r a n g i n g a l l the t e s t s i n ascending order of t h e i r *V v a l u e s . The expected c o s t of performing a sequence of t e s t s i n the order s p e c i f i e d by S i s C ( S ) = I C, • II (1.0 - R ± ) (E6.1) jes J i<j Equation 6.1 can be e a s i l y i d e n t i f i e d w i t h the general o b j e c t i v e func-t i o n E2.1, i . e . g j ( a ± i ) = c 1 • n (1.0 - Ri) i<j Hence the necessary c o n d i t i o n of o p t i m a l i t y namely the c o n d i t i o n t h a t t e s t j immediately precede t e s t k can be obtained by s u b s t i t u t i n g the a p p r o p r i a t e expressions i n t o C2.2, i . e . R K • c . • n ( i . o - R.) < R, • c k • n ( i . o - R±) i<j i<j 60 n ( i . o - R i ) > o.o i < j • c j < R j • c k i . e . < (C6.1) R j R k Since the e x p r e s s i o n C6.1 depends o n l y on the c o n s t a n t s a s s o c i a t e d w i t h each t e s t item, t h i s e x p r e s s i o n C6.1 becomes a s u f f i c i e n t con-d i t i o n of o p t i m a l i t y . Hence, as i t was shown i n the p r o j e c t c o n s t -r u c t i o n sequencing problem w i t h a l i n e a r demand f u n c t i o n , the o p t i m a l permutation can be obtained by a r r a n g i n g the t e s t s i n ascending order of the " 7 R r a t i o s as s t a t e d by M i t t e n . 6.2 S e q u e n t i a l Search and T e s t i n g : A complicated p i e c e of machinery may c o n s i s t of thousands of com-ponents. When the machine f a i l s i t I s a c o s t l y and time consuming task to i d e n t i f y the f a u l t y component i n the system. Instead of randomly examing each component of the system i t i s d e s i r a b l e to have a search s t r a t e g y to minimize the time and money i n v o l v e d i n f i n d i n g the f a u l t . A number of papers have been w r i t t e n on t h i s type of c o m b i n a t o r i a l o p t i m i z a t i o n problem (20, 21, 22). 6 1 The problem i s as f o l l o w s : A system c o n s i s t i n g of K independent components has the proper t y t h a t whenever one component f a i l s the system f a i l s . When the system f a i l s , the i t h component i s known to have an a •priori p r o b a b i l i t y p.^  of being the component that caused the system f a i l u r e . I f the components can be t e s t e d one at a time and i t r e q u i r e s Tj_ time u n i t s to t e s t the i t h component, then the problem i s to determine the order i n which the components should be t e s t e d i n order to minimize the expected time u n t i l the f a i l e d component i s found. Let S ( l , 2, , N) be a t e s t sequence. The expected time to perform the t e s t s i n t h a t order i s C(S) = P l • T X + p 2 • ( T ^ ) + j I ( p, • T. T ± ) (E6.2) jeS 3 i = l Equation 6.2 can be e a s i l y i d e n t i f i e d w i t h the general o b j e c t i v e func-t i o n E2.1, i . e . gj<oij> - PJ • ( * j r ^ y i > Hence the necessary c o n d i t i o n of o p t i m a l i t y becomes " P j ' Tk < ~ Pk ' T j 62 i . e . T j T, k < (C6.2) Pj Pk Again, s i n c e the e x p r e s s i o n C6.2 depends only on the c o n s t a n t s asso-c i a t e d w i t h the t e s t s , e x p r e s s i o n C6.2 becomes a s u f f i c i e n t c o n d i t i o n f o r t e s t j to immediately precede t e s t k. Therefore the o p t i m a l permu-t a t i o n i s e a s i l y obtained by a r r a n g i n g t e s t s i n ascending order of the T r a t i o s . P 6.3 P r o d u c t i o n Scheduling: In manufacturing i n d u s t r y i t i s o f t e n the s i t u a t i o n t h a t a number of jobs need to be processed on a machine and each job should be d e l i -vered to the customer before a c e r t a i n date. I f a job i s not d e l i v e r e d by the s p e c i f i e d due date, a p e n a l t y may be imposed on the manufacturer. Hence i t i s d e s i r a b l e f o r the manufacturer to schedule the j o b s to minimize the p e n a l t y c o s t . T h i s k i n d of p r o d u c t i o n s c h e d u l i n g problem i s r a t h e r complicated and a number of s o l u t i o n methods have been pro-posed (23, 24, 25, 26, 27). I t w i l l be shown th a t the g e n e r a l formula-t i o n presented i n Chapter 2 can be e a s i l y a p p l i e d to s o l v e t h i s type of job s c h e d u l i n g problems. The problem i s s t a t e d by Emmons(27) as f o l l o w s : 63 N jobs are r e q u i r e d to be processed on a machine. A l l j o b s are a v a i -l a b l e s i m u l t a n e o u s l y a t time zero and job i , i = 1,2, ,N , has a p r o c e s s i n g time p^ and a due date d^, both of which are known i n advance. Setup times are n e g l e c t e d ; that i s , they are assumed to be independent of the sequence (as are p r o c e s s i n g times) and hence may be i n c l u d e d i n p^. The l a t e n e s s of job i i s d e f i n e d as = - d± where I s the completion time of job i . The l a t e n e s s of a job may be p o s i t i v e or n e g a t i v e , depending on whether the job i s completed on time (C^ d^) or not. The t a r d i n e s s of job i i s then d e f i n e d as T^ = max ( 0, ). I t i s r e q u i r e d to f i n d an o p t i m a l permutation P of a l l the N jobs such t h a t the t a r d i n e s s of the sequence s p e c i f i e d by P i s a minimum, i . e . i t i s to minimize an o b j e c t i v e f u n c t i o n of the form E Tj = E max ( 0, L. ) jeer jea E max ( 0, Cj-dj ) jea E max ( 0, E Pm+Pj-dj ) (E6.3) jea mea^j Equation 6.3 can be e a s i l y i d e n t i f i e d w i t h the gene r a l o b j e c t i v e func-t i o n E2.1, i . e . S j ^ i j ) = max ( 0 , E p m + p j - dj ) mea. . Hence the necessary c o n d i t i o n of o p t i m a l i t y C2.2 becomes max ( 0, Z Pm + p, - d j ) - max ( 0 , E p m + p k + P j meo^ meOij max ( 0 , Z p m + p k - d k ) - max ( 0, E p m + P j + P k mea ij mea^ Let W = T. pm m meo^j and C - £ Pm + Pk + P j mea^j then the c o n d i t i o n becomes max max ( 0, W + p j - d j ) - max ( 0, C - d j ) ( 0, W + p k - d k ) - max ( 0, C - d k ) C > W + Pj max ( 0, W + Pj - d j ) <_ max ( 0, C - d j ) 65 Hence the L.H.S. of e x p r e s s i o n C6.3 must be l e s s than or equal to zero. S i m i l a r l y , the R.H.S. of C6.3 i s a l s o l e s s than or equal to z e r o . M u l t i p l y both s i d e s of the e x p r e s s i o n C6.3 by -1 , i t becomes max ( 0, C - dj ) - max ( 0, W + p j - d j ) >^  max ( 0, C - d k ) - max ( 0, W + p k - d k ) (C6.4) Ex p r e s s i o n C6.4 i s the necessary c o n d i t i o n f o r job j to immediately precede job k when job j i s to be processed at time U. I t i s i n t e r e s -t i n g to note that although the c o n d i t i o n C6.4 i s d e r i v e d f o r two a d j a -cent elements j and k, when Pj _^ P k > the e x p r e s s i o n C6.4 i s the necessary c o n d i t i o n f o r element j preceding element k w i t h any number of other elements i n between them. Then proof i s q u i t e s t r a i g h t forward. L e t S be a sequence w i t h job j preceding j o b k. Let o"a, 0*k and OQ be s e t s of elements before job j , i n between j o b s j and k, and a f t e r job k r e s p e c t i v e l y . L e t S' be a sequence obtained by i n t e r c h a n g i n g the p o s i t i o n s of job j and job k i n the sequence S. Then sequence S i s p r e f e r a b l e to se-quence S' , i f job t a r d i n e s s i n S i s not g r e a t e r than t h a t i n S'. Since the sub-sequence before job j i n S i s e x a c t l y the same as t h a t b e f o r e job k i n sequence S', there are no changes i n t a r d i n e s s f o r any job i n set O a . S i m i l a r l y there are no changes i n t a r d i n e s s f o r jobs i n set 0 C. 66 I f pj f_ P k , then T i <_ f o r a l l i e o b , where T ± and T| are t a r d i n e s s of job i In sequences S and S' r e s p e c t i v e l y . Since c o n d i t i o n C 6 . 4 ensures that' T. + T. < T* + T,* J k — j k Then, as cla i m e d , e x p r e s s i o n C 6 . 4 i s the necessary c o n d i t i o n f o r job j preceding job k w i t h any number of elements i n between them,pro-v i d e d p. < p, . T h i s i s a s p e c i a l p r o p e r t y of p r o d u c t i o n s c h e d u l i n g 3 k to minimize the job t a r d i n e s s whereas the necessary c o n d i t i o n of o p t i -m a l i t y f o r the p r o j e c t c o n s t r u c t i o n sequencing problem i s o n l y a p p l i c a b l e to two adjacent elements. C o n d i t i o n 6.4 depends not o n l y on the constants (namely the pro-c e s s i n g time and due date) a s s o c i a t e d w i t h jobs j and k, but a l s o on a parameter U which i s the time when job j i s to be processed. I f C6.4 i s independent on the v a l u e of W, then i t becomes a s u f f i c i e n t c o n d i -t i o n f o r job j preceding job k. To achieve t h i s , l e t us assume t h a t : max ( 0, C - dj ) >_ max ( 0 , C - d k ) t h i s r e q u i r e s max ( 0, W + p k - d k ) > max ( 0, W + P j - d j ) t h i s r e q u i r e s W + P k - d k > W + p - d 67 i . e . that i s d k - ( P k - P j ) < d j Thus, i n order to s a t i s f y the necessary c o n d i t i o n 6.4, the combined c o n d i t i o n s r e s u l t i n g from the above two hypothesis are d k ~ (P k - Pj> 1 d d < d k i . e . P j < p k (C6.5) dj < d k (C6.6) and d j ~ P j - d k " p k (C6.7) Hence, when c o n d i t i o n s 6.5 to 6.7 are s a t i s f i e d , c o n d i t i o n 6.4 i s always tru e independent of the v a l u e of the parameter W. Therefore c o n d i t i o n s 6.5 to 6.7 are s u f f i c i e n t to guarantee th a t job j should precede j o b k i r r e s p e c t i v e of when j o b j i s to be processed and whether or not they are ad j a c e n t . 68 An example of job s c h e d u l i n g i s presented to i l l u s t r a t e the use of the g e n e r a l a l g o r i t h m o u t l i n e d i n s e c t i o n 2.4. Note t h a t the g e n e r a l a l g o r i t h m c o n t a i n s two e l i m i n a t i o n mechanisms: one i s to d i s c a r d nodes which v i o l a t e the necessary c o n d i t i o n of o p t i m a l i t y , and the other i s to d i s c a r d those nodes which v i o l a t e the bounding c o n d i t i o n . In order to i l l u s t r a t e the e f f e c t i v e n e s s of the f i r s t e l i m i n a t i o n mechanism, the example below w i l l be s o l v e d by u s i n g the necessary c o n d i t i o n a l o n e . EXAMPLE JOB i A B C D E DUE DATE d ± 25 73 31 32 15 PROCESS TIME p ± 6 12 16 32 80 d i - I > i 19 61 15 0 -65 SOLUTION: (1) Step 0 : By s u f f i c i e n t c o n d i t i o n s C6.5 to C6.7, i t i s seen t h a t A < C , A < D, C < D . Therefore i t can be concluded that job A should be processed before job C which should be processed before job D. Hence there e x i s t three stage 1 nodes, i . e . A, B and E. (2) Step 1 : Stage 2 branching by a s s i g n i n g e l i g i b l e jobs to stage.2 nodes as shown i n F i g u r e 7. (3) Step 2 : Apply C6.4 to each branch, thus e l i m i n a t i n g three of the seven stage 2 nodes. 70 ( A ) Step 1: Stage 3 branching. There are 8 e l i g i b l e stage 3 nodes as shown i n F i g u r e 7. (5) Step 2: Apply C6.4 to each branch, r e s u l t i n g i n 4 stage 3 nodes. (6) Step 1: Stage 4 branching. There are 7 stage 4 nodes. (7) Step 2: Apply C6.4 to each branch; e l i m i n a t e 4 nodes. (8) Step 1: Stage 5 b r a n c h i n g , i . e . adding to each branch the only remaining j o b . ( 9 ) Step 2: Apply C6.4 to each branch, r e s u l t i n g i n the o n l y complete sequence A C D B E, which i s the g l o b a l o p t i m a l s o l u t i o n . By t o t a l enumeration there are 5! = 125 sequences i n which i t i s p o s s i b l e to arrange these f i v e j o b s . I n the s o l u t i o n shown above, o n l y 14 branches were e s t a b l i s h e d , among which only three were of f u l l l e n g t h sequences. The t o t a l number of computations r e q u i r e d at each stage to e v a l u a t e c o n d i t i o n C6.4 i s o n l y h a l f of the number of nodes at that stage. The reason i s i l l u s t r a t e d by an example — at stage 2, job B a f t e r job A does not v i o l a t e C6.4J but then j o b A a f t e r job B must v i o l a t e the necessary c o n d i t i o n 6.4. Hence c o n d i t i o n C6.4 i s a c t u a l l y a p p l i e d o n ly once at stage 2 f o r nodes A and B. As shown i n t h i s c hapter, s e q u e n t i a l t e s t i n g and p r o d u c t i o n sche-d u l i n g problems a l l belong t o the c l a s s of c o m b i n a t o r i a l o p t i m i z a t i o n 71 problems s p e c i f i e d i n Chapter 2. Furthermore, s e q u e n t i a l t e s t i n g p r o-blems are extremely simple to s o l v e as the o p t i m a l permutations can be obtained immediately by a p p l y i n g the necessary c o n d i t i o n of optima-l i t y . Although p r o d u c t i o n s c h e d u l i n g problems are more i n v o l v e d and i n g e n e r a l the o p t i m a l permutation can not be obtained as e a s i l y as tha t i n s e q u e n t i a l t e s t i n g problems, i t i s shown i n the example t h a t by a p p l y i n g the necessary c o n d i t i o n of o p t i m a l i t y a l o n e , the compu-t a t i o n a l e f f o r t i s reduced by 90% compared w i t h t h a t r e q u i r e d by t o t a l enumeration. S U M M A R Y A modified Branch-and-Bound algorithm i s shown to guarantee e f f i c i e n t convergence to the global optimal sequence for project construction sequencing problem and other s i m i l a r problems i n I n d u s t r i a l Engineering. The global optimal sequence has been observed to be i d e n t i c a l to the l o c a l optimal sequence involving a l l the projects, thus i n d i c a t i n g a p r a c t i c a l approach to determine allowable errors i n cost estimates of the projects. 72 R E F E R E N C E S E. B a l a s , "An A d d i t i v e A l g o r i t h m f o r S o l v i n g L i n e a r Programs w i t h Zero-One V a r i a b l e s " , Operations Research V o l . 13, pp 517-526 (1965). R. J . Dakin, "A Tree-search A l g o r i t h m f o r Mixed Integer Programming Problems", The Computer J o u r n a l V o l . 8, pp 250-255 (1965). N. J . Driebeek, "An A l g o r i t h m f o r the S o l u t i o n of Mixed I n t e g e r Programming Problems", Management Science V o l . 12, pp 576-587 (1966). A. M. G e o f r i o n , "Integer Programming by I m p l i c i t Enumeration and B a l a s ' Method", SIAM Review 9, pp 178-190 (1967). A. H. Land and A. Doig, "An Automatic Method f o r S o l v i n g D i s c r e t e Programming Problems", Econometrica V o l . 28, pp 497-520 (1960). J . W. F a v e t t and N. P l y t e r , "The Optimal Assignment of F a c i l i t i e s to L o c a t i o n s by Branch and Bound", Operations Research V o l . 14, pp 210-232 (1966). P. C. Gilmore, "Optimal and Suboptimal Algorithms f o r the Quadratic Assignment Problems", SIAM J o u r n a l V o l . 10, pp 305-313 (1962). E. L. L a w l e r , "The Quadratic Assignment Problem", Management Science V o l . 9, pp 586-599 (1963). G. H. Brooks and C. P. White, "An A l g o r i t h m f o r F i n d i n g Optimal and Near Optimal S o l u t i o n s to the P r o d u c t i o n Scheduling Problem", J o u r n a l of I n d u s t r i a l E n g i neering V o l . 16, pp 34-40 (1965). E. I g n a l l and L. Schrage, " A p p l i c a t i o n of the Branch-and-Bound Techniques to Some Flow Shop Scheduling Problems", Operations Research V o l . 13, pp 400-412 (1965). 73 74 11. Z. A. Lonnicki, "A Branch-and-Bound Algorithm for the Exact Solution of the Three-Machine Scheduling Problem", Operational Research Quar-terly Vol. 16, pp 89-100 (1965). 12. J. D. C. Little, K. G. Murty, D. W. Sweeney, and C. Karel, "An Algorithm for the Travelling Salesman Problem", Operations Research Vol. 11, pp 972-989 (1963). 13. W. L. Price, "Increasing the Capacity of a Network Where the Costs Are Nonlinear: A Branch-and-Bound Algorithm", CORS Journal Vol. 5, pp 100-114 (1967). 14. P. J . Kolesar, "A Lranch-and-Bound Algorithm for the Knapsack Pro-blem", Management Science Vol. 13, pp 723-735 (1967). 15. M. A. Efroymson and T. L. Ray, "A Branch-and-Bound Algorithm for Plant Location", Operations Research Vol. 14, pp 361-368 (1966). 16. W. S. Butcher, Y. Y. Hairaes, and W. A. Hall, "Dynamic Programming for the Optimal Sequencing of Water Supply Projects", Water Resources Research Vol. 5, pp 1196-1204 (1969). 17. T. L. Morin and A. M. 0. Esogbue, "Some Efficient Dynamic Pro-gramming Algorithms for the Optimal Sequencing and Scheduling of Water Supply Projects", Water Resources Research Vol. 7, pp 479-484 (1971). 18. H. W. Price, "Least-Cost Testing Sequencing", Journal of Industrial Engineering Vol. 10, No. 4 (1959). 19. L. G. Kitten, "An Analytic Solution to the Least Cost Testing Sequence Problem", Journal of Industrial Engineering Vol. 11, p 17 (1960). 20. R. Bellman, "Dynamic Programming", Princeton University Press (1957). 21. D. C. Denby, "Minimum Downtime as a Function of Reliability and Priority Assignments in a Component Repair", Journal of Industrial Engineering Vol. 18, pp 436-439 (1967). c 75 22. H. Greenberg, "Optimum Test Procedure Under S t r e s s " , Operations Research V o l . 12, pp 688-692 (1964). 23. S. E. Elmaghraby, "The One Machine Scheduling Problem w i t h Delay C o s t s " , J o u r n a l of I n d u s t r i a l E n g i n e e r i n g V o l . 19, pp 105-108 (1968). 24. M. Held and R. M. Karp, "A Dynamic Programming Approach to Sequencing Problems", S o c i e t y f o r I n d u s t r i a l and A p p l i e d Mathematics, V o l 10, pp 196-210 (1962). 25. E. L. Lawler, "On Scheduling Problem w i t h D e f e r r a l C o s t s " , Management Science V o l . 11, pp 280-288 (1964). 26. A. S c h i l d and I . J . Fredman, "Scheduling Tasks w i t h L i n e a r Loss F u n c t i o n s " , Management Science V o l . 7, pp 280-285 (1961). 27. H. Emmons, "One-Machine Sequencing to Minimize C e r t a i n F u n c t i o n of Job T a r d i n e s s " , Operations Research V o l . 17, pp 701-715 (1969). APPENDIX A COMPUTER PROGRAMME LISTING 77 5461 U N I V E R S I T Y C P B c C Z I M P U T n r. r.i-?!r«^r TS ( Av 1 >0) AY SYSTEM WILL SHUTPOWN AT 4:00 P.M. THIS JOB SUB yI TTFC THROUGH FRONT OF SK P F A 0 F R **************** r u p=4pn T=?M  SICNOM WAS: 14: 54:43 C 7-0 1-71 TSCU" S T GNFD ON AT 1^:54:56 OA' 07-01-71 COM(1,1361) SCCV-'PRE TTM£=l?0,PAG.PS=400 I N T F G F P HPT, TATA, ^, SFX 1ST 0 IAEA'S IP1*1 ° ( 70) , IMHF X ( ?0) , I. ( ?0) ,1 00(7 0) ,1. Sf T ( ->r\ ) ,  1 IM 20 ) ,S ( 20 ) , PL!> ( 5n ) , ?.IUR4NK(?0) COMMON MFXIST, SFXI ST{ 20) , N UP- F R ,OX,0(20) , 1 0 AT A ( 2 ,20 ) , C ( ?0 ) , IS F00° ( 20 ) , tiP'T, 30 PT ( 50, 20)  r HI 1BLF °F< EC IS 10 N OL OG , X , Y , A f P , u , 0 PC OS T , PA LOS.UB, 1P WL H S »P Li? t T X , XD » 2TX0 RF AO (5,100) DINT, OX, NUBEP. C r c 0 I N T . INTEREST RATE c X?-' * X VAX[ v!j-.t DF ivA MO c OX : INTERVAL SIZE I \ ' J.T. MATRIX c MUR FR : TOTAL NO. OF PROJECTS, MUST BF .LE. 20 c 0 A T A . NAWS OF PROJECTS» Pt^'UMF^T OAT A r 0 ' OUTPUT, PFPf'VMFNT OAT A 0 c . COST, PP-HMANFMT OAT A C P'DEX : I ?;Otr X { ) = NO. OF PRGjrc.TS IN BLOCK C I NO : A WORK PIG SET TO CALL SUB ?. 0 U T IMF SCAN c L : PPOJFCTS IN BLOCKS c IT IS ALSO USED ONCE IM F.I NO 1NG P. T. MATRIX c IS F OOP : P^T I'-'AL. SEOUENCF r ONCOST : OPTIMAL COST c PJRANK : SEQUENCE BY UNIT 0.0 ST S C c 1?0 FOPVAT(F5.?,F6.L,13) 00 P 1 = 1 , M'JBEP  P DATA! 1,1) = I FPAD(5,10 1) (CATA(?,N), N=l,NUBEP) 101 FOP VAT(?0A4) PEA 0(5, 102) (0(N), N=l,NUBFP) 102 FORMAT ( 1OFS .1 ) PEAP(5,10?) (0(M), N = l,NUPr.R) X--AX = O.O A — 0.0 00 14 I = 1, MUBER P ( I ) = C( I ) / 0(1) IF ( R( I ) .GT . A ) A = P(I ) 1/. XV A X = X A X * 0(1)  SOOO •• !• ! T •'(*>, 2C0 ) OINT , X \ y ,N!jQF£ , ( 0 T A ( 7 , v ) , 1 , - O P E ) 200 FORMAT ( 1H1 , • >>ATA: • ,/ , • INTEREST PATE • , F P . 7 , / , » '.AXp-'UV np'-'ANO • , l P P . l . / t * NO. OF PROJECTS' ,1 3,/,' NAME ' .2C12X.A4)) V.P IT F( 6.701) (C(N), N = 1 f NUB FR ) 201 FORMAT( 1X , •COST ' ,20F6.0) ur. j T H ( ? n ? ' ) ( C ( - \ ' ) t V = 1 , N ! ' P ^ P ) 77 I 20? rC ' i - ."AT ( 1 X , » OUTPUT ' , ?.:)ff: .0 ) Wr I T r I (- , 2 ) ( P. (,\') , \- = 1 , jo F ) 20O FOP.iVAT ( • U. COST * , 20F6.3) 78 c r TO r i N H R A N D S P Y U MI T C O S T S A = A + 10-0.0 nn 5 1 1 = 1. N U P F P 00 5? J = It ^UPE° I F ( J . G T. I ) GO T H H = >t I) J J = I GO Tn 5 2 5 3 IF ( P ( J ) . GF. P ) GO TO 52 P. = P(J) J J = J 5? CONTINUE IIM? A\"< ( T ) = P AT A ( 2 . J.) ) 51 (• ( J J ) = A TO CDMPUTF R VALUES AMD STOPF P.T. INTO MATQIX 7O0O f.-AX = X'-iAX/OX + 1 o n 1 1 = 1 , "AX IF ( I .GT. 1 ) GO TG 2 X = O.O — 7 7 _ _ T R 3 ? X = X + DX 1 CALL T IMF(X,TX ) TO FIND P VALUES OF ALL PFOJECTS FOR A GIVEN X VALUE PO A J = l.MJRFR xn = x + n { j ) . C A L L T l :-F { x n , T X O ) : R(J) = C(J) / ( 1.0 - ( l . C + D I N T ) * * ( T X - T X O ) I F ( J . G T . 1 ) GO T O 5 T E S T = R(J) I F ( P ( J ) . G T . T F S T ) C O N T I N U E 6 ' 7 ) TFST = R ( J ) SUP = TEST + 100. TO PANK THE R VALUES FOR THAT GIVEN X VALUE 00 t> K = I, NURFR TFST = SUP - 50.0 00 7 J = It N'UBFR IF ( 'r (J) .Gr. TEST ) GO TO 7 T P S T = f ( J ) I. ( K ) = J 7 CONTINUE 6 tUL(K)-) = SUP 00 °> J = 1t MUPFR 00 10 K = It \'U:3FR If- (L(J) .fic. N'4TPIX(I,J| = C O N T I N U E C O N T I V U F C O N T I N U E I TF( 6,2 04) i)ATA( 1 . K ) DATA(2 t K) 1—GO ro i o -1 7 10 Q 1 J>i>4 F I ; K 1 - A T {// , • T J •' F • , 7 X , •GF-.iA^O' , 1 3 X , ' P P h :< I 1 1 I - 1 i M A X X = ( I - l ) * ox CALL T I M F ( X , T X ) T = T X 11 '•••I- T TT ( r,, ? m ) T , X , ( '1A T P I V ( I , V) , v = l , M<--> F f ) A T M X ' ) ? 0 3 r r ; i v 'VM < r c. l , r--•>. i , .?r.A4) c c C START OFCONPOS I T ION WITH N F X I S T = 0 C C 79 50 00 N F X I S T = 0 WR I TF ( fc , ?05 ) 205 FC"!P f'i AT (//, • I N I T I A L HF COM ?OS I T IUN : • , / / ) f. C START STAf.F 1 PLANCH I NG C ( J P C O S T = o . o M n n e i = o 7 = o . o I H P T = o 4B J S T A P T = 1 JFNI) = NURFP - I OPT C A L L C O P Y ( 7 . X M A X ) G A I L F L O C K ( Z , X M A X , J S T A 3 T , J F N O , I M O F X , I P L O C K , L ) C 7. : T O T A L O U T P U T Q F O P T I M A L S F 0 U F N C 1 B E F O R E T H F N F S ' P P O J E C T C c no 15 I B 1, T P - L O O K .7 I F ( INOFX ( I R) .NE. 1. ) GO T n ]_.', I O J T : P O S I T I O N IN O P T I M A L SEQUENCE T S F C O ° IOPT = IOPT 4- 1 I = 0 00 4 4 I I = I , IB 44 T = I + T N O F X ( I I ) . 1 > '-4 '• 5 •'> 6 '. 7 -~ k • n *i 1 • 7 I St OOP ( I (DPT) = L ( I ) x = O P C O S T F A L L C O S T O P (X » O P C O S T , I S F 0 O P ( I O P T ) , I O P T , 7 , 7 > ' A X ) 7 - 7 M A X G O T O 15 r C C C r TO P L A C E P R O J E C T S IN T H I S BLOCK INTO 0 p T IN A L S E O U F N C F TO GET T H E P AN GE OF T H I S P.LOCK Z : TOTAL OUTPUT B E F O R E T H I S BLOCK 7MAX : TOTAL OUTPUT I N C L U D I N G T H I S PLOCK -V": 4 ~*7 1A 1ST AGE = IOPT + 1 UB = 0.5 U f t I T F ( 6 , 2 0 6 ) I P , I S T A G F 2 C 6 FOPNAT I / / , • A S S I G N P R O J E C T S IN 9 L 0 C K * , 1 3 , ' Tf] STAC-P • ,! 3, 1 • NOO-S: • ,/) '5 3 • hh N F X I S T = IO ° T IF ( IOPT .GO. 0 ) GO TO 12 0 0 13 J = 1 , NF XI ST S E X I S T ( J ) = I S E O O P ( J ) 13 S ( J ) = I S E Q O P I J ) ' . 3 7 I C C C r E L E M E N T S ' ? F c O ' ' E T H I S MI.OCK HAVE ALL P E E N ASS I C "-'EC T J I OfTI'-'AL S E l H ^ ' F A S S I G N E L E M E N T S IN T H I S PLOCK TO THE NEXT NO OF TO F I N D THE FNOOING OF T H I S ^LOCK IN OPO-F To i/SF S'tP. COPU 1? t T ^ T A L = 0 •' ft 7 7 r. r. c 00 46 J - 1 , I BLOCK 46 ITPTAL = ITPTAL * I ^ ' ) F X ( J ) IHICT = i n p T - ( NUBER - ITPTAL ) 80 I M O T : i s TH E W I R E * P F FLFMFNTS SFT 1. WHICH GAVE Al P F A O v ^ E F M ASSIGNED TO OPTICAL S c 01JFNC E 1 2 1 ^-"• 8 f c c CALL ADD ( 7, I D I O T , INDEX ( P>.), I. , 7MAX ) MIN = 7/OX + I MAX = Z MAX/OX + 1 . I C A N O = f) I I = INDEX ( TP ) - 1 PC 17 I ST AG l ^ l , I l CALL C P P Y I Z , 7 MAX) CALL I. C M INOEXt 1 3 ) , TOPT, I STAP.E .1 STAG I t ? . I ' ' [ I ' » K Q K ) GO TO ( 1 3 , 10 ) , K OK KOK = 2 M IA.NS N"01 WITH I NC OOP L E TE L.O.S., CHECK ZIG7AG -4 c c c 19 CALL Z IGZ AG ( '-'I M ,1 NO EX ( I ? ) , T 7 I G , I ST AG1 , TCPT , I STAGE ) GO TO ( 2 0 . 1 7 ) , I Z I G I Z I G = 1 MEANS NODE WfT-f INCOMPLETE L.O.S. MUST PF p F T A f f<; F 0 = 2 MEANS NOnF DISCARDED = 6 >n vB ••A3' *^4 C C c TO FIND PWLOS FOR THE NODE WITH COMPLETE LOS 13 12 = IOPT + 1 13 = IOPT + I N D E X ( I B ) Pl-.'LOS = OPCOST 7 l = t  00 22 1 4 = 1 2 , 1 3 X = PWLOS CALL COSTOPfX,PWLOS,S(14),14,ZZ,ZZMAX) 22 11 = ZZMAX WRITE (6 , 207 ) LIB F T 10 11 ' 12 ' 1 3 2 0 7 FOR M i> 1 ( 1 0 X , 1 U B = ' , 02 0 . 1 1) IF ( UP .LT. 1.0 .OR. OB .GT. PWLOS ) OF = ?'•••'L OS W P I T E ( 6 F 2 0 P ) PWLOS, UP 208 FORMAT( 10X, 'POLOS = ',P?P.11 ,5X,•UP =' ,D?0. 1 1 ,//) TO FIND THE 1. B.S. FOP THIS NO 0 E F f 1 ft • i o 20 NEXIST = IOPT + I S E X I S T ( N E X I S T ) = S ( N E X I S T ) CALL COS TOP ( OPCOST, PWLPS,S( NEXIST) ,MFX I S T . Z . Z Z ) CALL C 0 3 Y ( 7 Z . Z M A X ) CALL PLOCK( 7Z , z M A X , i , i i , TNO,I P L , L S F T ) FALL Lb I ZZ , I NO,[BL,LSFT,PWLPS) ICAND = IC A N n + 1 OPT(ICANO,NFXI ST ) = S ( N F X T S T ) R L B ( ICANO) = P'/LBS NFX 1ST = N E X 1ST - 1 17 CONTINUE ^2 0 w21 23 " 24 75 ••2 7 is*-29 3 0 1 GO TO 50 END OF STAGE 1 BRANCHING FOR THAT BLOCK. CH-CK POUNDS M 13 = 1 * r M S T = I S T A ^, F c c c ?. II = 13 I? = ICANP 1)0 2'( L l = I-l, 12 81 IF ( (RLB(LL) - UR) .LT. O.0C005 ) GO TO 24 LP .GT. OR, .VPOF 0 1 ST. AROFO I F ( LL . F O . 12 ) GO TO 25 13 = LL I C A N D = ICAMO - 1 CO 26 LLL = LL, I CAMO FIB(LLL ) = PI P( L l L» U  0 0 Zfy N = 1, ISTAGF 26 H P T I L L L , N) = PPT(LLLU,N) GO TO 2 3 25 I C A N D = r C A N O - 1 24 COM T I N UE ROUND CHECK COMPLETE WF'I TE ( 6, 210 ) ISTAGE, OB, ICAND 2.10 FOR'MT(// , i FNO OF STAGE',IB,' BOUND CHECK, UB = «,020. 11,/, I • NUMBER OF BRANCHES REMAINING = ',I3) 00 4 3 LLL = 1 , ICAND  ^3 K I T E ( 6 , ?. I 5 ) LLL, (OPT ( L L L , N ) , N = L , ISTAGE) 2 15 FL'PMATf. • OP T( ' , I 3 , » ) : ' , 20A4) 21 CALL PR ANCH(UP, ICAND,I OPT,0"C0ST,Z,7MA X,ISTAGE,INOEX( I 1) ,KOK) GO TO (27, 23, 15, 5.', ), KOK K Q K = 1 MEANS ONLY ONE CANDIDATE IN OPT, SO "R OBI E '•' CAN START AFRESH = 2 MEANS f'CVr ANALYSIS BY LOS CONSTRUCTION ETC. = 3 MEANS ELEMENTS IN BLOCK IR HAVE BEEN OPT I Af-'Ll. Y ASSIGNED = 4 MEANS DIMENSION OF OPT IS EXCEEDED SINCE ONLY ONE CANDIDATE, SO FILL IN OPT WITH THE KNOWN SOLF PARTIAL S 27 DU 4 7 LLL = 2, 50 00 4 7 N = 1, IOPT 47 OPT(LL L,N) = 0PT(1,N) GO TO 43 28 II = 1 OP I TE i( ,2 12. ) ISTAGE, I CAMP  212 FOP MAT( / / » * END OF STAGE',13,• BRANCHING BY SUBROUTINE BRANCH. THE IRE ARE', I?,' BRANCHES') TF ( ICAND .EQ. 1 ) GO TO 21 WRITE(6,211) 211 F Of' N AT ( • BEGIN TO EXAMINE THESE BRANCHES RV l.O.S. CONSIDERATION* , 1 //)  1 EL I". I = 0 40 I START = II IEVD = ICAND 00 29 ISTAG2 = ISTART, I END Tf? NT TERM J ME COLUMN M'l'-'RFR O p THAT NODE 72 = 7 NEXIST = I STAGE - I J ST ART = IOPT + I DO 30 J = JSTAPT , NFX 1ST S( J ) = 0^ > T( I S T A G ? ,.) ) Sf X 1ST ( j ) r ; i p r ( i s r \G2,J ) 0 C 3 1 J J = 1. , N I I B E R I F ( SExrSXfJ) . \ ' F . 1 A T A ( ? , J J ) J C P T O 31 7.2 = 12 • P ( J J ) O P TO 3 0 ~M C O N T I N U E  3 0 C U P 1 I F U F '•' I N 7 2 - 7 ? / O X + 1 V N = I S T A O ? + I F t I'-" I X P I T R ( A , ? ! 3 ) NM , ( O ->T ( I S T \G ? , N ) , 0 = I I S T A 0 R- ) ? 1 3 F O P " A T ( / , « P O P B P V J C H N P Y O F , J 1 , 1 3 . ' : • , 2 0 A 4 ) C A L 1 C O P Y ( 7 ? , Z " A X )  MM = N O . O F P. E •'•'A I MI 0 0 E L E M E N T S I N I ' V C F X ( I P ) + T H E PR E S F N uM. = I N D F X I T B ) + I O P T - N F X I S T 0 0 3 2 L L = 1, MM I F ( ."AT ( Ml H12, L L ) . E O . O P T ( I S T A G 2 , I S T A O E ) ) G O T O 3 3 3 2 C O N T I N U E 3 3 C A L I L O S f I N O E X ( I P ) , I Q P T , T ST A 0 E , L t. , S , * I N Z 2 , K OK )  G O T!.1 ( 3 4, 3D ) , K0;< K O K : = 2 M E A N S N 1 0 E W I T H I N C O M P L E T E L . O . S . , C H E C H Z I G Z A G ? 5 C A L L Z I G Z A G ( - ' I N Z 2 , I N D E X ( IF.) , T Z I G, L L , T P P T , I S T AG.F) G O T O ( 3 6 , 3 7 ) , I Z I G I Z I G : = 2 M E A N S N O D E D I S C A R D E D U P U A TJ N G S E T O P T 3 7 I C A N D = I C A N O - 1 I F ( I S T A G 2 . E O . I E N D ) G O T O 2 9 I F L I M I = I E L I Ml + 1 DO 3 9 1 1 = I S T A G 2 , I C A N D 0 0 3 0 J J = I , 1 S T A G E  3 0 O P T ( 1 I ,JJ) = O P T ( I I + 1 , JJ) I I = I S T A G 2 G O T O 4 0 3 4 I ? = I O P T + 1 1 3 = I O P T + I N D E X ( I B ) P W L O S = O P C O S T  Z Z = Z 0 0 3 8 14 = 1 2 , 1 3 X = P W L O S C A L L C O S T O P ( X . P W L O S , S ( J 4 ) , I 4, Z Z ,Z ZMA X.) 3 B Z Z = Z 7 N A X W R I T E ( 6 , 2 0 7 ) U P  I E ( U B . O T . P W L O S ) UP = P V.LOS W P I T E ( 6 , 2 0 B ) P W L O S , U B T O F I M P L . B . S . F O R T H I S N C O E 2 6 N E X I S T = I S T A G E S E X I S T ( N E X T S T ) = S I N E X I S T ) 17 = 7  J S T A r T = [P'^T * I P W L B S = O P C O S T 0 0 4 2 J J = J S T A R T , I S T A G E V = PW L B S C A L L C O S T O M X , P W L B S ,S ( J J) , J J , ZZ , 7 ZMAX ) '•7 Z Z = ZZ'-'AX  F A L L C P P Y ( l l , Z M A X ) ~ J F ^ O = P O - X ( I P ) + I O P T - I S T A G E C A L L BI. P C K ( 7 7. , Z M A X , I , J F N O , I ;JD , I -?L , I S E T ) F A L L L B ( Z Z , I N ' l , I R L , L S F T , PWL B S ) P L B ( I S T A G ? ) = P W L B S .?<"> Cr VT I N U E C END L . n . S . C H P f . K . START BOUND C.HfcCK SO WP ITE ( 6 , 2 l*> ) ICAND, I S T A O c , IJB 2 1 6 FORMAT(//,» AFTER L.O.S. f l l F C K , TUF^S A R E 1 » 13, ' c-RANC.HfS AT ST.Ar,r« 1,13,/, • START BOUNDING CHECK, UB =' , 0 2 r . \ \ , / ) 0 0 4 5 1 = 1 , ICAND >-7 4 5 WP 1 T E ( 6 , ? 1 7 ) I , P1. a ( I ) , ( 0 ? r ( I , r;) , N= 1 , T S T A 0 c ) v ; ? 1 7 FO!-MAT(« f , L n i , I 3 , ' ) = ' , .'V C . 1 1 , 2 0 A4 ) > ' 15 GO TO 4 1 CONTINUE . 1 W F I T E ( 6 , 2 1 4 ) l ^ C O S T , ( I S F O O P ( N 4 ,^M»NUBER) ? 214 f 0 R N A T ( / / , • OPTIMAL SOLOTI ON: • ,/, » COST = 020. 11 , 1/,' SF QUINCE I S : • , ?0A41 WR IT E { 6 , 2 I S ) ( IU - AN - ( N) ,N = 1 , M U P- E R ) 2 1 3 99 FOP M A T { / , ' RANK P-M U.C.:',20A4) R E A 0 ( 5 , i n 3 ) NUMBER 7 103 FORMAT{13) 5S I F ( NUMBER .GT. 0 ) CALL POSTO?(NUMBER) STOP >•' •. END -1 c V:? C i -i c c c * ' -\ c •.7 c c / g SUBROUT INE BLOCK ( X X , > X M A X , J START,JEMO,T N n E X , T BLOGK,L) INTEGER DATA, S E X I S T DIMENSION I NO = X ( 20) , L ( 2 0) , L c. E T ( 2 0 ) , T N n ( p n ) , I N { 2 0 ) r(l C O MON N E X I ST , S EX 1ST ( 20 ) ,.\UPER , 0X,0( 20 ) , L D A T M 2 , 2 C ) , C ( 2 0 ) , I S F Q G P ( 2 0 ) ,01 NT, 2 M A T ( 6 5 0 , 2 0 ) , M A T R I X ( 6 5 0 , 2 0 ) , J5 3 0 P T ( 5 0 , 2 0 ) '6 c ?7 c X X : STAP T I N G OF MAMO ^ . c X X ••'AX : ENODING DEMAND c JSTART : ST A R T I N G COLUMN c J END : FNDDING COLUMN > :-l c THIS S U B R O U T I N E FINDS TOTAL DECOMPOSITION •'2 c v3 c Hi ^  C A L L SCAN ( X X , XX MAX , J S T ART , J F N 0, 0 , IND, I PL ,L SET) - 5 5 TBLOCK = I B L . "6 CO 12 I = 1, I BLOCK -7 1 I ir- DEX ( F ) = IND( I ) I 1 = J F ND - JSTART +• 1 00 13 I - 1 , 11 13 L ( I ) = L S E T ( I ) > n I F { I P. LOCK . EQ. 1 ) GO TO 2 7 12 = 1 13 = I BLOCK • 4 15 11 = 12 '5 IRLOCK = [3 *^6 c TO CHECK FOR FUR THE. F 0 EC O N p o S I T I ON » •! 0 0 14 I = I I , IBLUCK I I = T - 1 I F ( INDE X( I ) .ED. 1 ) GU TC 14 • 1 0 c TO r IMO RANGE. OF COLUMNS FOR SCANNI>'0 1 I F ( I . 0 T . 1 ) r,"» rn 17 ; ? . i • 3 • 4 1 5 i 6 ' 11 * 6 1 7 :>0 . J J = 1 J J J = I N D E X ( 1 ) GO TO 1 3 1 7 J J = 1 on 1 9 j = l , I I 1 9 J J = J J + I N D E X ! J ) 84 TT JJJ = J J + r-j">F x( i) - i *._Q C TO GFT ALL THE PARAMETERS 1 0 OP PEP TO USE SUBP PUT I ME ADD Vn 1 8 Z = XX 2 1 NUMBER = O V IF ( I .GT. 1 ) GO TO 2 0 M I COUNT = f NDF X(1 ) GO TO 2 1 TO FIND THE OUTPUT OF PRECEDING BLOCKS 2 0 I COUNT = C 0 0 22 J = 1 , II 2 2 ICOUNT = ICCUMT + TNDEX(J) CALL A 0 0 ( 1 , NU^E 1 3 »I 0 n i IN T , L , SUM) -3 I \2 3 3 <4 - 5 C c Z = SUM NUMBER = ICOUNT ICOUNT = IMOFX( I ) TO FIND THE MAXIMUM TANGE OF THIS BLOCK 2 1 CALL ADO(Z,NUMBER, I COUNT,L,YMAX) ~T7 C C •» 7 «• } « 3 9 + 1 TO SEE ANY FURTHER DECOMPOSITION IN THIS BLOCK FUR CALL SCANIZ,YMAX,JJ,JJJ,NUMPFP, INO, TEL,L S E T) IF ( IBL .EQ. 1 ) GO TO 14 THpP OFCOMPOSI TI ON ACHlFVEO. UP DA TP SETS L IM?FX 0 0 2 J J = J J , J J J 2 3 L(J) = LSFT(J) 1 3 = I BLOCK - I 0 0 2 4 J = 1 , 1 3 2 4 INIJ) = INOEXI I+J) 0 0 2 5 J =• 1 , IBL v 2 4 4 4 5 4 6 4 7 2 5 INDEX! I I+J) = I N 0 ( J ) 0 0 2 6 J = 1 , 1 3 2 6 IMDFX( I I+IBL+J) = IN{ J) 1 3 = I BLOCK + I 8 L - 1 1 2 = I G O T O 1 5 t B - 4 9 5 2 5 ? "~T4 N ) W 2 1 2 CONT INUF DECOMPOSITION IS C.PMPLETEO W R I T E ( 6 , 2 1 2 ) I BLOCK FORMAT {/,' DECOMPOSITION P F. S U L T S : ' , 5 V , « N1.1 B E '< OF BLOCKS DO 4 1 5 I = 1 , I BLOCK IF ( T .GT. 1 ) GO TO 4 1 6 ->4 - C 5 , 5 6 • 5 8 ='.13) NNN = 0 NN = 1 GO TO ^17 NN = NNN + 1 NNN = NNN + INDEX! I ) W P I T F ( 6 , 4 2 2 ) INDEX { I ) , I , ( L ( M ) , ^ • = ^ M , \<r M ) •6 1 (•2 * 3 h ft 6 r i 4 1 6 4 1 7 4 1 5 <*22 FORMAT I 2 (NX , I 3 P R O J E C T S I N B LOCK ' , I 3 , • : ' , 1 !; A4 ) G O T O 2 3 2 7 WR I T E ( 6 , 2 1 3 ) 2 1 3 FP F M A T ( ' D E C O M P O S I T I O N I S N O T P O S S I B L E ' ) 2 * R E T U R N F MD 6 7 6 8 ^ 9 7 0 7 1 c. c c c 85 SUP, ROU TINE SCANIY ,V"\Y , J J , J J J , N'.r-'PRF , INDEX, I BLOCK, I. ) I NT EOF p. 0 ATA , SF X T ST Y £ Yf-AX ARE THE START IMG C ENDING DELANO Lf- V! L TO SCAN JJ r, J J J ARE THE STARTING f. ENDING COLUMNS TO SCAN IBLCCK : NO. P F BLOCKS IN P.T. OBTAINED BY THIS SCANNING ICOUNT : A WORKING T CO!. TO COUNT TOP MR. OF PROJECTS IN A BLOCK NUNPEP : A V.OPKING T°OL TO COUNT TOTAL NO. Of R' ^  J c 0 T IN' BLOCKS SOF A^> INClUniNG PRECEDING BLOCKS y c •) c > c i c ? c 3 c c INDEX : INOfv (N ) = NO. OF PROJECTS IN BLOCK V 5 DIMENSION I ND E X ( 2 0 ) , L ( 2 0 ) 'V, COMMON MEX I ST , SEX I ST( 20 ) ,NUBEP ,DX ,0( 20) , 7 I 0 A T A(2 ,20) ,0(20) , ISE00P(20) ,DI NT, B 2MATI650,20) ,MAT»IX(650 ,2^) , ' 3 0 P T ( 5 0 , ? n ) 0 MIN = Y/OX + 1 >1 MAX = YMAX/OX + 1 V IP-LOCK = 0 •» ICOUNT = 0 A YY = Y -!> NUMRFR = HI MP RE 00 1 J = J J , J J J IE ( ICOUNT .EQ. 0 ) JS = J GO TO .1000 2000 WRITE (6,204) j , M I N I , MAX, JS 204 FORMAT(• J= ', I 3 , ' MIV=',I4,« MAX: 10 00 00 2 I = '-'IN, MAX 3 1 P < ICOUNT .NE. 0 ) GO TO 2 2 7 ICOUNT = ICOUNT + 1 LfNUMRER + ICOUNT ) = "AT(I,J) GO TO 2 ^6 30 00 IC. = NUMBER + ICOUNT >7 WR I TE(6 ,2 n5) J,I ,NU MB ER, I BLOCK, I COUNT,I ( IC ) 1 R 205 F O P ,--AT( 51 4, A4) j " 4 1 • GO TO 2 10 C WHETHER IT IS ALREADY IM SET L \\ 22 KK = NUMB E 3 + I 12 KKK = NUMBER + I COUNT 13 19 DP 6 K ~ KK, KKK IF ( MATII.J) .EQ. L(K) ) GO TO 2 6 CONTINUE 16 GO TO 7 XI 2 CONTINUE 18 IF ( (J-JS+1) - ICOUNT ) I, B, 2 3 IV I B IF ( J .FO. J J J .AND. TP.IOCK .FO. C ) GO TO 11 y?\ 2? 24 -> <r, C TO FOtS POINT, A NEW BIOCK IS FORCED C IF ICOUNT = 2, I.E, 2 PROJECTS IN THIS BLOCK, THEN IT CAN C EASILY FURTHER DECOMPOSED INTO 2 BLOCKS IF ( ICOUNT .NE. 2 ) GO TO 1B I BLOCK = I BLOCK + I TN0E y ( IP-LOCK ) = 1 26 t BlTOCK = ! BLOCK + I 9 7 ! INDEX( I BLOCK) = I GO T O 1 2 •2 9 j iH I BLOCK = f CLOCK + 1 30 j 1N0E X( I BLOC K) = ICOUNT 31 : r T O P . F S F T S T A R T I N G P P W FRf. P |.|'' TWT S C A ? i N 1 »-T, I F r M i t ,vf \T, rr\\\ SUBF. I l l ' TI NF A DP I S TO l ; I M r i TOTAL PUT PUT 'IF 1? C M I A O P ( v Y , M r P E >., I C O U N T , 1 . . S U M ) YY = S U " ^ NUMBER = NUMBER + I COUNT I COUNT = 0 A :'.| ;)0.< 86 " 7 M[,v = S'.jr-'/DX *• 1 y •' ' j l CONT I N U F C U P TO T H I S P O I N T , THERE ARE AT L E A S T 2 B L O C K S 10 P. T . "AT P I X . Pi" I NT01)T •V CO TO 10 • * . i ' AO OO 0 0 15 1 = 1 , 1 P L OC K I F ( I . O T . 1 ) GO TO 16 NNN = NUMPRF NN = NUMPRF + 1 GO TO 17 16 NN = NNN + 1 17 NNN = NNN + I N O E X ( 1 ) 15 U ' P I T E ( 6 , 2 0 2 ) I , I N O E X ( T ) , ( L I »••> , N = M N , N M N ) y* 2 0 ? F O R M A T ( • B L O C K ' , I 3 , » HAS ' , I 3 , ' PP OJ EOT S : • , 1 l> A- A ) GO TO 1 0 2 \ WR I T E ( 6 , 2 0 0 ) J , N U M B E R , I C O U N T, I C L O C K , ( F'OEY (v ) T I P.LOCK) ••*? 2 0 0 F O R M A T ( 1 X , ' E R R O R I N S C A N » , A I 4 , 1 O X , 2 P T A ) ; } GO TO 1 0 -•.A 1 1 I B L O C K = 1 .- r; T N O E X ( l ) = N U B F R - N E Y 1 S T GO TO in f 7 5 0 0 0 RI T E ( 6 , 2 0 1 ) 2 0 1 FOP,MAT ( « D F C O M P O S I T TON NOT P O S S I B L E ' ) 1 0 R E T U R N -• 0 C E N D A 5 C C C C SPIER OUT IN E ^ 0 ( Y , N U M B E R , I C O U M T , 1. , SUM) Y : T O T A L OUTPUT B E F O R E THE BLOCK UNO E P.C ON S I D F ? A T I ON N'JMPFP : TOTAL N O . OF P R O J E C T S ^ F O P E T H I S BLOCK I COUNT L SUM N O . OF °KOJECTS I N T H I S B L O C K A L L THE P R O J E C T S A R R A N G E D IN 0 R 0 P R OF B L O C K S T O T A L O U T P U T OF T H I S B L O C K , I NC L I'D I Mr: THOSE PR EC ^ O IMC I N T F G F P DATA D I M E N S I O N L ( 2 0 ) C O ' ' M O N NE X I S T , SF X I ^ T { ? 0 ) , M!.ln F P , i) X , O ( ? 0 ) , i - 9 • 70 V i 72 7 3 C C * 7 A 7 5 76 • 7 p. ?'i LOAT A ( 2 , ?o > , C( 20 ) , IS EwOP ( 2 0 ) , i) I N T , 2 M A T ( 6 5 0 , 2 0 ) , M A T R I X ( 6 5 o ,?0) , 3 0 P T ( 5 0 , 2 0 ) SUM = Y 12 MM = NIJMRFP + I v».'M = f,if j ' 4 P F ? -t- ICOU'-'T Of: n > = DO 1A N = IE ( L ( M ) SUM = SUM 0 0 TO 13 14 C O N T I N U F 1 , ~ — v i' y NUP FR ~. O A T A ( 2 , M 0 ( M ) ?? ; At. ) ) GO TO 1A J7 •oo 1 C'NM I MUE 3 F T U R N END C C SUBROUTINE C <i STOP ( 0 r S T I ,C.0ST2 ,NA'<F,K, 7, 7 A X ) INTEGER NAT A f. CnSTl : COST BEFORE AOOINO THF NEW PROJFCT C COST2 : COST AFTER AOOINO THE NEW PROJECT C NAME : NAVF OF T OF M<=V PROJECT C R : NEV. P! OJEC. T» S 'OS I T ION IN T11 [} POLL SE 0 J~ C Z : TOTAL OUTPUT OF OPTIMAL S c CUE NCR BEFORE C ZNAX : TOTAL OUTPUT OF OPTIMAL S.EOUENCF !"CLU~>T COMMON NEXI ST.SEXI ST(20) , NU Q F R OX ,0(20 ) , 1 r AT A ( 2 , 20 ) , r. ( 20 ) , I S rorp ( 20 ) , 0 I NT , 2 " A T ( 6 5 0 ,2 0 ) , '•* A T K IX ( 6 5 0 , 2 0 ) ,  30PT ( r)P , ?0) DOUBLE PR EC IS TOM ni_ OG , CO S T 1, CO S T 2 , T , X , Y 00 1 1 = 1 , NU PER IF ( N A M F .NE. P A T A(2 »I ). ) GO TO 1 IF ( K .ED. 1 ) GO TO B X = Z  C Al L TIME ( X , T ) 6 7?N\X = Z + 0(1) C0ST2 = COSTl + C U ) / (1.0 + ^ I NT) ** T GO TO 4 1 CONTINUE 3 COST? = C(I )  X = 0.0 Y = 0.0 ZMAX = 0(1) 4 GO TO 2 4000 WRI TE (6 ,? CO ) Z»X, V,C(I ) ,0(1 ) , COS T ?, NAM. F POP FOR'-'AT ( ' Z = « , F « . l t - X=',0 1 5.7,' L C<~- * = ' , C 1 5 . 7 , ' 1,' COST I- > , 01 5. 7, • N A F = ' , A 4 ) 2 RETURN END C C C SUBROUTINE CDPYJX, XMAX) INTEGER SEXIST COMMON MEXI ST,SF X IS T( 20 ) ,MUBER,0X,0120) , 10 AT A (? ,?0 ) , C( 20 ) , IS EQL,ri (2 n),DINT, 2 MAT(650,20) , MATRI X(650 ,?0) , BQPT(50,20)  f '•' I N = X/DX + 1 1 MAX = X" A X/DX + 1 DO 1 I = IMIN, IMAX L L = 0 00 2 J = 1, NUBER IF ( N EXIST . CQ. n ) or, TQ 6  00 3 K = I, NEX1ST IF ( MATRIX(I,J) .-Q. SFXISTCO ) GO T n 4 3 C ONT I CUE 6 MAT(I,J-LL) = MATRIX{T,J) GO TO 2 4 I I. = LL * 1  2 CONTINUE 1 CONTINUE GO TO 2000 1000 IF ( NFXIST . ^ Q . 0 ) GO TO 5 VM' I T F ( 6 , 2 n l° ) ( S r X 1 S T ( N ) , M = 1 , NF X I S T) ?'ip r r<~~ \ T ( 1 S c Y f S T : • , O A4 I 5 NN = NUBE;> - MEXIST 0 0 11 I = I IN, IM AV XX = ( 1-1 ) * OX 11 V'P1TE(6,201) VX,0«,T( !,••!) ,N=l,MN) 2 01 FORMAT(EB.1, 20AA) 7•''•00 RFTIPN  END r C c SUR POUT I f"E L B S ( J S T A: < T , J F N 0 , L , C 0 S T , 0 U T P U T ) r C J STAR T i START I MG COLUMN OF TiT5 1 ?•'-»c P E EC T S'j';-BL0F 0 JENO : FN00 TNG COLUMN OF THE y >.i PERFECT SUB-PIOC.K C L : MAMF OF PROJECTS IM ORDER OF SJF-Bl. nC<S C COST : CSQT OF LBS FOR THE IMPERFECT SUP-P. LOCK C OUTPUT : OUTPUT OF LBS FOR TMfc IM P FR E EC T SUB-BL')C:< r T INTEGER DATA DIMENSION L(20) ,C0ST<20) ,OUTPUT(20) CO''"'0\i M EX I ST , SEX IST{ 20 ) ,NURE" »0X ,0< 20) , 1 DATA(2 ,20) ,C(23) , I S E C ™ (2^) ,DINT, 2-AT(6 C0,20) , MATsT X(650,70) ,  3CPT(50,20 ) 00 1 I = JSTAP.T, JENO DO 2 J = 1 , NUP.ER IE ( L ( I ) .EO. OATA(?,J) ) GO TO 3 ? CONTINUE 3 CPST( ! ) = C(J) OUTPUT ( I ) = (UJ.) 1 CONTINUE IF ( JSTA^T .EO. JE'ID) GO TO 2000 DO 4 I = J STAPT, J END TESTC = COST(I) TESTO = OUT PUT( I ) IIC = I 110 = I DO 5 J = I , JE ND IF ( TESTE. .LE. COST(J) ) GO TO 6 TESTC = CGST(J) I [C = J  (•> IF ( TESTC . G E • OUTPUT(J) ) GC TO 5 TESTn = OUTPUT(J) 1 If1 = J 5 CONTINUE IF { I IC. . FQ. I ) GO TO 7 STOP F - COS T( I ) COST ( I ) = T ES TC C 0S T{ I IC) = STOPf 7 IF ( I ro .EO. I ) GO TO 4 STORE = OUT PUT( I ) OUTPUT(I) = TESTO OUTPUT ( I t f ) = STO">F /, CONTINUE CD T l 2 n n 0 1000 './RI T^ (6, 700) (COST( N) ,N^JSTA" T, JENO) 2 00 FORMAT(' COST = » , 20F5 .0 ) • V,f» I TE ( 6 , 70 I ) ( OUTPUT ( N) ,N = JST APT , JFND) ?">! FOR"AT ( • r.i| TPUT= » , ?0i--/,. n) •?r-rO RETURN ran r. ^ 8 9 C C r S U P . R O U T I N E LOS ( I N 0 R * , 11 . ^ T • [ S T A G ! " , I , S , I V , K O K ) I T R GF P S , D A T A 0 IMF M S I 0 . N S ( 2 0 ) C OM M O M NEXT S T , S E X I S T ( 2 0 I , N ! J " r p ,OX t O ( 2 T ) , 1 0 A T A ( 2 » 20) , C ( 2 0 ) , I S E C D ' M ? R ) , ' M N T , 2 A T ( 6 * 0 , ? O ) , v A T R I X ( •% 5 0 , 2 0 ) , i • c 3 C P T ( 5 0 , 2 0 ) h I r C c I N D E X : N O . o c E L C M F N T S I N T H I S ?• 1. OC K >- I 0 PT F, I S T A G ' - H A V E T H c I P. T ' N J E MCANINC, A $ f !E ;F TM«- 0 T M o } 0 0 . '-' A T ?• r S : A S E Q U E N C E W I T - I ( N N + P ' O E X ) E L E ; V E R T c , T H C S T •V "N ^ 0 r r.' T s ^ c A P E S U P P L I E D BY I N P U T , T H E P E S T 4 p . r rOUN 0 I :V T-1 r s S U B . r I : T H E E L F OF N T A T I T H COLUMN I N M A T I S S (MM M » c I N : T H F E I ^ S T POW MUMPER I N MAT c r KOK : = 1 MEANS C l J M O L E T F 1. . 0 . S . = 2 M F \ M S I T . ' " ^ l . r T r L . O . S . i C c I S I = I S T A G E S ( I S l ) = ' V A T ( I N , I ) . n L L L = 1 + 1 > • !. r I w 0 w 1 I S A P 0 W A T S v A L L E C' 0 E A r: 0 L E V E L O M N T P O v ? I N T H I S i. ? l i O w 1 = " I N >U = 1 S T A f. E + 1 - 5 M,3 = I O ° T + I N D E X nu = TOPT + INDEX - I S T A G E + 1 • A 0 0 3 3 M = M l , M 3 . 7 r TO F I N D P R O J E C T ' S O U T P U T C A P A C I T Y = r - i */• 'i 0 0 3 4 I I = I , N U B F R I F ( S ( ' • ' ' ' ) . E Q . D A T \ ( 2 , I I ) ) GO T O 6 0 %\ 3 4 C O N T I N U E •' 2 6 0 I R 0 W 2 = I r - ' O W I + 0 ( T I ) / O X r T O P I \ D T H E P R O J E C T F O ' J MTU P O S I T I O N I N S E ~ 0 " I " O N 2 T • \ 0 0 3 5 K = 1 , M 4 r. T O S E E WH f TM P R M A TP I X( IP 0 W 2 , K ) T S A L R E A D Y P ! $ DO 3 6 L L = I S I , M>-. %7 IF ( v A T ( I * O W ? , K ) . F O . S ( L L ) ) GO TO 3 5 3 6 C O N T I N U E ' n r I S NATR IX ( IRHW ? , K ) E L I G I P I . F BY C O N O I T I O V I N I ? rv., \ or S ( M" ) DO 3 7 L L = L L L , v ^ I F ( M A T ( I R 0 W 7 , K ) . E Q . J / A T ( I P O'/.'l , L L ) ) G O T O • • ? UL 3 7 C O N T I N U E • 3 3 5 O f ' M T r NUF •A r C O '•• PL E T I ON O F 0 0 3 5 MEAN S L O S T M C 0 " P L E T F f. •• T y- on S I T I ON M H T c I L | _ FO ' r > 4 1 KOK = 2 I 1 E ( 6 , 2 0 ^ ) T S 1 , S ( I S l ) , ( S ( N ) , N = l , N " ) ' 7 2 0 3 F 0 \ M A T ( / , ' S T A G ^ ' , 1 3 , ' 1 DOE o r C U P I E P f V ' , At , ' p r o 3 L E T c L . " . ^ ' '•. B 1 . ' , / , 1 0 X , • S = » , 2 0 A ' f ) GO TO 5 6 ' ? n 3 ° . S ( f ) = MAT ( I R 0 W 2 , K ) 71 IT ( " . F . ,'"> ) O r TO B<> • 7 I T ( K . N T - . M 4 ) 00 P T A I M M = M G O T D 41 ftl I P O W I = imw?. I . L L = K + 1 7 3 C O N T I MM I F 90 T C O ' - ' P L E T I O N O F O J 0 3 ' - ' F A N S L . O . S . I S C 0 ' ' ° L E T E 30 K O K = I W R I T E ( 6 , ? 0 7 ) I S I , S ( I S 1 ) , ( S ( M ) ,0 = 1 , M ) 2 0 7 F O R M A T ! / , ' S T A G E ' , 1 3 , ' 0 0 0 E O C C U P I E D P Y ' , A £ , ' H A S C O " P L E T F 1 , / , 1 0 X , • S = • , 2 0 A 4 ) 5ft R F T U R " r C C F N D S U B R O U T I N E Z I 0 7 . A G ('•• IM , I N D E X , I Z I G , I P O S , I O ° T , I S T A O F ) I N T E G E R D A T A 0 I :•' E N S 10 *.' L ( 2 0 ) C O M M O N M E X I S T , S E X 1 S T ( 2 0 ) , N U P. IfP , O X , 0 ( 2 0 ) , 1 0 A T A ( 2 , 2 0 ) , C I ? 0 ) ,ISEOOP ( 2 0 ) , 0 IN T , i 2 MAT ( 6 C 0 , 2 0 ) ,"ATRIXt 6 5 0 , ? 0 ) , c 3 0 P T ( 5 0 , 2 0 ) (.. c MI N : STARTING ROW OF MAT > c INDEX : NO. OF ELEMENTS IN THE PL OCK UN OER CO"RI0 F P AT IO'-1 c L : T H E SET CONTAINING E 11 0 I B LE EI E >.' P N T S A F T F R THE <"  0 n E ".0 c IZIG : = 2 MEANS THE NOOF WITH I M T ON' p|_ ET F LOS OA or n r <;r A r p P D . 1 c = 1 l'E\NS N O O F RE T AI N F 0 » T H O U G H I . n . c . IS I *.rf">'' • N r r F . 3 *4 C 0 c c c c 7 M A X E N O D I N O D E M A N D O F T H I S B L O C K C A L C U L A T P' T ^ I S S O B R 0 1 J T I ^ E " 0 N U M B E R = I O P T + I N D E X - I S T A G E + 1 - I P O S C i ^ c N L K - 8 F R : N O . O F - E L E M E N T S I N S E T L ' 1 c 1 2 0 0 1 T = 1 , N U M B E R ' 3 .i 1 L ( I ) = M A . T ! I N , I P O S + t ) c c c T O F I N D T H E S T A R T I N G R O W K M I N A N D E N D O I N G ? R > W K'»AX A 0 0 0 2 0 2 3 0 0 0 W R I T E ( 6 , 2 0 2 ) I ' V 0 E X , '•' I N , I F O S , N U M B F R , ( L ( N ) , N = 1 , N U V - ? S R ) F O R " A T ( • I N D E X , ' • ' I N , I P C S , M U « B E » : • , c 1 4 , 5 X , ' L : • , ? i ; 4 ) 0 0 2 1 = 1 , N U P F R . 1/' ( O A T A ( 2 , I ) . \ F . " . A I C I N , O N . ' S ) ) ( N = M I 11 + 0 ( I ) / 0 X TO ? K M I C O C O N K M A 0 0 T O 3 T I N U F X = K M I N A 1 = 1 , NUMBER 00 I F K M A G O cor1 err 5" J = I , NURE R ( D A T A ! ?,J) . M E . L ( I ) ) X = KM A X + 0 ( J ) / D X T O 4 T f N1.) E T T NU F G O T O 5 I/. ir-AX = ;<MAX I ' - ' If = KM IN GO TO 5 000 6000 WR I TF ( 6 , 206 ) I M I M t I MAX 206 FORMAT (• I " I 0- = » , T 4 , 1X , » T M A X = ' , I 4 ) <"^fO J£NP = |vpny + fppT _ [STAGE + 1 91 C r. c DO 6 I = IM[N, I MAX TO FIND TH E CLE F N T TM SET I POSITIONED I F F T E F S T IN 00 7 J = 1, JFND • • AT AT Rr i 00 p L l . = 1, NU^ER IF ( A T ( I , J I . N e . L { L L ) ) 0 0 TO a >* c * fS c THE L F F T F S T ELEMENT IN L HAS FEN N FOUND. CAN IT JOIN SET L? • 7 f. J I F ( J .EO. J END ) GO TO 6 1 > /• "1 J J = J «• 1 00 9 J J J = J J , JFND X c - 2 r I S I T THE ELEMENT 00COPYING THE NODE? • i C. "A IF { M A T ( I , J J J ) .EO. MAT(MIN, IPOS) ) GO T O O i; 5 0 c is IT ALREADY IN SET L V G 00 10 LLL = 1, NUMBER I F ( AT ( I , J J J ) . FO. L U L L ) ) GO TO 9 10 GO." i T I NUE >-1 G .4 S6 ,7 r C TO THIS POINT, THIS ELEMENT SHOULD B E APPc 0 TO SET L NUMBER = NUMBER + I L(NUMBER) = MAT( I, J J J ) GO TO 1000 20 Oo WP I TE ( 6, ? o i ) I, NIJMBFR, L( VUMBFR) Vo 71 7 2 ? 3 C C C 201 FORMAT! ' AT ROW, I'*, 3X , • NU MB F H= ' , I 4 , » RESET T'AX 1000 DO 1 I 11 = 1, NUBER IF { 0 A T A ( 2 , I I ) . c 0 . L(NU'-'RE^) ) 0 ° T' I. (NO . ) = • , A4 ) 74 7^ 7 7 7H 7 9 11 CONTINUE 12 KMA X = K.MAX + 0! I I ) /DX 9 CONTINUE IE ( I MAX .FO. K M AX ) GO TO 6 c C SEE WHET Hi S ET L HAS ALL ELEMENTS U \ 2 3 3 3 4 3 5 IF ( NUMB Ef KMIN = I + GO TO 14 CONTINUE CONTINUE EQ. (JEND-1) ) GO TO 13 •i6 4 7 8 3 •M9 !90 M C r WRI T E ( 6 , 2 04) 204 FOR MAT (» n r 7 CC' V DL F TE . E R R O ° IM ZIGZAG') 6 CONTINUE IF ( NUMB FR .EO. (JEND-1 ) ) GO TO 13 C O '•' PI. E T TO N OF 00 6 MTA-VS s^T |. M f , T OO'-'-P I. E T F . f f -"i c -ui;r>.D i c. 16 I 2 I G = 2 W»U T F(6 ,?OS ) ' 11 IG , I NO FX , NUMf^R, (I. (N ) , M= {, NIO-RF;? 1 92 •> 205 ro.RMAT( » IZI 0 , 1 M O E X , N U M B E ° , S E T L : ' , 3 I 4 , 2 0 A4 ) WPITE(6,207) v 7 207 FPM'.MI/, 1 THIS NODE IS DISCARDED' , / ) r ~r GO TO 15 13 IZIG = I V>. VP I TF. (6,205) I 7 1 G , I MO F X , 00 MB E R » ( L ( N ) » N = 1 » Nl I .M R E P ) WPITF(6,20P) •> 208 FOPMAT(/,' TH r S NOPE IS RFTAINEO',/) " 3 15 RETURN  END C V C 7 0 •3 C KJj> SUBROUTINE l.P.(Z7, TOO, I 0 L , 1. S E T , P W L P S )  DCUHLF <,">•> EC I S I ON "WHS , A, X ,01.00 ll COMMON N EXIST, SEX IST( 20),NOREF,0X,0(20) , '•V 1 DATA (2 ,20) ,C( 20) , IS EOOP ( 2 0 ) , 01 NT, < ? 2NAT(650,20) ,MAT RI X(6 5 0,2 0) , : 'i 30PT ( 50 , ?0 ) K L ~ 01 NF NS I 0N I NO (20) , L S ET ( 2O ) , OPT "NT (20 ) ,COS T ( R R )  i~ r. V3 I -C ll : STARTING DEMAND LEVEL i 9 C NUMBER : A CO I IN T FR , I ND EC ATI NG HOW MANY F L E '-'E NT S I N SUB-BLOCKS AI READY N-i C USED IN COMPUTING POL P,S ' '2 C K'3 NUMBER = 0 *4 DO 22 L L = 1 , IB L ?5 JSTART = NUMBER + 1 .'-'6 JFNO = NUMBER + IND(LL) 2 7 NUMBER = JEND +•'> •">. CALL L B S ( J S T A R T , J E N ),LSET,COST,OUTPUT) . 9 c -,o C TO FIND PWLBS FOR THIS IMPERFECT SUB-BLOCK. V l c •2 00 23 LLL = JSTART , JEND 5 3 IF ( l l . L .NE. J S T A ^ T ) GO TO 25 »*3 X = ZZ GO TO 24 ••• 25 X = X + OUTPUT( LLL-I.) V/ 24 CALL T I-'-'E (X , A ) 25 PKLBS = PWLBS + COST! LLL ) / ( ( 1. .o+o INT )**A ) 31 n = x + OUTPUT(JEND) Is COOT I N U E 1 WRITE ( 6 , 20 l ) P'.-.'L.BS 4 ? 20], r 0 P '•' A T ( // , 1 OX , 'PV.LB S =',020.11 ,///) k*3 RETURN -4 E ND r r ' 7 C C S UP R OUT I NE A N C H (Uri, I CAN!), I 0 PT , OPC 0 S T , I , .'MAX , I S T A 0 r » I \:n'X , KOK ) 5 O • 1 INTEGFP SEXIST, OAT A, OPT DOUBLE PRECISION 'JB , P'.U.ns, Y , ONCOST D I *•' > N S ION L ? P " i ) , M->?( 2 0) , L S f " T ( ?D) , P f. ( CUMNUN '.'FX I ST , SEX I ST ( 20 ), NUB E'- , HX, D( ?o ), J 1 1DAT A ( 2 , ?r>) ,r ( ?o) , I SFQOP ( ?o) ,ni r;T, 9 3 1 •' 1 2 w AT (( >c0 , 20 ) , M ATP I X { 6 50,20) , V ! 30PT{50,20) 7 C r c ICAMO : NO. OF SEQUENCES IN OPT, INPUT F. OUTPUT K c. c IOPT . THF 1ST IOPT CFLU"NS IN OPT A'-?F KN'HvN ° 0T I '•' IMPUT r, OUTPUT AL SOLD T IONS, } c OPCOST : OPTIMAL COST SO FAR FOR THOSE IOPT PROJECTS , IN'PUT "5 0 7 : A G C. * A 0 A T E r' 0'ITPIJT OF T«OS= IOPT P<^n JECTS, J N P 0 T t r. 7. M A X : ENDING OUTPUT OE THE PL OCA IN Pf 00. MA IN, I MP t.lT F I STAGE . f ; r n c <; A-jp ADDED TO { T S T A G E + 1 ) TH STAGE, I N POT c. INDEX : r.O, OF PROJECTS IN THE BLOCK f M pPOG. 'OR!, I VPUT 7 c KOK = I MEANS PRO PL FN CA*' START F R p •'• • ,:LGiMNI\'G \ G A I c = 3 MEANS ( 10 R T + I NDE X ) = ( I STAGE* 1 ) ,H E f ;C F 0°T . S r 0 . K NOH -V PY P r. = 2 V nANS ( 1ST AG- + 1 )TH MPO = S NFFOS '-'OR - A 'VA 1 v S I S c = 4 v E A N S 0 I MF'iS I ( N Of OPT IS EXCEEDED i :r?-c c ' 7 T, I EL I MI - 0 4 IE ( ICAND .NF. 1 ) GO TO 27 c ONLY ONE MODE AT T H I S STAGE, SO ITS OPTICAL OOSIT I^ M T S KMO..'*! I. -. t Vrr I TE ( 6 , 2 I 2 ) I STAGE ->7 7 1 > ? ! > F C P . M AT (//, IX, ****** THERE IS ONI.Y ONE BR A NO' R E '•' A I MI K'r, \ T STAGF ' , 113,' * * * * * * , / / ) • 7o NEXIST = IOPT ,i o CALL CORY(Z,Z) •' 1 = 7/DX + 1 IF ( 0 P T( 1 , I 0 ° T+ I ) .EN. MAT(^IN,l) ) GO TO ?B N N = NUBFR - IOPT W'RITE(6,?13) ( "• A T ( M IN , N ) , N=l,NN) 2 13 F OP v- AT { / , 1 X , 3 ( 2 X , • H EL P ' ) , • f'.ATl MIN.N) =• ,2" A 4) KOK -= 4 ; 7 GO TO O^Q "• - 2B JSTART = IOPT + 1 ' ;R IOPT = ISTAGE ...RO NEXIST = fST-A.GF * l D O 12 J J = JSTART, ISTAGE '2 ISFCPP(JJ) = O P T l l , JJ ) SEX I ST(JJ) = 0^T( 1 , JJ) PWLfS = OPCOST CALL C O S TCP( nWLOS ,0 12 Z = ZZMAx PCOST, IS E OOP(JJ), J J, 7, 77-AX) r T A '< F AWAY ALL FL EVENTS A L R E A D Y T N 0 ° T I '•' AL SFOOFNCF, THE REST CAN •'.3 c S T A F T A T THE PEGPNIND V. R I TE ( 6 . 2 1 4 ) 10 3 T, { I SFfOPC M ) ,N=1 , I i PT) 214 F O R -A T ( / , ' POSIT!VI S 1 T J 1 , I " , » [N .r yT r v i L s •- 0 u (--.; r c A - E "10 0 UP 1 c M 11 1 BY' , 2 M A 4) .1 7 W P I T E ( 6, 20 7 ) NT 237 FORMAT(/,' THE REST PROJECTS C A ;V S T A FT .'>FRFSH',//) •;4 K.P.K. = 1 Of1 T O ''6 C 07 C BEGIN ( ISTAGE* I ) TH P. R A NC H I NG , I . E . THE ( I S T A r E + I - I 0 ;-> T ) T u STAGF NO^E .BB ?7 1ST AGF = I S T A G E + 1 ^•5 WR I TE ( 6 , 2 0 6 ) [ S T A G F 1 0 R 0 6 F O R M A T ! / , ' . TO F I N D ' , I 3 , * TH S T A G E N O r F s rvnv P R E F E R F NC E M A T P iy, , // ) ... > 2 = ICAND M = ICAND • 3 8 I START - Ml 9 4 I END = M 2 • / . GO TO 1000 >• 7 20 on W«ITF(6,201) M l , v? , ICAND F OP AT ( / , 1 Ml , v 2 , IC AND : ' ,314,/) - 3 i C 1030 DO 3 0 NOPE I = I ST APT, TEND ' 1 r. TO FIND COLUMN \HJMB E1* OF THE PP F C E 0 I NO NODE - 7 c ^ -, N E X I S T = I S T \ G E - ? - + IF ( NEXIST .N^. 0 ) GO TO 5 ZZ = z : > '•• GO TO 1 7 5 DO 6 M3 = 1, NEXIST -"!3 6 SEX I ST(M3) = O^T(N0DE1 ,M3) c j •"• C TO FIND OUTPUT DEMAND LEVEL EXCLUDING TEE LA ST N O D E •* 1 y ~ l2 c IF ( NEXIST .NE. IOPT ) GO TO 4 - T. 1 1 - 1 k 4 GO TO I * 5 4 I I = NF X I ST - IOPT j> *^  IL = 7 M>7 DO 2 I = 1 , 11 DO 3 J = 1, NUBER 5 -? •»0 IF < DATA(2,J) .NE. OPT(NODF1 , IDPT+I ) ) ZZ = ZZ + 0(J) GO TO 3 GO TO 2 3 CONI r.NUt 2 CONTINUE 1 GO TO 3000 5 4000 WRITE(6 , 202) ZZ 4 6 20? FORMAT!/,' ZZ =•,F9.1) 7 ? o n o MINZZ = ZZ/DX + I CALL COPY(ZZ.ZZ) 49 r ^ n *- -• r. M M : NO. QF FLEMENTS IN INDEX ALREADY IN OPT c c2 MM = I STAGE - 1 - I OPT " o p c --4 c M M : NO. OF REMAINING ELEMENTS IN INDEX + THE ° E C F N I \ G f O D E • 55. c MM = INDEX - MM + I *7 GO TO 5 000 =• 8 6 ">C0 WP. I TE ( 6 , ?00 ) MM - o 2 00 FOR M AT ( / , • M V = i , ». k. H O 0 0 NExisr = I SI AGE - 1 ''• I DO 31 J = 1 , MM • P ? IF ( MAT (MINZZ, J) .EO. OPT ( N - D E I , N f c X IS 1 ) ) GO TO 32 31 CONTINUE -A 32 LOC = J LL = M M _ J >6 DO 33 LLL = I, LL • 7 33 NC2(LLL) = ''A T ( M I NZ Z , LOC + LL I ) v 6 « f NN = NODE I + I El IM 1 V0 9 NN = I STAGF - 1 70 WPITE(6,216) NNN, ( OP T ( NODE 1 , ) ,N = 1 , f. w) ? 1 ? 1 6 F 0 R M A T ( / , 1 r-no BRANCH N! I M D F f-' • , I », ?nf u ) v.-p I TE (i., 2 70 ) (nn ? ( N ) , N -1 ,11 ) 220 r 0 P A T ( ] ?Y , "SET N ? : ' , 2n^'») s r x i S T ( N E X L S T ) = O P T ( \nnni ,r:rx i S T ) 9 5 C A L L C O S T C P ( O P C O S T , P r . ' L O S , C-F X I S T ( N E X I S T) , N E X I S T » 7 7. » Z 2 ) C I-* r 7 2 : STARTING QF M A ftf) L r V F l FOP THF I ST S'iF-moCK >> V C 0 MIN2 = Z7/DX + 1 CALL C 0 P Y ( Z ? , Z v A X ) CALL RLOCK ( Z2 , 7. VAX , 1 , JENO, I VO, J PL , L SFT ) • r ONLY ELEMENTS IN POTM NO? f. T H E 1ST SUE-EL Of. K C A N P F TOE •N F- v T MPpf-.V 7 l. INDl = T N D ( 1 ) LOC = 0 DO 34 LLL = I , LL DO 35 II = 1, INDl > IE ( N C ? ( L L L ) . N E . LSET(II) ) GO TV 35 J IOC = LOC + L * L2(LOC. ) = NO? (LLL ) i GO TO 3 4 3 5 CONTINUE ^ 34 CONTINUE  IE ( LOG .NE. 0 ) OO TO 36 ,.7 NN = (STAGE - 1 •> NNN = NOD El + TEL IM I '..RI TF( 6,715) NNN , ( 0° T ( NODE 1 , N ) , M = l , f1 N ) 1 "> 215 F 0 R '•' A T ( /, * F^ANfH NIP- 3 E ^  ' , I 3 , 20 A 4 ) j , 14 W P I T F ( 6 t 2 1 0 )  ~ 2 10 F F. - A T ( • THIS ^ANCH IS ELIMINATED, SINCE NO P'-'^JFCF CAM ^'LI 0,-1 FT 3, 1 • , / ) ^ ICAND = ICAND - 1 '5 TEL I f 11 = IELIMI + 1 IF ( NO DE 1 .EO. ICAND + l ) GO TO 30 •7 C_ ' "~ C DELATING THOSE IN 0 DT C IM 1/3 = - IELIMI V l n 0 3 7 J J = NODE 1 , 0 3 7 DO ? 7 LL = I, NEX 1ST ]_i 3 7 OPT(JJ,LL) = OPT(JJ+l,LL)  ;1 4 IF ( ICAND .LE. ' ' 3 ) GO TO I 7 f5 M3 = 03 + 1 16 DO 18 J J = '-'3 , IC AND VT 00 IP LL = t, I STAGE • 0 - J IP 0°T ( J J , LL ) = OPT ( J ) +l,L 1. ) \ '1 17 Ml = NODFl v2 = I rN0 - 1 i l IE { NODEl .EO. I END ) GO TO 30 •2 GO TO 3 8 /3 3 C-. IE ( LOC .GT. 1 ) GO TO 39 IF ( f'A T ( v I N2 , I ND (1 ) ) . r E . L 2 ( 1 ) .OP. IN 0( 1 ) . c ? . 1 ) G O TO 13 M , V = I STAFF - 1 * ^ N N N = N O Of 1 + IELIMI / 7 WPl TF(ft ,2 O R ) L2(1 ) , NNN, (OPT ( NO P F 1 , N),N = 1 ,N N ) ? -1 20 5 F 0 f' A T ( / , • F L E 0 E N T • ,A4,« A P P c Ac S El IGIDLE E 0 ;• T u F N F x T N nDF ON OP. A 9 i NCH NU"MP,FR ' , I 3, 20 A4 ) 3n V;R I T c (6,200) r r , v,» T ( • (0 I T IHJC T T N °N S T T I r'" A T T H" f - S T r ^>.' J f T V T. 1 r T S N3-a —-* I LOCK, IT IS IN FACT N N'T E L I !i I PL ?•' ' ) s 0 0 TO 14 13 fPT (NOOf-'1 , I STAGF 1 = 1 2 ( 1 ) 9 6 WRI K (6 , 2 P U n n j ( N 0 0 E 1 , 1ST AGE ) GO JO 3 0 10 IF ( L O G . G T . 2 ) GO TO 54 * - or, A i L L = 1 » 2 IF ( NAT ( VTN? , INO( 1 ) ) . NF . L 2 ( L L ) ) CO TO 41 > NN = ISTAGF - 1 NNN = NOOFl + I E L IN I ) IF { I 1. .FO. 2 1 GO TH 15 •y,3 W R I T E ( 6 , 2 ° B ) L2(1 ) , N MN , ( 0 !°T ( NODE 1 » N ) t 1« N'! ) £'. Wi- I T- ( '.,2 09) OPT ( NO OF 1 , ISTAGE ) = L2C2) v. 16 W K I T E ( 6 , 2 1 3 ) 0,;)T{NOOE1, ISTAGE) -'• 7 GO TO 30 , .7 >. 15 WFITF(6,2rn) L2(2), NMN, (0 P T(N 0 0 E1 , N ) ,N =1,N N )WRITE(6 ,209 ) h.—~ OPT ( \! OF 1 , I ST AGE ) - L2( 1 ) GO T O 16 .? 41 CONTINUF "3 C 4 0 NO . OF ELIGIBLE '"MRPJECTS FOLLOWING PRECEDING f : 0 ^ c IS .GE. 2 "•^ f. * "J 0 TO; tLI'-UNATr THE ONE CLE *• F N T IN SET L2 WHKH IS TH E -I I OH TEST TN MAT ->? c ** ON THE 1ST ROW, SPICE IT CAN'T PR TH F ME XT NODE .! : P 54 00 5 1 LL = 1, LOC IF ( '* AT ( '-• I N 2 , IN R ( 1 ) ) .ME. L 2 (I. L ) ) GO TO 5 1 r NN = I STAGE - . 1 M.Ni'i = NUDE 1 + I ELI MT »-3- WRITF(6,20«) L 2(L L ) , NNN, (0?T(NO OF 1,N) , N= 1 , N N ) •*4 WRIT c(6,2 09) >5 GO TO 52 -;6 51 CONTINUE • 7 0n TO 4 0 > -r y- 52 LOC = LOC - I ,.o IF ( LL .EG. (LOC+1) ) GO TO 40 "7 ^ ' » J *• • 00 53 LLL = I L , LOC ^1 53 L 2 ( LL L ) = L2ILLI+1) 72 c 7 ? c. TO CHECK WHETHER A 1)01 NG T H r NEW NOOES WILL FXCFE o n ! •<FNs ION OF OPT • ** C ^5 AO IF ( (ICANO+LOC-1) .LE. 50 ) GO TO 46 7JR WR I TE { 6 , 2 19) ICAND, OP T ( MOD F 1 , I S T AGE- 1 ) , { 1.2 ( N) = I ,L 00 ) 7-7 2 1-9 FORMAT {/,' DIMENSION OF OPT EXCEEDED, ICANC=1 , I 4 , * N OQ F 0 ° T = ' , 75 1A4,/,' F. RANCHING FROM THIS NO DF :',20AA) 7 1 KOK = 4 • 'i 00 TO ';sD >J1 A 6 OPT(Nont 1 ,I ST AGE) = L2(1) •V P. 1 TE(6,21 1 <) O ' T p ^ o o F l , ISTAGE) >3 2 1 ? FORMAT { ' P P T=' , A4) 3 4 I! = ICAND + 1 1 5 1 I! = I r At- n + i oc - 1 V r o A 2 Ll. = i f , i n 00 A 2 J J = 1, ME XI.ST •'vH 42 OPT (Li. , J J ) = 1PT ( NOO" 1, JJ ) 00 A3 LL = 2, LOC OPT( ICANO + Ll-1 ,ISTAG r) = L 2{L L) "I A ? W I T f (/, , 2 l 3 ) R , P T ( IC A•'r; *• i | - 1 , \ s T A G c ) I C Af'0 = T I I i o r.OM T I NU E C 97 r ALL THE NEW P0D r S HAVE BEEN A0n r0 PM C /,s P P 4 4 i = i , rr, A MO  4 4 WRITE! 6,217) I, (0 ; 3T(1,N), N=1,ISTA0E) 2 17 F O R M A T ( 1X, 'OPT! • , I B , ' ) :',20A4) KOK = 2 IF ( ( I OPT+1NOEX) .NE. IS TAPE) 00 TO O^o C 0. E L E NE NTS PE TH* BLOCK IN 0! JEST I P N HAVE P F AC-'^ O LAC-T STAGE, Tn r- I T u 0 "C ONE WITH LONEPEST P . 0. , W H I C H WILL P E T H E 0 - ' T C JSTAPT = IOPT + 1 WRITE(6,204) 2B4 FORMAT!/, ' UB PRINTED HERE IS NDN-C ONVENT I ON AL ' ) 00 7 I = 1, TCANO  X = OPCOST 2.1-7 00 P J = JSTAPT, I STAGE CALL COSTOP ( X ,PWLOS , 0'> T { I , J ) , J , 2 I , 11N A X ) 17. = Z7.-"AX 8 X = PWLOS  v P. I TE ( 6, 203 ) I , PWLOS , UB 203 FORMAT(« O P T ! ' , 13, • ) HAS PWLOS =',020. 11 ,' IP =',020. 11) IF ( I .NE. 1 ) GO TO 0 10 UB = PWLOS LOC = I GO TO 7  9 I F ( PWLOS . E E . UB ) GO TO 7 GO TO 10 7 CONTINUE DO 11 J = JSTAPT, I STAGE 11 rSEOnp(j) = OPT!LOC,J) WP I TE ( 6 , 205 ) UB , ( I SEOOPf f O ,N = 1 , I STAGE) < 2 0 5 FO^AT!// ' UB= ' ,020. 11 ,/, • PTIMAL EQU NCE SO FAP : ' , ? rN \ 4 ) •1 KOK = 3 soo PET UP N •'1 FN 0 i 2 C c c SUPROUTINF POSTOP(NUMBER) INTEGER DATA DIMENSION COST!2), 0UTPUT(2) DOJBLF PPECISION R1 ,P2,TX , TXO,X,X0 , DT 1,0T COMMON ME x i ST, S cXIST(?0) ,NOR FR , DX , 0! 20 ) , IP AT A(2, ?0) ,C( 20 ) , IS C H. J< 20) ,'MNT, 2MAT(6E0 ,?E ) .MAT" IX ( 6 EO ,20) , r •3 c 30P T! 5C,20) c • r r TMI ^  SUB -PUT I M c n E R E E) 2 S S F N S I T I V I T Y l \N A L Y S IS c C NUMBER : T H r S E POSITION'S IN OPTIMA L SEQUENCE A- E FX£"IN cO. C WRITE!6,?00) NUMBER 200 FORMAT!//,' SENSITIVITV ANALYSIS:',//,' CUT-JFF ^OINT i v T H E O P T ! 1 • 1 AL SEOOEVC^ T S POSITION' ,13,//) C c FOR PROJECTS R RF CTO I MO I S F COP( Ml 1 FR ) c 98 - IF ( NUMBER .EQ. 1 ) GO TO 10 I STOP = NUMBER - 1 • 7 00 1 IPOS = 1, ISTOP I COUNT = 0 V DO 2 11 = 1, NUB ER w IF ( DATA(2,11) .NF. I SFCOP( IPQS) ), CO TO 3 1 COS T(1 ) = 0( I I) 7 OUTPUT!1) = 0(11) ICOUNT = ICOUNT + 1 GO TO 4 >-' 3 IF ( DATA (2,11) . N,r~ . I S F OOP ( I PO S + 1 ) ) C.o TO COS 112) = C( I I ) • 7 OUTPUT(2) = 0(11) ) B ICOUNT = ICOUNT + 1 * 1 4 IF ( [COUNT .EO. 2 ) GO TO 5 2 CONTINUE c ' ? c TO FIND THE DEMVNO L EV El. JUST PRECEDING THESE TU 0 AO J A C E N T PROJECTS 7 3 c ' 4 5 IF ( IPOS .NE. 1 ) GO TO 6 X = 0.0 1 5 GO TO 7 6 DO 3 II = 1, NUB EP IF ( DAT A I ) .N c. ISEOOP(IPOS- 1 ) ) GO TO B X = X + •( I I ) GO TO 7 3 CONTINUE ;2 / I I = I PUS 4- I |>3 WRITF(6 , 201 ) IPOS, I I , I SE00?( IPOS) , ISEMOP(T I ) , X -4 201 FORMAT!/,• POS I T TONS ' ,13,* A^P',I3,» IN THF 0 3 T ! M A L s F :;. J rNCF ARE 0 -5 ICCUPIED BY PROJECTS:' ,2^4,' , PUT O.N LINE AT DE'-''N D LF.VF 1. OF', FO . 1 ) •6 CALL T IMF(X,TX) ••7 XO = X + OUTPUT(1) r-" CALL TIMF(XO,TXO) -R DTI = TX - TXO GO TO 1000 h 2000 R I = COST(l) / { 1.0 - ( 1.0 + DINT)**DT1 ) 7 2 WRI TE (6 ,205 ) TX ,TXD,OT 1 ,P.l 1 « 1000 XO = X «- OUTPUT! 2) CAM. T I F ( XOi, TXO ) 15 DT = TX - TXO ~6 0 2 = C0ST(2) / ( i . o - ( 1 .0+01 NT)**PT ) GO TO 300O "> •< 4000 WRITE(h ,2M5) TX, TXO, OT, R2 ~ P 2^5 FORM AT(• TV,TXO,0T,R : •,AD I 4.3) 30 00 Cl = F-2 * ( 1.0 - ( 1.0 + DINT )**l>r 1 ) n P = ( C. 1/COSTU) - 1.0 ) * 1^0.0 :+?. 1 V- P I T E ( 6 ,202) I S E 0 0 D ( IPOS) ? C P S T ( l ) t P, Cl 2 02 F 0 R ?>• A T ( / , ' COST OF' , A 4 , 1 IS',FA.O,. , f T RAM I v n rAS r • » = F . 2, ' v TO' • 1,F7.1,' WITHOUT MOVING BEHIND') "5 GO TO 11 c 7 -»H r. FOR PROJFCTS AFTER I SF 00 P ( NU'-'P F-P ) 10 DC 13 1 1 = 1 , NUBFR ! 0 IF ( DATM2,II) • NE . ISE00°(1) ) GO TO 13 ' 1 X = o.o OUTPUT ( 2) = i! ( T I ) o r TO 1/, 13 C.n*i T I NUE 9 9 1 1 x = x + n i J r P sj T ( l ) 14 CALL T I '•' F ( X , T X ) xr. = x + O U T P U T ^ ) ; CALL T i?•:,*:( x n , TXO > DT = TX - TXO P I = C.nsTf?) / ( l . o - (1 .P+PINT)**DT } W R I T E ( 6 , 2 0 6 ) 2 0 6 FPF M.AT ( / / , * ***** FOP PROJECTS AFT FT. THE CUT-OFF POIN T ,//) 00 TH 5 0 0 0  t o o n V. R I T E ( 6 , 2 ° 5 ) TX, TXO, OT, R I 50 00 r START = NUMBER * 1 00 9 I^OS = I START , NUBER 00 1? 11 = 1, NU B ER IF ( 0 A T A ( 2 , T I ) .NE. I S E O O P ( I P O S ) ) GO T 0 12 C O S T ( ? ) = C( 1 I )  OUT PUT ( ? ) = 0 ( 1 1 ) GO TO 15 12 CONTINUE 15 WP IT E if: , 203 ) IPOS, ISFQOP< I P ? S ) 2 0 3 FCP. MAT( / , » POSI Tl 0"" , 13 , » I N THE OPTIMAL S FOU FNCC IS OCCUPIED [«V P I P O J ECT',A 4 )  XO = X + O U T P U T ( 2 ) CALL T I M F ( X O , TXO) OT = TX - TXO GO TO 7 0 0 0 R.orn P2 = C O S T ( ? ) / ( l . O - ( I . 0 + 01 NT)**DT ) W R I T E ( 6 , 2 0 5 ) TX,TXH, QT, R2  7 E 00 C? = RI * ( 1 .0 - (1 .O + CINT)**DT ) P = ( 1.0 - C 2 / C O S T ( 2 ) ) * 1 0 0 . 0 9 W R I T E ( 6 , 2 0 4 ) I S E Q 0 D ( IPOS ) , C O S T ( 2 ) , P, C ? ?04 FOR •"• A T ( / , ' COST 0F«,A4,« I S ' , F 6 . 0 , ' , IT CAN 0 E 0 i< E AS E ' » F 6 .2, ' ^  TO' 1,F7.1,' WITHOUT MOVING FORWARD') RETURN  END C C c SUP.POUT I.N E T I M F ( X , T ) OQUBL E PPEC IS ION T, X,  1 0 L 0 0 , DSORT IF ( X .GT. 3 0 0 0 . 0 ) GO TO 1 T = DSCRT( X/2B.23 ) GO TO 2 I T = ( 1 2 . 5 / ( 1 0 . 0 * * ? ) ) * ( X**2 ) + 9.2 2 RETIJPN  SPAT A. F I L E APPENDIX B SOLUTION OF THE A PROJECT SEQUENCING PROBLEM D A T A : I N T E R E S T F A T E 0.05 MAXIMUM DEMAND ^ 2 0 0 . 0 NO. OF P R O J E C T S 4 NAME A 8 C D COST _ 7CC._ 6 0 0 ._ 'J3ft._ OUTPUT 2000'. T 2 0 0 . "700". ' " 3 0 0 7 U.COST 0 . 3 5 0 0 . 5 C 0 0.4*30 0 . 3 3 0 T I M E DEMAND P R E F E R E N C E M A T R I X _ 0 . 0 0 . 0 0 _ C A 0_ T . 9 ~ T o o T b ' D~" C " A '" 0 2.7 2 0 0 . 0 D C A B 3.3 3 0 0 . 0 D C A 3 3.8 4 0 0 . 0 0 C A B 4.2 5 0 0 . 0 D A C 8 4.6 6 C 0 . 0 D A C 8 5 . 0 7 0 0 . 0 D A C 13 5.3 8 C 0 . 0 D A C 8 5.6 9 0 0 . 0 D A C F3 5 .9 1 0 0 0 . 0 D A C 8 6.2 1 1 0 0 . 0 D A C B 6.5 l2.CLQl° °_ A J? 6 7 8 ' ' TBOO.O" D A "C B~ 7 . 0 14 0 0 . 0 D A C 8 7.3 1 5 0 0 . 0 D A C 8 7.5 1 6 0 0 . 0 D A C B 7.8 1 7 C O . 0 D C A 8 _8_. 0 18 0 0 . 0 • D C A B_ 8." 2 1 9 0 0 ; 0 0 C S 8 8.4 2 0 0 0 . 0 0 C A B 8.6 2 1 0 0 . 0 0 C A 8 8. 8 22 0 0 . 0 0 C A 8 9 . 0 2 3 0 0 . 0 D C A B 9.2 2 4 0 0 . 0 D C A 0 — 9 7 4 2 5 0 0 7 0 ~ ~ ' 0 A C 8 " 9 . 6 2 6 0 0 . 0 0 A C 8 9 . 8 2 7 0 0 . 0 D A C B 1 0 . 0 2 3 0 0 . 0 0 A C 8 1 0 . 1 2 9 0 C . 0 D A C B 1 0 . 3 3 0 0 0 . 0 A 0 8 C 1 0 . 4 3 1 0 0 . 0 A D B C 1 0 . 5 3 7 0 0 . 0 A 0 8 C 1 0 . 6 3 3 0 0 . 0 A C ft C 1 0 . 6 3 4 C 0 . 0 A D B C 1 0 . 7 3 5 0 0 . 0 A 0 8 C 1 0 ^ 8 3 6 0 0 . 0 A D 8 C_ TO. 9 3 7 0 0 . 0 A 0 'B "C 1 1 . 0 3 8 0 0 * 0 A 0 B C 1 1 . 1 3 9 C 0 . 0 A 0 8 C 11 . 2 4 0 C 0 . 0 A D B C 1 1 . 3 4 1 0 0 . 0 A 0 C B 1 1 . 4 4 2 0 0 . 0 A D C B I N I T I A L D E C O M P O S I T I O N : CECOMPCS IT ION IS NOT P O S S I E l . E 102 ASSIGN PROJECTS IN CLOCK 1 TO STAGE 1 NODES: STAGE _1 NCOF. OCCUP I »Y 0 _WA_S_ CONP_L E J N E M ..i) L S . " " s "= 6 c " A "~"q"~ ua = o. SGOOCCCOCCCU oo t PV.'LOS = 0.L2873569e360 04- UB - 0 . 1 2 « 73 '3603360 OA .PJCGWSJT ION IS NOT POSSIBLE PWLBS = 0.120173657670 04 STAGE 1 NODE OCCUPIED BY C HAS INCOMPLETE L.O.S. S = C A 8 INDEX,M I.N, IPGS,NUMBER: 4 1 2 2 L: A B {Z IG, INDEX NUMBER ,SET L: 1 4 3 A 8 0 THIS NODE IS RETAINEO DECOMPOSITION RESULTS: NUMBER OE BLOCKS = 3 1. PROJECTS IN OLOCK 1: D l _ PROJECTS IN bLOCK 2: A T "PROJECTS TN BLOCK" 3: G PWLBS = 0. 1312 154 45 29D 04 STAGE 1 NODE OCCUPIED eY A HAS INCOMPLETE L.O.S. S = A 0 INDEX, MIN, I PCS, NUMBER: 4 1 3 1 L : F3 I Z I G , INDEX ,NUMBER,SET L: 2 4 2 8 C THIS NODE I S DISCAROED AFTER L.O.S. CHECK, THERE ARE 2 BRANCHES AT STAGE 1 START BOUNCING CHECK, UB = C.I 2 i7356S836D 04 RLD I I ) = 0. 1 20173657671) C4 D RLB< 2 ) = 0.1312154452SO C4 C "END 6 F $ f A G E 1 BOUND CHECK, UB = 0 ~. 1 2 S 73 56S 8360 04 NUMBER GE BRANCHES REMAINING = 1 OPT{ 1 ) : D * * * * T H E R E IS ONLY f NE FRANOH REMAINING A! STAGE 1 ***** P O S I T I O N S 1 TO I I N O P T I V A L SEQUENCE ART: OCCUPIED tiY D 103 THE REST PROJECTS CAN START AFRESH D E C G i N P O S I T I O N I S N O T P O S S I B L E ASSIGN PROJECTS IN BLOCK 1 TO STAGE 2 NODES: STAGF 2 NODE OCCUPIED BY C HAS COMPLETE L.O.S. S = D C A 8 UB = 0.50C000C0CC0D CO PWLOS = 0. 12S731;69B260 04 IJ3 = 0.1287356? 33 60 04 OECCMPOS IT ION RESULTS : NUMBER OF BLOCKS = 2 1 PROJECTS IN BLOCK 1: 1 PROJECTS IN BLOCK 2: PWLBS = 0.12373569836D 04 STAGE 2 NODE OCCUPIED BY A HAS INCOMPLETE L.O.S. S = 0 A B INDFX,MIN,IPUS,NUM8ER: 3 4 2 1 L: B IZIG, INDEX,NUMBER, SET L: 1 . 3 2 3 C T f l ^ S - i T O D E - T S""iTcTAT'REF DECOMPOSITION IS NOT POSSIBLE PWLBS = 0. 12H2SE95435D 04 AFTER L.C.S. CHECK, THERE ARE 2 BRANCHES AT STAGE 2 ~S'T ART~LU3UN'D INrG~C"HEC'K7~ UB"~ 0TT2'8'7336T836D~~04 RLB( I J = 0.12073569B36D G4 D C RLBl 2 ) = 0. 12329395435D C4 0 A •END~"0E~ST7.r3T""T UB""rJ . - r 2 l T 7 3 5 S 9"3li6D _C4 NUMBER GF CRANCHES REMAINING = 2 OPT( l ) : 0 C OPT{ 2 ) : 0 A TO FIND 3 TH STAGE NODES F I- CiM PRFFEPENOE MATRIX 104 F G P H A N C h NlJV.nrj- ) I- C S r T 01)? : A F OFCC MTCS i f T o M " K f O l l T s : ' Ntir n r | O F M O C K S = ?. 1 R R U J i d S IN F.l. I X K l : A 1 PP. n . i r C . IS I N P L O C K ? : F O P T = A F O R E R A N C H N U ^ P F F . 2_ 0 _A • _ " S E T N i i>T ' V " " D E C C ••' P C S I T I O N IS NOT R l . S S I P L E ELEMENT H A ' J ' > i A R S L l . I G J B l E f OR T H F N E X T t-HKK O N B R A N C H M I S ' B r R ? 0 A B U T D U E T O I T S P O S I T I O N AT T I E F I R S T rMlW IN T H E 1 S T S U D - L L O L K , I I I S I N F A C . T H I S BP A NC H 1 S F L ^MJJNA TF_n_t_ S I N C E NO_«>P C-JFCJ C A N f U L LCW_ I T C P T { 1 ) : 0 C A E N O *! t : S T A G F \ >;h A N C ' . I N G F Y S U ' . P C U T I N K B R A N C H . T H E R T A R E 1 R R A N C H F S * * * * * T F P P . F IS ONI Y f."a : - .RANf. t . R E M A I N I N G A T S T A G E B * v * * < P O S I T I O N S I T O I IN U P T I M/„L S E O U E N C E A k F ' ' ( . C O P I E D f . Y D C T H E K F S 1 P P f ! J r C ( S C A N S T A K T AT R E S H O E C C M P C S l T I C N I S N E T P U S S I P L F O P T I C A L S C L U T I C N : C O S T = 0 . 1 2 F 7 B S V - S B 3 M ) 0 4 S E C U E N C E I S : 0 C. A p. R A N K : ;Y L . C . : A D N B S E N S I T l V I T Y A N A L Y S I S : C U T - O F F P O I N T ] t- T h f ' . , J T IV AI. c E O U E N C C I S P f S I T I O N 1 * * * * * FTR, P R O J E C T S A F T r R T L f C U T - O F F P O I N T * * * * * P O S I T I O N 7 I N T H E O P T I C A L S R C U F N C E I S O C C U P I E D B Y P R O J E C T C C C S I O F C I S 3 ' . 6 . , I T L A N D E C R F A S E S O . 2 V. T O 1 6 7 . 2 a I T U O U T vpviNG F O R W P O S I T I O N 3 I N T r - f OR I I '' A L S E C L E N <" F I S O C C U P I E D B Y P R O J E C T A COST OF A I S 7 ( 0 . , IT CAM D E C R E A S E 6 2 . 7 0 ? , T f J 2 6 1 . 1 WITHOUT MOVING F OH WAP. P O S I T I C N A IN THE O P T I C A L S f O U E N C F I S O C C U P I E D BY P R O J E C T B COST OF B I S 6 0 0 . , _ I T C A N _ OF C_P F AS E_ .7 c % TO 21 1_. 3_ w I THOUT MO V IN G_FO RWAP STOP 0 E X E C U T I C N T E R M I N A T E D ' SRUN - L C A C t f 5=SCwU{ I'-PG'," f 3 E X E C U T I O N B E G I N S DATA: I N T E R E S T RATE 0.05 MAXIMUM DEMAND 4 2 0 0 . 0 106 NO. OF P R O J E C T S 4 NAME A B C D COST 7 C C . 6 0 0 . 3 3 6 . 1 1 4 . "OUTPUT 2 0 0 0 . 1 2 0 0 . 7 0 0 . 3 0 0 . U.COST 0 . 3 5 0 0 . 5 0 0 0 . 4 8 0 0, .3 8 0 T I ME DEMAND P R E F E R E N C E M A T R I X 0.0 0. 0 D c A 8 1.9 1 0 0 . 0 D c A B 2. 7 2 0 0 . 0 D c A B 3.3 3 0 0 . 0 D c A 3 3.8 4 0 0 . 0 D c A B A.2 5 0 0 . 0 D A C B 4.6 6 C 0 . 0 D A C B 5.0 7 0 0 . 0 D A C B 5.3 8 0 0 . 0 0 A C B 5.6 9 0 0 . 0 D A c B 5.9 1 0 0 0 . 0 D A c B 6.2 1 1 0 0 . 0 0 A c 6 6.5 1 2 0 0 . 0 D A c B 6.8 1 3 0 0 . 0 0 A c 8 7.0 1 4 0 0 . 0 D A c B 7.3 1 5 0 0 . 0 D A c B 7. 5 1 6 0 0 . 0 D A c B 7.8 1 7 0 0 . 0 D C A 8 8.0 1 8 0 0 . 0 D C A B 8.2 1 9 0 0 . 0 D C A B 8.4 2 o r j o . o D C A B 8.6 2 1 0 0 . 0 D C A B 8. 8 2 2 0 0 . 0 D C A B 9.0 2 3 0 0 . 0 D C A B 9.2 2 4 0 0 . 0 D C A B 9.4 2 5 0 0 . 0 D A C B 9.6 2 6 0 0 . 0 D A C B 9.8 2 7 0 0 . 0 D A C B 1 0 . 0 2 8 0 0 . 0 D A C 8 1 0 . 1 2 9 0 0 . 0 D A C B 1 0 . 3 3 0 0 0 .0 A D 8 C 1 0 . 4 3 1 0 0 . 0 A 0 B C 1 0 . 5 3 2 0 0 . 0 A D B C 1 0 . 6 3 3 0 0 . 0 A C B C 1 0 . 6 3 4 C 0 . 0 A D B C 1 0 . 7 3 5 0 0 .0 A 0 B C 1 0 . 8 3 6 0 0 . 0 A D B C 10 . 9 3 7 0 0 . 0 A D B C I 1 .0 3 8 0 0 . 0 A C B C 1 1 . 1 3 9 C 0 . 0 A 0 B C 11. 2 4 0 C 0 . 0 A D B c 11 .3 4 1 0 0 . 0 A 0 C B 1 1 . 4 4 2 0 0 . 0 A D C B I N I T I A L D E C O M P O S I T I O N : OECCMPCS IT ION IS NOT P O S S I E L E A S S I G N P R C J E C T S " I N DLGCK 1 TO S T A G E I NODES*. 107 S T A G E 1 NODE O C C U P I E D BY D HAS C O M P L E T E L . O . S .  S = D C A D UB = 0.50000CCOCOOO 0 0 PWLOS = 0 . 1 2 8 7 3 5 6 9 2 3 6 0 0 4 . UB = 0 . 1 2 8 7 3 5 6 9 3 3 6 0 OA D E C G M P C S I T ION I S NOT P O S S I B L E PWLBS = G. 1 2 0 1 7 3 6 5 7 6 7 0 0 4 STAGE 1 NCDE O C C U P I E D BY C HAS I N C O M P L E T E L . O . S . S = C A B I N D E X , M I N , I P O S , N U M B E R : 4 1 2 2 L : A B I Z I G , I N D E X ,NUMBER,SET L: 1 4 3 A B D T H I S NODE IS R E T A I N E D D E C O M P O S I T I O N R E S U L T S : NUMBER OF B L O C K S = 3 1 P R O J E C T S I N B L O C K 1: D 1 P R O J E C T S IN BLOCK 2: A 1 P R O J E C T S I N B L O C K PWLBS = 0 . 1 3 1 2 1 5 4 4 5 2 9 D 04 S T A G E 1 NODE O C C U P I E D e Y A HAS I N C O M P L E T E L . O . S . S = A B I N D E X , M I N , I PCS,NUMBER: 4 1 3 1 L : 8 I Z I G , I N D E X , N U M B E R , S E T L : 2 4 2 B C T H I S NODE I S D I S C A R O E D A F T F R L . O . S . C H E C K , THERE ARE 2 BRANCHES AT STAGE START BOUNDING CHECK, UB = C. 1 2 3 7 3 5 6 9 8 3 6 D 04" R L B ( 1 ) = R LB< 2 ) = 0. 1 201 7 3 6 5 7 6 7 D 04 D 0 . 1 3 1 2 1 5 4 4 5 2 9 0 04 C END OF STAGE 1 BOUND C H E C K , U8 = NUMBER OF BRANCHES R E M A I N I N G = 1 OPT. 1 ) : D D.1287356S636D 04 ***** THERE I S ONLY ONE BRANCH R E M A I N I N G AT STAGE 1 * * * * * P O S I T I G N S 1 TO 1 I N O P T I M A L SEQUENCE ARE O C C U P I E D BY D THE REST P R O J E C T S CAN START A F R E S H 108 CECOMPGS IT IGN IS NOT P O S S I B L E A S S I G N P R O J E C T S I N BLOCK 1 TO STAGE 2 NODES: S T A G E 2 NODE O C C U P I E D BY C HAS C O M P L E T E L . O . S . S = D C A B UB = 0 . 5 0 0 0 0 0 C 0 C 0 0 D CO PWLOS = C. 1 2 8 7 3 E 6 9 8 3 6 D C4 U3 = 0.12 fi73 5 6 9 8 3 6 D 04 D E C O M P O S I T I O N R E S U L T S : NUMBER OF 3 L G C K S = 2 1 P R O J E C T S IN BLOCK 1: A 1 P R O J E C T S IM B L O C K 2: B PWLBS = 0 . 1 2 8 7 3 5 6 9 8 3 6 D 0 4 S T A G E 2 NODE O C C U P I E D BY A HAS I N C O M P L E T E L . O . S . S = 0 A B I N D E X , M I N ,1POS,NUMBER: 3 4 2 1 L: B I Z I G t I N D E X , N U M B E R , S E T L : 1 3 2 B C Tf-riT _N~UDE I S R E T A I N E D D E C C M P C S I T ION IS NOT P O S S I B L E PWLBS = 0. 1 2 8 2 E E 9 5 4 3 5 0 C4 A F T E R L . O . S . C H E C K , THERE ARE 2 E R A N C h E S AT STAGE 2 "START BfJUN D IN (7~ChTCK~, LTR = 0TT21T7i 56S 8 3 60 C4 R L B ( 1 ) = 0 . 1 2 8 7 3 5 6 9 8 3 6 0 G4 0 C R L B { 2 ) = 0. 1 2 8 2 9 8 9 5 4 3 5 0 C4 D A END "OF "STAGE 2 BOUND C H E C K , UB = " 0. 1 2 8 7 3 9 3 3 6 0 C4 NUMBER OF ERANCHES R E M A I N I N G = 2 OPT( I ) : D C O P T ( 2 ) : D A TO F I N D 3 TH STAGE NODE S FROM P y F F E D E N C E M A T R I X 109 FGR BRANCH NUMBCR 1 0 C SR.T N02 : A B OECCMPCS IT ION RESULTS: NUMBER DF BLOCKS = 2 1 PROJECTS IN BLCCK I: A I PROJECTS IN BLOCK 2: B OPT = A FOR. PLANCH NUMBER 2 0 A  SET NO 2: B OECCMPCS IT I ON IS NOT POSSIBLE ELEMENT B APPEARS ELIGIBLE FOR THE NEXT NODE ON BRANCH NUMBER 2 0 A BUT OUE TO ITS POSITION AT THE FIRST ROW IN THE 1ST SUB-BLOCK, IT IS IN FACT THIS BRANCH IS ELIMINATED, SINCE NO PROJECT CAN FOLLOW IT  CPT( 1) : D C A END OF STAGE 3 BRANCHING BY SUBROUTINE BRANCH. THERE ARE 1 BRANCHES THERE IS ONLY ONE BRANCH REMAINING AT STAGE 3 ***** POSITIONS 1 TO 3 IN OPTIMAL SEQUENCE AR F OCCUPIED BY D THE REST PROJECTS CAN START AFRESH OECCMPCSITION IS NCT POSSIBLE OPTIMAL SCLUTICN: COST = 0. 12P7356S336D 04 SEQUENCE IS : D C A B RANK BY U.C.: A D C B SENSITIVITY ANALYSIS: CUT-OFF PCINT IN THC OPTIMAL SEQUENCE IS POSITION 1 FCR PROJECTS AFTER TEE CUT-OFF POINT ***** PUS I HON COST OF POSITI ON 2 IN THE OPTIMAL SEQUENCE IS OCCUPIED BY PROJECT C C IS 3 36. , IT CAN DECREASE 50,233! TO 167.2 WITHOUT vnviNG FURW. 3 IN THE OPTIMAL Sr- 0 L E N C E IS OCCUPIED BY PROJECT A 1 1 0 C O S T O F A . I S 7 C 0 . , I T C A M D E C R E A S E 6 2 . 7 0 ? T O 2 6 1 . 1 W I T H O U T M O V I N G F O K W A t -P O S I T I O N 4 I N T F E O P T I'- 'AL S E Q U E N C E I S O C C U P I E D B Y P P O J E C T B C O S T O F B I S 6 0 0 . , I T C A N D E C R E A S E 6 4 . 7 9?: T O 2 1 1 . 3 W I T H O U T M O V I N G F O R W A , S T O P 0 E X E C U T I O N T E R M I N A T E D U R U N - L C A C V 5 = S E Q U ( 1 3 9 C , 1 3 9 4 ) E X E C U T I O N B E G I N S 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0050547/manifest

Comment

Related Items