E-Book Content
Timed coloured Petri nets and their application to logistics
The study reported in this monograph is sponsored by the TNO Institute for Production and Logistics (IPL) as part of the TASTE project.
TIMED COLOURED PETRI NETS AND THEIR APPLICATION TO LOGISTICS
PROEFSCHRIFT ter verkrijging van de graad van doctor aan de Technische Universiteit Eindhoven, op gezag van de Rector Magni cus, prof. dr. J.H. van Lint, voor een commissie aangewezen door het College van Dekanen in het openbaar te verdedigen op donderdag 17 september 1992 om 16.00 uur door
Willibrordus Martinus Pancratius van der Aalst geboren te Eersel
Dit proefschrift is goedgekeurd door de promotoren prof. dr. J. Wessels en prof. dr. K.M. van Hee
Contents 1 Introduction
1.1 Problem statement . . . . . . . . . . . . . . . . . . . 1.2 Petri nets . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Time and colour in Petri nets . . . . . . . . . . . . . 1.3.1 Adding colour . . . . . . . . . . . . . . . . . . 1.3.2 Adding time . . . . . . . . . . . . . . . . . . . 1.4 Analysis of timed coloured Petri nets . . . . . . . . . 1.4.1 Currently used analysis methods . . . . . . . 1.4.2 Analysis methods based on the ITCPN model 1.5 ExSpect . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Application to logistics . . . . . . . . . . . . . . . . . 1.7 Other methods . . . . . . . . . . . . . . . . . . . . . 1.8 Outline of this monograph . . . . . . . . . . . . . . .
2 A timed coloured Petri net model
2.1 2.2 2.3 2.4
Introduction . . . . . . . . . . . . . . Notations . . . . . . . . . . . . . . . Transition systems . . . . . . . . . . The model . . . . . . . . . . . . . . . 2.4.1 Semantics of an ITCPN . . . 2.4.2 Alternative ring rules . . . . 2.5 Some further concepts and properties 2.6 Interesting performance measures . . 2.7 Conclusion . . . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
1 4 6 6 7 10 10 12 16 18 19 22 23
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
3.1 Introduction . . . . . . . . . . . . . . . . . . 3.2 Method ATCFN . . . . . . . . . . . . . . . . 3.2.1 Application to project engineering . . 3.3 Method MTSRT . . . . . . . . . . . . . . . 3.3.1 The modi ed transition system . . . 3.3.2 Using the modi ed transition system 3.4 Method PNRT . . . . . . . . . . . . . . . . 3.5 Dealing with large colour sets . . . . . . . . 3.5.1 Approach 1: remove the colour . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. 67 . 71 . 76 . 79 . 82 . 90 . 97 . 109 . 111
i
. . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . .
3 Analysis of time in nets
. . . . . . . . .
. . . . . . . . . . . .
1
23 24 29 34 37 41 47 58 65
67
ii
CONTENTS
3.5.2 Approach 2: re ne the net 3.6 An example . . . . . . . . . . . . 3.7 Conclusion . . . . . . . . . . . . . 3.8 Appendix . . . . . . . . . . . . .
. . . .
. . . .