Dynamic programming for the stochastic matching model on general graphs: The case of the 'N-graph'

Loïc Jean (1, 2) , Pascal Moyal (1, 2)

1 IECL - Institut Élie Cartan de Lorraine
2 PASTA - Processus aléatoires spatio-temporels et leurs applications

In this paper, we address the optimal control of stochastic matching models on general graphs and single arrivals having fixed arrival rates, as introduced in [12]. On the 'N-shaped' graph, by following the dynamic programming approach of [5], we show that a 'Threshold'-type policy on the diagonal edge, with priority to the extreme edges, is optimal for the discounted cost problem and linear holding costs.

Mots clés: Markov Chains; Queueing Systems; Graphs and Networks; Markov decision processes; Matching

Domaines: Mathématiques [math]; Probabilités [math.PR]

Loïc Jean, Pascal Moyal. Dynamic programming for the stochastic matching model on general graphs: The case of the 'N-graph'. 2023. ⟨hal-04434805⟩