HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Marking optimization of stochastic timed event graphs using IPA

Abstract : This paper addresses the marking optimization of stochastic timed event graphs. The transition firing times are generated by random variables with general distributions. The marking optimization problem consists of obtaining a given cycle time while minimizing a p-invariant criterion. 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 solution is non-increasing in transition firing times in stochastic ordering's sense. Based on some existing lower bounds and upper bounds of the average cycle time, we show that the p-invariant criterion reaches its minimum when the firing times become deterministic and we establish the reachability conditions of a given cycle time. We also propose a heuristic algorithm. It starts from the optimal solution to the deterministic case and iteratively adds tokens to adequate places as long as the given cycle time is not obtained. Infinitesimal perturbation analysis of the average cycle time with respect to the transition firing times is used to identify the adequate places in which the new tokens are added. Numerical results show that the heuristic algorithm provides near optimal solutions.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:29:00 PM
Last modification on : Friday, February 4, 2022 - 3:18:17 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 7:31:58 PM


  • HAL Id : inria-00074816, version 1



Jean-Marie Proth, Nathalie Sauer, Yorai Wardi, Xiaolan Xie. Marking optimization of stochastic timed event graphs using IPA. [Research Report] RR-1856, INRIA. 1993, pp.28. ⟨inria-00074816⟩



Record views


Files downloads