Séminaire Lotharingien de Combinatoire, B29d (1992), 9
[Formerly: Publ. I.R.M.A. Strasbourg, 1993, 1993/033, p.
Walter Gutjahr and Georg Pflug
Average Execution Times of Series-Parallel Networks
The papers investigates a model for series-parallel
processing structures developed by E. Gelenbe. We show that,
under the so-called combinatorial distribution assumption,
the average total execution time of a series-parallel
processing structure cannot grow essentially slower than n1/2,
where n is the number of primitive tasks in the structure.
The following version is available: