Stepwise refinements of net models and their place invariants

Zuberek, W.M.

Proc. 8-th Int. Workshop on Petri Nets and Performance Models (PNPM'99); Zaragoza, Spain, 8-10 September 1999, pp.92-101.

Abstract:

Schedules for manufacturing cells can be systematically derived by simple stepwise refinements which, in consecutive steps, increase the complexity of the cell by introducing its components one after another. Timed Petri net models of schedules derived in this way have some convenient structural properties - net models are covered by conflict-free subnets, determined by place invariants of the model. These place invariant implied subnets can be used for evaluation of the basic performance characteristics of the model. The paper shows that place invariants of net models of schedules can be obtained by the same stepwise refinements that are used for model derivation. Simple examples of performance evaluation are included as an illustration of the use of place invariants in the analysis of schedules.

Keywords:

Timed Petri netsw, stepwise refinement, manufacturing cells, structural analysis, place invariants.

References:

• Banaszak, Z., "Modeling of manufacturing systems"; in Modern Manufacturing, pp.253-286, Springer-Verlag 1994.
• Carlier, J., Chretienne, P., Girault, C., "Modelling scheduling problems with timed Petri nets"; in Advances in Petri Nets 1984 (Lecture Notes in Computer Science 188), pp.62-82, Springer-Verlag 1985.
• Cavalieri, S., Mirabella, O., Zingarino, G., "A Petri net based approach for FMS performance evaluation"; Proc. 23-rd Int. Conf. on Industrial Electronics, Control, and Instrumentation (IECON'97), New Orleans, LA, vol.3, pp.1204-1209, 1997.
• 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 & Hall 1993.
• Ezpeleta, J., Garcia-Valles, F., Colom, J.M., "A class of well structured Petri nets for flexible manufacturing systems"; in Application and Theory of Petri Nets 1998 (Lecture Notes in Computer Science 1420), pp.64-83, 1998.
• Frey, G., Mossig, K., Schnabel, M., "Assembly line sequencing based on Petri net T-invariants"; Proc. 9-th IFAC Symp. on Information Control in Manufacturing (INCOM'98), Nancy-Metz, France, vol.2, pp.33-38, 1998.
• Holliday, M.A., "Deterministic time and analytical models of parallel architectures"; Ph.D. Thesis, Computer Science Department, University of Wisconsin - Madison, Technical Report #652, 1986.
• Krueckeberg, F., Jaxy, M., "Mathematical methods for calculating invariants in Petri nets"; in Advances in Petri Nets 1987 (Lecture Notes in Computer Science 266), G. Rozenberg (ed.), pp.104-131, Springer-Verlag 1987.
• 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.
• Murata, T., "Petri nets: properties, analysis and applications"; Proceedings of IEEE, vol.77, no.4, pp.541-580, 1989.
• Ramchandani, C., "Analysis of asynchronous concurrent systems by timed Petri nets"; Project MAC Technical Report MAC-TR-120, Massachusetts Institute of Technology, Cambridge MA, 1974.
• Reisig, W., Petri nets - an introduction (EATCS Monographs on Theoretical Computer Science 4); Springer-Verlag 1985.
• 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.
• Silva, M., Valette, R., "Petri nets and flexible manufacturing"; in Advances in Petri nets 1989 (Lecture Notes in Computer Science 424), pp.374-417, Springer-Verlag 1989.
• Xue, Y., Kieckhafer, R.M., Choobineh, F.F., "Automated construction of GSPN models for flexible manufacturing systems", Computers in Industry, vol.37, no.1, pp.17-25, 1998.
• 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., "Application of timed Petri nets to modeling and analysis of flexible manufacturing cells"; Technical Report #9503, Department of Computer Science, Memorial University of Newfoundland, St.John's, NF, Canada A1B 3X5, 1995.
• 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.

Available in pdf and postscript.