Extreme Runtimes of Schedules Modelled by Time Petri Nets

• Autorzy: Popova-Zeugmann L. , Werner M.
• Języki publikacji: EN

Abstrakty

EN

In this paper, a method to determine best-case and worst-case times between two arbitrary markings in a bounded TPN is presented. The method uses a discrete subset of the state space of the net and achieves the results, which are integers, in polynomial time. As an application of the method the solution of a scheduling problem is shown.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 67, nr 1-3
• Strony: 163--174
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Popova-Zeugmann L.

• Logic in Computer Science Group, Department of Computer Science, Humboldt University, Berlin, Germany

autor

Werner M.

• Communication and Operating Systems Group Department for Electrical Engineering and Computer Science TU Berlin, Germany

Bibliografia

• [1] Berthomieu, B., Diaz, M.: Modeling and Verification of Time Dependent Systems Using Time Petri Nets, Advances in Petri Nets 1984, 17, No. 3, 1991.
• [2] Berthomieu, B.,Menasche, M.: An Enumerative Approach for Analyzing Time Petri Nets, Proceedings IFIP (R. E. A. Masom (ed.), Ed.), 17, No. 3, North-Holland, 1983.
• [3] Boucheneb, H., Berthelot, G.: Towards a Simplified Building of Time Petri Net Reachability Graphs, Proceedings of Petri Nets and Performance Models PNPM 93, IEEE Computer Society Press, Toulouse France, 1993.
• [4] Bucci, G., Fedeli, A., Sassoli, L., Vicario, E.: Timed State Space Analysis of Real-Time Preemptive Systems, IEEE Transactions on Software Engineering, 30(2), 2004, 97–111.
• [5] Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.: Introduction to Algorithms, second edition, MIT Press, 2001.
• [6] Graham, R.: Bounds on the performance of scheduling algorithms, in: Computer and job scheduling theory (E. Coffman, Ed.), John Wiley and Sons, 1976, 165–227.
• [7] Heiner, M., Popova-Zeugmann, L.: Worst-case Analysis of Concurent Systems with Duration Interval Petri Nets, Entwurf komplexer Automatisierungssysteme (E. Schnieder, D. Abel, Eds.), TU Braunschweig, IfRA, 1997.
• [8] Lui, C. L., Layland, J. W.: Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Enviroment, JACM, 20(1), January 1973, 46–61.
• [9] Merlin, P.: A Study of the Recoverability of Communikation Protocols, Ph.D. Thesis, University of California, Computer Science Dept., Irvine, 1974.
• [10] Popova-Zeugmann, L.: Zeit-Petri-Netze, Ph.D. Thesis, Humboldt-Universität zu Berlin, 1989.
• [11] Popova-Zeugmann, L.: On Parametrical Sequences in Time Petri Nets, Proceedings of the CS&P’97 Workshop (H.-D. Burkhard, L. Czaja, P. Starke, Eds.),Warsaw, 1997.
• [12] Popova-Zeugmann, L., Schlatter, D.: Analyzing Path in Time Petri Nets, Fundamenta Informaticae 37, IOS Press, 1999, 311–327.
• [13] Stankovic, J. A., Spuri, M., Natale, M. D., Buttazzo, G. C.: Implications of Classical Scheduling Results for Real-Time Systems, IEEE Computer, 28(6), June 1995, 16–25.
• [14] Starke, P. H.: INA - Integrated Net Analyzer, Berlin, 1997, Manual.