Abstract
Timed Petri nets can be used to model and analyse scheduling problems. To support the modelling of scheduling problems, we provide a method to map tasks, resources and constraints onto a timed Petri net. By mapping scheduling problems onto Petri nets, we are able to use standard Petri net theory. In this paper we will show that we can use Petri net based tools and techniques to find conflicting and redundant precedences, upper- and lower-bounds for the makespan, etc. This is illustrated by a Petri net based analysis of the notorious 10×10 problem due to Fisher & Thompson (1963)
Zusammenfassung
Petrinetze mit Zeitbewertungen können zur Modellierung und Analyse von Scheduling-Problemen eingesetzt werden. Zur Unterstützung der Modellierung von Scheduling-Problemen stellen wir eine Methode zur Abbildung von Arbeitsgängen, Ressourcen und Randbedingungen auf Petrinetze mit Zeitbewertung vor. Hierbei können wir auf die Standard-Petrinetztheorie zurückgreifen. In der vorliegenden Arbeit wird gezeigt, daß petrinetz-basierte Werkzeuge und Techniken eingesetzt werden können, um widersprüchliche und redundante Prezedenzrelationen, obere und untere Schranken für die „Durchlaufzeit“, etc. zu finden. Dies wird anhand einer petrinetz-basierten Analyse des inhärent schwierigen 10×10 Problems von Fisher and Thompson (1963) gezeigt.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aalst WMP van der (1992a) Modelling and Analysis of Complex Logistic Systems. In: Pels HJ, Wortmann JC (eds) Integration in Production Management Systems, IFIP Transactions B-7. Elsevier Science Publishers Amsterdam, pp 277–292
Aalst WMP van der (1992b) Timed coloured Petri nets and their application to logistics, Ph.D. thesis, Eindhoven University of Technology, Eindhoven
Aalst WMP van der (1993) Interval Timed Coloured Petri Nets and their Analysis, in: Ajmone Marsan M (ed) Application and Theory of Petri Nets 1993. Lecture Notes in Computer Science Vol 691, Springer, Berlin, pp 453–472
Aalst WMP van der (1994) Putting Petri nets to work in industry. Computers in Industry 25: 45–54
Baker KR (1974) Introduction to Sequencing and Scheduling. Wiley & Sons, New York
Berthomieu B, Diaz M (1991) Modelling and verification of time dependent systems using Time Petri Nets. IEEE Transact Software Eng 17:259–273
Carlier J, Chretienne P (1988) Timed Petri net schedules. In: Rozenberg G (ed) Advances in Petri Nets 1988, Lecture Notes in Computer Science Vol 340. Springer, Berlin, pp 62–84
Carlier JP, Chretienne P, Girault C (1984) Modelling scheduling problems with Timed Petri Nets. In: Rozenberg G (ed) Advances in Petri Nets 1984, Lecture Notes in Computer Science Vol 188. Springer, Berlin, pp 62–84
Carlier J, Pinson E (1989) An algorithm for solving the job-shop problem. Manag Sci 35: 164–176
Chretienne P (1983) Les réseaux de petri temporisés. Ph.D. thesis, Univ. Paris VI, Paris
Fisher H, Thompson GL (1963) Probabilistic learning combinations of local job-shop scheduling rules. In: Muth JF, Thompson GL (eds) Industrial Scheduling. Prenctice-Hall, Englewood Cliffs, pp 225–251
French S (1982) Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Wiley & Sons, New York
Gao GR, Wong YB, Ning Q (1991) A timed Petri-net model for loop scheduling, Proceedings of the 12th International Conference on Applications and Theory of Petri Nets, Gjern, pp 22–41
Haupt R (1989) A survey of priority rule-based scheduling. OR Spectrum 11: 3–16
Hillion HP, Proth JP (1989) Performance Evaluation of Job-Shop Systems Using Timed Event Graphs. IEEE Transact Automatic Control 34: 3–9
Jensen K (1992) Coloured Petri Nets. Basic concepts, analysis methods and practical use. EATCS monographs on Theoretical Computer Science. Springer, Berlin
Jensen K, Rozenberg G (eds) (1991) High-level Petri Nets: Theory and Application. Springer, Berlin
Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1993) Sequencing and scheduling: Algorithms and complexity. In: Graves SC, Rinnooy Kan AHG, Zipkin P (eds) Handbooks in Operations Research and Management Science, Vol 4: Logistics of Production and Inventory. North-Holland, Amsterdam
Marsan M, Balbo AG, Conte G (1984) A Class of Generalised Stochastic Peri Nets for the Performance Evaluation of Multiprocessor Systems. ACM Transact Comput Syst 2: 93–122.
Marsan M, Balbo AG, Conte G (1986) Performance Models of Multiprocessor Systems. The MIT Press, Cambridge
Martinez J, Silva M (1982) A simple and fast algorithm to obtain all invariants of a generalised Petri Net, In: Girault C, Reisig W (eds) Application and theory of Petri nets: selected papers from the first and the second European workshop, Informatik Fachberichte 52, Berlin. Springer, Berlin, pp 301–310
Murata T (198) Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE 77: 541–580
Peters N (1994) Analysis of scheduling problems by means of INA/ExSpect, Master's thesis, Eindhoven University of Technology, Eindhoven
Petri CA (1962) Kommunikation mit Automaten, Ph.D thesis, Institut für instrumentelle Mathematik, Bonn
Pinedo M (1995) Scheduling: theory, algorithms, and systems. Prentice-Hall, Englewood Cliffs
Ramamoorthy CV, Ho GS (1980) Performance Evaluation of Asynchronous Concurrent Systems Using Petri Nets. IEEE Transact Software Eng 6: 440–449
Reisig W (1985) Petri nets: an introduction. Prentice-Hall, Englewood Cliffs
Starke PH (1992) INA: Integrierter Netz-Analysator, Handbuch
Watanabe T, Yamauchi M (1993) New priority-lists for scheduling in timed Petri nets, In: Ajmone Marsan M (ed), Application and Theory of Petri Nets 1993. Lecture Notes in Computer Science Vol 691, Springer, Berlin, pp 493–512
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
van der Aalst, W.M.P. Petri net based scheduling. OR Spektrum 18, 219–229 (1996). https://doi.org/10.1007/BF01540160
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01540160