Abstract
We give a method to compute the throughput in a timed live and bounded free-choice Petri net under a total allocation (i.e. a 0-1 routing). We also characterize and compute the conflict-solving policies that achieve the smallest throughput in the special case of a 1-bounded net. They do not correspond to total allocations, but still have a small period.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baccelli, F., Cohen, G., Olsder, G.J., Quadrat, J.P.: Synchronization and Linearity. John Wiley & Sons, New York (1992)
Bouillard, A., Gaujal, B., Mairesse, J.: Extremal throughput in free-choice nets. Research Report RR LIP 2005-14, ENS Lyon, France (2005)
Carlier, J., Chretienne, P.: Timed Petri net schedules. In: Rozenberg, G. (ed.) APN 1988. LNCS, vol. 340, pp. 62–84. Springer, Heidelberg (1988)
Chretienne, P.: Les Réseaux de Petri Temporisés. PhD thesis, Université Paris VI, Paris (1983)
Cohen, G., Dubois, D., Quadrat, J.P., Viot, M.: A linear system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing. IEEE Trans. Automatic Control 30, 210–220 (1985)
Desel, J., Esparza, J.: Free Choice Petri Nets. In: Cambridge Tracts in Theoretical Comp. Sc., vol. 40. Cambridge Univ. Press, Cambridge (1995)
Gaubert, S., Mairesse, J.: Modeling and analysis of timed Petri nets using heaps of pieces. IEEE Trans. Aut. Cont. 44(4), 683–698 (1999)
Gaujal, B., Haar, S., Mairesse, J.: Blocking a transition in a free-choice net and what it tells about its throughput. Journal of Computer and System Sciences 66(3), 515–548 (2003)
Mairesse, J., Vuillon, L.: Asymptotic behavior in a heap model with two pieces. Theoret. Comput. Sci. 270, 525–560 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bouillard, A., Gaujal, B., Mairesse, J. (2005). Extremal Throughputs in Free-Choice Nets. In: Ciardo, G., Darondeau, P. (eds) Applications and Theory of Petri Nets 2005. ICATPN 2005. Lecture Notes in Computer Science, vol 3536. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11494744_8
Download citation
DOI: https://doi.org/10.1007/11494744_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26301-2
Online ISBN: 978-3-540-31559-9
eBook Packages: Computer ScienceComputer Science (R0)