Timed Petri nets in modeling and analysis of manufacturing systems

Zuberek, W.M.

Int. Journal of Factory Automation, Robotics and Soft Computing, issue 2, pp.30-37, 2007 (ISSN 1828-6984).

Abstract:

Petri nets are formal models of systems which exhibit concurrent activities. As formal models, Petri nets are bipartite directed graphs, in which the two types of vertices represent, in a very general sense, conditions and events. In order to study performance aspects of systems modeled by Petri nets, the durations of modeled activities must also be taken into account. This can be done in different ways, resulting in different types of nets "with time". In timed Petri nets, occurrence times are associated with events. For timed nets with constant occurrence times, if the net is covered by a family of simple cyclic subnets, basic performance characteristics can be obtained by structural analysis, without the exhaustive generation of the state space. The paper overviews basic concepts of Petri nets, introduces timed Petri nets, and applies these concepts to hierarchical modeling and evaluation of manufacturing systems.

Keywords:

Timed Petri nets, performance analysis, manufacturing systems, hierarchical modeling.

References:

• Aalst van der, W.M.P., "Interval timed colored Petri nets"; in: Advances in Petri nets 1993 (Lecture Notes in Computer Science 674), pp.126-147, Springer-Verlag 1993.
• Ajmone Marsan, M., Balbo, G., Bobbio, A., Chiola, G., Conte, G., Cumani, A., "The effect of execution policies on the semantics and analysis of stochastic Petri nets"; IEEE Trans. on Software Engineering, vol.15, no.7, pp.832-846, 1989.
• Ajmone Marsan, M., Balbo, G., Conte, G., "The early days of GSPNs"; in Performance Evaluation: Origins and Directions (Lecture Notes in Computer Science 1769), pp.505-512, Springer-Verlag 2000.
• Ajmone Marsan, M., Balbo, G., Conte, G., Donatelli, S., Franceschinis, G., Modeling with Generalized Stochastic Petri Nets; J. Wiley and Sons 1995.
• Ajmone Marsan, M., Conte, G., Balbo, G., "A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems"; ACM Trans. on Computer Systems, vol.2, no.2, pp.93-122, 1984.
• Bause, F., Kritzinger, P.S., Stochastic Petri Nets - An Introduction to the Theory, Vieweg Verlag 1996.
• Bobbio, A., Puliafito, A., Telek, M., Trivedi, K.S., "Recent developments in non-Markovian stochastic Petri nets"; Journal of Circuits, Systems, and Computers, vol.8, no.1, pp.119-158, 1998.
• Chiola, G., Ajmone Marsan, M., Balbo, G., Conte, G., "Generalized stochastic Petri nets: a definition at the net level and its implications"; IEEE Trans. on Software Engineering, vol.19, no.2, pp.89-107, 1993.
• Desrochers, A.A., Al-Jaar, R.Y., Applications of Petri Nets in Manufacturing Systems; IEEE Press 1995.
• DiCesare, F., Harhalakis, G., Proth, J.M., Silva, M., Vernadat, F.B., Practice of Petri Nets in Manufacturing; Chapman and Hall 1993.
• Girault, C., Valk, R., Petri Nets for Systems Engineering; Springer-Verlag 2002.
• Haas, P.J., Stochastic Petri Nets; Springer-Verlag 2002.
• Hillston, J., A Compositional Approach to Performance Modeling; Cambridge University Press 1996.
• Jensen, K., Colored Petri Nets - Basic Concepts, Analysis Methods and Practical Use, vol.1; Springer-Verlag 1992.
• Jensen, K., Colored Petri Nets - Basic Concepts, Analysis Methods and Practical Use, vol.2; Springer-Verlag 1995.
• Koutny, M., "A compositional model of time Petri nets"; in: Application and Theory of Petri Nets 2000 (Lecture Notes in Computer Science 1825), pp.303-322, Springer-Verlag 2000.
• Krueckeberg, F., Jaxy, M., "Mathematical methods for calculating invariants in Petri nets"; in: Advances in Petri Nets 1987 (Lecture Notes in Computer Science 266), pp.104-131, Springer-Verlag 1987.
• Lindemann, C., Performance Modeling with Deterministic and Stochastic Petri Nets; Wiley and Sons 1998.
• Martinez, J., Silva, M., "Simple and fast algorithm to obtain all invariants of a generalized Petri net"; in: Applications and Theory of Petri Nets (Informatik Fachberichte 52); pp.301-310, Springer-Verlag 1982.
• Merlin, P.M., Farber, D.J., "Recoverability of communication protocols - implications of a theoretical study"; IEEE Trans. on Communications, vol.24, no.9, pp.1036-1049, 1976.
• Molloy, M.K., "Performance analysis using stochastic Petri nets"; IEEE Trans. on Computers, vol.31, no.9, pp.913-917, 1982.
• Murata, T., "Petri nets: properties, analysis and applications"; Proceedings of IEEE, vol.77, no.4, pp.541-580, 1989.
• Peterson, J.L., Petri Net Theory and the Modeling of Systems; Prentice-Hall 1981.
• Petri, C.A., "Kommunikation mit Automaten"; Ph.D. Dissertation, University of Bonn, Bonn, Germany 1962; also: Memorandum MAC-M-212, Project MAC, Massachusetts Institute of Technology, Cambridge, MA.
• Proth, J.M., Xie, X., Petri Nets; Wiley and Sons 1996.
• Reisig, W., Petri Nets - An Introduction (EATCS Monographs on Theoretical Computer Science 4); Springer-Verlag 1985.
• Reisig, W., Elements of Distributed Algorithms - Modeling and Analysis with Petri Nets; Springer-Verlag 1999.
• Rokyta, P., Fengler, W., Hummel, T., "Electronic system design automation using high level Petri nets"; in: Hardware Design and Petri Nets, pp.193-204, Kluwer Academic Publ. 2000.
• Sethi, S.P., Sriskandarajah, C., Sorger, G., Blazewicz, J., Kubiak, W., "Sequencing of parts and robot moves in a robotic cell"; Int. Journal of Flexible Manufacturing Systems, vol.4, pp.331-358, 1992.
• Sifakis, J., "Structural properties of Petri nets"; in: Mathematical Foundations of Computer Science 1978 (Lecture Notes in Computer Science 64), pp.474-483, Springer-Verlag 1978.
• Sifakis, J., "The compositional specification of timed systems - a tutorial"; in: Computer Aided Verification (Lecture Notes in Computer Science 1633), pp.2-7, Springer-Verlag 1999.
• Wang, J., Timed Petri nets; Kluwer Academic Publ. 1998.
• Wu, Z., "CEM/T net, a high level Petri net for FMS modeling"; International Journal of Intelligent Control Systems, vol.3, no.3, pp.377-387, 1999.
• Zhou, M-C., Petri Nets in Flexible and Agile Automation; Kluwer Academic Publishers 1995.
• Zuberek, W.M., "Timed Petri nets - definitions, properties and applications"; Microelectronics and Reliability (Special Issue on Petri Nets and Related Graph Models), vol.31, no.4, pp.627-644, 1991.
• Zuberek, W.M., "Hierarchical derivation of schedules for manufacturing cells"; Proc. 9-th Symp. on Information Control in Manufacturing (INCOM-98), Nancy-Metz, France, pp.423-428, 1998.
• Zuberek, W.M., "Stepwise refinements of net models and their place invariants"; Proc. 8-th Int. Workshop on Petri Nets and Performance Models (PNPM'99), Zaragoza, Spain, pp.92-101, 1999.
• Zuberek, W.M., "Discrete-event simulation of timed Petri net models"; Proc. 33-rd Annual Simulation Symposium; Washington, D.C., pp.91-98, 2000.
• Zuberek, W.M., "Petri nets in hierarchical modeling of manufacturing systems"; Proc. IFAC Conf. on Control System Design (CSD'2000), Bratislava, Slovakia, pp.287-292, 2000.
• Zuberek, W.M., Bluemke, I., "Hierarchies of place/transition refinements in Petri nets"; Proc. 5-th IEEE Int. Conf. on Emerging Technologies and Factory Automation (ETFA'96), Kauai, Hawaii, pp.355-360, 1996.
• Zuberek, W.M., Kubiak, W., "Timed Petri nets in modeling and analysis of simple schedules for manufacturing cells"; Computers and Mathematics with Applications, vol.37, no.12-12, pp.191-206, 1999.
• Zuberek, W.M., Zuberek, M.S., "Transformations of timed Petri nets and performance analysis"; Proc. 33-rd Midwest Symp. on Circuit and Systems (Special Session on Petri Net Models), Calgary, Alberta, pp.774-778, 1990.