In: Ajmone Marsan, M.: Lecture Notes in Computer Science, Vol. 691; Application and Theory of Petri Nets 1993, Proceedings 14th International Conference, Chicago, Illinois, USA, pages 357-376. Springer-Verlag, 1993.
Abstract: This paper addresses the performance evaluation and marking optimization of stochastic timed event graphs. The transition firing times are generated by random variables with general distribution. The marking optimization problem consists in obtaining a given cycle time while minimizing a p-invariant criterion (or S-invariant). Some important properties have been established. In particular, the average cycle time is shown to be non-increasing with respect to the initial marking while the p-invariant criterion is non-decreasing. We further prove that the criterion value of the optimal solutions is non-increasing in transition firing times in stochastic ordering's sense. Lower bounds and upper bounds of the average cycle time are proposed. Based on these bounds, we show that the p-invariant criterion reaches its minimum when the firing times become deterministic. A sufficient condition under which an optimal solution for the deterministic case remains optimal for the stochastic case is given. These new bounds are also used to provide simple proof of the reachability conditions of a given cycle time. Thanks to the tightness of the bounds for the normal distribution case, two algorithms which lead to near-optimal solutions have been proposed to solve the stochastic marking optimization problem with normal distributed firing times.