In this paper we address the performance evaluation and optimization of a strongly connected event graph with random firing times. We proposed an upper bound and a lower bound for the average cycle time of event graphs knowing the initial marking. We then prove that, under some weak conditions on the firing time distributions, it is possible to reach, on average, a cycle time smaller than any given value C* with a finite marking, assuming that C* is greater than the greatest firing time. Finally, we propose a heuristic algorithm to reach such an average cycle time while minimizing a p-invariant criterion.