A PETRI NET FORMULATION FOR THE GENERAL SCHEDULING PROBLEM by MICHAEL KENJI IMAI B.Eng.Mgt., McMaster U n i v e r s i t y , 1979 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE i n THE FACULTY OF GRADUATE STUDIES (Department of E l e c t r i c a l E n g i n e e r i n g ) We a c c e p t t h i s t h e s i s as c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d UNIVERSITY OF BRITISH COLUMBIA September, 1981 © M i c h a e l K e n j i I ma i 1981 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an advanced degree a t the U n i v e r s i t y o f B r i t i s h C o l u m b i a , I ag r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e head o f my department o r by h i s o r h e r r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Michael K. Imai Department o f E l e c t r i c a l Engineering The U n i v e r s i t y o f B r i t i s h C o l u m b i a 2075 Wesbrook P l a c e V a n couver, Canada V6T 1W5 D a t e October 2, 1981 i i A b s t r a c t T h i s t h e s i s i n t r o d u c e s a new P e t r i net f o r m u l a t i o n f o r the g e n e r a l s c h e d u l i n g problem. The f i r s t p a r t of t h i s t h e s i s c o n c e r n s the development of the P e t r i net f o r m u l a t i o n . The P e t r i net f o r m u l a t i o n i s a s y n t h e s i s of c o n c e p t s from t h r e e c l a s s e s of P e t r i n e t s , marked graphs, timed P e t r i n e t s and c o l o u r e d P e t r i n e t s . The g e n e r a l approach t o the s c h e d u l i n g problem b e g i n s w i t h the c o n s t r u c t i o n of a P e t r i net which models the s t r u c t u r e of the g e n e r a l s c h e d u l i n g problem. The s c h e d u l i n g s t r a t e g y i s modeled by m o d i f y i n g the a l g o r i t h m f o r the a n a l y s i s of P e t r i n e t s . A s c h e d u l e i s g e n e r a t e d by the e x e c u t i o n of the P e t r i net model under the m o d i f i e d a n a l y s i s . In the second p a r t of t h i s t h e s i s , The P e t r i net f o r m u l a t i o n i s used f o r the a n a l y s i s of a p a r t i c u l a r s c h e d u l i n g problem. The problem a d d r e s s e d i s the s c h e d u l i n g of a t a s k system on a s e t of p r o c e s s o r s of d i f f e r e n t speeds. The s c h e d u l i n g s t r a t e g y t o be a n a l y z e d i s l i s t s c h e d u l i n g . A new h e u r i s t i c i s proposed f o r the o r d e r i n g of the t a s k s i n t o a l i s t . The proposed h e u r i s t i c combines n o t i o n s from the h i g h e s t l e v e l s f i r s t h e u r i s t i c and the l o n g e s t p r o c e s s i n g time h e u r i s t i c . The performance of the proposed h e u r i s t i c i s e v a l u a t e d by a c o m p a r i s i o n w i t h o t h e r l i s t o r d e r i n g h e u r i s t i c s . The s c h e d u l e s which a r e g e n e r a t e d by the proposed h e u r i s t i c are compared t o the s c h e d u l e s which a r e g e n e r a t e d by the h i g h e s t l e v e l s f i r s t h e u r i s t i c , the Coffman and Graham A l g o r i t h m A and a random l i s t f o r f i f t e e n precedence c o n s t r a i n t s . The proposed h e u r i s t i c g e n e r a t e d a b e t t e r s c h e d u l e i n 98 of 160 cases t e s t e d f o r the 15 precedence c o n s t r a i n t s . The proposed h e u r i s t i c g e n e r a t e d a s c h e d u l e as good as the s c h e d u l e which i s g e n e r a t e d by any o t h e r l i s t i n a f u r t h e r 39 c a s e s . i v T a b l e of C o n t e n t s A b s t r a c t i i T a b l e of C o n t e n t s i v L i s t of F i g u r e s v i L i s t of T a b l e s v i i i Acknowledgement .. i x 1 I n t r o d u c t i o n 1 1.2 Overview of the T h e s i s 4 2 P e t r i Nets 6 2.1 B a s i c Concepts and Ideas 6 2.2 A n a l y s i s of P e t r i Nets 18 2.2.1 S t r u c t u r a l A n a l y s i s 1 8 2.2.3 B e h a v i o r a l A n a l y s i s 22 2.3 C l a s s e s of P e t r i Nets 25 2.3.1 Marked Graphs 27 2.3.2 Timed P e t r i Nets 28 2.3.3 C o l o u r e d P e t r i Nets 35 3 The P e t r i Net F o r m u l a t i o n 41 3.1 The G e n e r a l S c h e d u l i n g Problem 41 3.2 The P e t r i Net F o r m u l a t i o n 45 3.2.1 The C o n s t r u c t i o n of the P e t r i Net Model 46 3.2.2 M o d e l i n g the B e h a v i o r of a S c h e d u l i n g S t r a t e g y 63 3.3 R e l a t e d Work 67 4 The A n a l y s i s of a S c h e d u l i n g Problem 75 4.1 The S c h e d u l i n g Model 77 4.2 A l g o r i t h m s f o r L i s t O r d e r i n g 8 1 4.3 E x p e r i m e n t a l O u t l i n e 95 4.4 R e s u l t s and D i s c u s s i o n 98 5 C o n c l u s i o n s and S u g g e s t i o n s f o r F u r t h e r Research 109 5.1 Summary and C o n c l u s i o n s 109 5.2 S u g g e s t i o n s f o r F u r t h e r Research 111 B i b l i o g r a p h y 114 Appendix A D e f i n i t i o n s and N o t a t i o n 123 Appendix B Sample R e s u l t s 128 v i L i s t of F i g u r e s 2.1 A simple P e t r i net . 7 2.2 A marked P e t r i net 9 2.3 T4 f i r e d 11 2.4 T3 f i r e d 11 2.5 2 consumer - s i n g l e producer 14 2.6 A p e r s i s t e n t P e t r i net 17 2.7 S t r u c t u r a l a n a l y s i s 20 2.8 B e h a v i o r a l a n a l y s i s 24 2.9 A r e a c h a b i l i t y t r e e 26 2.10 A marked graph 29 2.11 F i r i n g a timed t r a n s i t i o n 31 2.12 A timed t r a n s i t i o n 32 2.13 A timed t r a n s i t i o n ....... . .... ..................... 32 2.14 A producer-consumer system 36 2.15 A c o l o u r e d P e t r i net 38 2.16 S i m i l a r t r a n s i t i o n s 40 2.17 A t r a n s i t i o n scheme 40 3.1 A task system 44 3.2 A l g o r i t h m 1 47 3.3 The marked graph a f t e r Step 6 — . . — ... 49 3.4 Colour s e t s 51 3.5 A d y n a m i c a l l y r e c o n f i g u r a b l e a r c h i t e c t u r e ........... 53 3.6 Tasks ,T3 and T7 58 3.7 GRID A l g o r i t h m .... 65 3.8 A c a p a c i t a t e d computation graph 70 3.9 A l g o r i t h m to f i n d s(k) ... 72 v i i 3.10 Resource c o n f l i c t r e s o l u t i o n 73 4.1 C o l o u r s e t f o r p r o c e s s o r s of d i f f e r e n t speeds 79 4.1 Example 1 82 4.3 Example 1 l e v e l s 84 4.4 Coffman Graham A l g o r i t h m A 85 4.5 Example 1 - CG A l g o r i t h m A 86 4.6 Example 1 c h a i n l e n g t h 89 4.7 Ordered l i s t s of t a s k s f o r Example 1 92 4.8 Schedules f o r Example 1 93 4.9 Schedules f o r Example 1 94 B.1 Example 8 - <:most c o n s t r a i n e d 128 B.2 Example 9 - < : l e a s t c o n s t r a i n e d 129 v i i i L i s t of T a b l e s 3.1 T r a n s i t i o n scheme, T4 51 3.2 Task p r o c e s s o r r e q u i r e m e n t s and e x e c u t i o n times 55 3.3 T r a n s i t i o n scheme, T3 57 3.4 T r a n s i t i o n scheme, T7 57 3.5 T r a n s i t i o n scheme, T4 57 3.6 An a d m i s s a b l e s c h e d u l e 70 4.1 Bounds f o r l i s t s c h e d u l i n g 76 4.2 C o l o u r s e t f o r exp e r i m e n t s 97 4.3 Summary of R e s u l t s 99 4.4 Average w/w* 101 4.5 R e s u l t s f o r Example 1 104 B.1 Example 1 l o n g e r e x e c u t i o n t i m e s slower p r o c e s s o r s ..130 B.2 Example 1 slow e r p r o c e s s o r s 131 B.3 Example 1 l o n g e r e x e c u t i o n t i m e s 132 B.4 Example 1 u n i t e x e c u t i o n t i m e s 133 i x Ac knowledqement I would l i k e t o thank Dr. Mabo R. I t o f o r i n t r o d u c i n g b o th the t o p i c s i n v o l v e d i n the r e s e a c h , P e t r i n e t s and s c h e d u l i n g t h e o r y . I a l s o thank him f o r h i s guidance and encouragement thoughout the c o u r s e of t h i s work. I g r a t e f u l l y acknowledge the f i n a n c i a l support of both the N a t i o n a l S c i e n c e s and E n g i n e e r i n g C o u n c i l and the U n i v e r s i t y of B r i t i s h Columbia'. 1 CHAPTER 1 INTRODUCTION A P e t r i net i s a f o r m a l model of i n f o r m a t i o n f l o w . P e t r i n e t s a r e p a r t i c u l a r l y u s e f u l f o r the d e s c r i p t i o n and the a n a l y s i s of systems which e x h i b i t asynchronous c o n c u r r e n t b e h a v i o r . P e t r i n e t s p r o v i d e a n a t u r a l and compact r e p r e s e n t a t i o n f o r asynchronous c o n c u r r e n t systems. The n a t u r a l and compact r e p r e s e n t a t i o n i s r e f l e c t e d i n a s i m p l e g r a p h i c a l r e p r e s e n t a t i o n . P e t r i n e t s a re e a s i l y extended so as to i n c r e a s e t h e i r a b i l i t y t o model systems. T h i s e x t e n d i b i l i t y a l l o w s compact and n a t u r a l d e s c r i p t i o n s f o r a wide v a r i e t y of systems. An i m p o r t a n t a s p e c t of P e t r i n e t s i s the a b i l i t y t o model both the s t r u c t u r e and the b e h a v i o r of systems. The s t u c t u r e of a system i s the s t a t i c p r o p e r t i e s i n a system which impose r e s t r i c t i o n s on the b e h a v i o r of the system. The b e h a v i o r of a system i s the s e t of a c t i o n s which occur as a r e s u l t of c o n d i t i o n s i n the ' system. The b e h a v i o r i s dynamic i n n a t u r e s i n c e the o c c u r r e n c e of an a c t i o n causes new c o n d i t i o n s t o become v a l i d . The new c o n d i t i o n s i n t u r n a l l o w more a c t i o n s t o o c c u r . Thus, P e t r i n e t s a r e a p o w e r f u l method of d e s c r i b i n g systems i n which the s t r u c t u r e and b e h a v i o r a r e of e q u a l importance. The g e n e r a l s c h e d u l i n g problem i s t h a t of s c h e d u l i n g the 2 e x e c u t i o n of a s e t of t a s k s on a set of r e s o u r c e s . For the purposes of t h i s t h e s i s , the s e t of r e s o u r c e s i s a computer system. The computer system i s c o m p rised of p r o c e s s o r s , p r i m a r y and secondary s t o r a g e , and p o s s i b l y o t h e r d e v i c e s . The t a s k system then c o n s i s t s of b l o c k s of independent code from a program. I t i s assumed the r e s o u r c e s a r e s u f f i c i e n t f o r the e x e c u t i o n of a l l of the t a s k s ; t h a t i s , the minimum amount of any r e s o u r c e i s the maximum, over a l l t a s k s , of the minimum amount r e q u i r e d by any s i n g l e t a s k . I t i s assumed t h a t a v a l i d s c h e dule e x i s t s . The scope of the problem i s t o f i n d the best schedule g i v e n a t a s k system, a s e t of r e s o u r c e s and a s c h e d u l i n g s t r a t e g y . The g e n e r a l s c h e d u l i n g problem may be c o n s i d e r e d i n terms of s t r u c t u r e and b e h a v i o r . The s t r u c t u r e of the g e n e r a l s c h e d u l i n g problem i s the o p e r a t i o n a l precedence c o n s t r a i n t s of the t a s k system. F u r t h e r s t r u c t u r e i s imposed by the r e s o u r c e s which a r e used f o r the e x e c u t i o n of the t a s k system. I f we c o n s i d e r s t o r a g e d e v i c e s as a s e t of r e s o u r c e s , the s e t of r e s o u r c e s may be s u b d i v i d e d i n t o p r i m a r y and secondary s t o r a g e w i t h p r i m a r y s t o r a g e b e i n g the f a s t e r of the two. The secondary s t o r a g e may be c o m p r ised of d i s k and tape d r i v e s . In e i t h e r c a s e , t h e r e are d i f f e r e n c e s which impose c o n s t r a i n t s on the use of the r e s o u r c e of s t o r a g e space. These r e l a t i o n s between the members of a s e t of r e s o u r c e s add t o the s t r u c t u r e of the g e n e r a l s c h e d u l i n g problem. The t o t a l b e h a v i o r of a system i s c h a r a c t e r i s e d by a 3 s t a t e space. The t r a n s i t i o n s between the s t a t e s are the p o s s i b l e a c t i o n s which may oc c u r i n a p a r t i c u l a r s t a t e . Suppose t h a t a p a r t i c u l a r b e h a v i o r i s imposed on the a c t i o n s of the system. As the system p r o g r e s s e s t h r o u g h the s t a t e space, a c e r t a i n sequence of s t a t e s i s f o l l o w e d . In terms of the g e n e r a l s c h e d u l i n g problem, t h e s t a t e s are d e f i n e d by the t a s k s which have completed e x e c u t i o n , the t a s k s which a re t o be e x e c u t e d and the t a s k s which a r e c u r r e n t l y e x e c u t i n g . A sche d u l e i n t h i s d e s c r i p t i o n i s a sequence of s t a t e s . The s c h e d u l i n g s t r a t e g y determines which sequence of s t a t e s i s f o l l o w e d . Hence, the s c h e d u l i n g s t r a t e g y i s the b e h a v i o r of the g e n e r a l s c h e d u l i n g problem. The o b j e c t i v e of t h i s t h e s i s i s the development of a P e t r i net f o r m u l a t i o n t o p r o v i d e a means of s t u d y i n g g e n e r a l s c h e d u l i n g problems. P e t r i n e t s have the a b i l i t y t o model both the s t r u c t u r e a r i s i n g from the precedence r e l a t i o n of the t a s k system and the s t r u c t u r e a r i s i n g from the r e l a t i o n s h i p s p r e s e n t i n the r e s o u r c e s . P e t r i n e t s a l s o have the a b i l i t y t o d e s c r i b e the b e h a v i o r of the system. The s c h e d u l i n g s t r a t e g i e s to be e v a l u a t e d a r e modeled by m o d i f i c a t i o n s t o the P e t r i net a n a l y s i s . In an e a r l y paper by S h a p i r o and S a i n t [ 8 4 ] , P e t r i n e t s are a p p l i e d t o a sequencing problem. The machine code f o r a FORTRAN DO-loop e x e c u t i n g on a CDC 6600 i s o p t i m i s e d u s i n g a P e t r i net model of the DO l o o p and the hardware c o n s t r a i n t s . The modeling which was p r e s e n t e d i s a t a much lower l e v e l than 4 i s i n t e n d e d by the P e t r i net f o r m u l a t i o n t o be p r e s e n t e d h e r e . The method of o p t i m i z a t i o n i s e x e c u t i o n of the net u n t i l a s o l u t i o n which i s a t or near a t h e o r e t i c a l o p t i m a l one i s found. A second use of P e t r i n e t s i n a s c h e d u l i n g c o n t e x t uses a r e s t r i c t e d c l a s s of P e t r i n e t s which cannot model c o n f l i c t s [92, 9 3 ] . To r e s o l v e a c o n f l i c t , a P e t r i net i s g e n e r a t e d f o r each p o s s i b l e r e s o l u t i o n . Each net i s then e v a l u a t e d t o determine the b e s t manner i n which t o r e s o l v e the c o n f l i c t . In both approaches the o p t i m i z a t i o n i s t h rough e x h a u s t i v e s e a r c h e s ; t h i s i s not the aim of the f o r m u l a t i o n t o be p r e s e n t e d h e r e . Both approaches a r e d i s c u s s e d i n d e t a i l a f t e r the i n t r o d u c t i o n of the f o r m u l a t i o n . 1.2 Overview of the T h e s i s Chapter 2 i s an i n t r o d u c t i o n t o P e t r i n e t s . The b a s i c i d e a s and p r o p e r t i e s are d i s c u s s s e d a t an i n f o r m a l l e v e l . The a n a l y s i s of P e t r i n e t s i s p r e s e n t e d i n two s e c t i o n s , the s t r u c t u r a l a n a l y s i s and the b e h a v i o r a l a n a y l s i s . Three c l a s s e s of P e t r i n e t s , marked graphs, t i m e d P e t r i n e t s and c o l o u r e d P e t r i n e t s , are i n t r o d u c e d w i t h emphasis on the p r o p e r t i e s which a r e r e l e v a n t t o the development of the f o r m u l a t i o n i n Chapter 3. Chapter 3 d e a l s w i t h the d e f i n i t i o n of the P e t r i net f o r m u l a t i o n of the g e n e r a l s c h e d u l i n g problem. The g e n e r a l 5 s c h e d u l i n g model upon which the f o r m u l a t i o n i s based i s p r e s e n t e d . The d e f i n i t i o n of the P e t r i net f o r m u l a t i o n i s s e p a r a t e d i n t o two l o g i c a l s e c t i o n s . F i r s t , the c o n s t r u c t i o n of the P e t r i net model of the f o r m u l a t i o n i s d i s c u s s e d . S e c o n d l y , the modeling of the b e h a v i o r of the s c h e d u l i n g s t r a t e g y by the P e t r i net a n a l y s i s i s p r e s e n t e d . The P e t r i net f o r m u l a t i o n i s compared i n d e t a i l t o p r e v i o u s uses of P e t r i n e t s f o r s c h e d u l i n g . Chapter 4 p r e s e n t s the a n a l y s i s of a s p e c i f i c s c h e d u l i n g problem t o demonstrate the use of the P e t r i net f o r m u l a t i o n . The problem which i s a n a l y z e d i s the use of l i s t s c h e d u l i n g on p r o c e s s o r s of d i f f e r e n t speeds. R e s u l t s of the comparison of the h e u r i s t i c s and a d i s c u s s i o n of the r e s u l t s i s p r e s e n t e d . Chapter 5 i s a summary of the s i g n i f i c a n t r e s u l t s and c o n c l u s i o n s . S u g g e s t i o n s f o r f u r t h e r r e s e a r c h a r e a l s o i n c l u d e d . Appendix A c o n t a i n s the f o r m a l d e f i n i t i o n s and the f o r m a l n o t a t i o n f o r the terms which are d i s c u s s e d a t an i n f o r m a l l e v e l i n t h i s t h e s i s . 6 CHAPTER 2 PETRI NETS A P e t r i net i s a f o r m a l model f o r the r e p r e s e n t a t i o n of systems. P e t r i n e t s a r e u s e f u l f o r the modeling of systems i n which the c o n c u r r e n c y of a c t i o n s i s an im p o r t a n t a s p e c t of the system. In these s i t u a t i o n s , the P e t r i n e t s p r o v i d e a n a t u r a l r e p r e s e n t a t i o n f o r the system which i s r e f l e c t e d i n a si m p l e g r a p h i c a l r e p r e s e n t a t i o n . The P e t r i net i s e a s i l y extended to i n c r e a s e i t s a b i l i t y t o model d i f f e r e n t c o n c u r r e n t systems. 2.1 B a s i c Concepts and Ideas A P e t r i net i s a p a i r , , where P i s a s e t of p l a c e s and T i s a s e t of t r a n s i t i o n s [ 5 3 ] , A c o n v e n i e n t means of c o n c e p t u a l i z i n g a P e t r i net i s i n terms of i t s g r a p h i c a l r e p r e s e n t a t i o n , a b i p a r t i t e d i r e c t e d graph. F i g u r e 2.1(a) shows the graph of a s i m p l e net whose f o r m a l r e p r e s e n t a t i o n appears i n F i g u r e 2 . 1 ( b ) . The f o r m a l r e p r e s e n t a t i o n i s d e f i n e d i n Appendix A. In the g r a p h i c a l r e p r e s e n t a t i o n , the two types of nodes, c i r c l e s and r e c t a n g l e s , r e p r e s e n t p l a c e s and t r a n s i t i o n s , r e s p e c t i v e l y . The s t r u c t u r a l p r o p e r t i e s of the net a r e the r e l a t i o n s h i p s between the p l a c e s and the t r a n s i t i o n s of the ne t . The r e l a t i o n s h i p s a r e the d i r e c t e d edges i n the g r a p h i c a l r e p r e s e n t a t i o n of the n e t . A p l a c e which i s con n e c t e d by an P4 P6 P3 P5 (a) G r a p h i c a l R e p r e s e n t a t i o n P={P1 rP2,P3 rP4,P5,P6} T={T1,T2,T3,T4} TI : P1 -> P2 T2: P2+P4 P1+P-3 T3: P3+P5 -> P4+P6 T4: P6 * P5 (b) Formal R e p r e s e n t a t i o n F i g u r e 2.1: A simple P e t r i net 8 edge from i t s e l f t o a t r a n s i t i o n , i s s a i d t o be an i n p u t p l a c e t o t h a t t r a n s i t i o n . A p l a c e which i s c o n n e c t e d by an edge from a t r a n s i t i o n t o i t s e l f i s s a i d t o be an output p l a c e of t h a t t r a n s i t i o n . S i m i l a r i l y , t r a n s i t i o n s may be d e s c r i b e d i n terms of i n p u t s and o u t p u t s t o p l a c e s . In F i g u r e 2 . 1 ( a ) , p l a c e P5 i s an output p l a c e of t r a n s i t i o n T4. P l a c e s P2 and P4 are i n p u t p l a c e s t o t r a n s i t i o n T2. C o n s i d e r the analogy of the f l o w c h a r t of a computer program. The s t r u c t u r e of the f l o w c h a r t r e p r e s e n t s the r e l a t i o n s h i p between the d i f f e r e n t s e c t i o n s of the program. I f a marker i s used to t r a c e on the f l o w c h a r t the e x e c u t i o n of. the program, th e n , the marker t r a v e r s e s the f l o w c h a r t as the d i f f e r e n t s e c t i o n s of the program are e x e c u t e d . The markers i n a P e t r i net a r e c a l l e d t o k e ns which a r e h e l d i n the p l a c e s of the n e t . The g r a p h i c a l r e p r e s e n t a t i o n of a token i s a d o t 1 , as shown i n F i g u r e 2.2. A marked P e t r i net i s a t r i p l e , , where m i s a marking. A marking i s a d i s t r i b u t i o n of tokens i n the p l a c e s of a n e t . Each marking r e p r e s e n t s a d i f f e r e n t s t a t e of the P e t r i n e t ; j u s t as i n the f l o w c h a r t a n a l o g y , the f l o w c h a r t marker i n d i c a t e s the s t a t e of the computer program. The b e h a v i o r a l or dynamic p r o p e r t i e s of the net are c h a r a c t e r i z e d by the movement of tokens i n the n e t . Tokens move through the net by the f i r i n g of the t r a n s i t i o n s . A 1 I f a p l a c e h o l d s s e v e r a l t o k ens i t i s c o n v e n i e n t t o i n d i c a t e the number of tokens by the number r a t h e r than a number of d o t s . 9 F i g u r e 2.2: A marked P e t r i net 10 t r a n s i t i o n may f i r e i f i t i s e n a b l e d i n the c u r r e n t marking under the assumed f i r i n g r u l e s . In the s i m p l e s t f i r i n g r u l e , a t r a n s i t i o n i s e n a b l e d when t h e r e i s a t l e a s t one token i n each of i t s i n p u t p l a c e s . In more complex f i r i n g r u l e s , w e i g h t s which are a s s i g n e d t o t h e - edges and c a p a c i t i e s which a r e a s s i g n e d t o p l a c e s are taken i n t o c o n s i d e r a t i o n when d e t e r m i n i n g whether a t r a n s i t i o n i s e n a b l e d . In F i g u r e 2.2, t r a n s i t i o n T4 i s e n a b l e d under the marking shown. A t r a n s i t i o n f i r e s by removing a token from each of i t s i n p u t p l a c e s and d e p o s i t i n g a token i n t o each of i t s output p l a c e s . The f i r i n g of a t r a n s i t i o n i s assumed t o occur i n s t a n t a n e o u s l y . The movementof tokens i s shown i n F i g u r e s 2.3 and 2.4 which i l l u s t r a t e s the f i r i n g of t r a n s i t i o n s , T4 then T3, r e s p e c t i v e l y , on the marked net of F i g u r e 2.2. The e x e c u t i o n of a net i s the f i r i n g of a sequence of t r a n s i t i o n s from an i n i t i a l marking of the n e t . The P e t r i net models the s t r u c t u r e and the b e h a v i o r of systems which may be e x p r e s s e d i n terms of c o n d i t i o n s and e v e n t s . The p l a c e s r e p r e s e n t c o n d i t i o n s which may be p r e s e n t i n the system and the t r a n s i t i o n s r e p r e s e n t the events i n the system which occur as a r e s u l t of the c o n d i t i o n s p r e s e n t . The edges i n d i c a t e which c o n d i t i o n s a r e n e c e s s a r y f o r the o c c u r r e n c e of an event and which c o n d i t i o n s r e s u l t from the o c c u r r e n c e of an e v e n t . C o n s i d e r the f o l l o w i n g c o n d i t i o n s and e v e n t s f o r the net shown i n F i g u r e 2.1. 11 F i g u r e 2.4: T3 f i r e d 1 2 P1: consumer ready t o consume a u n i t P2: consumer ready t o t a k e a u n i t from b u f f e r P3: b u f f e r empty P4: b u f f e r f u l l P5: producer ready t o produce a u n i t P6: producer ready t o d e p o s i t a u n i t i n t o b u f f e r T1: consumer consumes a u n i t T2: consumer t a k e s a u n i t from b u f f e r T3: producer d e p o s i t s a u n i t i n t o b u f f e r T4: producer produces a u n i t The P e t r i net now models the i n t e r a c t i o n of a producer and a consumer through a bounded b u f f e r . The marking i n d i c a t e the c o n d i t i o n s i n the system which are c u r r e n t l y v a l i d . The example i l l u s t r a t e s two i m p o r t a n t i d e a s u n d e r l y i n g the a b i l i t y of P e t r i n e t s t o model systems. F i r s t , the net c o r r e c t l y models the c o n c u r r e n c y i n the system. In F i g u r e 2.4, t r a n s i t i o n s T2 and T4 are e n a b l e d under the marking. In terms of the producer-consumer system, the consumer can t a k e a u n i t from the b u f f e r or the producer can produce another u n i t . These a c t i o n s may occur c o n c u r r e n t l y , which i s modeled i f both T2 and T4 f i r e t o g e t h e r . The a b i l i t y t o model c o n c u r r e n c y a r i s e s s i n c e the f i r i n g of a t r a n s i t i o n causes o n l y a l o c a l change of s t a t e . Only p l a c e s which are i n p u t or output t o a t r a n s i t i o n a r e a f f e c t e d . 13 The second i m p o r t a n t i d e a i s t h a t the P e t r i net model imposes the c o r r e c t sequencing of events i n the system. In the example, t r a n s i t i o n s T4 and T3 a r e f i r e d b e f o r e T2 may f i r e . In terms of the producer-consumer system, the producer must produce a u n i t and d e p o s i t i t i n t o the b u f f e r b e f o r e the consumer can take a u n i t from the b u f f e r . The t r a n s i t i o n s a r e sequenced s i n c e t hey are c o n n e c t e d by a s e r i e s of edges upon which the tokens t r a v e l . P e t r i n e t s thus have the a b i l i t y t o model c o r r e c t l y b o t h the c o n c u r r e n c y between events and the sequ e n c i n g c o n s t r a i n t s of e v e n t s of the system. C o n s i d e r the a d d i t i o n of a second consumer t o the producer-consumer example shown i n F i g u r e 2.2. The P e t r i net must model the c o n t e n t i o n between the consumers when both a r e ready t o take a u n i t from the b u f f e r . The P e t r i net model i s shown i n F i g u r e 2.5 where the a d d i t i o n a l p l a c e s a re the c o n d i t i o n s and e v e n t s of the second consumer. T r a n s i t i o n s T2 and T6 share a common i n p u t p l a c e , P4, and are s a i d t o be i n c o n f l i c t . Under the marking shown, e i t h e r T2 or T6 but not bo t h may f i r e . Hence the P e t r i net c o r r e c t l y models the c o n t e n t i o n f o r the u n i t i n the b u f f e r . C o n f l i c t i s a s t r u c t u r a l p r o p e r t y which e x i s t s as a r e s u l t of the r e l a t i o n s h i p between r e l a t e d e v e n t s . The b e h a v i o r of a system i s c h a r a c t e r i z e d by the movement of tokens i n the P e t r i net model of the system. P r o p e r t i e s of the b e h a v i o r of the system can be i n f e r r e d from the b e h a v i o r a l p r o p e r t i e s of the P e t r i n e t . Three such p r o p e r t i e s of P e t r i 14 F i g u r e 2.5: 2 consumer - s i n g l e producer system 15 nets a r e l i v e n e s s , p e r s i s t e n c e and boundedness. The l i v e n e s s p r o p e r t y i s i m p o r t a n t f o r the d e t e r m i n a t i o n of the p r o p e r t i e s of a system. A t r a n s i t i o n i s l i v e i f t h e r e e x i s t s a marking r e a c h a b l e from the i n i t i a l marking i n which the t r a n s i t i o n i s e n a b l e d . A marking, m2, i s r e a c h a b l e from a marking, m,, i f t h e r e e x i s t s a sequence of t r a n s i t i o n s , e, which t a k e s m, through a sequence of s t a t e s r e s u l t i n g i n m2. A s t r o n g e r statement of l i v e n e s s i s t h a t a t r a n s i t i o n i s l i v e i f t h e r e e x i s t s a marking r e a c h a b l e from a l l o t h e r markings of the net i n which the t r a n s i t i o n i s e n a b l e d . A net i s l i v e i f a l l of i t s t r a n s i t i o n s a re l i v e . I f the P e t r i net model of a system i s l i v e , then one can i n f e r (assuming a c o r r e c t model), t h a t the system has no a c t i o n s which never occur and t h a t the system cannot reach a s t a t e i n which no a c t i o n s may o c c u r . The l i v e n e s s p r o p e r t y of P e t r i n e t s has been the s u b j e c t of much r e s e a r c h [3, 5, 6, 11, 43, 52, 53, 55, 68, 69, 76, 88, 94]. The use of the l i v e n e s s p r o p e r t y f o r d e t e r m i n i n g p r o p e r t i e s of p a r a l l e l programs [36, 38, 44, 48} and f o r d e t e r m i n i n g p r o p e r t i e s of c o n c u r r e n t systems [18, 31, 37, 41, 50, 51, 70, 71, 72, 76, 83, 91, 98, 99] i s a l s o w e l l s t u d i e d . The b e h a v i o r a l p r o p e r t y c l o s e l y r e l a t e d t o c o n f l i c t i s p e r s i s t e n c e . A marked net i s p e r s i s t e n t i f the f i r i n g of a t r a n s i t i o n does not d i s a b l e any o t h e r t r a n s i t i o n . In F i g u r e 2.5, the f i r i n g of one of T2 or T6, under the marking shown, removes a t o k e n from the p l a c e , P4, t h u s d i s a b l i n g the o t h e r 16 t r a n s i t i o n . Hence, the net i s not p e r s i s t e n t . I f no c o n f l i c t s e x i s t i n the n e t , t h e n , the net i s p e r s i s t e n t . However, a net may have a c o n f l i c t and e x h i b i t p e r s i s t e n c e . In F i g u r e , 2 . 6 , the t r a n s i t i o n s T1 and T2 are i n c o n f l i c t s i n c e they share a common i n p u t p l a c e . The f i r i n g of T1 under the marking shown does not d i s a b l e T2. The f i r i n g of T2 under i t s e n a b l i n g marking does not d i s a b l e T1. The p e r s i s t e n c e p r o p e r t y of P e t r i n e t s i s u s e f u l i n the modeling and d e s i g n of hardware [8, 6 6 ] . A p e r s i s t e n t P e t r i net model of a hardware c i r c u i t ensures t h a t no race h a z a r d s e x i s t i n the c i r c u i t . The f i n a l p r o p e r t y of P e t r i n e t s t o be d i s c u s s e d i s boundedness. For some i n t e r p r e t a t i o n s of a n e t , one may c o n s i d e r the tokens t o r e p r e s e n t r e s o u r c e s and the p l a c e s t o r e p r e s e n t s t o r a g e f o r the r e s o u r c e s . For most r e a l systems of i n t e r e s t , the amount of s t o r a g e f o r r e s o u r c e s i s f i n i t e . A p l a c e i s k—bounded i f the token count of t h a t p l a c e never exceeds k. A net i s bounded i f a l l of i t s p l a c e s a r e bounded. A net i s s a f e i f a l l of i t s p l a c e s a r e bounded by a v a l u e of one. I t can e a s i l y be seen t h a t the examples d i s c u s s e d are not o n l y bounded but a l s o s a f e . T h i s completes the i n t r o d u c t i o n t o P e t r i n e t s and the p r o p e r t i e s r e l e v a n t t o the model i n t r o d u c e d i n Chapter 3. P e t r i n e t s are a r i c h a r e a of r e s e a r c h c o v e r i n g a wide range of a p p l i c a t i o n s and t h e o r e t i c a l t o p i c s . A s e l e c t i o n of papers i s l i s t e d i n the B i b l i o g r a p h y and a l s o i n the two survey papers [ 2 , 7 8 ] , 17 Figure 2.6: A persistent P e t r i net 18 2.2 A n a l y s i s of P e t r i Nets The a n a l y s i s of P e t r i n e t s i s s e p a r a t e d i n t o two phases: s t r u c t u r a l and b e h a v i o r a l a n a l y s i s [ 7 4 ] . The s e p a r a t i o n of the a n a l y s i s i n t o two phases i s based upon the two s t a g e s of m o d e l i n g , s y n t h e s i s of the model and o p e r a t i o n of the model. The s t r u c t u r a l a n a l y s i s d e t e r m i n e s the s t a t i c p r o p e r t i e s of the net and the b e h a v i o r a l a n a l y s i s d e t e r m i n e s the dynamic p r o p e r t i e s of the n e t . The s t r u c t u r a l a n a l y s i s i s used t o r e s t r i c t the b e h a v i o r a l a n a l y s i s t o P e t r i n e t s which are l i v e and bounded. 2.2.1 S t r u c t u r a l A n a l y s i s S t r u c t u r a l a n a l y s i s i s based upon the n o t i o n t h a t c e r t a i n s t r u c t u r e s i n the net a f f e c t the b e h a v i o r of the n e t . The c h a r a c t e r i s t i c m a t r i x i s an nX m m a t r i x r e p r e s e n t i n g the s t r u c t u r e of the n e t . The elements of r , r i j ' a r e the net e f f e c t on the token count of p l a c e i by the f i r i n g of t r a n s i t i o n j . The s t r u c t u r e s are i d e n t i f i e d by the s o l u t i o n s t o r«g<0, r»g>0, f•r<0, and f»r>0, where f and g are v e c t o r s and "•" i s a matix m u l t i p l i c a t i o n . The s o l u t i o n s t o r«g^0 and t o r»g<0 i d e n t i f y s e t s of 19 t r a n s i t i o n s which c r e a t e or d e s t r o y t o k e n s . C o n s i d e r the example shown i n F i g u r e 2.7. g, i s the t r a n s p o s e of a p o s i t i v e i n t e g e r s o l u t i o n t o r«g>0 1. Each element of g, i s g r e a t e r than or e q u a l t o z e r o . T2 and T3 a r e i d e n t i f i e d by the non-zero elements of g,. The s t r u c t u r e s i d e n t i f i e d by the p o s i t i v e i n t e g e r s o l u t i o n s t o r«g>0 are c a l l e d g e n e r a t o r s . As T2 and T3 are r e p e a t e d l y f i r e d , an a r b i t r a r y number of tokens can accumulate i n p l a c e P4. g 2 i s the t r a n s p o s e of a n o n - t r i v i a l s o l u t i o n t o r»g<0. T1 and T2 form an a b s o r b e r . I f T1 and T2 are r e p e a t e d l y f i r e d , an a r b i t r a r y number of tokens can be removed from the p l a c e P4. I f a g e n e r a t o r e x i s t s , the net cannot be bounded. I f an a b s o r b e r e x i s t s i n a net which i s bounded, t h e n , the net i s not l i v e [ 8 8 ] , The s o l u t i o n s t o f«r<0 and t o f«r^0 i d e n t i f y s e t s of p l a c e s which a f f e c t the movement of tokens t h r o u g h the n e t . f , i s a p o s i t i v e i n t e g e r s o l u t i o n t o f»r<0. The p l a c e s P3 and P4 which a r e i d e n t i f i e d by the non-zero elements of f , are c a l l e d a d e a d l o c k . I f t r a n s i t i o n T3 or T2 i s f i r e d a t o k e n remains i n P4 or P3, r e s p e c t i v e l y . However, i f T1 or T4 i s f i r e d , t h e n , P3 l o s e s a token which i t cannot r e g a i n by the f i r i n g of any o t h e r t r a n s i t i o n . f 2 i s a s o l u t i o n t o f«r>0 which i d e n t i f i e s P5 as a t r a p . Once a token i s p l a c e d i n P5 i t cannot be r e t u r n t o the r e s t of the n e t . In g e n e r a l a t r a p c o n s i s t s of s e v e r a l p l a c e s ; the tokens i n the t r a p remain i n the t r a p unable t o 1The r e l a t i o n s ^ and > a r e component-wise c o m p a r i s o n s . (a) A Pe t r i net (b) C h a r a c t e r i s t i c matrix, T 9i=(0, 1 , V, 0) g 2 = ( 1 , 1 , 0 , 0 ) f , = (0, 0, 1 , 1 , 0) f 2=(0, 0, 0, 0, 1) (c) Solutions to r»g, f»r Figure 2.7: Structural analysis 21 c i r c u l a t e i n the r e s t of the n e t . I f a deadlock e x i s t s i n a ne t , t h e n , the net i s not l i v e . I f a t r a p e x i s t s i n a n e t , t h e n , the net i s l i v e i f i t i s not bounded [ 8 8 ] . The dot p r o d u c t , r * g , i s the o v e r a l l r e s u l t on the token count of a p l a c e by the f i r i n g of a sequence of t r a n s i t i o n s , e. In the f i r i n g sequence, a, each t r a n s i t i o n i s f i r e d k^ t i m e s , where g = ( k ) , k 2 , . . . , k i , . . . , k | r i ) . I f r«g=0, t h e n , the net e f f e c t of a f i r i n g sequence, c, on a marking x i s 0. I f the net e f f e c t i s 0 , th e n , a marking r e t u r n s t o i t s e l f , t h a t i s , x=x. The f i r i n g sequence, y, where y i s any marking on a p a t h from the r o o t node and > i s a component-wise comparison, X i > y i f 1y^ i s t r u e . F i g u r e 2.8 shows a P e t r i net and i t s r e a c h a b i l i t y t r e e . The i n i t i a l marking of the net i s P1+P3. T3 i s the o n l y t r a n s i t i o n e n a b l e d i n the i n i t i a l m arking. The marking P1+P4 i s c r e a t e d by the f i r i n g of T3. T r a n s i t i o n T2 f i r e s on the marking P1+P4 y i e l d i n g the marking P1+P2+P3. Note t h a t P1+P2+P3>P1+P3 and P2>0P2, hence, the c o e f f i c i e n t of P2 becomes o. T r a n s i t i o n s T1 and T3 a r e e n a b l e d under P1+oP2+P3. The f i r i n g of T1 c r e a t e s the marking P1+oP2, s i n c e u-1=o. S i n c e t h e r e a r e no t r a n s i t i o n s which are e n a b l e d under P1+uP2, the node i s marked as a dead marking. The f i r i n g of T3 i n the (a) a P e t r i net (P1+oP2+P3)* where * i n d i c a t e s an e x i s t i n g s t a t e and ** i n d i c a t e s a dead s t a t e (b) R e a c h a b i l i t y Tree F i g u r e 2.8: B e h a v i o r a l a n a l y s i s 25 marking P1+uP2+P3 c r e a t e s the marking P1+oP2+P4. T r a n s i t i o n T2 i s f i r e d t o c r e a t e the marking P1+uP2+P3. S i n c e the marking l a b e l s a node, the l e a f i s marked as an e x i s t i n g node. The g e n e r a t i o n of the t r e e i s complete s i n c e a l l of the l e a v e s a r e e i t h e r dead markings or e x i s t i n g markings and no new markings can be g e n e r a t e d . The p r o p e r t i e s of the net a r e d e c i d e d by i n s p e c t i o n of the r e a c h a b i l i t y t r e e . The t r e e of F i g u r e 2.8(b) has a l e a f marked as a dead s t a t e . Thus, the net i s not l i v e . S i n c e the t r e e c o n t a i n s nodes which are l a b e l e d w i t h markings which use u f o r a c o e f f i c i e n t , the net i s not bounded. The net i s not p e r s i s t e n c e s i n c e the net i s not l i v e . F i g u r e 2.9 shows the r e a c h a b i l i t y t r e e f o r the P e t r i net of F i g u r e 2.6. The t r e e c o n t a i n s no l e a v e s which are marked as dead m a r k i n g s , hence, the net i s l i v e . The c o e f f i c i e n t s f o r each p l a c e i n each of the markings i s 1, t h e r e f o r e the net i s s a f e . The net i s a l s o p e r s i s t e n t , s i n c e , each node has a t most a s i n g l e s u c e s s o r . 2.3 C l a s s e s of P e t r i Nets The P e t r i net model p r e s e n t e d i n Chapter 3.3 i s based upon t h r e e c l a s s e s of P e t r i n e t s : marked graphs, timed P e t r i n e t s and c o l o u r e d P e t r i n e t s . Marked graphs a r e a c l a s s of P e t r i n e t s w i t h a r e s t r i c t e d s t r u c t u r e . The r e s t r i c t i o n p e r m i t s g e n e r a l c o n d i t i o n s f o r the l i v e n e s s and the s a f e n e s s 26 • r (P1+P2) | T1 (P3+P4) | T3 (P3+P1) j T2-(P2+P4) j T3 (P1+P2)* where * i n d i c a t e s an e x i s t i n g s t a t e F i g u r e 2.9: R e a c h a b i l i t y t r e e f o r net of F i g u r e 2.6 27 of nets b e l o n g i n g t o the c l a s s . The timed n e t s model the n o t i o n of time i n the n e t . C o l o u r e d n e t s a l l o w the modeling of r e s o u r c e a t t r i b u t e s and dynamic h i e r a r c h i e s . The timed P e t r i n e t s and c o l o u r e d P e t r i n e t s are e x t e n s i o n s t o the P e t r i n e t s d e s c r i b e d i n Chapter 2.1. The e x t e n s i o n s i n c r e a s e a b i l i t y of P e t r i n e t s t o model systems i n a n a t u r a l and compact manner. 2.3.1 Marked Graphs The c l a s s of P e t r i n e t s known as marked g r a p h s 1 , i s c r e a t e d by r e s t r i c t i n g the s t r u c t u r e of the n e t . Each p l a c e of the net i s r e s t r i c t e d t o be an i n p u t t o a s i n g l e t r a n s i t i o n and to be output t o a s i n g l e t r a n s i t i o n . The example shown i n F i g u r e 2.1 i s a marked graph. S i n c e no c o n f l i c t s a r e a l l o w e d , o n l y d e t e r m i n i s t i c systems can be modeled w i t h a marked graph. However, the r e s t r i c t i o n s do a l l o w a s i m p l i f i c a t i o n of the a n a l y s i s of the n e t s . Marked graphs a r e a p a r t i c u l a r i l y w e l l -s t u d i e d c l a s s of P e t r i n e t s [17, 44, 39, 52, 53, 67, 69, 70, 92, 93, 100] and many r e s u l t s a re known f o r t h i s c l a s s of P e t r i n e t s . Due t o the r e s t r i c t e d n a t u r e of the s t r u c t u r e of the marked graph, a d i r e c t e d graph, G=, where V i s a s e t of v e r t i c e s and E i s a s e t of edges, may be used as the g r a p h i c a l r e p r e s e n t a t i o n of a marked graph. The s e t s V and E a r e the t r a n s i t i o n s and p l a c e s , r e s p e c t i v e l y , of the marked graph. The 1A marked graph i s not t o be c o n f u s e d w i t h a marked P e t r i n e t . 28 tokens i n t h i s r e p r e s e n t a t i o n are r e c t a n g l e s p l a c e d on the edges of the graph. The producer-consumer model of F i g u r e 2.2 i s shown i n i t s d i r e c t e d graph r e p r e s e n t a t i o n i n F i g u r e 2.10. As a marked graph i s e x e c u t e d , the tokens move from edge t o edge as the t r a n s i t i o n s f i r e . The tokens f o l l o w the d i r e c t e d paths i n the graph, G. The l i v e n e s s and s a f e n e s s p r o p e r t i e s can be s p e c i f i e d i n terms of the d i r e c t e d p a t h s . The f o l l o w i n g theorems d e f i n e t h e s e p r o p e r t i e s . Theorem 2 [17] A marking i s l i v e i f and o n l y i f the token count of e v e r y d i r e c t e d c i r c u i t i s p o s i t i v e . Theorem 3 [17] A l i v e marking i s s a f e i f and o n l y i f e v e r y edge i s i n a d i r e c t e d c i r c u i t w i t h a token count of 1. In the producer-consumer example shown i n F i g u r e 2.10, the l i v e n e s s and s a f e n e s s are v e r i f i e d e a s i l y . There a r e t h r e e d i r e c t e d c i r c u i t s , T2-P1-T1-P2-T2, T2-P3-T3-P4-T2 and T4-P5-T3-P6-T4. By i n s p e c t i o n , each c i r c u i t has a token count of 1. Hence, the marked graph i s l i v e and s a f e . 2.3.2 Timed P e t r i Nets In a r e a l system, a c t i o n s o c c u r over a d u r a t i o n of t i m e . D u r i n g t h i s time n e i t h e r the i n p u t c o n d i t i o n s nor the output c o n d i t i o n s are v a l i d . As d e s c r i b e d above, the t r a n s i t i o n s have been assumed t o occur i n s t a n t a n e o u s l y . The n o t i o n of time i s 29 30 i n t r o d u c e d i n the form of a d e l a y between the time the t r a n s i t i o n i n i t i a t e s f i r i n g by removing tokens from the i n p u t p l a c e s and the time the t r a n s i t i o n completes f i r i n g by d e p o s i t i n g tokens i n the output p l a c e s [63, 64, 82, 81, 92, 93, 102]. F i g u r e 2.11 i l l u t r a t e s how a timed t r a n s i t i o n f i r e s where t r a n s i t i o n T1 has a d e l a y of T,, a p o s i t i v e r e a l number. An a l t e r n a t i v e method of modeling the n o t i o n of time i s a d e l a y i n the p l a c e s of the net [10, 71, 73, 8 7 ] , Tokens are unable t o be used t o enable t r a n s i t i o n s f o r a d e l a y time a f t e r i t i s d e p o s i t e d i n a p l a c e . The modeling of the time d e l a y i n t h i s manner r e q u i r e s a complex mechanism f o r the e x e c u t i o n of a timed n e t . U s i n g the i d e a s of s t e p w i s e r e f i n e m e n t s [ 9 4 ] , the two methods of modeling time can be shown t o e q u i v a l e n t . C o n s i d e r t r a n s i t i o n T1 of F i g u r e 2.12(a) w i t h time d e l a y , r , . T r a n s i t i o n T1 can be s u b s t i t u t e d by two t r a n s i t i o n s , T1' and T1", and a p l a c e PT1, as shown i n F i g u r e 2.12(b). In the net of F i g u r e 2.12(b), T1' and T1" occur i n s t a n t a n e o u s l y and the token i s h e l d i n p l a c e PT1 f o r a time r , . The time d e l a y i s now modeled as a d e l a y i n a p l a c e . S i m i l a r i l y , a p l a c e w i t h a d e l a y may be r e p l a c e d by a t r a n s i t i o n w i t h a d e l a y and two p l a c e s as shown i n F i g u r e 2.13. A second concept of importance f o r timed P e t r i n e t s i s synchrony. In r e a l systems, s e v e r a l a c t i o n s may b e g i n c l o s e enough i n time t h a t they may be c o n s i d e r e d t o b e g i n 31 A T1 B 0 (a) T r a n s i t i o n T1 P l a c e A 1 r— — t t P l a c e B i - J — T t + T, (b) Token count of p l a c e s A and B 1 0 1 0 F i g u r e 2.11: F i r i n g of t r a n s i t i o n TI A T1 B (a) O A T1 ' PT1 T1 " (b) F i g u r e 2.12: A timed t r a n s i t i o n - O T1 (a) T1 A' ' TA A" .(b).. F i g u r e 2.13: A timed t r a n s i t i o n 33 s i m u l t a n e o u s l y . I f each a c t i o n i s modeled as a s e p a r a t e t r a n s i t i o n , then i n o r d e r t o c o r r e c t l y s i m u l a t e the b e h a v i o r of the a c t i o n s , the t r a n s i t i o n s must b e g i n f i r i n g a t the same t i m e . The n o t i o n of synchronous f i r i n g of t r a n s i t i o n s a l s o reduces the s i z e of the s t a t e space of the n e t . C o n s i d e r two s t a t e s , one i n which k t r a n s i t i o n s are e n a b l e d and the second i n which the k t r a n s i t i o n s have been f i r e d . I f a s i n g l e t r a n s i t i o n i s f i r e d a t a t i m e , t h e r e are k! d i f f e r e n t o r d e r s i n which the t r a n s i t i o n s may be f i r e d . For the f i r i n g sequences, t h e r e are I (f) i n t e r m e d i a t e s t a t e s i n which some of the t r a n s i t i o n s have been f i r e d . I f the t r a n s i t i o n s a r e a l l o w e d t o f i r e s y n c h r o n o u s l y , then, a l l of the i n t e r m e d i a t e s t a t e s are e l i m i n a t e d . Hence, a more compact r e p r e s e n t a t i o n of the s t a t e space i s p o s s i b l e . The i n t r o d u c t i o n of the n o t i o n of time t o P e t r i n e t s c o m p l i c a t e s the d e s c r i p t i o n of the s t a t e of a n e t . A marking, m, of a net i s no l o n g e r s u f f i c i e n t t o d e s c r i b e the s t a t e of a n e t . At any t i m e , t r a n s i t i o n s may be f i r i n g and t h i s i n f o r m a t i o n must be i n c l u d e i n the s t a t e d e s c r i p t i o n . The time a t which the d e s c r i p t o r i s taken i s an i s s u e here. A c o n v e n i e n t time t o d e s c r i b e the net i s the i n s t a n t a f t e r a t r a n s i t i o n completes f i r i n g [ 1 0 2 ] . At t h i s t i m e , o t h e r t r a n s i t i o n s may become e n a b l e d and b e g i n f i r i n g as a r e s u l t of the t r a n s i t i o n c o m p l e t i n g i t s f i r i n g . The t r a n s i t i o n s which have not completed f i r i n g a r e d e s c r i b e d by the r e m a i n i n g time f u n c t i o n , r . 34 r = { ( T i , R i ) } c T X H + where i s a r e a l p o s i t i v e number which i s the time r e m a i n i n g i n the f i r i n g of t r a n s i t i o n T±. The s t a t e of a t i m e d net i s a p a i r , (m,r), when a t r a n s i t i o n has j u s t completed f i r i n g . S i n c e the modeling of the n o t i o n of time i s a b e h a v i o r a l e x t e n s i o n , the a n a l y s i s of timed P e t r i n e t s d i f f e r s o n l y i n the b e h a v i o r a l a n a l y s i s . A t r e e c a l l e d the graph of i n s t a n t a n e o u s d e s c r i p t o r s , GRID, r e p r e s e n t s the s t a t e space of the t i med n e t . The graph of i n s t a n t a n e o u s d e s c r i p t o r s i s g e n e r a t e d i n the same manner as the r e a c h a b i l i t y t r e e , d e s c r i b e d i n Chapter 2.2.2. The nodes of the GRID are i n s t a n t a n e o u s d e s c r i p t o r s , d^=(m^,r^), and the edges are l a b e l e d w i t h a s e l e c t o r , where a s e l e c t o r , scT*. The s e l e c t o r , s-x, i n d i c a t e s which t r a n s i t i o n s were f i r e d t o c r e a t e the s t a t e , d j . S i n c e tokens become a v a i l a b l e to. enable t r a n s i t i o n s a t the c o m p l e t i o n of the f i r i n g of a t r a n s i t i o n , a s t a t e i s not dead i f t r a n s i t i o n s have y e t t o complete f i r i n g . A s t a t e i s dead i f t h e r e are no t r a n s i t i o n s which have not completed f i r i n g and t h e r e are no t r a n s i t i o n s e n a b l e d . 35 2.3.3 C o l o u r e d P e t r i Nets In a P e t r i net model of a system, the tokens o f t e n r e p r e s e n t r e s o u r c e s i n the system. The r e s o u r c e s may have a t t r i b u t e s which may not be e a s i l y r e p r e s e n t e d i n a P e t r i n e t . Many a u t h o r s have add r e s s e d t h i s problem by a s s i g n i n g the a t t r i b u t e s t o the tokens [ 2 1 , 32, 38, 71, 73, 83, 98, 99, 101], C o l o u r e d tokens are a c o n v e n i e n t method of v i s u a l i z i n g t o k e n s w i t h a t t r i b u t e s [38, 83, 101]. Except i n the case of an i n f i n i t e number of c o l o u r s , a P e t r i net w i t h c o l o u r e d tokens has an e q u i v a l e n t P e t r i net w i t h u n c o l o u r e d t o k e n s . The c o n s t r u c t i o n of the e q u i v a l e n t net w i t h o u t c o l o u r e d tokens i n v o l v e s a d u p l i c a t i o n of t r a n s i t i o n s and p l a c e s f o r each c o l o u r [ 7 9 ] . The c o n s t r u c t i o n r e s u l t s i n a l a r g e and complex n e t . The use of c o l o u r e d tokens p r o v i d e s a n a t u r a l and compact r e p r e s e n t a t i o n . Beyond the s i m p l e use of a t t r i b u t e s , the i m p o s i t i o n of a p a r t i a l o r d e r on the c o l o u r s a l l o w s the modeling of p r i o r t y h i e r a r c h i e s . C o n s i d e r the example shown i n F i g u r e 2.14 [ 3 8 ] . The p r o d u c e r s , P i , and P i 2 , d e p o s i t u n i t s i n t o the c o r r e s p o n d i n g b u f f e r , B-J-. The consumers, C, and C 2 consume u n i t s from b u f f e r s , B, and B 2, r e s p e c t i v e l y . The consumers i n t e r a c t w i t h t h e i r c o r r e s p o n d i n g b u f f e r t h rough a c h a n n e l of c a p a c i t y one. Consumer C, t a k i n g a u n i t produced b y producer PT T has the h i g h e s t p r i o r i t y on the c h a n n e l over a l l o t h e r s . Consumer C 2 t a k i n g a u n i t produced by producer P 2 2 has the l o w e s t p r i o r i t y on the c h a n n e l . The p r i o r i t y i s a dynamic 3 6 F i g u r e 2.14: A producer-consumer system 37 p r i o r i t y s i n c e the p r i o r i t y of the consumers depends on the u n i t s p r e s e n t i n the b u f f e r s . The c o l o u r e d P e t r i net model of the producer-consumer system of F i g u r e 2.14 i s shown i n F i g u r e 2.15. The p a r t i a l o r d e r on the c o l o u r s i s shown at the bottom of F i g u r e 2.15. The l a b e l s on the o utput edges of the t r a n s i t i o n s are the c o l o u r of the token d e p o s i t e d i n the output p l a c e . The l a b e l s on the i n p u t edges of the t r a n s i t i o n s are the minimum c o l o u r which may be used t o enable the t r a n s i t i o n . The tokens a r e compared under the p a r t i a l o r d e r shown. Tokens not connected by a p a t h a r e not comparable and cannot be used f o r an edge so l a b e l e d . The p r i o r i t y of a t r a n s i t i o n i s d etermined by the minimum c o l o u r of the tokens which a r e a v a i l a b l e t o enable the t r a n s i t i o n a t t h a t p o i n t i n the e x e c u t i o n of the n e t . Suppose P7 c o n t a i n s a token of c o l o u r C 1 2 and P8 c o n t a i n s a token of c o l o u r C 2 2 . Both T5 and T6 are e n a b l e d but T5 has a h i g h e r p r i o r i t y s i n c e the minimum e n a b l i n g c o l o u r of T5, C 1 2 , i s h i g h e r than the minimum e n a b l i n g c o l o u r of T6, C 2 2 . I f P7 has a token of c o l o u r C 1 2 and P8 has a token of c o l o u r C 2 1 , e i t h e r T5 or T6 may f i r e s i n c e C 2, and C 1 2 are incomparable under the p a r t i a l o r d e r . One can e a s i l y see t h a t i f P7 has a token of c o l o u r C l 1 f t h e n , T5 has p r i o r i t y over the f i r i n g of any o t h e r t r a n s i t i o n . The c o l o u r e d P e t r i net c o r r e c t l y models the dynamic p r i o r i t y h i e r a r c h y s p e c i f i e d . The c o l o u r e d P e t r i n e t s may a l s o be used t o model r e e n t r e n c y "in computer s o f t w a r e [38, (Pi 1) (Pia) (Pai) F i g u r e 2.15: A c o l o u r e d P e t r i net 39 101 3 . A f u r t h e r a b s t r a c t i o n of the c o l o u r e d P e t r i net model i s the i n t r o d u c t i o n of t r a n s i t i o n schemes [32, 9 8 ] . T r a n s i t i o n s a r e s i m i l a r i f they a r e connected t o the same p l a c e s i n the same manner except f o r the l a b e l s on the c o n n e c t i n g edges. An example of s i m i l a r t r a n s i t i o n s i s shown i n F i g u r e 2.16. The two t r a n s i t i o n s may be thought t o be two i n s t a n c e s of the t r a n s i t i o n shown i n F i g u r e 2.17. A t r a n s i t i o n scheme may be thought of as a mapping of elements of P* onto o t h e r elements of P*. Thus, t r a n s i t i o n schemes a l l o w a c o l o u r e d net t o r e t a i n the n a t u r a l r e p r e s e n t a t i o n of a system. F i g u r e 2.16: S i m i l a r t r a n s i t i o n s p Q R • • e • • ® F i g u r e 2.17: A t r a n s i t i o n scheme 41 CHAPTER 3 THE PETRI NET FORMULATION A s c h e d u l i n g problem i s comprised of a t a s k system, the r e s o u r c e s f o r i t s e x e c u t i o n and a s t r a t e g y f o r the s c h e d u l i n g of t a s k s . A P e t r i net i s used here t o f o r m u l a t e the s t r u c t u r e of the t a s k system and the s t r u c t u r e of the r e s o u r c e s . The t o o l s of a n a l y s i s of P e t r i n e t s a r e used t o model the b e h a v i o r of the s c h e d u l i n g s t r a t e g y . The approach which i s d e f i n e d here d i f f e r s s i g n i f i c a n t l y from p r e v i o u s P e t r i - n e t - b a s e d approaches t o s c h e d u l i n g problems. 3.1 The G e n e r a l S c h e d u l i n g Model The g e n e r a l s c h e d u l i n g model p r e s e n t e d here d i f f e r s s l i g h t l y from a more c o n v e n t i o n a l treatment of the model [16, 26, 27, 2 8 ] . The f o r m a l i z a t i o n f o r the model i s p r e s e n t e d i n Appendix A. The main d i f f e r e n c e i s t h a t the p r o c e s s o r s a r e t o be c o n s i d e r e d as j u s t another r e s o u r c e and not as a s p e c i a l r e s o u r c e . The reason f o r the t r e a t m e n t of the p r o c e s s o r s as another r e s o u r c e i s demonstrated d u r i n g the c o n s t r u c t i o n of the P e t r i net model. The s c h e d u l i n g problems a r e drawn from the g e n e r a l s c h e d u l i n g model. The r e s o u r c e s of the g e n e r a l s c h e d u l i n g model a r e any p h y s i c a l r e s o u r c e which a t a s k may r e q u i r e i n o r d e r f o r i t t o be e x e c u t e d . In g e n e r a l , the r e s o u r c e s i n c l u d e a t l e a s t one se t of p r o c e s s o r s . A d d i t i o n a l r e s o u r c e s may r e p r e s e n t p r i m a r y 42 or secondary s t o r a g e , i n p u t / o u p u t d e v i c e s or s u b r o u t i n e l i b r a r i e s . A s e t of r e s o u r c e s may c o n t a i n i d e n t i c a l u n i t s , u n i t s of d i f f e r e n t f u n c t i o n a l i t y , u n i t s of d i f f e r e n t speed or a c o m b i n a t i o n of u n i t s of v a r y i n g f u n c t i o n a l i t y and/or speed. For example, s e v e r a l s u b r o u t i n e l i b r a r i e s may each c o n t a i n d i f f e r e n t s e t s of s u b r o u t i n e s . The s u b r o u t i n e l i b r a r i e s may be c o n s i d e r e d t o be a s i n g l e type of r e s o u r c e w i t h u n i t s of v a r i n g f u n c t i o n a l i t y . I t i s c o n v e n i e n t t o c o n s i d e r the r e s o u r c e s t o be a v a i l a b l e i n d i s c r e t e u n i t s , where a u n i t i s the s m a l l e s t amount which can be a q u i r e d by a t a s k . The t a s k system of the g e n e r a l s c h e d u l i n g model i s d e f i n e d on a s e t of t a s k s , ={T, , T 2, . . . , T r } , where r i s the c a r d i n a l i t y of the s e t . Each t a s k of the s e t , ^7, i s assumed t o be e x e c u t e d once. The o p e r a t i o n a l precedence c o n s t r a i n t s s p e c i f y the d a t a dependencies between the t a s k s . The precedence c o n s t r a i n t s are a p a r t i a l o r d e r , <, on the t a s k s . I f T^0 i s the e x e c u t i o n time of t a s k j on p r o c e s s o r i . 43 The e q u a l i t y i s i n t r o d u c e d s i n c e two dummy t a s k s are used i n the c o n s t r u c t i o n of the P e t r i net f o r m u l a t i o n . I f a t a s k T^ i s unable t o be e x e c u t e d on a p r o c e s s o r j , t h e n , T— i s i n f i n i t e . Each t a s k i s assumed t o execute on a t l e a s t one p r o c e s s o r . A t a s k system i s shown i n F i g u r e 3.1. The t a s k s e t c o n s i s t s of ten t a s k s , T1 through T10. Each node i n the graph r e p r e s e n t s a t a s k . The l a b e l s of the nodes i n d i c a t e the t a s k and the e x e c u t i o n time of the t a s k . The d i r e c t e d edges of the graph i n d i c a t e t h a t d a t a i s t r a n s f e r r e d between t a s k s and the d i r e c t i o n of the t r a n s f e r . The t a s k s r e q u i r e r e s o u r c e s t o e x e c u t e . The r e s o u r c e r e q u i r e m e n t s are s p e c i f i e d by (f^ = [ R 1 ( T j ) , R 2 ( T j ) , . . . , R s ( T j ) ] f o r each t a s k j , where s i s the number of s e t s of r e s o u r c e s . The component R ^ ( T j ) s p e c i f i e s the the amount of r e s o u r c e i r e q u i r e d f o r the e x e c u t i o n of t a s k T j . I t i s assumed t h a t the maximum requirement of any t a s k may be s a t i s f i e d by the i n i t i a l r e s o u r c e c o n f i g u r a t i o n . The r e s o u r c e r e q u i r e m e n t s a r e s p e c i f i e d i n the d i s c r e t e u n i t s i n which the r e s o u r c e s are a v a i l a b l e . I t i s assumed t h a t a t a s k r e q u i r e s an amount of r e s o u r c e f o r the d u r a t i o n of i t s e x e c u t i o n . The t a s k n e i t h e r r e q u i r e s more r e s o u r c e s d u r i n g the e x e c u t i o n nor does the t a s k r e l e a s e any r e s o u r c e s u n t i l i t completes e x e c u t i o n . Tasks whose r e s o u r c e r e q u i r e m e n t s a r e such may be modeled as s e p a r a t e t a s k s . The c l a s s of s c h e d u l i n g s t r a t e g i e s t o be c o n s i d e r e d here 44 T9/2 T10/1 Task/execution time F i g u r e 3.1: Task system \%J, <,{ri)) 45 i s r e s t r i c t e d t o s t r a t e g i e s which are nonpreemptive. Nonpreemptive s c h e d u l i n g s t r a t e g i e s are c h a r a c t e r i z e d by t a s k s b e i n g e x e c u t e d w i t h o u t i n t e r r u p t i o n , t h a t i s , once a t a s k b e g i n s e x e c u t i o n , i t runs t o c o m p l e t i o n w i t h o u t s t o p p i n g . The performance c r i t e r i a used here i s t o m i n i m i s e the e x e c u t i o n t i m e , w, which i s the time t o execute a l l of the t a s k s of the t a s k s e t . The o p t i m a l e x e c u t i o n time i s denoted by w*. The performance of a s c h e d u l i n g s t r a t e g y on a g i v e n problem i s e x p r e s s e d as a r a t i o , w/w*. 3.2 The P e t r i Net F o r m u l a t i o n The P e t r i net based approach t o the s c h e d u l i n g problem i s s e p a r a t e d i n t o two phases. F i r s t , the s c h e d u l i n g model i s f o r m u l a t e d as a t i m e d - c o l o u r e d P e t r i n e t . The P e t r i net models the s t r u c t u r e of the s c h e d u l i n g problem, t h e d a t a r e l a t i o n s h i p s between the t a s k s and the p r o p e r t i e s of the r e s o u r c e s . The second phase models the b e h a v i o r of the s c h e d u l i n g problem. The b e h a v i o r of the s c h e d u l i n g problem i s d e t e r m i n e d by the s c h e d u l i n g s t r a t e g y and the i n i t i a l s e t of r e s o u r c e s . The s c h e d u l i n g s t r a t e g y i s modeled by m o d i f i c a t i o n s t o the b e h a v i o r a l a n a l y s i s of the P e t r i n e t . Hence, a s c h e d u l e i s g e n e r a t e d by the e x e c u t i o n of the net f o r an i n i t i a l m a rking. 46 3.2 .1 The C o n s t r u c t i o n of the P e t r i Net Model The P e t r i net model i s a c o l o u r e d P e t r i net extended w i t h the use of t r a n s i t i o n f i r i n g t i m e s . The net s t r u c t u r e i s d e r i v e d from the precedence c o n t r a i n t s of the task system. The c o l o u r e d tokens are used to model the r e s o u r c e s , both the data and p h y s i c a l r e s o u r c e s , r e q u i r e d f o r the e x e c u t i o n of the task system. Each task i s r e p r e s e n t e d by a t r a n s i t i o n scheme. Each i n s t a n t i a t i o n of the t r a n s i t i o n scheme i s a s s i g n e d a f i r i n g t i m e , the e x e c u t i o n time of the task g iven the p a r t i c u l a r set of r e s o u r c e s . The c o l o u r e d - t i m e d P e t r i net p r o v i d e s a n a t u r a l r e p r e s e n t a t i o n for the task system and for the r e s o u r c e s used for the e x e c u t i o n of the task sys tem. A l g o r i t h m 1 i s an a l g o r i t h m f o r the c o n s t r u c t i o n of the P e t r i net model g i v e n the task system and the r e s o u r c e s . The a l g o r i t h m i s shown in F i g u r e 3 . 2 . The i n i t i a l p o r t i o n of the c o n s t r u c t i o n may be thought of i n terms of m a n i p u l a t i o n s to the g r a p h i c a l r e p r e s e n t a t i o n of the precedence c o n s t r a i n t s . The c o n s t r u c t i o n of the P e t r i net model beg ins wi th the d i r e c t e d a c y c l i c graph r e p r e s e n t i n g the precedence c o n s t r a i n t s of the task system. The g e n e r a l precedence r e l a t i o n i s f i r s t c o n v e r t e d to a s i n g l e - e n t r y node, s i n g l e e x i t node precedence g r a p h . The a d d i t i o n of the STOP-START edge completes the augmented precedence g r a p h . R e c a l l , a marked graph may be d e f i n e d i n terms of a d i r e c t e d g r a p h . Hence, the augmented precedence graph d e f i n e s a marked g r a p h . The nodes and edges 47 1. To the precedence graph, add two nodes l a b e l l e d "START" and "STOP". 2. Add a d i r e c t e d edge from the START node t o each . node which has no incoming edges except the STOP node. 3. Add a d i r e c t e d edge from each node which has no outgoing edges to the STOP. node. 4. Add a d i r e c t e d edge from the STOP node to the START node. L a b e l the edge "READY" and mark i t with a s i n g l e uncoloured token. 5. L a b e l each of the edges with a p l a c e name. 6. L a b e l each of the nodes wi t h a t r a n s i t i o n name. 7. Repeat Steps 8-11 f o r each r e s o u r c e . 8. Define a set of c o l o u r s , C i = ( X ^ , < i ) . 9. Add a p l a c e and l a b e l i t with the name of the r e s o u r c e . 10. Add d i r e c t e d edges to and from each node(task) which r e q u i r e s t h a t resource and l a b e l the edges with Cf. 11. Mark the p l a c e with the number of tokens r e p r e s e n t i n g the i n i t i a l r esource c o n d i t i o n s . 12. D e f i n e a set of c o l o u r s , Co( = (X^, <<*), f o r the data tokens. 13. D e f i n e a t r a n s i t i o n scheme f o r each node(task) i n the graph. 14. D e f i n e a set of c o l o u r s f o r the net, C=VCi^Co^Cd, where C 0 i s the uncoloured token. F i g u r e 3.2 A l g o r i t h m 1 48 ar e l a b e l e d f o r the f o r m a l r e p r e s e n t a t i o n . The d i r e c t e d a c y c l i c graph of the precedence c o n s t r a i n t s of a t a s k system i s shown i n F i g u r e 3.1 [ 1 6 ] . The precedence i s assumed t o be from the t o p t o the bottom. The marked graph r e s u l t i n g from Steps 1-6, i s shown i n F i g u r e 3.3. The marked graph r e t a i n s the n a t u r a l r e p r e s e n t a t i o n of t h e precedence c o n s t r a i n t of the t a s k system. The remainder of the c o n s t r u c t i o n d e a l s w i t h the r e s o u r c e s n e c e s s a r y f o r the e x e c u t i o n of the t a s k system. I t i s c o n v e n i e n t t o c o n s i d e r t h i s p o r t i o n of the c o n s t r u c t i o n as o p e r a t i n g on the f o r m a l r e p r e s e n t a t i o n of the n e t . The r e s o u r c e s are r e p r e s e n t e d by a p l a c e i n the P e t r i net marked w i t h tokens from a c o l o u r s e t . A p l a c e i s added t o the net which i s g e n e r a t e d by Steps 1-6 of A l g o r i t h m 1. The p l a c e i s c o n n e c t e d t o and from each t r a n s i t i o n ( t a s k ) which r e q u i r e s t h a t r e s o u r c e s . The modeling of the r e s o u r c e s i n t h i s manner i s based on the assumption t h a t a t a s k uses the r e s o u r c e f o r the d u r a t i o n of i t s e x e c u t i o n time and does not r e l e a s e the r e s o u r c e u n t i l the e x e c u t i o n i s completed. The edges are l a b e l e d w i t h the c o l o u r s e t d e f i n e d f o r the r e s o u r c e . The P e t r i net model a l l o w s the mo d e l i n g of a v a r i e t y of r e s o u r c e s and p r o c e s s o r s i t u a t i o n s . The modeling of the p r o c e s s o r s as a r e s o u r c e a l l o w s a s l i g h t l y more f l e x i b l e m o d e l i n g of f u n c t i o n a l l y d e d i c a t e d p r o c e s s o r s [ 5 7 ] . Groups of f u n c t i o n a l l y d e d i c a t e d p r o c e s s o r s 49 F i g u r e 3 . 3 : The marked graph a f t e r S t e p 6 50 may be modeled by d i f f e r e n t p l a c e s i n the n e t . A c o l o u r s e t and p a r t i a l order i s d e f i n e d f o r each group a l l o w i n g f o r the m odeling of v a r i a t i o n w i t h i n the group of p r o c e s s o r s . A c o l o u r s e t i s d e f i n e d f o r each r e s o u r c e p l a c e added i n Step 9. A c o l o u r i d e f i n e d f o r each a t t r i b u t e t o be c o n s i d e r e d f o r the r e s o u r c e . A p a r t i a l o r d e r i s d e f i n e d on t h e c o l o u r s e t r e f l e c t i n g the r e l a t i o n s h i p s between the a t t r i b u t e s of the r e s o u r c e s . The s p e c i a l case of i d e n t i c a l r e s o u r c e s , e i t h e r r e s o u r c e s or p r o c e s s o r s , i s modeled by u n c o l o u r e d t o k e n s . I f the r e s o u r c e s are not i n t e r c h a n g a b l e , a n u l l p a r t i a l o r d e r i s s p e c i f i e d . A t r a n s i t i o n scheme i s d e f i n e d f o r each t r a n s i t i o n ( t a s k ) of the net a f t e r a l l of the r e s o u r c e p l a c e s have been added. The t r a n s i t i o n scheme i s the f i n a l s t e p i n the s p e c i f i c a t i o n of the b e h a v i o r of the t r a n s i t i o n ( t a s k ) . The i n s t a n c e s of a t r a n s i t i o n scheme map a s e t of i n p u t tokens on t o a s e t of output t o k e n s . T h i s c o r r e s p o n d s t o d i f f e r e n t i n p u t c o n d i t i o n s f o r the e x e c u t i o n of the t a s k r e s u l t i n g i n d i f f e r e n t output c o n d i t i o n s . The t r a n s i t i o n schemes are d e f i n e d i n such a manner t h a t none of the c o l o u r s d e f i n e d i n Step 8 a r e redundant. A s i m p l e t r a n s i t i o n scheme i s shown i n T a b l e 3 . 1 . The t a s k i s t a s k T4 from the example shown i n F i g u r e 3 . 1 . The t a s k system i s assumed t o r e q u i r e no a d d i t i o n a l r e s o u r c e s f o r the e x e c u t i o n except the p r o c e s s o r s . The p r o c e s s o r s a r e of speeds C3 co e ci a C2 (g> (b) F i g u r e 3.4: C o l o u r s e t s P5 P6 P8 P r o c e s s o r P10 P1 1 • • O CO • • 2 • • C1 • • 3 • • • C2 • 4 T a b l e 3.1: T r a n s i t i o n scheme, T4 52 :b 2:b 3=1:2/3:1/2. The d a t a tokens a r e a l l u n c o l o u r e d . The t o p t o bottom o r d e r may be used t o d e f i n e a p r i o r i t y h i e r a r c h y between the i n s t a n t i a t i o n s of the t r a n s i t i o n scheme. Three examples i l l u s t r a t e the use of c o l o u r s e t s , p a r t i a l o r d e r s and the t r a n s i t i o n scheme i n modeling r e s o u r c e s . F i r s t c o n s i d e r the example of a s e t of p r o c e s s o r s of d i f f e r e n t speeds. A c o l o u r s e t and p a r t i a l o r d e r a r e shown i n F i g u r e 3 . 4 ( b ) . The c o l o u r s a r e d e p i c t e d by the d i f f e r e n t s hading of the t o k e n s . CO and C2 r e p r e s e n t the f a s t e s t and the s l o w e s t p r o c e s s o r s , r e s p e c t i v e l y . I t i s assumed t h a t the f a s t e r p r o c e s s o r i s t o be used b e f o r e a slower p r o c e s s o r , so the p a r t i a l o r d e r i s d i r e c t e d downwards. F i g u r e 3.4(a) shows a s l i g h t l y more complex c o l o u r s e t and p a r t i a l o r d e r . The c o l o u r s e t models a group of p r o c e s s o r s of d i f f e r e n t speeds and some of which a r e f u n c t i o n a l l y d e d i c a t e d . C2 and C3 r e p r e s e n t p r o c e s s o r s w i t h s p e c i a l hardware, f o r example, a f l o a t i n g - p o i n t p r o c e s s o r and an a r r a y p r o c e s s o r . C1 and CO are g e n e r a l purpose p r o c e s s o r s of d i f f e r e n t speeds. C1 i s assumed t o be f a s t e r than CO. The g e n e r a l purpose p r o c e s s o r s can p e r f o r m the f u n c t i o n s of C2 and C3 i n s o f t w a r e , and hence at a s l o w e r speed. The p a r t i a l o r d e r r e f l e c t s the d i f f e r e n c e s between the p r o c e s s o r s both i n the f u n c t i o n a l i t y and the speed. The f i n a l example i s a d y n a m i c a l l y r e c o n f i g u r a b l e a r c h i t e c t u r e [45, 46, 9 7 ] . The a r c h i t e c t u r e t o be modeled, CE- CE. F i g u r e 3.5: A d y n a m i c a l l y r e c o n f i g u r a b l e a r c h i t e c t u r e 54 shown i n F i g u r e 3.5, c o n s i s t s of t h r e e 1 6 - b i t computing e l e m e n t s , C E j . Each CEj c o n s i s t s of a p r o c e s s i n g element, PE^, a memory element, ME£, and an i n p u t / o u t p u t element, GEf. The computing elements are connected by two c o n n e c t i n g e l e m e n t s , MS£. The c o n n e c t i n g elements c o n t r o l the s i z e of the p r o c e s s o r s c r e a t e d by the computing elements. The r e c o n f i g u r a t i o n i s c o n t r o l l e d by the c o n t r o l element, V. The a r c h i t e c t u r e can be r e c o n f i g u r e d i n t o 1 6 - b i t , 3 2 - b i t or 4 8 - b i t p r o c e s s o r s . I f a c o n n e c t i n g element a l l o w s a c o n n e c t i o n , t h e n , the two computing elements a c t as a s i n g l e 3 2 - b i t p r o c e s s o r . I f the c o n n e c t i n g element does not a l l o w a c o n n e c t i o n , t h e n , the two computing elements are c o n s i d e r e d t o be two s e p a r a t e p r o c e s s o r s . The c o n n e c t i n g elements a l l o w the a r c h i t e c t u r e t o be r e c o n f i g u r e d i n t o c o m b i n a t i o n s of the 16-b i t computing elements. The o n l y r e s t r i c t i o n i s the two outermost computing elements cannot be connected t o form a 32-b i t p r o c e s s o r . C o n s i d e r the precedence c o n s t r a i n t s shown i n F i g u r e 3.1. The p r o c e s s o r r e q u i r e m e n t s and new t a s k e x e c u t i o n times appear i n T a ble 3.2. The t a s k e x e c u t i o n t i m e s are random i n t e g e r s between 1 and 5. The marked graph p o r t i o n of the P e t r i net model remains the unchanged as shown i n F i g u r e 3.3. A s i n g l e p r o c e s s o r s p l a c e i s added t o the marked graph. Three c o l o u r e d t o k e n s , C1, C2 and C3, a r e used t o r e p r e s e n t the t h r e e computing e l e m e n t s , C E 1 f CE 2 and C E 3 , r e s p e c t i v e l y . The p a r t i a l o r d e r on the c o l o u r s i s n u l l s i n c e the r e l a t i o n s h i p s Task No. of b i t s T i T1 16 3 T2 32 3 T3 • 16 5 • T4 48 3 T5 32 4 T6 32 5 T7 32 3 T8 1 6 1 T9 32 2 T10 16 1 Table 3.2: Task processor requirements and execution times 56 b e t w e e n t h e c o m p u t i n g e l e m e n t s i s more c l e a r l y m o d e l e d i n t h e t r a n s i t i o n s c hemes. F o r t h e s p e c i f i c a t i o n o f t h e t r a n s i t i o n s chemes, c o n s i d e r t a s k T3. The e x e c u t i o n o f t a s k T3 r e q u i r e s a 1 6 - b i t p r o c e s s o r . T h i s r e q u i r e m e n t i s s a t i s f i e d by any o f t h e t h r e e c o m p u t i n g e l e m e n t s a c t i n g a s a 1 6 - b i t p r o c e s s o r . I f t h e m i d d l e c o m p u t i n g e l e m e n t , C E 2 , i s a s s i g n d t a s k T3, t h e r e m a i n i n g c o m p u t i n g e l e m e n t s c o u l d o n l y be c o n f i g u r e d a s two 1 6 - b i t p r o c e s s o r s . A b e t t e r c o n f i g u r a t i o n w o u l d be t o c o n f i g u r e an end c o m p u t i n g e l e m e n t a s a 1 6 - b i t p r o c e s s o r , w h i c h a l l o w s t h e p o s s i b i l i t y o f a 3 2 - b i t p r o c e s s o r t o be c o n f i g u r e d . The t r a n s i t i o n scheme f o r t a s k T3 i s shown i n T a b l e 3.3 i n w h i c h t h e p r i o r i t y i s assumed t o be t o p t o b o t t o m . A t a s k r e q u i r i n g a 3 2 - b i t p r o c e s s o r , f o r e x a m p l e t a s k T7, i s e x e c u t e d on a p r o c e s s o r c o m p r i s e d o f t h e c o m p u t i n g e l e m e n t s , C E T - C E J o r C E 2 - C E 3 . The c o m p u t i n g e l e m e n t s must a l l be c o n n e c t e d i n o r d e r t o e x e c u t e t a s k T4 w h i c h r e q u i r e s a 4 8 - b i t p r o c e s s o r . The t r a n s i t i o n schemes f o r t a s k s T7 a n d T4 a r e shown i n T a b l e s 3.4 and 3.5, r e s p e c t i v e l y . I n c o n t r a s t t o t h e t r a n s i t i o n scheme a p p r o a c h t o t h e m o d e l i n g o f t h e d y n a m i c a l l y r e c o n f i g u r a b l e a r c h i t e c t u r e , c o n s i d e r m o d e l i n g t h e t h r e e c o m p u t i n g e l e m e n t s by t h r e e u n c o l o u r e d t o k e n s . The P e t r i n e t w o u l d be a g e n e r a l i s e d P e t r i n e t ( s e e A p p e n d i x 1 ) . The w e i g h t s on t h e e dges f r o m t h e p r o c e s s o r p l a c e i n d i c a t e t h e number o f c o m p u t i n g e l e m e n t s t o c r e a t e t h e p r o c e s s o r o f c o r r e c t w o r d w i d t h . A p a r t i a l n e t o f t a s k s T3 and T7 m o d e l e d i n t h i s f a s h i o n i s shown i n F i g u r e Input Data Processor Output Data P3 C1 P8+P9 P3 C3 P8+P9 P3 C2 P8+P9 Ta b l e 3.3: T r a n s i t i o n scheme f o r task T3 Input Data Processor Output Data P11+P12 C1+C2 P15 PI1+P12 C2+C3 P15 Table 3.4: T r a n s i t i o n scheme f o r task T7 Input Data Processor " Output Data P5+P6+P7 C1+C2+C3 P10+P11 Tabl e 3.5: T r a n s i t i o n scheme f o r task T4 F i g u r e 3.6: Tasks T3 and T7 59 3.6. However, t h i s approach does not a l l o w the modeling of the s p e c i a l i n t e r c o n n e c t i o n s between the p r o c e s s o r s , t h a t i s , the end computing elements, CE, and C E 3 , cannot be used t o form a 3 2 - b i t p r o c e s s o r . The u n c o l o u r e d tokens cannot model the p r i o r i t y g i v e n t o a s s i g n i n g a t a s k r e q u i r i n g a 1 6 - b i t p r o c e s s o r t o an end computing element, CE, or CE 3. The f i n a l s t e p i n the c o n s t r u c t i o n of the P e t r i net model i s the a s s e r t i o n t h a t a v a l i d P e t r i net has ben c o n s t r u c t e d . A v a l i d P e t r i net model i s a l i v e and bounded n e t , s i n c e the problem i s assumed t o be e x e c u t a b l e on f i n i t e r e s o u r c e s . The modeling of the s c h e d u l i n g s t r a t e g y depends on the s t a t e space of the n e t , the graph of i n s t a n t a n e o u s d e s c r i p t o r s , GRID. The GRID f o r a l i v e and bounded timed net i s f i n i t e . Theorem 4 a s s e r t s t h a t the P e t r i net model c o n s t r u c t e d by A l g o r i t h m 1 i s l i v e and bounded. Theorem 4 A l g o r i t h m 1 c o n s t r u c t s a l i v e and bounded P e t r i net from the a c y c l i c d i r e c t e d graph r e p r e n t a t i o n of the precedence c o n s t r a i n t s of a t a s k system. PROOF: F i r s t i t i s shown t h a t s t e p s 1-6 y i e l d s a l i v e and s a f e marked graph. Then i t i s t o be demonstrated t h a t the a d d i t i o n of the r e s o u r c e p l a c e s does not a f f e c t the s t r u c t u r a l l i v e n e s s p r o p e r t y and the net remains bounded. Steps 1-3 c o n v e r t s an a r b i t r a r y precedence r e l a t i o n i n t o a s i n g l e - e n t r y node, s i n g l e - e x i t node r e l a t i o n . I f one c o n s i d e r s the g r a p h i c a l r e p r e s e n t a t i o n of the precedence 60 r e l a t i o n , an a c y c l i c graph, t h e n , t h e r e e x i s t s a d i r e c t e d p a t h from the START node t o any node i n the graph. I f a node had no p r e d e c e s s o r s , t h e n , i t would be connected t o the START node by s t e p 2. I f a node had p r e d e c e s s o r s , t h e n , one c o u l d t r a c e back a l o n g a d i r e c t e d p a th t o a node w i t h no p r e d e c e s s o r s which would be co n n e c t e d t o the START node by s t e p 2. S i m i l a r i l y , each node i s on a d i r e c t e d p a t h t o the STOP node. T h e r e f o r e each node and each edge i s on a p a t h from the START node t o the STOP node. Step 4 adds an edge from the STOP node t o the START node. The d i r e c t e d p a t h s of the precedence graph become d i r e c t e d c i c u i t s i n which a l l the nodes and a l l of the edges l i e on a t l e a s t one such c i r c u i t . A l l of the d i r e c t e d c i r c u i t s c o n t a i n the STOP-START edge s i n c e the o r i g i n a l graph was assumed t o be a c y c l i c . Now c o n s i d e r the graph t o be a marked graph. When the STOP-START edge i s marked w i t h a READY t o k e n , every d i r e c t e d c i r c u i t has a token count of 1. Hence, the net i s l i v e and s a f e by Theorems 2 and 3. The remainder of the p r o o f i s based upon the s t r u c t u r a l l i v e n e s s of the n e t . C o n s i d e r the i n i t i a l s t a t e of the net w i t h the READY p l a c e marked w i t h s i n g l e t o k e n . The f i r i n g of the START node e n a b l e s the e x e c u t i o n of the t a s k s . By d e f i n i t i o n of the problem," a l l t a s k s execute once, hence, a l l t r a n s i t i o n s must f i r e once. F i r i n g the STOP node r e t u r n s the net t o the o r i g i n a l s t a t e . Hence, the net i s s t r o n g l y r e p e t i t i v e and r*g=0 has a p o s i t i v e i n t e g e r s o l u t i o n , where-r 61 i s the c h a r a c t e r i s t i c m a t r i x . S i n c e the net i s s a f e , f»r=0 has a p o s i t i v e i n t e g e r s o l u t i o n . Now c o n s i d e r the c h a r a c t e r i s t i c m a t r i c e s b e f o r e and a f t e r the a d d i t i o n of the r e s o u r c e p l a c e s , r and r * , r e s p e c t i v e l y . I f r i s an n x m m a t r i x , t h e n , the f i r s t n rows of r' a r e i d e n t i c a l t o the f i r s t n rows of r . The rows i n r ' f o r the r e s o u r c e p l a c e s a r e rows of z e r o e s . S i n c e t h e edges a r e drawn to and from each t a s k which r e q u i r e s the r e s o u r c e and the t a s k s do not consume the r e s o u r c e s , t h e n , a^j =b^^. a ^ i s the number of tokens from p l a c e i which i s r e q u i r e d f o r the f i r i n g of t r a n s i t i o n j . b^-j i s the number of tokens d e p o s i t e d i n p l a c e i by the f i r i n g of t r a n s i t i o n j . S i n c e the e n t r i e s r ^ j o n l y r e f l e c t the net r e s u l t on the token count of a p l a c e , t h e r e f o r e =0 f o r the e n t r i e s f o r the r e s o u r c e p l a c e s . C o n s i d e r the s o l u t i o n t o the e q u a t i o n r'»g'=0. S i n c e r»g=0 and o n l y rows were added t o r t o get r ' , then r'»g=0. T h e r e f o r e g i s a p o s i t i v e i n t e g e r s o l u t i o n t o r ' . C o n s i d e r the s o l u t i o n s t o the e q u a t i o n , f'»r'=0. S i n c e f»r=0 and o n l y z e r o rows are added t o r t o get r ' , then the f i r s t n elements of f a r e the same as f . The r e m a i n i n g elements of f 1 are a b i t r a r y p o s i t i v e i n t e g e r s f o r the s o l u t i o n t o be a p o s i t i v e i n t e g e r s o l u t i o n . f' = ( f - l , f 2 , • • • j f » w c 1 r ° 2 i • • • ' °s ^ where a-x a r e a r b i t r a r y p o s i t i v e i n t e g e r s and s i s the number of r e s o u r c e p l a c e s added. 62 S i n c e f • r ' = 0 and r ' « g'=0, t h e r e f o r e the net w i th the r e s o u r c e p l a c e s i s we l l -behaved and hence , s t r u c t u r a l l y l i v e . S i n c e the i n i t i a l s t a t e of the marked graph p o r t i o n of the net i s l i v e , on ly the r e s o u r c e p l a c e s must be marked in such a f a s h i o n that a l i v e s t a t e i s c r e a t e d . The r e s o u r c e p l a c e s are s e l f - l o o p s , hence , each resource p l a c e must be marked by at l e a s t the minimum set of e n a b l i n g tokens from the c o l o u r s e t . The minimum set of e n a b l i n g tokens i s the maximum for any s i n g l e t a s k . The presence of the minimum set of e n a b l i n g tokens ensures that each t r a n s i t i o n scheme may f i r e . S ince the net i s w e l l - b e h a v e d , and the i n i t i a l s t a t e i s l i v e t h e r e f o r e the net i s l i v e and bounded. Q . E . D . T h i s completes the c o n s t r u c t i o n of the P e t r i net model for the s c h e d u l i n g model . The P e t r i net i s l i v e and bounded for a l i v e i n i t i a l m a r k i n g . The i n i t i a l marking for the net r e p r e s e n t s the i n i t i a l r e s o u r c e c o n d i t i o n s for the e x e c u t i o n of the task system. A l i v e i n i t i a l marking i s a token in the READY p l a c e and at l e a s t one token in each of the r e s o u r c e p l a c e s . The e x e c u t i o n of the P e t r i net s i m u l a t e s the e x e c u t i o n of the task system. 63 3.2.2 M o d e l i n g the B e h a v i o r of a S c h e d u l i n g S t r a t e g y C o n s i d e r a s c h e d u l i n g problem, a t a s k system and the r e s o u r c e s f o r i t s e x e c u t i o n . The s t a t e space f o r the problem i s a l l of the c o m b i n a t i o n s of completed, p a r t i a l l y completed and unexecuted t a s k s . The t r a n s i t i o n s between the s t a t e s are the t a s k s which began e x e c u t i o n t o l e a d t o the next s t a t e . One may c o n s i d e r the s t a t e space t o be a d i r e c t e d graph where the nodes and edges are the s t a t e s and the s t a t e t r a n s i t i o n s , r e s p e c t i v e l y . The p a t h s between the i n i t i a l s t a t e i n which no t a s k s have been e x e c u t e d and a f i n a l s t a t e i n which a l l t a s k s have been executed r e p r e s e n t p o s s i b l e s c h e d u l e s f o r the t a s k system. S i n c e the s c h e d u l e s a r e p a t h s i n the s t a t e space, the o p t i m a l s c h e d u l e i s a p a t h w i t h the s h o r t e s t e x e c u t i o n time a l o n g i t s l e n g t h . To f i n d the o p t i m a l s c h e d u l e a l l of the p a t h s between the i n i t i a l s t a t e and a f i n a l s t a t e i n g e n e r a l must be s e a r c h e d . A s c h e d u l i n g h e u r i s t i c may be a p p l i e d t o the problem t o reduce the amount of the s e a r c h i n g of the s t a t e space t o a c h i e v e o p t i m a l or near o p t i m a l s c h e d u l e s . A s c h e d u l i n g h e u r i s t i c may be thought of as s e l e c t i n g a p a t h through the s t a t e space based on i n f o r m a t i o n from o n l y a p o r t i o n of the s t a t e space. I f the f o r m u l a t i o n of the s c h e d u l i n g model i s a timed P e t r i n e t , t h e n , the s t a t e space of the problem i s the s t a t e space of the P e t r i n e t . A v a l i d s c h e d u l e may be thought of as 64 a p a t h t h r o u g h the s t a t e space of the P e t r i n e t . The s t a t e space of a timed P e t r i net i s s e a r c h e d by the c o n s t r u c t i o n of the graph of i n s t a n t a n e o u s d e s c r i p t o r s , GRID. A v a l i d s c h e dule may be found by f i n d i n g a p a t h from the i n i t i a l d e s c r i p t o r , d 0 , t o a d e s c r i p t o r i n which a l l t r a n s i t i o n s have been f i r e d once. An a l g o r i t h m f o r the c o n s t r u c t i o n of a GRID of a l i v e and bounded t i m e d P e t r i net i s shown i n F i g u r e 3.7. The A l g o r i t h m c o n s t r u c t s the complete graph r e p r e s e n t i n g a l l of the s t a t e s r e a c h a b l e from the i n i t i a l d e s c r i p t o r . The complete graph i s n e c e s s a r y i n the o r i g i n a l a p p l i c a t i o n • o f the a n a l y s i s of timed n e t s [ 1 0 2 ] , where the timed n e t s were used f o r p r e l i m i n a r y performance e v a l u a t i o n . The c o n s t r u c t i o n of the complete graph i n the c o n t e x t of the s c h e d u l i n g model would y i e l d the o p t i m a l s c h e d u l e . However, s i n c e i t i s known t h a t both the a n a l y s i s of P e t r i n e t s and the g e n e r a l s c h e d u l i n g problem a r e NP-complete [16, 27, 5 5 ] , h e u r i s t i c methods are an approach t o r e d u c i n g -the amount of s e a r c h i n g and y e t a c h i e v e o p t i m a l or near o p t i m a l r e s u l t s . The a l g o r i t h m may be m o d i f i e d t o s e a r c h a r e s t r i c t e d amount of the s t a t e space of the n e t . The m o d i f i c a t i o n s t o the a l g o r i t h m are used t o model the b e h a v i o r of the h e u r i s t i c approach. The b e h a v i o r of the s c h e d u l i n g h e u r i s t i c i s modeled by Step 4 of the a l g o r i t h m . The problem of f i n d i n g which t r a n s i t i o n s t o f i r e on the c u r r e n t d e s c r i p t o r i s e x a c t l y the problem of f i n d i n g which t a s k s t o execute on the c u r r e n t 65 1. L a b e l the root node d 0=(m 0, r 0 ) , where m0 i s the i n i t i a l marking and r 0={} i s the i n i t i a l remaining time. 2. d i : = d 0 , where d^ i s the c u r r e n t node. 3. Repeat Steps 4-9 u n t i l t h e r e are no unmarked • leafs...-4. F i n d the s e l e c t o r s , {s-}, enabled on m^ of d^ 5. Repeat Steps 6 -8 f o r each S J . 6. Generate a new d e s c r i p t o r , d . 7. C r e a t e a new node and l a b e l i t d£ v) . J o i n the node with an edge and l a b e l i t s - j . 8. I f d^ +, i s an e x i s t i n g node, then mark i t wi t h a *. 9. Set the c u r r e n t node, to any unmarked l e a f . F i g u r e 3.7: An a l g o r i t h m f o r the g e n e r a t i o n of the GRID of a l i v e and bounded net 66 s t a t e . T h i s i s e a s i l y seen s i n c e the t a s k s a re modeled as t r a n s i t i o n s i n the P e t r i net f o r m u l a t i o n of the s c h e d u l i n g problem. The number of s e l e c t o r s which i s g e n e r a t e d by S t e p 4 c o n t r o l s the amount of the graph s e a r c h e d , and the p a r t i c u l a r s e l e c t o r s c o n t r o l the paths s e a r c h e d . The modeling of the b e h a v i o r of a s c h e d u l i n g h e u r i s t i c may be thought of i n terms of a s t a t i c or a dynamic s c h e d u l i n g h e u r i s t i c . C o n s i d e r the modeling of the b e h a v i o r of a s i m p l e s c h e d u l i n g h e u r i s t i c , l i s t s c h e d u l i n g . The l i s t s c h e d u l i n g h e u r i s t i c s c h e d u l e s the f i r s t unexecuted t a s k from a p r i o r i t z e d l i s t , L, as soon as a p r o c e s s o r becomes f r e e t o execute a new t a s k . The performance of the l i s t s c h e d u l i n g h e u r i s t i c i s dependent upon the g e n e r a t i o n of the l i s t , L. The Coffman and Graham A l g o r i t h m A f o r the g e n e r a t i o n of the l i s t , L, i s o p t i m a l i n the two i d e n t i c a l p r o c e s s o r case [16].' The b e h a v i o r of the l i s t s c h e d u l i n g i s modeled s i m p l y by implementing the s e a r c h f o r s e l e c t o r s as a scan of the l i s t , L. The l i s t s c h e d u l i n g h e u r i s t i c i n v o l v e s no s e a r c h i n g of the s t a t e space o t h e r than the s t a t e s a l o n g the p a t h s e l e c t e d . Another c l a s s of h e u r i s t i c s , lookahead h e u r i s t i c s , i n v o l v e s a l i m i t e d s e a r c h of the s t a t e space [ 4 ] . I f the paths r e p r e s e n t s c h e d u l e s , t h e n , paths not ending i n a f i n a l s t a t e are p a r t i a l s c h e d u l e s . S e v e r a l p a t h s may be s e a r c h e d u n t i l they a r e found t o be dominated by o t h e r p a r t i a l s c h e d u l e s . C o n s i d e r a subset of the t a s k s e t , . P o s s i b l e s c h e d u l e s a r e p e r m u t a t i o n s of 67 the subset of t a s k s . I f a p e r m u t a t i o n has a s m a l l e r c o m p l e t i o n t i m e , t h e n , i t dominates the o t h e r p e r m u t a t i o n s [4, 8 0 ] . The i d e a of sequence dominance may be used t o c o n t r o l the amount of the graph which i s c o n s t r u c t e d . 3.3 R e l a t e d Work The e x t e n s i o n of P e t r i n e t s t o i n c l u d e the n o t i o n of time i s d i r e c t l y founded on the d e s i r e f o r u s e f u l i n f o r m a t i o n from the P e t r i net model. The use of timed P e t r i n e t s f o r the performance e v a l u a t i o n of system i s w e l l documented [10, 21, 33, 70, 81, 82, 86, 102]. However much of the work i s l i m i t e d t o system which may be modeled by w e l l - b e h a v e d P e t r i n e t s . The use of timed P e t r i n e t s f o r the performance e v a l u a t i o n of g e n e r a l systems i s beyond the scope of the p r e s e n t work. W i t h i n the scope of the p r e s e n t work, timed P e t r i n e t s have a l s o been used i n the o p t i m i z a t i o n of sequencing d e c i s i o n s [84, 92, 9 3 ] , The n o t i o n of time c o n s t r a i n s the n e t , p r e c l u d i n g some of the sequences p o s s i b l e i n the untimed c a s e . An example of the use of P e t r i n e t s f o r the o p t i m i z a t i o n of sequencing d e c i s i o n i s p r e s e n t e d by S h a p i r o and S a i n t [ 8 4 ] . The problem a d d r e s s e d i s t h a t of g e n e r a t i n g e f f i c i e n t programs f o r machines w i t h p a r a l l e l o p e r a t i o n c a p a b i l i t i t e s . The a l g o r i t h m s a r e e x p r e s s e d i n a h i g h l e v e l a l g o r i t h m i c language. The example d e t a i l e d i n the paper i s . a FORTRAN DO-loop exe c u t e d on a CDC 6600. 6 8 The approach t o the sequencing problem b e g i n s w i t h the d e c o m p i l a t i o n of the a l g o r i t h m . The d e c o m p i l a t i o n i s the removal of the i n c i d e n t a l s e q u e n c i n g c o n s t r a i n t s i n t r o d u c e d by the h i g h l e v e l language. The decompiled v e r s i o n of the a l g o r i t h m i s modeled as a P e t r i n e t . Next the hardware c o n t r a i n t s a re added t o the P e t r i net model. The o p t i m i z a t i o n i s p erformed by a s i m u l a t i o n of the a l g o r i t h m , t h a t i s , e x e c u t i n g the n e t . The net i s e x e c u t e d f o r each s e t of i n i t i a l c o n d i t i o n s . The s i m u l a t i o n i s stopped when a l l s e t s of i n i t i a l c o n d i t i o n s have been t r i e d or when a s o l u t i o n near the t h e o r e t i c a l o p t i m a l i s a c h i e v e d . The scope of the problem which i s a d d r e s s e d by S h a p i r o and S a i n t i s more r e s t r i c t e d than the scope of the problem which i s a d d r e s s e d by the p r e s e n t work. The P e t r i net model of S h a p i r o and S a i n t models the FORTRAN DO-loop and the hardware at the l e v e l of machine o p e r a t i o n s and machine f u n c t i o n a l u n i t s . Thus, the S h a p i r o and S a i n t model i s a t a lower l e v e l than the P e t r i net f o r m u l a t i o n of S e c t i o n 3.2.1. The o b j e c t i v e of the work of S h a p i r o and S a i n t i s the o p t i m i z a t i o n of the machine code. In c o n t r a s t , p a r t of the o b j e c t i v e of the p r e s e n t work i s the modeling of s c h e d u l i n g s t r a t e g i e s , whether the s t r a t e g y i s a h e u r i s t i c s t r a t e g y or an o p t i m a l s t r a t e g y . The FORTRAN DO-loops imply r e p e t i t i o n of the machine o p e r a t i o n s . The t a s k s i n the g e n e r a l s c h e d u l i n g problem, which i s c o n s i d e r e d i n the p r e s e n t work a r e assumed t o be e x e c u t e d a s i n g l e t i m e . The problem a d d r e s s e d by S h a p i r o and S a i n t i s a 69 form of the g e n e r a l s c h e d u l i n g problem, and so, the p r e s e n t work i s a p p l i c a b l e . A more r e c e n t approach t o the problem of the o p t i m i z a t i o n of the sequencing of ev e n t s u s i n g a P e t r i net approach i s p r e s e n t e d by Tani e t . a l . [92, 9 3 ] . The b a s i s f o r the P e t r i net model used i n [92, 93] i s a t h e o r e t i c a l model of p a r a l l e l c o m p u t a t i o n , hence, the name c a p a c i t a t e d computation graph. The problems a d d r e s s e d f o r c a p a c i t a t e d c o m p u t a t i o n graphs are the e x i s t e n c e of a d m i s s a b l e s c h e d u l e s , a l g o r i t h m s f o r the e a r l i e s t and l a t e s t s c h e d u l e s , the t e r m i n a t i o n p r o p e r t y and the maximum computation r a t e f o r p e r i o d i c s c h e d u l e s . A computation graph, CG, i s a marked graph i n which s e l f -l o o p s a re a l l o w e d . A s e l f - l o o p i s an edge which i s i n p u t and output t o a s i n g l e node. A c a p a c i t a t e d c o m p u t a t i o n graph, CCG, i s a computation graph w i t h the edges l i m i t e d i n the t o t a l number of tokens which may be h e l d on an edge. The f i r i n g r u l e s must be a l t e r e d s i n c e a node cannot f i r e i f any of i t s output edges h o l d s the maximum number of t o k e n s . Each edge i n a CCG, i s a s s i g n e d a t i m e . The time r e p r e s e n t s the d e l a y i n p l a c i n g the token on the edge a f t e r the i n i t i a t i o n of the f i r i n g of a node. Each node i s f i r e d a maximum of X^ t i m e s , where X-£ i s a p o s i t i v e i n t e g e r . A c a p a c i t a t e d c o m p u t a t i o n graph i s shown i n F i g u r e 3.8. The l a b e l s on the edges, ( c e , d°, re ), i n d i c a t e the c a p c i t y of the edge, c e , . t h e i n i t a l marking of the.edge, d°, and the time 7 0 F i g u r e 3.8: A c a p a c i t a t e d computation graph k=l k=2 k = 3 k=4 k ~" 5 s,(k) 3 8 13 18 23 ...... s 2 ( k ) 0 5 10 15 20 ... s 3 ( k ) 0 2 5 10 15 ... Sfl(k) 2 7 12 17 22 Ta b l e 3.6: An admissable schedule f o r CCG of F i g u r e 3.8 71 d e l a y of the edge, r&. The s c h e d u l e f o r the CCG i s e x p r e s s e d i n terms of the s^(k) which i s the time of the k + U i n i t i a t i o n of the f i r i n g of node i . T a b l e 3.6 shows an a d m i s s a b l e e a r l i e s t s c h e d u l e f o r the CCG of F i g u r e 3.2. An a l g o r i t h m f o r the f i n d i n g of the s^(k) i s shown i n F i g u r e 3.9. The c a p a c i t a t e d c o mputation graph model does not have the a b i l i t y t o model r e s o u r c e c o n t e n t i o n between o p e r a t i o n s [ 9 3 ] . A system w i t h r e s o u r c e c o n t e n t i o n i s f i r s t modeled as a g e n e r a l i z e d P e t r i n e t . The c o n f l i c t i s r e s o l v e d a r b i t r a r i l y . Each p o s s i b l e r e s o l u t i o n of the c o n f l i c t i s modeled u s i n g a c o m b i n a t i o n of the d u p l i c a t i o n of p l a c e s and edges, the i n i t i a l m arking and the time d e l a y i n the p l a c e s . F i g u r e 3.10 i l l u s t r a t e s the r e s o l u t i o n of a c o n f l i c t by the d u p l i c a t i o n of the p l a c e s and two i n i t i a l m a r k i n g s . Each r e s o l u t i o n of the c o n f l i c t i s c o n v e r t e d to a CCG model f o r which a s c h e d u l e i s found. The b e s t s c h e d u l e , the schedule w i t h the s m a l l e s t c o m p l e t i o n t i m e , s p e c i f i e s the c o n f l i c t r e s o l u t i o n i n the s t r u c t u r e of the CCG. P a r t of the P e t r i net model which i s p r e s e n t e d i n S e c t i o n 3.2 i s a s p e c i a l case of the c a p a c i t a t e d c o m p u t a t i o n graph model. C o n s i d e r the marked graph r e p r e s e n t a t i o n c o n s t r u c t e d by S tep 1-6 of A l g o r i t h m 1. Each t a s k e x e c u t e s a s i n g l e time by d e f i n i t i o n of the problem, hence, X^=1, 1 ; SiOJ+r-ij f o r a l l input edges which are unmarked S i ( l ) - T j j f o r a l l output edges \ which are marked t o c a p a c i t y 4. Repeat Step 5 f o r 2 0 . The s e t of p r o c e s s o r s i s assumed t o be o r d e r e d , such t h a t , b,>b2>...^b*. A measure of a s e t of p r o c e s s o r s i s the p r o c e s s i n g power, B. The p r o c e s s i n g power of the i f a s t e s t p r o c e s s o r s , B'x, i s the sum of the speeds of the f i r s t i p r o c e s s o r s . The p r o c e s s i n g power of P i s B„. 78 The s e t of p r o c e s s o r s P, i s modeled by a c o l o u r s e t , C P=(X p,bj . Two t a s k s , T^ . and ^ , are ready t o e x e c u t e and a r e t o be a s s i g n e d t o t h e p r o c e s s o r s . The e x e c u t i o n t i m e s f o r the t a s k s a r e and T^, r e s p e c t i v e l y . To d e r i v e the f i r s t s o r t i n g c o n d i t i o n of t h e h e u r i s t i c , d e f i n e a q u a n t i t y , A. L e t the c h a i n l e n g t h of t h e t a s k s T^ and T^ be 1 y and l - j _ , r e s p e c t i v e l y . Suppose t a s k T^ i s a s s i g n e d t o execute on p r o c e s s o r i and t a s k i s a s s i g n e d t o e x e c u t e on p r o c e s s o r j . L e t 6 ^ be the l e n g t h of the c h a i n of t a s k when i t i s a s s i g n e d t o t h e p r o c e s s o r i . To c o n s i d e r o n l y the e f f e c t of the c u r r e n t a s s i g n m e n t , assume 88 the remainder of the c h a i n i s e x e c u t e d on the f a s t e s t p r o c e s s o r . S i m i l a r i l y f o r t a s k T^, C o n s i d e r the d i f f e r e n c e , A, between the c h a i n l e n g t h s . A " V - \ * T k / b i - { 1 r ; i + T i / b i ) ( , ) I f the a ssumption t h a t T i s a s s i g n e d t o p r o c e s s o r i i s v a l i d , t h e n , A>0. - ^ ( l | < - T K + T k / b i ) - ( l 1 - T 1 + T 1 / b ; j ) > 0 (2) ( l k - l 1 ) > r k - ^ / ^ - ( ^ - ^ / b ^ ) . (3) E q u a t i o n (3) s t a t e s t h a t t h e the d i f f e r e n c e i n t h e c h a i n l e n g t h s of the t a s k s must be g r e a t e r than the d i f f e r e n c e between the amount the e x e c u t i o n t i m e s a r e extended by the e x e c u t i o n on p r o c e s s o r i or j . S i n c e , the l i s t s h o u l d be o r d e r e d such t h a t t a s k i s h i g h e r p r i o r i t y , t h e r e f o r e , e q u a t i o n (3) may be i n t e r p r e t e d t o o r d e r t h e l i s t i n d e c r e a s i n g c h a i n l e n g t h s . The c h a i n l e n g t h s f o r Example 1 a r e shown i n F i g u r e 4.6. The second c r i t e r i a f o r s o r t i n g the l i s t of t a s k s r e s o l v e s the case of. e q u a l c h a i n l e n g t h . C o n s i d e r t h e s i t u a t i o n w i t h two p r o c e s s o r s r e a d y t o e x e c u t e two t a s k s , as d e s c r i b e d above. Assume t a s k i s a s s i g n e d t o p r o c e s s o r i and t a s k T^ i s a s s i g n e d t o p r o c e s s o r j . From e q u a t i o n ( 1 ) , A = T u ( 1 - l / b i ) - - r : i ( 1 - 1 / b ^ ) . I f t h e a s s u m p t i o n t h a t t a s k T^ i s a s s i g n e d t o p r o c e s s o r i i s v a l i d , then A>0. t a s k / c h a i n l e n g t h F i g u r e 4.6: Example 1 c h a i n l e n g t h 90 T h e r e f o r e , Hence, But, T k A l > ( 1 - 1 / b j ) / ( 1 - 1 / b - ) | 1 ~ 1 / b j | > i 1 - 1 /b ( i - i / b ^ / d - i / b ^ i and, The second c r i t e r i a i s to o r d e r the t a s k s i n or d e r of d e c r e a s i n g e x e c u t i o n time when the c h a i n l e n g t h s a r e e q u a l . Note e q u a t i o n (1) can a l s o be i n t e r p r e t e d t o o r d e r the l i s t L a c c o r d i n g t o d e c r e a s i n g subsequent c h a i n l e n g t h . S i m i l a r i l y , a second s o r t i n g c r i t e r i a i s the e x e c u t i o n time of the t a s k s . The maximum subsequent c h a i n l e n g t h maximum e x e c u t i o n t i m e , MSCMT, h e u r i s t i c and the maximum c h a i n l e n g t h maximum e x e c u t i o n t i m e , MCLMT, h e u r i s t i c a r e i d e n t i c a l , i n g e n e r a l , except i n c e r t a i n s i t u a t i o n s when e i t h e r h e u r i s t i c may y i e l d the wrong s c h e d u l e . C o n s i d e r two p r o c e s s o r s ready t o execute t a s k s and two t a s k s , T^ and T^, as above. Suppose the c h a i n l e n g t h of T^ i s g r e a t e r than the c h a i n l e n g t h of T^. F u r t h e r suppose the subsequent c h a i n l e n g t h of t a s k i s l e s s than the subsequent c h a i n l e n g t h of T,. U s i n g the MSCMT l i s t , T^ has a h i g h e r p r i o r i t y and i s a s s i g n e d t o a f a s t e r p r o c e s s o r . U s i n g the MCLMT l i s t , T^ has a h i g h e r p r i o r i t y and i s a s s i g n e d t o a f a s t e r p r o c e s s o r . E i t h e r l i s t may r e s u l t i n a worse sc h e d u l e than the r e v e r s e d s c h e d u l e V V V T i 91 depending on the d i f f e r e n c e s i n the l e n g t h s and the d i f f e r e n c e s i n the p r o c e s s o r speeds. T h i s i s a p o s s i b l e source of n o n - o p t i m a l i t y f o r e i t h e r h e u r i s t i c . The h e u r i s t i c reduces t o s i m p l e r forms i f r e s t r i c t e d problems are c o n s i d e r e d . I f the e x e c u t i o n times are r e s t r i c t e d t o be u n i t t i m e s , then the h e u r i s t i c reduces t o h i g h e s t l e v e l s f i r s t . Each t a s k can o n l y add a s i n g l e u n i t t o the l e n g t h , t h e r e f o r e , the l e n g t h i s i d e n t i c a l t o the l e v e l . I f the p a r t i a l o r d e r i s r e s t r i c t e d t o a n u l l p a r t i a l o r d e r , t h e n , the h e u r i s t i c reduces t o a l o n g e s t p r o c e s s i n g time h e u r i s t i c . A n u l l p a r t i a l o r d e r means the t a s k s a r e independent. In t h i s case the subequent c h a i n l e n g t h s of a l l t a s k s i s 0. The t a s k s a r e t h e n , o r d e r e d u s i n g the second c r i t e r i a i n t o a l i s t of d e c r e a s i n g e x e c u t i o n t i m e s . The l i s t s f o r Example 1 r e s u l t i n g from each of the t h r e e h e u r i s t i c s and a random l i s t a r e shown i n F i g u r e 4.7. The l i s t s a r e s o r t e d from the random l i s t shown. The Gantt c h a r t s of the s c h e d u l e s f o r the e x e c u t i o n of Example 1 on a s e t of p r o c e s s o r s P={P!,P 2,P 3,P„} a r e shown on F i g u r e s 4.8 and 4.9. The speeds of the p r o c e s s o r s a r e b, = 1 and b 2=b 3=b 4=2/3. (T1 T2 T3 T4 T5 T7 T10 T6 T9 T8 T14 T12 T13 T16 T15 T18 T19 T11 T21 T17 T20) (a) MCLMT ' (T1 T2 T3 T4 T5 T7 TG T9 T8 T10 T14 T12 T13 T16 T15 T18 T.19 T17 T11 T20 T21) (b) HLF (T2 T1 T3 T4 T5 T6 T7 T9 T10 T8 T13 T12 T14 T16 T15 T18 T19 T1.7. T20 T i l T21) (c) CG (T6 T13 T12 T18 T3 T5 T21 T2 T1 T16 T20 T14 T10 T11 T4 T17 T7 T8 T9 T19 T15) " (d) RANDOM Figure 4.7: Ordered l i s t s of tasks f o r Example 1 T10 T i l T21 T3 " T13 T19 T2 T6 T8 T12 T15 T1 T4 T5 T7 T9 T14 T16 K T18 T20 I 1 1 1 1 1 —I 1 1 ' i i » i i i i i 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 ( a ) HLF T10 T11 T20 T3 T12 T19 T2 T6 T8 T13 T15 T17 T1 T4 T5 T7 T9 T14 T16 T21 T18 I 1— 1 I . I ' i i i i I I i i i i i i 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 (b) MCLMT Figure 4.8: Schedules f o r Example 1 T10 T21 T3 T7 T12 T19 TI T1 1 T14 T15 T2 T4 T5 T8 T9 T13 T16 [ j r . , i i i T6 I I 1 1 1 Tie' • T20 1 1 1 0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80. 85 (a) Coffman-Graham T10 T20 T1 T12 T19 T3 T2 T4 T11 T5 T7 T8 T9 T14 T13 T15 T16 T17 I T2 1 T6 T18 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 (b) Random Figure 4.9: Schedules f o r Example 1 95 4.3 E x p e r i m e n t a l O u t l i n e The GRID a n a l y s i s a l g o r i t h m and the a d d i t i o n a l programs f o r the comparison of the h e u r i s t i c s are implemented i n LISP. The s y m b o l i c c o m p u t a t i o n a l c a p a b i l i t i e s of LISP a l l o w the r e t e n t i o n of the grammar-style d e f i n i t i o n of the t r a n s i t i o n s (see Appendix A and F i g u r e 2 . 1 ( b ) ) . The grammar-style d e f i n i t i o n s a l s o a l l o w the use of s e l f - l o o p s , an e s s e n t i a l p a r t of the P e t r i net f o r m a l i z a t i o n . T r a n s i t i o n s can a l s o be d e f i n e d as v e c t o r s of l e n g t h n, where n i s the number of p l a c e s . A v e c t o r i s d e f i n e d f o r the i n p u t p l a c e s and a l s o f o r the output p l a c e s . The non-zero elements of the v e c t o r i n d i c a t e which p l a c e s a r e connected t o the t r a n s i t i o n . S i n c e i n g e n e r a l , a t r a n s i t i o n i s connected t o a s m a l l number of p l a c e s , r e l a t i v e t o n, many of the elements of the v e c t o r are z e r o . The t h r e e h e u r i s t i c s d e s c r i b e d i n Chapter 4.2, and a randomly g e n e r a t e d l i s t , a r e compared f o r 15 p a r t i a l o r d e r s . The s o u r c e s of the p a r t i a l o r d e r s a r e as n o t e d i n T a b l e 4.3. Three s p e c i a l cases of the p a r t i a l o r d e r s are used i n the c o m p a r i s o n , a n u l l p a r t i a l o r d e r , a most c o n s t r a i n e d p a r t i a l o r d e r and a l e a s t c o n s t r a i n e d p a r t i a l o r d e r , the l a t t e r two p a r t i a l o r d e r s are shown i n F i g u r e s B.1 and B.2 of Appendix B. The s i z e of the t a s k s e t , %J , ranges i n s i z e from 10 t a s k s to 85 t a s k s . Four randomly g e n e r a t e d p a r t i a l o r d e r s of s i z e s , 40 t a s k s , 50 t a s k s , 65 t a s k s and. 75 t a s k s , a r e i n c l u d e d for. the 96 c o m p a r i s o n . Each t a s k i n the p a r t i a l o r d e r s i s a s s i g n e d an e x e c u t i o n time chosen from a u n i f o r m d i s t r i b u t i o n between a minimum e x e c u t i o n time and a maximum e x e c u t i o n t i m e . The e x e c u t i o n time i s assumed t o be a p o s i t i v e i n t e g e r . For the examples taken from o t h e r s o u r c e s , the comparisons a r e made f o r the d e f i n e d e x e c u t i o n t i m e s i n a d d i t i o n t o the random e x e c u t i o n t i m e s i f the e x e c u t i o n time a r e not d e f i n e d t o be u n i t e x e c u t i o n t i m e s . The c o l o u r s e t , X p, which i s used f o r the comparisons i s shown i n Table 4.2. The assumption t h a t the speeds a r e r a t i o n a l numbers and the e x e c u t i o n t i m e s are p o s i t i v e i n t e g e r s a v o i d s the problems a s s o c i a t e d w i t h f i n i t e machine a r i t h m a t i c f o r r e a l numbers. T h i s assmption i s made w i t h o u t l o s s of g e n e r a l i t y . A t a s k system i s d e f i n e d by a t a s k s e t , a p a r t i a l o r d e r , and the e x e c u t i o n t i m e s f o r the t a s k s . The t a s k s of the p a r t i a l o r d e r s a re a s s i g n e d d i f f e r e n t e x e c u t i o n t i m e s , thus c r e a t i n g s e v e r a l t a s k systems based on a s i n g l e p a r t i a l o r d e r . For each t a s k system, the sc h e d u l e i s found f o r i t s e x e c u t i o n on s e v e r a l d i f f e r e n t s e t s of p r o c e s s o r s . In terms, of the P e t r i net f o r m a l i z a t i o n , the P e t r i net i s exe c u t e d w i t h s e v e r a l i n i t i a l m a r k i n g s , mO, of the form, m0=(READY c , C £ ... c j ) . Each i n i t i a l marking i s a l i s t of tokens w i t h a s i n g l e READY C o l o u r ' P r o c e s s o r Speed c, 1 c 2 2/3 c 3 1/2 c. 1/3 c 5 1/5 c 6 1/6 T a b l e 4.2: C o l o u r s e t f o r e x p e r i m e n t s 98 token and two or more p r o c e s s o r t o k e n s . The READY token i s ne c e s s a r y f o r the p o r t i o n of the P e t r i net modeling the data dependencies (see Step 4 of A l g o r i t h m 1). c, and c^ are elements of the c o l o u r s e t , X p. At l e a s t one token i n the i n i t i a l marking i s the token c,, s i n c e i t i s assumed t h a t the f a s t e s t p r o c e s s o r has i t s speed n o r m a l i z e d t o 1. 4.4 R e s u l t s and D i s c u s s i o n A summary of the r e s u l t s i s shown i n Tab l e 4.3. n 0 i s the number of d i f f e r e n t s e t s of p r o c e s s o r s t e s t e d f o r the ta s k systems based on the p a r t i a l o r d e r , n, i s the number of times the l i s t from the h e u r i s t i c g e n e r a t e s the sc h e d u l e w i t h the s h o r t e s t e x e c u t i o n t i m e . n 2 i s the number of times the l i s t from the h e u r i s t i c g e n e r a t e s a sch e d u l e as good as a t l e a s t one o t h e r l i s t . The maximum c h a i n l e n g t h maximum t i m e , MCLMT, l i s t i s found t o generate a s c h e d u l e whose l e n g t h i s s h o r t e r than the l e n g t h of the s c h e d u l e s which a r e gen e r a t e d by the o t h e r h e u r i s t i c s i n 98 of 160 ca s e s f o r the f i f t e e n examples. The MCLMT l i s t i s a l s o found t o ge n e r a t e a sch e d u l e whose l e n g t h i s no l o n g e r than one or more of the h e u r i s t i c s compared i n 39 of 160 c a s e s t e s t e d . O v e r a l l , the MCLMT l i s t g e n e r a t e d the best s c h e d u l e of the f o u r l i s t s compared 86 per cen t of the cases t e s t e d . Note Example 1 ac c o u n t s f o r over 20 per cent of the cases Example r no MSCMT HLF CG RANDOM Notes ni ni ni ni n J ni t l ! 1 21 34 23 9 0 7 2 2 0 2 Example 2 l e s s 1 2 22 1 1 10 1 0 1 0 0 0 0 [14] p. 88 3 19 21 . 9 3 4 0 4 3 1 0 [24] 4 85 10 6 2 1 1 1 1 0 0 [57] 5 16 6 5 0 1 0 0 0 0 0 6 . 10 13 4 6 0 1 3 4 0 6 [15] p. 6 7 12 20 13 6 0 2 1 6 0 1 [1] 8 16 6 2 2 0 2 2 2 0 0 <:most constrained 9 15 6 5 1 0 1 0 1 0 1 <:least constrained 10 19 7 2 4 1 4 0 1 0 1 [14] p. 92 11 30 6 3 3 0 3 0 2 0 0 [59] 12 40 6 5 0 1 0 0 0 0 0 Randomly generated 13 50 5 5 0 0 0 0 0 0 o Randomly generated 14 65 6 6 0 0 0 0 0 0 0 Randomly generated 15 75 3 1 1 1 1 0 1 o o Randomly generated Total 160 98 39 9 23 14 23 1 11 Notes ":. 1. r Is the number of tasks. 2 . no Is the number of cases. 3 . n i 1s the number of best schedules. 4. ni Is the number of schedules at least as good as one other. Table 4 . 3 : Sumary of Results 100 t e s t e d . S i n c e , Example 1 i s Example 2 l e s s a s i n g l e independent t a s k , c o n s i d e r o n l y the r e s u l t s f o r examples 2 through 15. In t h i s c a s e , the MCLMT l i s t i s found t o generate the s h o r t e s t s c h e d u l e i n 75 of 127 ca s e s and t o generate a sc h e d u l e a t l e a s t as good as one o t h e r l i s t i n 30 of 127 c a s e s . The MCLMT i s found t o gen e r a t e the best s c h e d u l e i n 83 per cent of the ca s e s i f Example 1 i s ommitted. The r e s u l t s a r e h e a v i l y weighted by t a s k system w i t h fewer than 20 t a s k s . Examples 2, 4, and 11-15 are the examples i n which the number of t a s k s ranges from 20 t o 85, e x c l u d i n g Example 1. For thes e Examples, i t i s found t h a t the MCLMT l i s t g e n e r a t e d the s h o r t e s t s c h e d u l e i n 35 of 47 cases and a sch e d u l e a t l e a s t as good as one o t h e r l i s t i n another 8 of 47 c a s e s . For the l a r g e r t a s k systems, the MCLMT i s found t o gene r a t e the bes t s c h e d u l e i n 91 per cen t of the cases which were t e s t e d . The l e n g t h s of the s c h e d u l e s g e n e r a t e d by each of the h e u r i s t i c s i s compared t o J a f f e ' s lower bound on the l e n g t h of an o p t i m a l s c h e d u l e . The r a t i o i s an i n d i c a t i o n of the a b s o l u t e preformance of the h e u r i s t i c s . J a f f e ' s bound i s used s i n c e the bound i s e a s i l y c a l c u l a t e d . The r a t i o s w/w*' are shown i n Tab l e 4.4. The lower bound, w*', i s d e f i n e d by the f o l l o w i n g lemma. 101 Example r MCLMT HLF CG RANDOM 1 21 1.17 1 .35 1.35 1 .38 2 22 1.10 1.18 1 .27 1:38 3 19 1 .26 1 .50 1 .30 1 .42 4 85 1.14 1 .20 1.19 1 .37 5 16 1 .05 1.15 1 .25 1 .29 6 10 1.21 1 .45 1.29 1 .35 7 12 1.19 1.71 1 .26 2.00 8 .16 1.53 1 .53 1 .65 1 .76 9 15 1.13 1 .22 1 .20 1.19 10 19 1.11 1.1 1 1.28 1.41 1 1 30 1 .08 1.11 1.15 1 .21 12 40 1 .41 1 .57 1 .54 1.61 13 - 50 1.00 1 .04 1 .02 1.15 14 65 1 .04 1.13 1.14 1.15 15 75 1 .05 1.06 1 .08 1 .22 where w*' i s the lower bound on the length Of the optimal schedule Table 4.4: Average w/w*' 102 Lemma 1 [40] Let (%/,<, v) be a t a s k system t o be sc h e d u l e d on a set of p r o c e s s o r s of d i f f e r e n t speeds. L e t w* be the f i n i s h i n g time of an o p t i m a l s c h e d u l e . Then, w*>max(M/B a,h/bT). The r a t i o s g i v e n i n Ta b l e 4.4 a r e a s i m p l e mean of the cases t e s t e d f o r each example. The a c t u a l v a l u e of w/w*' ranges i n v a l u e from 1.00 t o 2.31. In g e n e r a l , the v a l u e s a re found t o be i n the range from 1.00 t o 1.50. The r a t i o w/w*' i s an i n d i c a t o r of performance f o r the l i s t o r d e r i n g h e u r i s t i c s compared. A l a r g e v a l u e of w/w*' may be caused by two re a s o n s . Under c e r t a i n c o n d i t i o n s , any l i s t used f o r l i s t s c h e d u l i n g r e s u l t s i n poor performance. T h i s case i s t o be d i s c u s s e d l a t e r i n the s p e c i f i c t e s t on Example 1. The second cause of a l a r g e v a l u e of w/w*' i s t h a t the lower bound may u n d e r e s t i m a t e the l e n g t h of an o p t i m a l s c h e d u l e . J a f f e ' s bound i s a v e r y l o o s e bound f o r c e r t a i n t y p e s of o p e r a t i o n a l precedence c o n s t r a i n t s . I f the p a r t i a l o r d e r i s ve r y h i g h l y c o n s t r a i n e d , such as Example 8, th e n , t h e r e a r e many c h a i n s which a re of a p p r o x i m a t e l y the same l e n g t h as the c h a i n d e f i n i n g the h e i g h t , h. C o n s i d e r the case where s e v e r a l such c h a i n s d i f f e r from the l o n g e s t c h a i n by o n l y a few t a s k s . Assume the s e t of p r o c e s s o r s i n c l u d e s o n l y a s i n g l e f a s t p r o c e s s o r and the bound f o r the o p t i m a l i s d e f i n e d by h/b^. I f the t a s k s on .the l o n g e s t c h a i n a r e exe c u t e d on the f a s t e s t 103 p r o c e s s o r s , then the r e m a i n i n g t a s k s on the c h a i n s which share t a s k s w i t h the l o n g e s t c h a i n must be ex e c u t e d on a slower p r o c e s s o r so d e l a y i n g the e x e c u t i o n of the s h a r e d p o r t i o n s of the l o n g e s t c h a i n . Thus, an o p t i m a l s c h e d u l e f o r the s e t of p r o c e s s o r s may be l o n g e r than the l e n g t h of the l o n g e s t c h a i n i n t h i s c a s e . An example of t h i s s i t u a t i o n i s d i s c u s s e d l a t e r . T a ble 4.5 i s an example of a t e s t run f o r a . p a r t i c u l a r assignment of e x e c u t i o n t i m e s f o r Example 1. The l e n g t h s of the s c h e d u l e s a r e compared t o J a f f e ' s lower bound f o r the l e n g t h of the o p t i m a l , w*', and the l e n g t h of an o p t i m a l s c h e d u l e , w*. The l e n g t h of an o p t i m a l s c h e d u l e i s i n c l u d e d as a comparison f o r J a f f e ' s lower bound. In g e n e r a l , the problem of f i n d i n g an o p t i m a l schedule i s i n t r a c t a b l e . The s t r u c t u r e of the precedence c o n s t r a i n t s of Example 1 and the s m a l l s i z e of the set of t a s k s e n a b l e s the c o n s t r u c t i o n of an o p t i m a l s c h e d u l e . The method of c o n s t r u c t i o n of an o p t i m a l s c h e d u l e i s s i m i l a r t o the method of Fernandez and B u s s e l l [25] f o r f i n d i n g the lower bound i n the case of i d e n t i c a l p r o c e s s o r s . In g e n e r a l , the f o l l o w i n g p r o c e d u r e amounts t o an e x h a u s t i v e s e a r c h . The c o n s t r u c t i o n of an o p t i m a l b e g i n s w i t h the i n s p e c t i o n of the Gantt c h a r t of the be s t s c h e d u l e r e s u l t i n g from the f o u r l i s t s . The t a s k assignments a r e swapped i f the swapping s h o r t e n s the l e n g t h of the s c h e d u l e . The swapping c o n t i n u e s u n t i l no f u r t h e r improvemant can be made. Processors Execution Time w MCLMT HLF CG RANDOM w* ' w* C l C l 70 72 72 72 66 68 C i C l C i 62 64 64 62 62 62 C l C l 88 88 95 93 80 82 C i C I C 2 67 67 82 82 62 67 C l C z C l C z 67 69 77 82 . 62 67 C l C l 90 92 92 92 88 90 C l C a C1 78 94 78 94 66 78 C i C i C i C ] 78 80 92 104 62 78 Table 4 . 5 : Results f o r Example 1 105 As an example, i t i s shown t h a t the l e n g t h of an o p t i m a l s c h e d u l e f o r the s e t of p r o c e s s o r s d e f i n e d by ( c , , c 2 , c 2 , c 2 ) i s 68. From the Gantt c h a r t shown i n F i g u r e 4.7(b), the t a s k system can be p a r t i t i o n e d i n t o t h r e e p a r t i t i o n s . T1 t o T1 1, T12 t o T14 and T15 t o T21. There i s no o v e r l a p between the e x e c u t i o n of the t a s k s i n each of the p a r t i t i o n s except f o r t a s k s T10 and T11 due t o the precedence c o n s t r a i n t s . T10 and T11 may o v e r l a p the second and t h i r d p a r t i t i o n s but i f they are e x e c u t e d as e a r l y as p o s s i b l e , t h e n , t h e r e i s no o v e r l a p . The l e n g t h of the o p t i m a l s c h e d u l e i s the sum of the l e n g t h s the o p t i m a l s c h e d u l e f o r each p a r t i t i o n . In the f i r s t p a r t i t i o n , the l o n g e s t c h a i n i s (T1, T4, T5, T7, T 9 ) . The l o n g e s t c h a i n i s of l e n g t h 38 u n i t s . Each t a s k i n the c h a i n i s e x e c t u t e d on the f a s t e s t p r o c e s s o r . A l l o t h e r t a s k s , i n the p a r t i t i o n i s e x e c u t e d on the slower p r o c e s s o r s and they complete e x e c u t i o n b e f o r e the t a s k s on the l o n g e s t c h a i n complete e x e c u t i o n . T h e r e f o r e the t a s k s not on the l o n g e s t c h a i n do not d e l a y the the t a s k s on the l o n g e s t c h a i n . S i n c e the p a r t i t i o n cannot be executed i n l e s s t i m e , the s c h e d u l e of l e n g t h 38 u n i t s i s o p t i m a l . In the second p a r t i t i o n t h e r e are s u f f i c i e n t p r o c e s s o r s f o r each t a s k t o be executed c o n c u r r e n t l y . The t a s k s a r e of e q u a l e x e c u t i o n t i m e s and two of the t a s k s a r e a s s i g n e d t o the slow p r o c e s s o r s . Note t h a t no b e n e f i t can r e s u l t from d e l a y i n g the e x e c u t i o n of any of the t h r e e t a s k s s i n c e the the e x e c u t i o n of two of the t a s k s on the f a s t p r o c e s s o r would 1 06 r e s u l t i n an e x e c u t i o n time of 8 u n i t s . Hence, the o p t i m a l i s 6 u n i t s . In the t h i r d p a r t i t i o n , c o n s i d e r the c h a i n s C1=(T16,T18,T21) and C2=(T16,T19). Chain C1 i s of l e n g t h 20 u n i t s and c h a i n C2 i s of l e n g t h 18. S i n c e o n l y one of the c h a i n s may be ex e c u t e d f u l l y on the f a s t p r o c e s s o r , e i t h e r T19 or T18 and T21 must be ex e c u t e d on a slower p r o c e s s o r . Assume T16 i s executed on the f a s t p r c e s s o r s i n c e i t i s common t o both c h a i n s . I f T19 i s exe c u t e d on a slower p r o c e s s o r , t h e n , the a c t u a l e x e c u t i o n time f o r c h a i n C2 i s 23 u n i t s and f o r c h a i n C1 i s 22 u n i t s . I f t a s k s T18 and T21 a r e executed on the sl o w e r p r o c e s s o r , t h e n , the a c t u a l e x e c u t i o n time f o r c h a i n C1 i s 28 and f o r c h a i n C2 i s 20. Hence, the e x e c u t i o n time i s m i n i m i z e d i f T19 i s exe c u t e d on a slower p r o c e s s o r . Note the e x e c u t i o n of t a s k s T15, T17 and T20 does not a f f e c t the e x e c u t i o n time of the p a r t i t i o n s i n c e the t a s k s may be ex e c u t e d s e r i a l l y on a slow p r o c e s s o r i n 21 u n i t s of t i m e . The l e n g t h of the o p t i m a l s c h e d u l e f o r the t h i r d p a r t i t i o n i s 22 un i t s . The l e n g t h of the o p t i m a l s c h e d u l e i s the sum of the l e n g t h s of the o p t i m a l s c h e d u l e s f o r each p a r t i t i o n . w*=38+6+22=67 The l e n g t h of an o p t i m a l s c h e d u l e f o r the e x e c u t i o n of Example 1 on the s e t of p r o c e s s o r s d e f i n e d by ( c 1 f c 2 , c2, c 2 ) i s 68 u n i t s . 107 A comparison between J a f f e ' s lower bound and the l e n g t h of an o p t i m a l schedule i n d i c a t e s t h a t , i n g e n e r a l , the bound i s r e l a t i v e l y c l o s e t o the l e n g t h of an o p t i m a l s c h e d u l e . However, note t h a t f o r the l a s t two s e t s of p r o c e s s o r s t e s t e d . The l e n g t h of an o p t i m a l s c h e d u l e exceeds the bound by a s i g n i f i c a n t amount, w*'/w*=1.26. In t h i s c a s e , the bound y i e l d s a poor e s t i m a t e of the l e n g t h of an o p t i m a l , as d e s c r i b e d above. The t a s k s of Example 1 are h i g h l y c o n s t r a i n e d as i l l u s t r a t e d i n F i g u r e 4.2. The second c o n d i t i o n , t h a t a s i n g l e f a s t p r o c e s s o r i s i n c l u d e d i n the s e t of p r o c e s s o r s , i s a l s o met i n the l a s t two c a s e s . T h i s b e h a v i o r i s v e r i f i e d u s i n g the o t h e r precedence r e l a t i o n s . The p r o c e s s o r speeds and the maximum e x e c u t i o n t i m e s a re a r b i t r a r y parameters i n the e x p e r i m e n t a l procedure o u t l i n e d i n Chapter 4.3. Sample r e s u l t s f o r t e s t runs t o examine the e f f e c t of a l t e r i n g t h e s e parameters a r e shown i n Appendix B. The parameters a r e changed t o a l t e r the r a t i o s , T W / T W I H and bi/b^. In the f i r s t t e s t , /r^,n=b, /bn and l o n g e r e x e c u t i o n times and slower speeds a r e used. In the second t e s t , /T„;„ b,/b „ i s a c h i e v e d by the use of a l a r g e v a l u e f o r . In each t e s t , the parameters d i d not s i g n i f i c a n t l y a f f e c t the dominance of the proposed h e u r i s t i c , MCLMT. The f i n a l t e s t on Example 1 i l l u s t r a t e s the r e s t r i c t i o n t o u n i t e x e c u t i o n t i m e s . Note t h a t the HLF and the MCLMT l i s t s 108 g e n e r a t e the same s c h e d u l e . T h i s b e h a v i o r i s v e r i f i e d w i t h the o t h e r precedence r e l a t i o n s . The s c h e d u l e s f o r the s e t s of p r o c e s s o r s i n c l u d i n g c, are f u r t h e r examples of s i t u a t i o n s i n which the l i s t s c h e d u l i n g s t r a t e g y y i e l d s poor performance. The Coffman and Graham A l g o r i t h m A l i s t g e n e r a t e s a schedule of the same l e n g t h as the HLF l i s t and the MCLMT l i s t . T h i s b e h a v i o r i s due to~ the u n i t e x e c u t i o n times and the r e l a t i v e l y s i m p l e s t r u c t u r e of the p a r t i a l o r d e r . A f i n a l o b s e r v a t i o n i n the r e s u l t s i s a comparison between the s c h e d u l e s g e n e r a t e d by the MCLMT l i s t and the MSCMT l i s t , d e s c r i b e d i n Chapter 4.2. Over the 160 cases t e s t e d , the MSCMT l i s t and the MCLMT l i s t g e n e r a t e d s c h e d u l e s of the same l e n g t h i n 121 of the c a s e s . In 20 of the cases the MCLMT l i s t g e n e r a t e d a b e t t e r s c h e d u l e and i n 19 of the ca s e s the MSCMT l i s t g e n e r a t e d a b e t t e r s c h e d u l e . T h i s agrees w i t h the n o t i o n t h a t the two h e u r i s t i c s a r e almost i d e n t i c a l . 109 CHAPTER 5 CONCLUSIONS AND SUGGESTIONS FOR FURTHER RESEARCH 5.1 Summary and C o n c l u s i o n s A P e t r i net f o r m u l a t i o n f o r the g e n e r a l s c h e d u l i n g problem i s de v e l o p e d i n t h i s t h e s i s . The P e t r i net f o r m u l a t i o n i s based upon t h r e e c l a s s e s of P e t r i n e t s , marked graphs, t i m e d P e t r i n e t s and c o l o u r e d P e t r i n e t s . The g e n e r a l approach t o the f o r m u l a t i o n b e g i n s by e x p r e s s i n g the s t r u c t u r e of the g e n e r a l s c h e d u l i n g problem i n terms of a P e t r i net model. The s c h e d u l i n g s t r a t e g y i s modeled by m o d i f y i n g the a l g o r i t h m f o r the a n a l y s i s of the P e t r i n e t . A schedule i s g e n e r a t e d by the e x e c u t i o n of the P e t r i n e t . The P e t r i net f o r m u l a t i o n may be thought of as the r e s u l t of a t r a n s f o r m a t i o n on the f o r m a l d e f i n i t i o n of the g e n e r a l s c h e d u l i n g problem. The main advantages of the P e t r i net f o r m u l a t i o n are th e s e of P e t r i n e t s i n g e n e r a l . As p r e s e n t e d i n t h i s t h e s i s , the P e t r i net f o r m u l a t i o n has the a b i l i t y t o model a wide v a r i e t y of r e s o u r c e and p r o c e s s o r c o n f i g u r a t i o n s . I f a c o n f i g u r a t i o n a r i s e s which cannot be modeled under the f o r m u l a t i o n p r e s e n t e d h e r e , then the P e t r i n e t s a r e e a s i l y e xtended t o improve t h e i r a b i l i t y t o model a p a r t i c u l a r s i t u a t i o n . S chedules a r e e a s i l y g e n e r a t e d f o r the e x e c u t i o n of a t a s k system on d i f f e r e n t s e t s of i n i t i a l r e s o u r c e s by s i m p l y e x e c u t i n g the P e t r i net model w i t h d i f f e r e n t i n i t i a l m a r k i n g s . The P e t r i net f o r m u l a t i o n i s a compact and n a t u r a l d e s c r i p t i o n 1 10 of the g e n e r a l s c h e d u l i n g problem. The l o g i c a l s e p a r a t i o n of the modeling of the s t r u c t u r e and the m o d e l i n g of the b e h a v i o r i n the s c h e d u l i n g problem a l l o w s changes t o made i n e i t h e r the s t r u c t u r e or the b e h a v i o r of the problem w i t h o u t i n d e p e n d e n t l y . C o n s i d e r the problem a n a l y s e d i n Chapter 4, namely, l i s t s c h e d u l i n g f o r a s e t of p r o c e s s o r s of d i f f e r e n t speeds. Suppose the p r o c e s s o r s a re now to be f u n c t i o n a l l y d e d i c a t e d and t o be of d i f f e r e n t speeds w i t h i n a f u n c t i o n a l group. The s e t of p r o c e s s o r s i s modeled by a set of c o l o u r e d tokens but the a n a l y s i s modeling the l i s t s c h e d u l i n g remains unchanged. Suppose i n s t e a d , a d i f f e r e n t s c h e d u l i n g s t r a t e g y i s d e s i r e d t o be modeled f o r the s e t of p r o c e s s o r s of d i f f e r e n t speeds. The GRID a n a l y s i s i s m o d i f i e d to model the s c h e d u l i n g s t r a t e g y and the P e t r i net remains the same. The l o g i c a l s e p a r a t i o n of the modeling of the b e h a v i o r and of the s t r u c t u r e of systems p r o v i d e s f l e x i b i l i t y i n the use of the f o r m u l a t i o n . There a r e two d i s a d v a n t a g e s t o t h e i r f o r m u l a t i o n . The P e t r i net f o r m u l a t i o n t a k e s advantage of the assumption t h a t a t r a n s i t i o n i s d e f i n e d t o f i r e as soon as i t i s e n a b l e d , s u b j e c t t o c o n f l i c t r e s o l u t i o n . S i n c e the t a s k s a r e modeled as t r a n s i t i o n s , the e a r l i e s t s c h e d u l e s a r e g e n e r a t e d under the P e t r i net f o r m u l a t i o n . The f o r m u l a t i o n does not i n c l u d e a n a t u r a l r e p r e s e n t a t i o n f o r the modeling of a r b i t r a r y d e l a y s . A t r a n s i t i o n i s a l s o assumed t o f i r e c o m p l e t e l y and t o be u n i n t e r r u p t e d once i t b e g i n s f i r i n g . T h i s n o t i o n p r e v e n t s 111 c o n s i d e r a t i o n of preemptive s t r a t e g i e s . Note t h a t b oth of t h e s e d i s a d v a n t a g e s may be overcome by m o d i f i c a t i o n s t o the i m p l e m e n t a t i o n of the b e h a v i o r a l a n a l y s i s which i s used f o r the study of the problem i n Chapter 4. The use of the P e t r i net f o r m u l a t i o n of the g e n e r a l s c h e d u l i n g problem i s demonstrated i n l i s t s c h e d u l i n g f o r the e x e c u t i o n of a t a s k system on a s e t of p r o c e s s o r s of d i f f e r e n t speeds. A new h e u r i s t i c i s proposed f o r o r d e r i n g the l i s t of the t a s k s . The proposed h e u r i s t i c , MCLMT, o r d e r s the l i s t i n o r d e r of d e c r e a s i n g c h a i n l e n g t h , and d e c r e a s i n g e x e c u t i o n time i n the case of e q u a l c h a i n l e n g t h s . The s c h e d u l e s which are g e n e r a t e d by the proposed h e u r i s t i c a re compared t o the s c h e d u l e s which are g e n e r a t e d by the h i g h e s t l e v e l s f i r s t h e u r i s t i c , A l g o r i t h m A of Coffman and Graham, and a randomly g e n e r a t e d l i s t . In the c o m p a r i s o n s , the proposed h e u r i s t i c g e n e r a t e d a b e t t e r s c h e d u l e i n 98 of 160 c a s e s t e s t e d and a s c h e d u l e as good as a t l e a s t one o t h e r s c h e d u l e i n an a d d i t i o n a l 39 of 160 c a s e s . 5.2 S u g g e s t i o n s f o r F u r t h e r R e s e a r c h The major s u g g e s t i o n f o r f u r t h e r r e s e a r c h i s the f u r t h e r use of the P e t r i net f o r m u l a t i o n . The use of the f o r m u l a t i o n p r e s e n t e d i n t h i s t h e s i s i s a r e l a t i v e l y s i m p l e s c h e d u l i n g problem. The s c h e d u l i n g problem d i s c u s s e d l i s t s c h e d u l i n g f o r a s i m p l e r e s o u r c e s t r u c t u r e c o n s i s t i n g of a s i n g l e s e t of p r o c e s s o r s of d i f f e r e n t speeds. 1 1 2 The f o r m u l a t i o n may be used t o e v a l u a t e s c h e d u l i n g s t r a t e g i e s o t h e r than l i s t s c h e d u l i n g . L i s t s c h e d u l i n g , as noted i n the comparison of the h e u r i s t i c s , i s known t o y i e l d poor performance i n the case where t h e r e e x i s t s a l a r g e d i f f e r e n c e the the speed of the f a s t e s t and s l o w e s t p r o c e s s o r . The problem w i t h l i s t s c h e d u l i n g i s t h a t a t a s k may be a s s i g n e d t o a slow p r o c e s s o r when a b e t t e r s c h e d u l e would r e s u l t i f the e x e c u t i o n of the t a s k i s d e l a y e d u n t i l a f a s t e r p r o c e s s o r i s a v a i l a b l e . T h i s s i t u a t i o n s u g gests a look-ahead s t r a t e g y may p e r f o r m b e t t e r i n t h i s s i t u a t i o n . A look-ahead s t r a t e g y i s w i t h i n the modeling c a p a b i l i t i e s of the P e t r i net f o r m u l a t i o n as p r e s e n t e d i n Chapter 3. The f o r m u l a t i o n may be used f o r the e x a m i n a t i o n of the e f f e c t s of more s t r u c t u r e d s e t s of r e s o u r c e s . The s e t of p r o c e s s o r s which was used f o r the comparisons i n Chapter 4 s p e c i f i e d no i n t e r c o n n e c t i o n s between the p r o c e s s o r s . I t i s shown th r o u g h the example of the d y n a m i c a l l y r e c o n f i g u r a b l e a r c h i t e c t u r e t h a t the f o r m u l a t i o n i s c a p a b l e of modeling an a r b i t r a r y s t r u c t u r e i n the r e s o u r c e s . The s p e c i a l r e l a t i o n s h i p between the computing elements of the r e c o n f i g u r a b l e a r c h i t e c t u r e i s modeled n a t u r a l l y t h rough the use of a s e t of c o l o u r e d tokens and the t r a n s i t i o n schemes. Other r e l a t i o n s i n the r e s o u r c e s , such as those imposed by a network a r c h i t e c t u r e , may be modeled u s i n g a c o m b i n a t i o n of c o l o u r s e t s f o r the r e s o u r c e s , the t r a n s i t i o n schemes and the s e t of c o l o u r e d d a t a t o k e n s . 1 1 3 The f i n a l s u g g e s t i o n f o r f u r t h e r r e s e a r c h t a k e s i d e a s from the s c h e d u l i n g problem t o suggest changes i n P e t r i net t h e o r y . The P e t r i net f o r m u l a t i o n i s unable t o model e i t h e r a r b i t r a r y d e l a y s , or the p a r t i a l f i r i n g of a t r a n s i t i o n which has a time d u r a t i o n a s s o c i a t e d w i t h i t . E x t e n s i o n of the P e t r i net t h e o r y t o a l l o w c o n s i d e r a t i o n of P e t r i n e t s which pos s e s s the s e modeling c h a r a c t e r i s t i c s i s d e s i r a b l e . 1 1 4 B i b l i o g r a p h y 1. Adam, T.L., Chandy, K.M., D i c k s o n , J.R., "A Comparision of L i s t S chedules f o r P a r a l l e l P r o c e s s i n g Systems," Comm. ACM, V o l . 17(12), Dec. 1974, p. 685-590. 2. Agerwala, T., "Some A p p l i c a t i o n s of P e t r i N e t s , " P r o c . N a t i o n a l E l e c t r o n i c s Conf., V o l . 32, 1978, p. 149-157. 3. A g e r w a l a , T., Chued—Amphai, Y—C., " S y n t h e s i s Rule f o r C o n c u r r e n t Systems," P r o c . 15th Design Automation Conf., June 1978, p. 305-311. 4. Appelbe, W.F., I t o , M.R., " S c h e d u l i n g H e u r i s t i c s i n a M u l t i p r o g r a m m i n g Environment," IEEE T r a n s . Computers, V o l . C -27(7), J u l y 1978, p. 628-637. 5. A r a k i , T., Kasami, T., "Some D e c i s i o n Problems R e l a t e d t o the R e a c h a b i l i t y Problem f o r P e t r i N e t s , " Theor. Comput. S c i . , V o l . 3, 1977, p. 85-104. 6. A r a k i , T., Kasami, T., " D e c i d a b l e Problems on the S t r o n g C o n n e c t i v i t y of P e t r i Net R e a c h a b i l i t y S e t s , " Theor. Comput. S c i . , V o l . 4, 1977, p. 99-119. 7. Ayache, J.M., Azema, P., D i a z , M., "Observer: A concept f o r O n — l i n e D e t e c t i o n of C o n t r o l E r r o r s i n C o n c u r r e n t Systems," P r o c . 9th I n t ' l . Symp. F a u l t - T o l e r a n t Computing, 1979, p. 79-86. 8. Azema, P., V a l e t t e , R., D i a z , M., " P e t r i Nets as a Common T o o l f o r Design V e r i f i c a t i o n and Hardware S i m u l a t i o n , " P r o c . 13th Design Automation Conf., 1976,. p. 109—116. 9. Baer, J — L . , E l l i s , C.S., "Model, D e s i g n , and E v a l u a t i o n of a C o m p i l e r f o r a P a r a l l e l P r o c e s s i n g Environment," IEEE Trans. S o f t w a r e E n g i n e e r i n g , V o l . S E - 3 ( 6 ) , Nov. 1977, p. 394-405. 10. B e r l i n , F.B., "Time-extended P e t r i N e t s , " M.A. T h e s i s , U n i v e r s i t y of Texas a t A u s t i n , 1979. 11. B e r t h e l o t , G., R o u c a i r o l , G., " R e d u c t i o n of P e t r i N e t s , " M a t h e m a t i c a l F o u n d a t i o n s of Computer S c i e n c e , 1976, p. 202-209. 12. B e s t , E., Schmid, H.A., "Systems of Open Pathes i n P e t r i N e t s , " M a t h e m a t i c a l F o u n d a t i o n s of Computer S c i e n c e , 1975, p. 186-193. 1 1 5 13. B r a u e r , W., ed., Net Theory and A p p l i c a t i o n s , S p r i n g e r - V e r l a g , (New Y o r k , 1980). 14. Coffman, E.G., J r . , Graham, R.L., "Optimal S c h e d u l i n g f o r Two—Processor Systems," A c t a I n f o r m a t i c a , V o l . 1 ( 1 ) , 1972, p. 203-213. 15. Coffman, E.G., J r . , Denning, P . J . , O p e r a t i n g Systems Theory, P r e n t i s s - H a l l , ( T o r o n t o , 1973). 16. Coffman, E.G., J r . , ed., Computer and Job Shop S c h e d u l i n g Theory, John W i l e y ( T o r o n t o , 1976). 17. Commoner, F., H o l t , A.W., Even, S., P n u e l i , A., "Marked D i r e c t e d Graphs," J . Comput. S y s t . S c i . , V o l . 5 ( 5 ) , 1971, p. 511-523. 1 8 . C o n t r o n i s , J.Y., L a u e r , P.E., " V e r i f i c a t i o n of C o n c u r r e n t Systems of P r o c e s s e s , " P r o c . I n t ' l . Computing Symp., 1977, p. 197-207. 1 9 . C o u r v o i s i e r , M., V a l e t t e , R., " D e s c r i p t i o n and R e a l i z a t i o n of P a r a l l e l C o n t r o l Systems," P r o c . 15th IEEE F a l l COMPCON, 1977, p. 167-172. 20. C o u r v o i s i e r , M., Seek, J.P., "Hardware Implementation of G e n e r a l i z e d P e t r i N e t s , " E l e c t r o n i c L e t t e r s , V o l . 15(24), 22 Nov. 1 9 7 9 , p.770-772. 21. Cox, L.A., J r . , " P r e d i c t i n g C o n current Computer System Performance U s i n g P e t r i Net Models," P r o c . 1978 ACM Annual Conf., 1978, p. 901-913. 22. C r e s p i - R e g h i z z i , S., M a n d r o i l i , D., "Some A l g e b r e i c P r o p e r t i e s of P e t r i N e t s , " A l t a F requenza, V o l . 4 5 ( 2 ) , Feb. 1976, p. 130-137. 23. Devy, M., D i a z , M., " M u l t i l e v e l S p e c i f i c a t i o n and V a l i d a t i o n of the C o n t r o l i n Communication Systems," P r o c . I n t ' l . Conf. D i s t r i b u t e d Computer Systems, 1979, p. 43-50. 24. E c k e r , K., " A n a l y s i s of a Simple S t r a t e g y f o r Resource C o n s t r a i n e d Task S c h e d u l i n g , " P r o c . I n t ' l . Conf. P a r a l l l e l P r o c e s s i n g , 1978, p. 181-183. 25. Fernandez, E.B., B u s s e l l , B., "Bounds on the Number of P r o c e s s o r s and Time f o r M u l t i p r o c e s s o r O p t i m a l S c h e d u l e s , " IEEE T r a n s . Computers, V o l . C-22(8), Aug. 1973, p. 745-751. 1 16 26. Garey, M.R., Graham, R.L., "Bounds f o r M u l t i p r o c e s s o r S c h e d u l i n g w i t h Resource C o n s t r a i n t s , " SIAM J . Computing, V o l . 4 ( 4 ) , 1975, p. 187-200. 27. Garey, M.R., Johnson, D.S., " C o m p l e x i t y R e s u l t s f o r M u l t i p r o c e s s o r S c h e d u l i n g Under Resource C o n s t r a i n t s . " SIAM J . Computing, V o l . 4 ( 2 ) , 1975, p. 397-411. 28. G o n z a l e s , M.J., J r . , " D e t e r m i n i s t i c P r o c e s s o r S c h e d u l i n g , " ACM Computing S u r v e y s , V o l . 9 ( 3 ) , 1977, p. 173-204. 29. G o n z a l e s , T., I b e r r a , O.H., S a h n i , S., "Bounds f o r LPT Schedules on U n i f o r m P r o c e s s o r s , " SIAM J . Comput., V o l . 6 ( 1 ) , 1977, p. 155-166. 30. G o y a l , D.K., " S c h e d u l i n g E q u a l E x e c u t i o n Time Tasks Under U n i t Resource R e s t r i c t i o n , " P r o c . I n t ' l . Conf. P a r a l l e l P r o c e s s i n g , 1 9 7 8 , p. 188-192. 31. G r a b o w s k i , J . , "The U n s o l v a b i 1 i t y of Some P e t r i Net Language Problems," I n f . P r o c e s s i n g L e t t . V o l . 9 ( 2 ) , 17 Aug. 1979, p. 60-63. 32. G r e n r i c h , H.J., Lautenbach, K., "The A n a l y s i s of D i s t r i b u t e d Systems by P r e d i c a t e / T r a n s i t i o n N e t s , " Semantics of C o n c u r r e n t Computation, S p r i n g e r — V e r l a g , (New York, 1979), p. 123-146. 33. Han, Y.H., "Performance E v a l u a t i o n of a D i g i t a l System U s i n g a P e t r i N e t - L i k e Approach," P r o c . N a t i o n a l E l e c t r o n i c s Conf., V o l . 32, 1978, p. 168-172. 34. H e i m e r d i n g e r , W.L., Han, Y.H., "A Graph T h e o r e t i c Approach t o F a u l t T o l e r e n t Computing," F i n a l R e p o r t , A i r Forc e O f f i c e of S c i e n t i f i c R e s e a r c h , C o n t r a c t No. F44620-75-C-0053, Sept. 1977. 35. H e i m e r d i n g e r , W.L., "A P e t r i net Approach t o System L e v e l F a u l t T o l e r e n c e A n a l y s i s , " P r o c . N a t i o n a l E l e c t r o n i c s Conf., V o l . 32, p. 161-165. 36. Herzog, O., "Automatic Deadlock A n a l y s i s of P a r a l l e l Programs," P r o c . I n t . Computing Sypm., 1977, p. 209-216. 37. Herzog, 0., " S t a t i c A n a l y s i s of C o n c u r r e n t P r o c e s s e s f o r Dynamic P r o p e r t i e s U s i n g P e t r i N e t s , " Semantics of C o n c u r r e n t Computation, S p r i n g e r - V e r l a g , (New York, 1979), p. 66-90. 117 38. I r a n i , K.B., Zervos, C.R., "Modelling of C o n f l i c t s , P r i o r i t y H i e r a r c h i e s and Reentrancy i n Concurrent S y n c h r o n i z a t i o n S t r u c t u r e s , " Proc. 1 9 7 9 I n t ' l . Conf. P a r a l l e l P r o c e s s i n g , 1979, p. 196-204. 39. I z b i c k i , H., "Marked Graphs With G e n e r a l i z e d F i r i n g R u l es," Proc. Symp. Recent Advances i n Graph Theory, 1974, p. 307-310. 40. J a f f e , J.M., " E f f i c i e n t S c h e d u l i n g without the F u l l Use of Processor Resources," Theor. Comput. S c i . V o l . 12(1), 1980, p.1-17. 41. J a n i c k i , R., "A C h a r a c t e r i z a t i o n of C o n c u r r e n c y - l i k e R e l a t i o n s , " Semantics of Concurrent C o n f u t a t i o n , S p r i n g e r - V e r l a g , (New York, 1979), p. 109-122. 42. Jantzen, M., "On the H i e r a r c h y of P e t r i Net Languages," RAIRO I n f . Theor./Theor. I n f . , V o l . 13(1), 1979, p. 19-30. 43. Jones, N.D., Landweber, L.H., L i e n , Y.E., "Complexity of Some Problems i n P e t r i Nets," Theor. Comput. S c i . , V o l . 4, 1977, p. 277-299. ••, 44. Karp, R.M., M i l l e r , R.E., " P a r a l l e l Program Schemata," J . Comput. S y s t . S c i . , V o l . 3, 1969, p. 147-195. 45. Kartashev, S.I., Kartashev, S.P., "Dynamic A r c h i t e c t u r e : Problems and S o l u t i o n s , " Computer, V o l . 11(7), J u l y 1978, p.26-40. 46. Kartashev, S.I., Kartashev, S.P., "A Multicomputer System with Dynamic A r c h i t e c t u r e , " IEEE Trans. Computers, V o l . C-28(10), Oct. 1979, p. 704-721. 47. Kasami, T., M i l l e r , R.E., "Homomrphisms Between Models of P a r a l l e l Computation," IBM Research Report, RC-7796, 1979. 48. Kwong, Y.S., "On Absence of L i v e l o c k s i n P a r a l l e l Programs," Semantics of Concurrent Computation, S p r i n g e r - V e r l a g , (New York, 1 979), p. 172-1.90. 49. Lauer, P.E., Campbell, R.H. , "A D e s c r i p t i o n of Path E x p r e s s i o n s by P e t r i Nets," Proc. 2nd ACM Symp. P r i n c i p l e s of Programming Languages, 1975,. p. 95—105. 50. Lauer, P.E., Campbell, R.H., "Formal Semantics of a C l a s s of High L e v e l P r i m a t i v e s f o r C o o r d i n a t i n g Concurrent Processes," Acta I n f o r m a t i c a , V o l . 5, 1975, p. 297-332. 1 18 51. Lautenbach, K., Schmid, H.A., "Use of P e t r i Nets f o r P r o v i n g C o r r e c t n e s s of Con c u r r e n t P r o c e s s Systems," I n f o m a t i o n P r o c e s s i n g '74, 1974, p. 181-191. 52. L i e n , Y.E., "A Note on T r a n s i t i o n Systems," I n f o r m a t i o n S c i e n c e s , V o l . 10, p.347-362. 53. L i e n , Y.E., " T e r m i n a t i o n P r o p e r t i e s of G e n e r a l i z e d P e t r i N e t s , " SIAM J . Comput., V o l . 5 ( 2 ) , June 1976, p. 251-265. 54. L i p t o n , R.J., " R e d u c t i o n : A Method of P r o v i n g P r o p e r t i e s of P a r a l l e l Programs," CACM., V o l . 18(12), Dec. 1975, p. 717-721. 55. L i p t o n , R.J., "The R e a c h a b i l i t y Problem R e q u i r e s E x p o n e n t i a l Space," Y a l e U n i v e r s i t y , Dept. of Computer S c i e n c e , Research Report No. 62, Jan. 1976. 56. L i u , J.W.S., L i u , C.L., "Bounds on S c h e d u l i n g A l g o r i t h m s f o r Heterogeneous Computing Systems," I n f o r m a t i o n P r o c e s s i n g 74, N o r t h — H o l l a n d , (Amsterdam, 1974), p7 349-353. 57. L i u , J.W.S., L i u , C.L., "Performance A n a l y s i s of M u l t i p r o c e s s o r Systems C o n t a i n i n g F u n c t i o n a l l y D e d i c a t e d P r o c e s s o r s , " A c t a I n f o r m a t i c a , V o l . 1 0 ( 1 ) , 1978, p. 95-104. 58. Manacher, G.K., " P r o d u c t i o n and S t a b l i z a t i o n of Real-Time Task S c h e d u l e s , " J . ACM, V o l . 1 4 ( 3 ) , J u l y 1967, p. 439-465. 59. M a n d r o i l i , D., "A Note on P e t r i Net Languages," I n f o r m a t i o n and C o n t r o l , V o l . 3 4 ( 2 ) , June 1977, p. 169-171. 60. M a r t i n , D.E., E s t r i n , G., "Experiments on Computations and Systems," IEEE T r a n s . E l e c t r o n i c Computers, V o l . EC-16(1), Feb. 1967, p. 59-69. 61. M e i l i n g , E., "On the M o d e l l i n g Power of P e t r i N e t s , " Dept. of Computer S c i e n c e , C o r n e l l , TR79-403. 62. M e r l i n , P.M., "A Methodology f o r the Design and Implementation of Communication P r o t o c o l s , " IEEE T r a n s . Communications, V o l . COM-24(6), June 1976, p. 614-621. 63. M e r l i n , P.M., F a r b e r , D.J., " R e c o v e r a b i l i t y of Communication P r o t o c o l s - I m p l i c a t i o n s of a T h e o r e t i c a l Study," IEEE Trans. Communications, V o l . COM-24(9), Sept. 1976, p. 1036-1043. 1 19 64. M i l l e r , R.E., Kasami, T., "Comparing Models of P a r a l l e l Computation by Homomorphisms," P r o c . COMPSAC, 1979, p.794-799. 65. Memmi, G., " N o t i o n de D u a l i t y et de Sy m e t r i e Dans l e s Reseaux de P e t r i , " Semantics of Con c u r r e n t Computation, S p r i n g e r - V e r l a g , (New York, 1979), p. 9 1-108. 66. Misunas, D., " P e t r i Nets and Speed Independent D e s i g n , " CACM, V o l . 16(8), Aug. 1973, p. 474-480. 67. Murata, T., " S t a t e E q u a t i o n , C o n t r o l a b i l i t y and Maximal Ma r k i n g of P e t r i N e t s , " IEEE Trans. Automatic C o n t r o l , V o l . A C - 2 2 ( 2 ) , June 1977, p. 412-416. 68. Murata, T., " C i r c u i t T h e o r e t i c A n a l y s i s and S y n t h e s i s of Marked Graphs," IEEE T r a n s . C i r c u i t s and Systems, V o l . CAS-24, J u l y 1977, p. 400-405. 69. Murata, T., Koh, J.Y., " R e d u c t i o n and Expansion of L i v e and Safe Marked Graphs," P r o c . 1979 ISCAS, 1979, p. 841-844. 70. Murata, T., " S y n t h e s i s of Marked Graph Computation Models f o r P r e s c r i b e d Resources and Performance," P r o c . COMPSAC, 1979, p. 807-812. 71. Noe, J.D., N u t t , G.J., "Macro E-Nets f o r R e p r e s e n t a t i o n of P a r a l l e l Systems," IEEE T r a n s . Computers, V o l . C-22(8), Aug. 1973, p.718-727. 72. Noe, J.D., Crowley, C P . , Anderson, T.L., "Design of an I n t e r a c t i v e G r a p h i c a l Net E d i t o r , " P r o c . CIPS-ACM P a c i f i c R e g i o n a l Symp., 1974, p. 386-402. 73. Noe, J.D., " H i e r a r c h i c a l M o d e l l i n g W ith Pro N e t s , " P r o c . N a t i o n a l E l e c t r o n i c s Conf., V o l . 32, 1978, p. 155-160. 74. Pacas-Skewes, E., "A Design Methodology f o r D i g i t a l Systems U s i n g P e t r i N e t s , " Ph.D. T h e s i s , U n i v e r s i t y of Texas, A u s t i n , 1979. 75. P a t i l , S.S., "Asynchronous L o g i c A r r a y , " P r o j e c t MAC, TM-62, May 1975. 76. P a t i l , S.S., " C o o r d i n a t i o n of Asynchronous E v e n t s , " MIT P r o j e c t MAC, TR-62, June 1970. 77. P e t e r s o n , J . L . , "Computation Sequence S e t s , " J . Comput. S y s t . S c i . , V o l . 1 3 ( 1 ) , 1976, p. 1-24. 1 20 78. P e t e r s o n , J.L., " P e t r i N e t s , " Computing S u r v e y s , V o l . 9 ( 3 ) , Sept. 1977, p. 223-252. 79. P e t e r s o n , J . L . , "A Note on C o l o r e d P e t r i N e t s , " I n f . P r o c e s s . L e t t . , V o l . 11(1), 29 Aug. 1980, p. 40-44. 80. Ramamoorthy, C.V., Fox, T.F., L i , H.F., " S c h e d u l i n g P a r a l l e l P r o c e s s a b l e Tasks f o r a U n i p r o c e s s o r , " IEEE T r a n s . Computers, V o l . C-25(5), May 1976, p. 485-495. 81. Ramamoorthy, C.V., Ho, G.S., "Performance E v a l u a t i o n of Asynchronous C o n c u r r e n t Systems U s i n g P e t r i N e t s , " IEEE T r a n s . Software E n g i n e e r i n g , V o l . S E - 6 ( 5 ) , Sept. 1980, p. 440-449. 82. Ramachandani, C , " A n a l y s i s of Asynchronous Concurrent Systems By P e t r i N e t s , " MIT P r o j e c t MAC, TR-120, Feb. 1 974. 83. S c h i f f e r s , M. , Wedde, H., " A n a l y s i n g Program S o l u t i o n s of C o o r d i n a t i o n Problems by CP—Nets," Mathemat i c a l F o u n d a t i o n s of Computer S c i e n c e , S p r i n g e r — V e r l a g , (New York, 1 9 7 8 ) , p. 462-473. 84. S h a p i r o , R.M., S a i n t , H., "A New Approach t o O p t i m i z a t i o n of Sequencing D e c i s i o n s , " Automaatic Programming, V o l . 6 ( 5 ) , 1970, p. 257-288. 85. S h a p i r o , S.D., "A S t o c h a s t i c P e t r i Net w i t h A p p l i c a t i o n s t o M o d e l l i n g Occupancy Times f o r Co n c u r r e n t Task Systems," Network, V o l . 9, 1979, p. 375-379. 86. S i f a k a s , J . , "Use of P e t r i Nets f o r Performance E v a l u a t i o n , " P r o c . 3 r d I n t ' l . Symp. M e a s u r i n g , M o d e l l i n g and E v a l u a t i n g Computer Systems, 1977, p. 75—93. 87. S i f a k a s , J . , " R e a l i z a t i o n of F a u l t T o l e r e n t Systems by Coding P e t r i N e t s , " P r o c . 8 t h I n t ' l . Symp. F a u l t T o l e r e n t Computing, 1978, p. 205. 88.. S i f a k a s , J . , " S t r u c t u r a l P r o p e r t i e s of P e t r i N ets," M a t h e m a t i c a l F o u n d a t i o n s of Computer S c i e n c e , S p r i n g e r - V e r l a g , (New York , 1978), p. 474-483. 89. S i l v a , M., D a v i d , R., "Programmed S y n t h e s i s of Automatic L o g i c D e s c r i b e d by P e t r i N e t s : A Method of Implementation on a Microcomputer," RAIRO Autom/Syst. A n a l , e C o n t r o l , V o l . 1 3 ( 4 ) , p. 369-393 121 90. S t a r k , P.H., "Free P e t r i Net Languages," M a t h e m a t i c a l F o u n d a t i o n s of Computer S c i e n c e , S p r i n g e r - V e r l a g , (New York, 1978), p. 506-515. 91. S z l a n k o , J . , " P e t r i Nets f o r P r o v i n g Some C o r r e c t n e s s P r o p e r t i e s of P a r a l l e l Programs," P r o c . I F A C / I F I P Workshop on R e a l Time Programming, 1977, p. 75—83. 92. T a n i , K., Murata, T., " S c h e d u l i n g P a r a l l e l Computations w i t h S t o r a g e C o n s t r a i n t s , " P r o c . 12th A s i l o m a r Conf. C i r c u i t s , Systems and Computers, 1978, p. 736-743. 93. T a n i , K., Onaga, K., Kakusho, 0., "Modeling and A n a l y s i s of R e s o u r c e — C o n s t r a i n e d Network Problems by P e t r i N e t s , " P r o c . I n t ' l . Conf. C y b e r n e t i c s and S o c i e t y , 1978, p. 884-888. 94. V a l e t t e , R., " A n a l y s i s of P e t r i Nets by S t e p w i s e R e f i n e m e n t s , " J . Comput. S y s t . S c i . , V o l . 18, 1979, p. 35-46. 95. V a l k , R., "On C o m p u t a t i o n a l Power of Extended P e t r i N e t s , " M a t h e m a t i c a l F o u n d a t i o n s of Computer S c i e n c e , S p r i n g e r - V e r l a g , (New Y o r k , 1 9 7 8 ) , p. 526-535. 96. Van Leuwen, J . , "A P a r t i a l S o l u t i o n t o the R e a c h a b i l i t y Problem f o r V e c t o r A d d i t i o n Systems," P r o c . 6th Symp. Theory of Computing, 1974, p. 303-304. 97. V i c k , C R . , K a r t a s h e v , S . I . , K a r t a s h e v , S.P., "Adaptable A r c h i t e c t u r e s f o r Supersystems," Computer, V o l . 13(11), Nov. 1980, p. 17-35. 98. Voss, K., "Using P r e d i c a t e / T r a n s i t i o n Nets t o Model and A n a l y s e D i s t r b u t e d Database Systems," P r o c . COMPSAC, 1979, p. 801-806. 99. W i n t e r , R., "An E v a l u a t i o n Net Model f o r the Performance E v a l u a t i o n of a Computer Network," P r o c . 3rd I n t ' l . Symp. Me a s u r i n g , M o d e l l i n g and E v a l u a t i n g Computer Systems, 1979, p. 95-113. 100. Y o e l i , M. , G i n s b e r g , A., " P e t r i Net Languages and T h e i r A p p l i c a t i o n s , " U n i v e r s i t y of W a t e r l o o , F a c u l t y of M a t h e m a t i c s , Research Report CS-78-45, Nov. 1978. 101. Zervos, C.R., I r a n i , K.B., " C o l o r e d P e t r i N e t s : T h e i r P r o p e r t i e s and A p p l i c a t i o n s , " RADC-TR-77-246, Aug. 1977. 1 22 Zuberek, W.M., "Timed P e t r i Nets and P r e l i m i n a r y Performance E v a l u a t i o n , " Proc. 7th Symp. Computer A r c h i t e c t u r e , 1980, p. 88-96. 123 Appendix A D e f i n i t i o n s and N o t a t i o n P e t r i Net N o t a t i o n n i s the number of p l a c e s . m i s the number of t r a n s i t i o n s . S c h e d u l i n g N o t a t i o n n i s the number of p r o c e s s o r s . r i s the number of t a s k s . s i s the number of r e s o u r c e s . D e f i n i t i o n 1 [53] I f P={A,,A 2,...,A A] i s a s e t symbols, then P* i s d e f i n e d r e c u r s i v e l y , as f o l l o w s . ( i ) A, the empty s t a t e , i s i n P*. ( i i ) A i i s i n P*, 1 P={AT,A 2,...,A A} i s a s e t of p l a c e s . T={ t , , 1 2 , . • • , t*\} P* P* i s a s e t of t r a n s i t i o n s t i : \ a ^ A i "> ? b i i A i 1 24 D e f i n i t i o n 3 [53] A marked P e t r i n e t , MPN. MPN= m i s an element of P* D e f i n i t i o n 4 [53] The c h a r a c t e r i s t i c m a t r i x , r . ( r i 3 ) = a x i - b i 3 D e f i n i t i o n 5 [80] A timed P e t r i n e t , TPN. TPN= 0 : T^ ( T | , T ^ ) a f u n c t i o n mapping a t r a n s i t i o n onto a p o s i t i v e r e a l number, T. D e f i n i t i o n 6 [102] An i n s t a n t a n e o u s d e s c r i p t o r , d . d i = ( m i r r i ) m^ _€ P* i s the marking. T X R i s the r e m a i n i n g t i m e . D e f i n i t i o n 7 [38] A c o l o u r e d P e t r i n e t , CPN. CPN= C=(X,<): a s e t of c o l o u r s X and a p a r t i a l o r d e r , <. F: A X a f u n c t i o n mapping each edge c A onto a c o l o u r , where A i s the s e t of edges. 125 D e f i n i t i o n 8 A s t a t e y i s d i r e c t l y reachable from a s t a t e x, i f there e x i s t s a t r a n s i t i o n , t , enabled i n x which when f i r e d r e s u l t s i n the s t a t e x, x=t=3> y. D e f i n i t i o n 9 A s t a t e y i s reachable from a s t a t e x through a sequence of t r a n s i t i o n s , «=a,e2 •.•«\, i f there e x i s t s a sequence of s t a t e s , x^, 1 x i ^ - | X = tf X, D e f i n i t i o n 10 A path i n a d i r e c t e d graph i s a sequence of edges such t h a t the edges are connected head t o t a i l . Def i n i t i o n 11 A d i r e c t e d c i r c u i t i s a path with one common node, the f i r s t and l a s t node. 1 26 D e f i n i t i o n 12 [16] A t a s k system ( %/, < , { } , { (R }) £ 7 =(T,,T 2,...,T r): a s e t of t a s k s <: an i r r e f l e x i v e p a r t i a l o r d e r on T ^ - : e x e c u t i o n time of t a s k i on p r o c e s s o r j . (P, =[R, (Tj ) ,R2 (Tj ) , . . . , R s ( T j ) ]: r e s o u r c e requirement of task j . D e f i n i t i o n 13 [40] The t o t a l e x e c u t i o n t i m e , v, of a task system, i D e f i n i t i o n 14 [40] A c h a i n s t a r t i n g w i t h t a s k , T j , i s a s e t of t a s k s , (T j , . . . , Tj , T^ , . . . , T-j) , such t h a t , T^ i s an immediate s u c e s s o r of T j , Tj I~I c /™\ i~i t~ r r o c c s s o r s MCLMT HLF CG RANDOM w* ' C I C l 120 126 128 126 104 c i C i 135 145 146 139 123 C l C l C! 1 19 130 131 133 104 C i C J 140 168 154 144 136 C i C J C l 138 160 158 156 104 C I C 3 C l C i 138 160 158 156 104 C i C i C l 129 148 149 154 104 C i C l 186 188 188 190 177 C I C l 238 244 248 243 213 C I C l C l 184 184 222 236 168 C I C i 244 246 290 248 236 C I C ] C l 210 210 286 282 177 C I C l C J 210 210 251 258 168 Table B.3: Example 1 with longer execution times Processors Execution Time w MCLMT HLF CG RANDOM w*' C l C i 12 12 12 12 1 1 C l c< 24 24 24 24 18 C l C l 15 15 15 15 14 C l c • C 3 24 24 24 24 13 C i Cs Ce 24 24 24 24 15 C I C 3 C 3 13 13 13 14 1 1 Table Et.4: Example 1 with u n i t execution times