Discrete Event Dynamic Programming with Simultaneous Events

This paper deals with an infinite-horizon discrete-event dynamic programming model with discounting, and with Borel state and action spaces. Instead of the usual n-stage contraction assumption (Denardo, E. V. 1967. Contraction mappings in the theory underlying dynamic programming. SIAM Rev.9 165–177.), uniform over all admissible state-action pairs, we propose milder conditions, sufficient for regularity, and allowing any number of simultaneous events. This model permits one to treat properly a number of problems typically associated with continuous-time maintenance models (Haurie, A., L'Ecuyer, P. 1982. A stochastic control approach to group preventive replacement in a multicomponent system. IEEE Trans. Automat. ControlAC-27 387–393; Haurie, A., L'Ecuyer, P. 1986. Approximation and bounds in discrete event dynamic programming. IEEE Trans. Automat. ControlAC-31 227–235; L'Ecuyer, P. 1983. Processus de décision markoviens à étapes discrètes: Application à des problèmes de remplacement d'équipement. Ph.D. thesis (in French), published in Les cahiers du GERAD, report no. G-83-06, Ecole des H. E. C., Montreal; L'Ecuyer, P., Haurie, A. 1987. The repair vs replacement problem: A stochastic control approach. Optim. Control Appl. Meth.8 219–230.). The main results concern the uniform convergence of the dynamic programming (DP) procedure to the optimal cost-to-go function, the existence of an ϵ-optimal policy for any ϵ > 0, and a set of sufficient conditions for the convergence of the DP procedure to an optimal policy.