Time Distribution in Structural Workflow Nets

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.