Extreme Runtimes of Schedules Modelled by Time Petri Nets

Issue title: Concurrency Specification and Programming (CS&P 2004)

Article type: Research Article

Authors: Popova-Zeugmann, Louchka | Werner, Matthias

Affiliations: Logic in Computer Science Group, Department of Computer Science, Humboldt University, Berlin, Germany. E-mail: [email protected] | Communication and Operating Systems Group, Department for Electrical Engineering and Computer Science, TU Berlin, Germany. E-mail: [email protected]

Abstract: 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.

Journal: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 163-174, 2005