Optimization of Stochastic Discrete Event Dynamic Systems: A Survey of Some Recent Results

Models of discrete event dynamic systems (DEDS) include finite state machines [24], Petri nets [35], finitely recursive processes [26], communicating sequential processes [18], queuing models [41] among others. They become increasingly popular due to important applications in manufacturing systems, communication networks, computer systems. We would consider here a system which evolution or sample path consists of the sequence $$y\left( {x,\omega} \right) = \left\{ {\left( {{t_0},{z_0}} \right),\left( {{t_1},{z_1}} \right),...,\left( {{t_s},{z_s}} \right)} \right\},{t_i} = {t_i}\left( {x,\omega} \right),{z_i} = {z_i}\left( {x,\omega} \right)$$ where z_i(x,ω)) ∈ W is the state of the system during the time interval $${t_i}\left( {x,\omega} \right) \le t < {t_{i + 1}}\left( {x,\omega} \right)$$, x∈X⊆Rn is the set of control parameters and ω∈Ω is an element of some probability space (Ω, ??, ℙ). Particular rules which govern transitions between states at time moments t_i. can be specified in the framework of one of the models mentioned above. For describing the time behavior the generalized semi- Markov processes proved to be useful [47].