An ordinal optimization approach to a token partition problem for stochastic timed event graphs

The paper addresses the optimal partition of tokens in stochastic timed event graphs. The transition firing times are random variables with general distribution. The problem consists in choosing an initial marking among a large set of candidate initial markings such that a criterion function (linear or nonlinear) of the initial marking and the average cycle time is minimized. We propose a simulation-based ordinal optimization algorithm for solving this problem. The algorithm simultaneously simulates a set of event graphs, each has a candidate initial marking as its initial marking. The most important feature of this approach is the capability of identifying with very short simulation run the candidate initial markings which can hardly be optimal solutions. Significant computation time saving is realized by stopping the simulation of the related nets at appropriate time.