Time Distribution in Structural Workflow Nets

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

Article type: Research Article

Authors: Chrz�stowski-Wachtel, Piotr | Findeisen, Paweł | Wolny, Grzegorz

Affiliations: Institute of Informatics, Warsaw University Banacha 2, 02-097 Warsaw, Poland. pch@mimuw.edu.pl; pf197857@students.mimuw.edu.pl; gwolny@mimuw.edu.pl

Note: [] Address for correspondence: Warsaw University, Banacha 2, 02-097 Warsaw, Poland

Abstract: Workflows with transition execution times having exponential distributions are considered. The aim is to determine the overall execution time without looking into the reachability space and its analysis using Markov processes. We concentrate on the so called structural workflows, which are represented with Petri nets constructed by means of specific refinement rules. With each refinement rule (sequence, choice, parallelization, loop) we associate formulas which allow to compute the overall execution time distribution. The class of exponential distributions is too narrow to keep the result within itself. We analyze the so called exponential polynomials, generalizing exponential distributions. They are closed under SUM and MAX functions. This closure property combined with the knowledge of refinements history enables us to find the requested formulas.

Journal: Fundamenta Informaticae, vol. 85, no. 1-4, pp. 67-87, 2008