# Contrôle optimal de files d'attente.

Maurice Robin

► To cite this version:

Maurice Robin. Contrôle optimal de files d'attente.. [Rapport de recherche] IRIA-RR-117, IRIA. 1975, pp.51. hal-04716095

HAL Id: hal-04716095

https://inria.hal.science/hal-04716095v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

ARCHIVES

Contrôle optimal
de files d'attente.

M. Robin

Rapport de Recherche n° 117

Mai 1975
# CONTRÔLE OPTIMAL DE FILES D'ATTENTE

M. Robin

## RESUME

On considère dans cet article, le problème de la détermination du nombre optimal de "serveurs" dans des types classiques de files d'attente : on formule dans chaque cas un problème de contrôle impulsionnel pour un processus de markov associé à la file d'attente. De façon analogue à A. BENSOUSSAN - J.L. LIONS on obtient des inéquations permettant de caractériser la politique optimale.

Ces conditions d'optimalité ont été résolues numériquement dans des cas particuliers.

Les méthodes utilisées sont applicables à des problèmes où les variables de décisions sont les taux d'arrivées ou de services et à des modèles de files d'attente plus généraux que ceux considérés ici.

## ABSTRACT

We consider here the problem of optimal choice of the number of servers for several types of classical queuing systems. For each case we consider an impulse control problem for a markov process associated to the queuing system. As in A. BENSOUSSAN - J.L. LIONS we obtain inéquations which allow to compute an optimal policy. These inequalities are solved numerically in some particular cases.

The method used can be applied to others problems for which decision variables are the arrival rate or service rate and to queuing model more general than those treated here.
# PLAN

## 0. Introduction

### 1. Problème M/M/S

1.1 Présentation heuristique du problème

1.2 Problème de contrôle

1.3 Conditions d'optimalité

1.4 Caractérisation partielle de la politique optimale

1.5 Applications numériques

### 2. Problème M/G/1

2.1 Hypothèses

2.2 Problème de contrôle
Conditions d'optimalité

2.3 Applications numériques

2.4 Généralisations diverses

Conclusions

Références
## O. Introduction.

Les modèles du type "file d'attente" sont utilisés dans de multiples applications : gestion de stock et de production, affectation d'équipes de maintenance, systèmes informatiques etc... La multiplicité des modèles rend impossible un traitement général des problèmes de contrôle de files d'attente.

Cependant, il semble que pour tous les cas classiques, on puisse systématiquement se ramener au problème du contrôle d'un processus de markov : une fois précisé le processus de markov que l'on contrôle, la programmation dynamique donne (au moins formellement) une condition suffisante d'optimalité facile à obtenir : on peut alors dans certain cas dégager des propriétés qualitatives de la politique optimale.

Dans le cas où le nombre de "clients" dans le système n'est pas markovien, il semble que cette façon de procéder n'ait pas été envisagée (pour les problèmes de contrôle). A notre connaissance la littérature sur ce sujet restreint les contrôles admissibles, les méthodes utilisées ensuite variant avec les cas envisagés (cf. [24], [2], [4], [12] par exemple).

Ici on se limitera à quelques exemples, les conditions d'optimalité obtenues sont des systèmes d'inéquations sur le coût optimal tout à fait analogues aux IQV introduites par BENSOUSSAN et LIONS [1] pour les diffusions et les mêmes méthodes de résolution numérique leur seront appliquées.

Ces inéquations posent cependant un certain nombre de difficultés théoriques pour lesquelles on renvoie à J.L. LIONS [9].

### - Généralités :

Pour décrire complètement le fonctionnement d'un système du type file d'attente il faut préciser les hypothèses faites sur les points suivants :

- nombre d'étape. une étape étant constituée d'une file d'attente et d'un poste de service comportant un ou pluqieurs serveurs.

Il peut y avoir plusieurs étapes en série ou en parallèle (ou les deux).

On ne considerera qu'une seule étape.
- **système ouvert ou fermé.** dans un système fermé un client sortant d'un poste de service peut éventuellement retourner dans une file d'attente située _en amont_.

**On ne considère ici que des sytèmes ouverts.** Mais les méthodes utilisées seraient analogues pour les systèmes fermés.

- **Capacité du système.** limitée ou non... Quand on a une capacité limitée à Nm, et qu'il y a Nm clients dans le système, toute arrivée ultérieure est refusée.

- **Processus d'arrivée.** Il peut y avoir plusieurs processus d'arrivée correspondant à plusieurs catégories de "clients". (on se restreint ici au cas d'une seule file d'attente).

On suppose ici que les arrivées pour un type de client se font _individuellement_, les intervalles entre arrivées étant indépendantes, équidistribuées, de loi donnée.

- **Processus de service.** Pour chaque serveur, les temps de services seront des v.a indépendantes, équidistribuées de loi donnée. _et service individuel..._

- **Discipline dans les files.** dans le cas d'une seule catégorie de clients la discipline sera _première arrivée, première servie_.

- **Variables de décision.** On peut avoir à contrôler :

- les taux de services (cf. SABETI [18])

- les taux d'arrivée (cf. LOW [17])

- le nombre de serveurs (cf. [2], [13])

- la catégorie de clients que l'on sert dans le cas de deux files d'attente, avec 1 serveur par exemple. (ici on traitera seulement le problème du nombre de serveurs).

- **Coûts.** On supposera ici que l'on a :

- un coût par unité de temps tenant compte du coût d'attente des clients et des coûts de fonctionnement c'est à dire fonction du nombre de clients et du nombre de serveurs, éventuellement du temps de service du client présent dans le poste.
- un coût à chaque instant de décision (ex.: coût instantané de changement du nombre de serveurs). Ceci sera précisé par la suite.

Pour pouvoir écrire plus précisément les problèmes de contrôle, il faut construire le processus stochastique correspondant à un contrôle ce qui ne peut être fait que dans chaque cas particulier.
# 1. Contrôle du système M/M/S.

On se propose ici de traiter le problème du choix du nombre de serveurs quand les arrivées forment un processus de poisson et quand les durées de services sont des variables aléatoires de loi exponentielle.

Ce problème se pose par exemple dans un atelier chargé de réparer des machines : les "serveurs" sont ici des postes de maintenance, les "clients" sont les machines. La mise en place d'un nouveau poste peut demander des moyens importants et couteux (coût fixe de mise en place); d'autre part, l'immobilisation des machines en attente d'être réparées se traduit par un manque à gagner qui sera représenté par le "coût d'attente". Enfin la maintenance est en générale couteuse et il y aura donc un coût de fonctionnement dépendant du nombre de postes.

## 1.1 Présentation heuristique du problème.

Soit donc une file d'attente pouvant comporter un nombre de serveurs $j \in \{0,1,\dots,S\} = U$

les arrivées forment un processus de Poisson de paramètre $\lambda$.

Les durées de services ont une loi exponentielle de paramètre $\mu$ (pour chaque serveur).

Quand le nombre de serveurs est fixé à $j$, il est bien connu (cf. [26]) que le nombre $N_t^j$ de clients dans le système à l'instant $t$ est un processus de markov.

On supposera que la capacité du système est limitée à $N_m$ clients; quand $N_t = N_m$, toute arrivée supplémentaire est refusée.

On peut obtenir les équations suivantes pour les probabilités de transition :
(équations de Chapman-Kolmogorov)

$$P^j(n;m,t) = \begin{array}{l} \text{probabilité aue } N_t = m \text{ sachant que } N_0 = n \\ \text{et que le nombre de serveurs est fixé à } j \end{array}$$
$$
\frac{dP^j}{dt}(o;m,t) = \lambda[P^j(1;m,t) - P^j(o;m,t)]
$$

$$
\begin{align*}
\frac{dP^j}{dt}(n;m,t) ={}& \lambda P^j(n+1;m,t) + (j\Delta n)\mu P^j(n-1;m,t) \\
& - [\lambda + (j\Delta n)\mu] \cdot P^j(n;m,t)
\end{align*}
$$

$o < n < N_m$

$$
\frac{dP^j}{dt}(N_m;m,t) = (j\Delta N_m)\mu[P^j(N_m-1;m,t) - P^j(N_m;m,t)]
$$

On notera $A_j$ la matrice suivante

<figure><img src="image_2.png" /></figure>

[C'est le générateur infinitésimal du semi groupe correspondant à P^j(n;m,t)]

On se donne maintenant la structure de coûts suivante :

- coût de fonctionnement et d'attente par unité de temps f(j;n,t) quand il y a
j serveurs et n clients à t

- coût de décision : C(i,j) quand on fait passer le nombre de serveurs de i à j.
Nous allons appliquer formellement la programmation dynamique pour
obtenir une caractérisation du coût optimal.

On remarquera que dans l'état actuel du problem nous sommes incapables d'écrire
explicitement le critère à optimiser.

Notons $u(j,n,t)$ le coût optimal sur $[t,T]$ quand à l'instant $t$, il y a n clients dans le système et j serveurs.

Soit $\tau$ le premier instant de décision $\ge t$

(a) si $\tau > t$ on peut prendre $\delta > 0$ et $t < \tau + \delta < \tau$ alors on a

$$
u(j,n,t) = E \left\{ \int_{t}^{\tau+\delta} f(j,N_s,s) ds + u(j,N_{\tau+\delta},\tau+\delta) \right\}
$$

(b) si $\tau = t$ et si l'on choisit un nombre de serveurs $j'$

$$
u(j,n,t) = C(j,j') + u(j',n,t)
$$

et il est clair que l'on doit avoir (pour que u soit effectivement optimal)

$$
u(j,n,t) = \min_{j' \in U} \{C(j,j') + u(j',n,t)\}
$$

u devant être le coût optimal on a également

$$
u(j,n,t) \le \min \left\{
\begin{array}{l}
E \int_t^{t+\delta} f + u(j,N_{t+\delta},t+\delta) \, ds \\
\\
\min_{j' \in U} C(j,j') + u(j',n,t)
\end{array}
\right\}
$$

ce qui s'écrit encore

$$
(1.2) \quad \left\{
\begin{array}{l}
u(j,n,t) \le E \int_t^{t+\delta} f ds + u(j,N_{t+\delta},t+\delta) \\
\\
u(j,n,t) \le \min_{j'} C(j,j') + u(j',n,t) \\
\\
\text{produit} = 0
\end{array}
\right.
$$
en explicitant les différentes valeurs possibles de $N_{t+\delta}$ et leurs probabilités on obtient (pour $\delta$ "petit")

$$ 
\begin{align*} 
E u(j,N_{t+\delta},t+\delta) &= \delta \{ \lambda u(j,n+1,t+\delta) + (j\Lambda n)\mu u(j,n-1,t+\delta) \\ 
&\quad - (\lambda + (j\Lambda n)\mu) u(j,n,t+\delta) + o(\delta) \} \\ 
&\quad + u(j,n,t+\delta) 
\end{align*} 
$$

pour $1 \le n \le N - 1$

On explicite aisément les cas $n = 0$ et $n = N$ et on trouve

$$ E u(j,N_{t+\delta},t+\delta) = \delta(A_j u)(j,n,t+\delta) + u(j,n,t+\delta) + o(\delta) $$

en passant à la limite $\delta \to 0$ (1.2) devient

$$ (1.3) \quad \left\{ \begin{array}{l} \displaystyle \frac{\partial u}{\partial t} (j,n,t) + A_j u + f \ge 0 \\[1em] \displaystyle u(j,n,t) \le \min C(j,j') + u(j',n,t) \\[1em] \displaystyle \frac{\partial u}{\partial t} (j,n,t) + A_j u + f (u - \min C(j,j') + u(j',n,t)) = 0 \\[1em] j = 0,1,\dots,S \end{array} \right. $$

Intuitivement, les inégalités (1.3) signifient que l'on a intérêt à choisir $j'$ (et donc à changer le nombre de serveurs) quand le nombre de clients devient tel que l'on a l'égalité

$$ u(j,n,t) = \min_{j'} C(j,j') + u(j',n,t) $$
A priori, le contrôle optimal sera donc caractérisé par une fonction $z(j,n,t)$ donnant le nombre de serveurs à choisir quand on est dans la situation $j$ serveurs, $n$ clients à l'instant $t$.

On verra qu'en fait la politique correspondant aux inéquations peut être caractérisée de façon plus simple (cf. § 1.5)

Les paragraphes suivants ont pour objet de formuler de façon précise le problème que l'on a esquissé ici.

## 1.2 Problème de contrôle

### Hypothèses :

On supposera donné dans ce paragraphe

- l'ensemble $U = \{0,1...,S\}$ ($S$ fini) des valeurs des décisions.

- une fonction $f(i,n,t)$ bornée, continue en $t$ sur $[0,T]$ ($T$ donné, fini)

- une constante $k > 0$ qui sera le coût fixe de décision pour simplifier; mais toutes les démonstrations seront valables avec $c(i,j)$ non constant.

On note :

$\Omega^1$ l'ensemble des fonctions en escalier sur $[0, \infty[$ à valeurs dans $N^+$, continues à droite.

$x_t(\omega) = \omega(t)$

$\mathfrak{F}_t^1 = \sigma \{ x_s, s \le t \}$ et $\mathfrak{F}_\infty^1 = \mathfrak{F}$

$\beta_t^1$ les translations $(\beta_t^1 \omega)(s) = \omega(t+s)$ et on suppose donné les processus de markov

($\Omega^1, \mathfrak{F}_t^1, \mathfrak{F}^1, \beta_t^1, x_t^j, \bar{P}_x^j$) construits à partir des fonctions de transition $\bar{P}^j$ du § précédent. Les processus $x^j$ sont fortement markoviens et continus à droite; nous aurons besoin des processus $(x_t^j, t)$ pour cela on notera
$$
\Omega = \Omega^1 \times \mathbb{R}^+ , \quad \mathfrak{F}_t = \mathfrak{F}_t^1 \otimes \mathbb{B}_{\mathbb{R}^+} \quad \text{(tribu borelienne de } \mathbb{R}^+)
$$

$$
\mathfrak{F} = \mathfrak{F}_{\infty}, \beta_t(\omega,s) = (\beta_t^1 \omega, s+t)
$$

$$
\bar{P}_{xs}^{j} = \bar{P}_{x}^{j} \otimes \varepsilon_{s} \quad (\varepsilon_{s} \text{ masse 1 en } S)
$$

enfin pour θ temps d'arrêt par rapport à F_t,
on note

$$
\mathfrak{F}_{\theta} = \sigma \{ A \cap \{ \theta \le t \} , A \in \mathfrak{F} \}
$$

$$
\mathfrak{F}^{\theta} = \beta_{\theta}^{-1} \mathfrak{F} = \sigma \{ x_{\theta+s} \mid s \ge 0 \}
$$

Contrôles admissibles

Un contrôle admissible v sera défini par une suite de $\mathcal{F}_t$ temps d'arrêt $\theta^i$, et une suite de $v.a. v^i$ $\mathcal{F}_{\theta^i}$ mesurable, à valeur dans

$$
U = \{0,1...,S\} \quad \text{avec}
$$

$$
(1.5) \qquad 0 \le \theta^1 < \theta^2 < \dots < \theta^n \le T
$$

On posera

$$
(1.6) \qquad v_t = v^i, \quad t \in [\theta^i, \theta^{i+1}[
$$

et l'on note $u_{\text{ad}}(0,T)$ l'ensemble des contrôles admissibles.

(1.6) ne définit $v_t$ que sur $[0, \lim_{n\to\infty} \theta^n] = \theta$ [si $\theta < T$ on prend une valeur quelconque de $U$ pour définir $v_t$ sur $[0,T]$.

Processus correspondant au contrôle v

On définit les mesures suivantes

$(v^0)$ donné)
$$
(1.7) \qquad P_{x_0}^{0,\nu} = \bar{P}_{x_0}^{\nu 0}
$$

$$
(1.8) \quad \left\{
\begin{array}{@{}l@{}}
  P_{x_0}^{1,v} (A) = P_{x_0}^{0,v} (A) \quad A \in \mathfrak{F}_{\theta^1} \\[\medskipamount]
  P_{x_0}^{1,v} (\beta_{\theta^1}^{-1} A | \mathfrak{F}_{\theta^1}) = \bar{P}_x^{v^n} \quad A \in \mathfrak{F}_{\theta^n} \quad \theta^n(A) \quad \text{A s.t.} \\[1em]
  (P_{x_0}^{0,v} \text{ p.s.})
\end{array}
\right.
$$

$$
(1.9) \quad \left\{
\begin{array}{@{}l@{}}
  P_{x_0}^{n,v} (A) = P_{x_0}^{n-1,v} (A) \quad \text{ pour } A \in \mathfrak{F}_{\theta^n} \\[\medskipamount]
  P_{x_0}^{n,v} (\beta_{\theta^n}^{-1} A | \mathfrak{F}_{\theta^n}) = \bar{P}_x^{v^n} \quad \text{ pour } A \in \mathfrak{F}_{\theta^n} \theta^n(A)
\end{array}
\right.
$$

l'existence et l'unicité d'une mesure P<sup>1,v</sup><sub>xo</sub> vérifiant (1.8) est une conséquence
du lemme 3.6 de STROOK-VARADHAN [15] de même pour P<sup>n,v</sup><sub>xo</sub> pour tout n fini.

On définit alors le critère J(v) par

$$
(1.10) \quad J(v) = \lim_{N \to \infty} E^{N-1, v} \left[ \int_0^{\theta^N} f(v_s, x_s, s) ds + k \sum_{i=1}^{N-1} \mathbf{1}_{(\theta^i < T)} \right]^*
$$

si cette limite existe
+ ∞ sinon

Remarque 1.1 :

L'espérance mathématique dans (1.10) ou bien à une limite, ou bien
tend vers $+\infty$, suivant que

$$
(1.11) \quad \lim_{N \to \infty} E^{N-1, \nu} \left( \sum_{i=1}^{N-1} \mathbf{1}_{(\theta^i < T)} \right) < +\infty
$$

ou non.

<footnote>* On utilisera toujours $E^{n,v}$ pour noter l'espérance par rapport à $P_{x_0}^{n,v}$</footnote>
En effet

$$
E^{N-1, v} \int_{0}^{\theta^{N}} f(v_s, x_s, s) ds
$$

est fini de toutes façons car $\theta^N \le T$ et f est bornée. D'autre part cette
quantité est croissante en N

$$
\begin{align*}
(1.12) \quad E^{N,v} \int_0^{\theta^{N+1}} &= E^{N,v} \left( \int_0^{\theta^N} + \int_{\theta^N}^{\theta^{N+1}} \right) \\
&= E^{N-1,v} \int_0^{\theta^N} + E^{N,v} \int_{\theta^N}^{\theta^{N+1}} \\
&\ge E^{N-1,v} \int_0^{\theta^N}
\end{align*}
$$

donc

$$
E^{N-1,v} \left( \int_{0}^{\theta^{N}} f \, ds \right) \text{ a une limite}
$$

Remarque 1.2 :

$$
(1.13) \quad \lim_{\substack{E^{N-1},v \\ \Rightarrow}} \left( \sum_{i=1}^{N-1} 1_{(\theta^i < T)} \right) < +\infty \\
\qquad \Rightarrow \quad P_{x_0}^{N-1,v} \left( \theta^{N-1} < T \right) \to 0
$$

en effet si on r'a pas $P_{x_0}^{N-1,v}(\theta^{N-1} < T) \to 0$

$$
E^{N-1,v} \left( \sum_{i}^{N-1} 1_{(\theta^i < T)} \right) = \sum_{i=1}^{N-1} P_{x_0}^{i,v} (\theta^i < T)
$$

ne peut pas être une série convergente.

Remarque 1.3 :

L'étude directe des inéquations (1.16) peut se faire avec les méthodes de BENSOUSSAN-LIONS (cf. [1] [9]).
1.3 Optimalité des inéquations

Hypothèses :

(1.14) On donne $f(i,n,t) \quad t \in [0,T], \ i \in \{0,1...,S\}, \ n \in \{0,...,N_m\}$
continue en t, positive, bornée.

(1.15) On suppose qu'il existe $u(i,n,t)$ continuellement différentiable en t, bornée telle que

$$
\[
\begin{array}{l}
\displaystyle \frac{\partial u}{\partial t} (i,n,t) + A_i u + f \ge 0 \\
u(i,n,t) \le k + \inf_{j \ne i} u(j,n,t) & \text{produit nul.}
\end{array}
\]
$$

$$
\begin{gather*}
u(i,n,T) = 0 \\
i \in \{0,1,\dots,S\}
\end{gather*}
$$

$$
(1.17) \quad \left\{
\begin{array}{ll}
\text{On note } z(i,n,t) \text{ l'indice réalisant} \\
\displaystyle \inf_{j \neq i} u(j,n,t) & \\
\bar{c}_i \text{ le complémentaire.} &
\end{array}
\right.
$$

Définition du contrôle ŷ associé aux inéquations

On note

$$
(1.18) \quad C_i = \{(n,t); u(i,n,t) < k + \inf_{j \neq i} u(j,n,t)\}.
$$
$\bar{c}_i$ le complémentaire.
$$
On suppose qu'en $t = 0$ on a $v_o$ serveurs actifs, $x$ clients dans le système.

On note

$$ (1.19) \qquad \begin{aligned} \hat{\theta}^1 &= \inf (s \ge 0 (x_s, s) \in \bar{c}_{v_o}) \\ \hat{v}^1 &= z(v_o, x_{\hat{\theta}^1}, \hat{\theta}^1) \end{aligned} $$

Puis

$$ \begin{aligned} \hat{\theta}^2 &= \inf (s > \hat{\theta}^1 (x_s, s) \in \bar{c}_{\hat{v}^1}) \\ \hat{v}^2 &= z(\hat{v}^1, x_{\hat{\theta}^2}, \hat{\theta}^2) \end{aligned} $$

etc...

On peut vérifier que $\hat{\theta}^i$ est un $\mathfrak{z}_t$ temps d'arrêt et donc que $\hat{v}^i$ est mesurable (d'après la définition de $\hat{v}^i$)

### Remarque 1.4

Soit $v$ un contrôle admissible $\{\theta^n, v^n\}$ pour $s \ge 0$ on pose

$$ (1.20) \quad Z_s \left\{ \begin{aligned} \tilde{v}_s &= v^i \\ \tilde{x}_s &= x_{\theta^{n+s}} \\ \tilde{y}_s &= \theta^n + s \end{aligned} \right. $$

$Z_s$ est un processus adapté à $\tilde{\mathfrak{z}}_s = \mathfrak{z}_{\theta^{n+s}}$ de plus pour la mesure $P_{xo}^{n,v}$ ce processus est markovien (fort) par rapport à $\tilde{\mathfrak{z}}_s$ avec une fonction de transition
$$
(1.21) \quad P_{v,x,y}^{(s,\Gamma_1 \times \Gamma_2 \times \Gamma_3)} = P_{\Gamma_1}^{(v)} \cdot P_{\Gamma_3}^{(y+s)} P^{v}(x,s,\Gamma_2)
$$
et une loi "initiale"

$$
(1.22) \quad \tilde{\mu}(\Gamma_1 \times \Gamma_2 \times \Gamma_3) = P_x^{n,v} (v^n \in \Gamma_1, x \in \Theta^n \in \Gamma_2, \Theta^n \in \Gamma_3) \\
\text{c'est à dire la loi de } Z_o \text{ pour } P_x^{n,v}
$$

On peut alors appliquer la formule de Dybkin (cf. [7].) pour obtenir,
pour tout temps d'arrêt borné $\tau$ par rapport à $\tilde{\mathfrak{F}}_S$

$$
(1.23) \quad E^{n,v} u(Z_t) - E^{n,v} u(Z_o) = E^{n,v} \int_o^t \tilde{A} u(Z_s) ds
$$

si u est bornée, $C^1$ en temps avec $\tilde{A}$ générateur infinitésimal du
semi groupe correspondant à (1.21)

$$
\text{i.e.} \qquad \tilde{A} = \frac{\partial}{\partial t} + A_v
$$

d'où

$$
\begin{align*}
(1.24) \quad E^{n,v} u\left(v^n, x_n, \theta^{n+\tau}\right) - E^{n,v} u\left(v^n, x_n, \theta^n\right) & \\
&= E^{n,v} \int_{\theta^n}^{\theta^{n+\tau}} \left(\frac{\partial u}{\partial t} + A_v^n u\right) (v^n, x_s, s) ds
\end{align*}
$$

(noter que $\tau \tilde{\mathfrak{F}}_t - t, a \Rightarrow \theta^n + \tau \mathfrak{F}_t$-temps d'arrêt cf. MEYER [10])

Théorème 1.1

Sous les hypothèses (1.14) (1.15) (1.16) on a

$$
(1.25) \quad u(v_o, x, o) = J(\hat{v}) \le J(v). \quad \forall v \in u_{ad}[o, T].
$$
## Démonstration

Soit v un contrôle quelconque $\in \mathcal{U}_{\text{ad}}[0,T]$. $n > N$

soit

$$ (1.26) \quad X = E^{N,V}[u(v_{n+1},x_{\theta^{n+1}},\theta^{n+1}) - u(v_n,x_{\theta^n},\theta^n)] $$

sur $\mathcal{F}_{\theta^{n+1}}$, $P_{x_0}^{N,V}$ est identique à $P_{x_0}^{n,V}$

$$ X_1 = E^{n,V}[u(v_{n+1},x_{\theta^{n+1}},\theta^{n+1}) - u(v_n,x_{\theta^{n+1}},\theta^{n+1})] $$

$$ X_2 = E^{n,V}[u(v_n,x_{\theta^{n+1}},\theta^{n+1}) - u(v_n,x_{\theta^n},\theta^n)] $$

$$ (1.27) \quad X = X_1 + X_2 \quad \text{or si } \theta^{n+1} < T $$

$$ u(v_n,x_{\theta^{n+1}},\theta^{n+1}) \le k + u(v_{n+1},x_{\theta^{n+1}},\theta^{n+1}) $$

$$ (1.28) \quad \Rightarrow \quad X_1 \ge -k \quad \text{si} \quad \theta^{n+1} < T $$

d'autre part

$$ (1.29) \quad \begin{aligned} E^{n,V}u(v_n,x_{\theta^{n+1}},\theta^{n+1}) = & E^{V,n}u(v_n,x_{\theta^n},\theta^n) \\ & + E^{V,n} \int_{\theta^n}^{\theta^{n+1}} \left( \frac{\partial u}{\partial t} + A(v_n)u \right) (v_n,x_s,s) \mathrm{d}s \end{aligned} \\ \text{(cf. (1.24))} $$

$$ \text{or} \quad \frac{\partial u}{\partial t} + A(v_n)u \ge -f(v_n,x_s,s) $$

$$ \Rightarrow \quad X_2 \ge -E^{n,V} \int_{\theta^n}^{\theta^{n+1}} f(v_n,x_s,s) \mathrm{d}s $$
d'où

$$
(1.30) \quad X \ge \mathbb{E}^{n,v} \left[ \int_{\theta^n}^{\theta^{n+1}} f(v_n, x_s, s) ds + k \mathbb{1}_{(\theta^{n+1} < T)} \right]
$$

On somme (1.25) pour n = 0 à N - 2 et on ajoute

$$
\begin{align*}
& E^{N-1,v}[u(v_{n-1},x_{\theta^N},\theta^N) - u(v_{n-1},x_{\theta^{n-1}},\theta^{n-1})] \\
& \geq - E^{N-1,v} \int_{\theta^{n-1}}^{\theta^N} f(v_{n-1},x_s,s)ds
\end{align*}
$$

d'où

$$
(1.31) \qquad u(v_o,x,o) \le E^{N-1,v} \left[ \int_0^{\theta^N} f(v_s,x_s,s)ds + k \sum_{i=1}^{N-1} \mathbb{1}_{(\theta^i < T)} \right] \\
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad + E^{N-1,v} u(v_{N-1},x_{\theta^N},\theta^N)
$$

en supposant $J(v) < +\infty$, on a

$$
E^{N-1, v} u(v_{N-1}, x_{\theta^N}, \theta^N) \rightarrow 0
$$

en effet,

$$
J(v) < +\infty \Rightarrow P_{XO}^{N-1, v} (\theta^{N-1} < T) \\
(\text{cf. Remarque 1.2})
$$

d'où

$$
\begin{align*}
E^{N-1,v} u(v_{n-1}, x_{\theta^N}, \theta^N) &= E^{N-1,v} \mathbb{1}_{(\theta^N < T)} u(\dots) \\
&\quad + E^{N-1,v} \mathbb{1}_{(\theta^N = T)} u(\dots)
\end{align*}
$$
or $u(...,T) = 0$

$$ \Rightarrow \mathbb{E}^{N-1, \hat{v}} u(v_{N-1}, x_{\hat{\theta}^N}, \hat{\theta}^N) = \mathbb{E}^{N-1, \hat{v}} \mathbb{P}_{(\hat{\theta}^N < T)} u(v_{N-1}, x_{\hat{\theta}^N}, \hat{\theta}^N) $$

$$ \leq |u| \cdot \mathbb{P}^{N-1, \hat{v}}(\hat{\theta}^N < T) $$

$$ \leq |u| \cdot \mathbb{P}^{N-1, \hat{v}}(\hat{\theta}^{N-1} < T) $$

$$ \rightarrow 0 $$

$$ (|u| = \sup_{i,n,t} |u(i,n,t)|). $$

$$ (1.32) \quad \Rightarrow \quad u(v_o, x, 0) \le J(v) \quad \forall v \in u_{ad} $$

Soit maintenant $\hat{v}$ le contrôle défini de proche en proche par (1.8)
(1.9).

Considérons :

$$ X_1 = \mathbb{E}^n, \hat{v} u(\hat{v}_n, x_{\hat{\theta}^{n+1}}, \hat{\theta}^{n+1}) - \mathbb{E}^n, \hat{v} u(\hat{v}_n, x_{\hat{\theta}^n}, \hat{\theta}^n) $$

$$ = \mathbb{E}^n, \hat{v} \int_{\hat{\theta}^n}^{\hat{\theta}^{n+1}} \left( \frac{\partial u}{\partial t} + A_{\hat{v}_n} u(\hat{v}_n, x_s, s) \right) ds $$

(cf. (1.24).)

sur $]\hat{\theta}^n, \hat{\theta}^{n+1}[$

$$ \frac{\partial u}{\partial t} + A_{\hat{v}_n} u + f(\hat{v}_n, x_s, s) = 0 $$

d'où

$$ (1.34) \qquad X_1 = - \mathbb{E}^n, \hat{v} \int_{\hat{\theta}^n}^{\hat{\theta}^{n+1}} f(\hat{v}_n, x_s, s) ds $$
d'autre part

$$
\begin{align*}
(1.35) \qquad X_2 &= E^{n, \hat{v}} [u(\hat{v}_{n+1}, x_{\hat{\theta}n+1}, \hat{\theta}^{n+1}) - u(\hat{v}_n, x_{\hat{\theta}n+1}, \hat{\theta}^{n+1})] \\
&= - E^{n, \hat{v}} k.n. (\hat{\theta}^{n+1} < T)
\end{align*}
$$

d'où

$$
\begin{align*}
(1.36) \qquad E^{n, \hat{v}} [u(\hat{v}^{n+1}, x_{\hat{\theta}n+1}, \hat{\theta}^{n+1}) - u(\hat{v}^n, x_{\hat{\theta}n}, \hat{\theta}^n)]
\end{align*}
\begin{equation*}
= - E^{n, \hat{v}} \left[ \int_{\hat{\theta}^n}^{\hat{\theta}^{n+1}} f(\hat{v}^n, x_s, s) ds + k.n. (\hat{\theta}^{n+1} < T) \right]
\end{equation*}
$$

en procédant comme pour (1.23) on a

$$
\begin{align*}
(1.37) \quad u(v_o, x, o) &= E^{N-1, \hat{v}} \left[ \int_0^{\hat{\theta}^N} f(\hat{v}_s, x_s, s) ds + k \sum_{i}^{N-1} 1(\hat{\theta}^i < T) \right] \\
&\quad + E^{N-1, \hat{v}} u(\hat{v}_{N-1}, x_{\hat{\theta}N}, \hat{\theta}^N) \\
\text{u borné} \quad \Rightarrow \quad & E^{N-1, \hat{v}} u(\hat{v}_{N-1}, x_{\hat{\theta}N}, \hat{\theta}^N) \to 0
\end{align*}
$$

d'où

$$
(1.38) \quad u(v_o, x, o) = J(\hat{v})
$$

<figure><img src="image_3.png" /></figure>
Remarque 1.5

On ferait la même démonstration quand le coût de la décision est $c |v^i - v^{i+1}|$ si $v^i \neq v^{i+1}$ les contraintes (1.16) s'écrivent évidemment dans ce cas

$$ (1.39) \qquad u(i,n,t) \le \inf_{j \neq i} (c|i-j| + u_{(j,n,t)}) $$

Remarque 1.6

Tous les résultats précédents s'étudient sans difficulté au problème du contrôle d'un processus de markov de saut quelconque par un contrôle "constant par morceau"(*)

On peut également les étendre aux cas du contrôle impulsionnel d'un processus de markov de saut, c'est à dire le cas ou en chaque instant de décision $\theta^i$ on fait subir un saut à l'état (c'est le cas des problèmes de remplacement de matériel).

<footnote>(*) Zabcyk [19] a étudié ce problème et a obtenu une caractérisation du coût optimal en terme de fonctions excessives; mais cette caractérisation semble difficilement utilisable pratiquement.</footnote>
## 1.4 Caractérisation partielle de la politique optimale

**Lemme 1.1** : Il existe deux fonctions $z_1(n,t)$, $z_2(n,t)$ (à valeur dans U) telles que

$$z_1(n,t) \leq z_2(n,t)$$

et

$$ (1.40) \quad \left| \begin{array}{l} z(i,n,t) = z_1(n,t) \text{ si } i < z_1(n,t) \\ z(i,n,t) = z_2(n,t) \text{ si } i > z_2(n,t) \end{array} \right. $$

$(z(i,n,t))$ définit par $(1.)$ est le nombre de serveurs à mettre en place à $t$, quand $v_{t-} = i, x_t = n$).

**Démonstration :**

$$ (1.41) \quad z_1(n,t) = \max [i, u(i',n,t) \geq c(i-i') + u(i,n,t) \quad \forall i'] $$

$$ (1.42) \quad z_2(n,t) = \min [i, u(i',n,t) \geq -c(i-i') + u(i,n,t) \quad \forall i'] $$

il sera toujours sous-entendu que $i,i'$ varient dans $\{0,1,...,S\}$

Pour montrer que $z_1 \leq z_2$ il suffit de prendre

$$ i' = z_2(n,t) \text{ dans (1.41)} $$

$$ i' = z_1(n,t) \text{ dans (1.42)} $$

$$ u(z_2(n,t),n,t) \geq c(z_1(n,t) - z_2(n,t)) + u(z_1(n,t),n,t) $$

$$ u(z_1(n,t),n,t) \geq -c(z_2(n,t) - \bar{z}_1(n,t)) + u(z_2(n,t),n,t) $$

$$ \Rightarrow c(z_1(n,t)-z_2(n,t)) \leq u(z_2(n,t),n,t)-u(z_1(n,t),n,t) \leq -c(z_1(n,t)-z_2(n,t)) $$
si on avait $z_1(n,t) > z_2(n,t)$, on aurait

$$0 < u(z_2,n,t) - u(z_1,n,t) < 0$$

$$\text{donc} \qquad z_1(n,t) \le z_2(n,t)$$

Soit maintenant $i' < z_1(n,t)$; d'après (1.39) on a

$$u(i',n,t) \le c|z_1(n,t)-i'| + u(z_1(n,t),n,t)$$

$$\text{i.e} \qquad u(i',n,t) \le c(z_1(n,t)-i') + u(z_1(n,t),n,t)$$

mais par définition de $z_1(n,t)$

$$u(i',n,t) \ge c(z_1(n,t)-i') + u(z_1(n,t),n,t)$$

$$\Rightarrow u(i',n,t) = c(z_1(n,t)-i') + u(z_1(n,t),n,t)$$

$$\Rightarrow z(i',n,t) = z_1(n,t)$$

$$\text{ceci } \forall i' < z_1(n,t)$$

On peut maintenant montrer que $z(i,n,t)$ ne peut pas être $> z_1(n,t)$

alors

$$c(j-i') + u(j,n,t) = c(z_1(n,t)-i') + u(z_1,n,t)$$

$$\text{i.e} \qquad c_j + u(j,n,t) = c z_1(n,t) + u(z_1(n,t),n,t)$$

$$(1.43) \quad \Rightarrow \quad c_j + u(j,n,t) \le c_j' + u(j',n,t) \quad \forall j'$$

(ceci par définition de $z_1$)

mais ceci contredit le fait que $z_1(n,t)$ est l'indice maximum vérifiant (1.43).
Les calculs sont analogues pour $z_2(n,t)$

On pourrait montrer que pour $z_1 < i < z_2$, on ne peut pas avoir

$$z(i,n,t) > z_2(n,t) \quad n^i \quad z(i,n,t) < z_1(n,t)$$

mais ceci ne suffit pas il faudrait montrer que pour tout $i$ $z_1(n,t) < i < z_2(n,t)$ on a

$$u(i,n,t) < \inf_{j \neq i} c |i-j| + u(j,n,t)$$

ce que je ne sais pas faire...

### Remarque 1.7

Un résultat analogue a été montré par SOBEL [13] dans un problème stationnaire avec le critère

$$\lim_{T \to \infty} \frac{1}{T} \int_0^T f(x_s, v_s) ds.$$

## 1.5 Problème stationnaire

On considère maintenant le problème précédent pour $t \in [0, \infty[$ avec l'hypothèse (remplaçant (1.14))

$$(1.44) \qquad f(j,n,t) = f_1(j,n) e^{-\alpha t} \quad f_1 \text{ bornée } \ge 0$$

où $\alpha$ est "le taux d'actualisation".

On peut refaire la construction du § 1.2 sans difficultés, le critère étant maintenant
$$
(1.45) \quad J(v) = \lim_{N \to \infty} E^{N,v} \left\{ \int_0^{\theta^{N+1}} e^{-\alpha t} f_1(v_t, x_t) dt + k \sum_{i=1}^N e^{-\alpha \theta^i} \right\}
$$

Comme au § 1.1, on peut obtenir formellement les inéquations suivantes :

$$
(1.46) \quad \left\{
\begin{array}{l}
A_j u - \alpha u + f_1 \ge 0 \\
\\
u(j,n) \le k + \min_{j \ne j} u(j',n) \\
\\
(A_j u - \alpha u + f_1) (u - k - \min_j u(j',n)) = 0
\end{array}
\right.
$$

On a alors le théorème suivant

Théorème 1.2 :

Supposons qu'il existe une fonction u(j,n) bornée vérifiant (1.46),
avec $f_1$ vérifiant (1.44)

Alors si $(v_o,x)$ est l'état initial,
on a

$$
u(v_o, x) = J(\hat{v}) \leq J(v) \quad \forall v
$$

où le contrôle $\hat{v}$ est défini comme dans (1.8) (1.9).

La démonstration est entièrement analogue à celle du Théorème 1.1.

Remarque 1.8

La caractérisation de la politique obtenue au § 1.4 est encore valable.
## 1.6 Applications

### 1.6.1 Méthode de résolution numérique

Considérons le cas stationnaire

$$ (1.47) \quad \left\{ \begin{array}{l} (A_i u)(i,n) - \alpha u(i,n) + f(i,n) \ge 0 \\[1em] u(i,n) \le \operatorname{Inf}_{j \ne i} (c|i-j| + u(j,n)) \\[1em] \text{produit nul} \end{array} \right. $$

(on a introduit un taux d'actualisation $\alpha$).

La résolution s'effectue pour les IQV correspondant au contrôle des diffusions cf. BENSOUSSAN-LIONS [1], GOURSAT-MAURIN [20], LEGUAY [21].

Ici, en posant $u_i^{(n)} = u(i,n)$, on part de $u_i^0$ vérifiant

$$ (1.48) \quad A_i u_i^0 - \alpha u_i^0 + f_i = 0 $$

puis on utilise un algorithme du type "relaxation et projection" cf. [22] pour résoudre

$$ (1.49) \quad \begin{aligned} & A_i u_i^{k+1} - \alpha u_i^{k+1} + f_i \ge 0 \\ & u_i^{k+1}(n) \le \operatorname{Inf}_{j \ne i} (c|i-j| + u_j^k(n)) \end{aligned} $$

[On peut montrer, comme dans le cas des diffusions $u_i^k \ge 0$, $u_i^{k+1} \ge u_i^k \ge \dots \ge 0$ et que la limite converge vers une solution de (1.47).]

### 1.6.2 Résultats numériques

On a pris $S = 5$, $N_m = 50$, $\lambda = 10$, $\mu = 5$ et on a résolu le problème évolutif sur $[0,2]$ avec $c(i,j) = 2|i-j|$
$$f(i,n) = 0.5 \cdot n + 0.4i$$

$$\Delta t = 0.02, \alpha = 0.1$$

la figure 1 donne les fonctions $z_1(n)$, $z_2(n)$ du cas stationnaire.

les figures 2, 3 donnent $z_1(n,t)$, $z_2(n,t)$ pour deux valeurs de $t$; dans le cas évolutif la politique devient stationnaire en $t = 0.8$ (résolution backward).

Les temps de calculs sur IBM 370/168 sont de l'ordre de 1'30" pour le problème d'évolution.

La figure 4 donne $z_1(n)$, $z_2(n)$ en stationnaire pour un cas où $\lambda = 5$ (temps moyen entre les arrivées 0.2).
<figure><img src="image_4.png" /><figcaption>nb de serveurs</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>M/M/S Fig. 2 et 3</figcaption></figure>

Nb de serveurs (i) (t = 1.98) Fig. 2

<figure><img src="image_6.png" /></figure>

Nb de serveurs (i) (t = 1.58) Fig. 3
<figure><img src="image_7.png" /><figcaption>Politique stationnaire</figcaption></figure>
## 2. Problème M/G/1.

### 2.1 Hypothèses

- Processus d'arrivée : processus de Poisson de paramètre $\lambda$

- Temps de service : loi quelconque, dont on note $G(t)$ la fonction de répartition.

- 1 seul serveur

- Les décisions consistent simplement à ouvrir ou fermer le poste de service. a priori on autorise la fermeture du poste de service pendant le service d'un "client".

Dans ce cas le client retourne dans la file. Il est alors logique de supposer que le coût de la fermeture dépend du temps de service déjà écoulé qui est ainsi perdu.

En notant $y$ ce temps écoulé, on notera $c(y)$ le coût de fermeture.

- On supposera que quand le poste est ouvert, on a un coût par unité de temps fonction du nombre de clients dans le système et du temps de service du client présent dans le poste

$$f_1(n,y,t)$$

- Quand le poste est fermé on a seulement

$$f_o(n,t)$$

- Enfin, l'ouverture du poste coûte $c_o = constante > 0$

- Dans le cas où le poste de service est ouvert, on peut montrer que le processus $(N_t, Y_t)$ est markovien (cf. [25] [26])

où $N_t$ = nombre de client dans le système

$Y_t$ = temps écoulé depuis le dernier départ du poste de service si $N_t \ge 1$
$= 0$ (par convention) si $N_t = 0$

Pour $u(n,y)$ regulière en y, le semi groupe de $(N_t, Y_t)$ a pour générateur infinitésimal
$$
(2.1) \qquad (A_1 u)(n,y) = \begin{cases} \frac{\partial u}{\partial y} + \frac{G'(y)}{1-G(y)} u(n-1,0) + \lambda u(n+1,y) - \left(\lambda + \frac{G'(y)}{1-G(y)}\right) u(n,y) & 1 \le n < N_m \\ \\ \frac{\partial u}{\partial y} + \frac{G'(y)}{1-G(y)} [u(n-1,0) - u(n,y)] & n = N_m \\ \\ \lambda[u(1,0) - u(0,0)] & \end{cases}
$$

A₁ est complètement défini par (2.1) si le support de G'(y) est [0,∞[.
Mais si G'(y) a un support borné [0,τ], $\frac{G'(y)}{1-G(y)} \to +\infty$ quand y → τ

et (au moins formellement)

$$
(2.2) \quad (A_1 u)(n, \tau) = u(n-1, 0) - u(n, \tau)
$$

Remarque 2.1

(i) Le processus $N_t$ est formé à partir de l'intéraction entre un
processus de markov (les arrivées) et un processus semi mar-
kovien (les départs); ce type de processus a été étudié dans
[6]. Tome 2

(ii) Quand le poste est fermé, il n'y a que $N_t = N_m$, après, toute arrivée est refusée.

Donc $N_t$ est markovien dans ce cas et le générateur correspon-
dant est

$$
(2.3) \quad (A_0 u)(n) = \begin{cases} \lambda(u(n+1) - u(n)) & n < N_m \\ 0 & n = N_m \end{cases}
$$
## 2.2 **Problème de contrôle - Condition d'optimalité**

On peut construire une suite de mesure $P_{xy}^{n,v}$ sur un espace $(\Omega, \mathcal{F})$ convenable de façon analogue au §1.2 (mais c'est un peu plus délicat..)

On écrira donc formellement le critère sans préciser la mesure par rapport à laquelle on prend l'espérance.

Supposons qu'en $t=0$ le poste est ouvert. On note $\theta^i$ les instants de décision $0 \le \theta^1 < \theta^2 \dots < \theta^n < \theta^{n+1} \le T$ les instants $\theta^{2i}$ sont les instants d'ouverture du poste de service ($i \ge 1$) et les instants de fermeture ($i \ge 0$).

Le critère s'écrira :

$$ (2.4) \qquad J(v) = E \left\{ \sum_{i \ge 0} \left[ \int_{\theta^{2i}}^{\theta^{2i+1}} f_1(N_t, Y_t, t) dt + \int_{\theta^{2i+1}}^{\theta^{2i+2}} f_0(N_t) dt \right. \right. \\ \left. \left. + C(Y_{\theta^{2i+1}}).1_{(\theta^{2i+1} < T)} + C_o.1_{(\theta^{2i+2})} \right] \right\} $$

## - **Inéquations du coût optimal**

On note :

$U_1(n,y,t)$ le coût optimal sur $(t,T)$ quand à t il y a n "clients" dans le système et que le dernier départ a eu lieu à $t-y$ ($y=0$ si $n=0$) et que le poste est ouvert.

De même :

$u_0(n,t)$ le coût optimal sur $(t,T)$ quand le poste est fermé à $t$.

Supposons le poste ouvert entre $t, t+\delta$, alors :

$$ (2.5) \qquad u_1(n,y,t) = E \left( \int_t^{t+\delta} f_1(N_s, Y_s, s) ds + u_1(N_{t+\delta}, Y_{t+\delta}, t+\delta) \right) $$
et

$$
(2.6) \quad \text{Eu}_1(N_{t+\delta}, Y_{t+\delta}, t+\delta) = u_1(n,y,t) + E \int_t^{t+\delta} \left( \frac{\partial u_1}{\partial t} + A_1 u_1 \right) (N_s, Y_s, s) ds
$$

si par contre on décide de fermer le poste à t

$$
(2.7) \quad u_1(n,y,t) = c(y) + u_0(n,t)
$$

d'où

$$
u_1(n,y,t) = \inf \left\{ \begin{array}{ll} E \int_t^{t+\delta} f_1 ds + u_1(N_{t+\delta}, Y_{t+\delta}, t+\delta) & \quad \text{c}(y) + u_0(n,t) \\ & \\ \text{c}(y) + u_0(n,t) & \quad \text{c}(y) \end{array} \right.
$$

en passant à la limite en $\delta$, comme au § 1. on obtient

$$
(2.8) \quad \left\{
\begin{array}{l}
\displaystyle \frac{\partial u_1}{\partial t} + A_1 u_1 + f_1 \ge 0 \\[1em]
u_1(n,y,t) \le c(y) + u_0(n,t) \\[1em]
\displaystyle \frac{\partial u_1}{\partial t} + A_1 u_1 + f_1 (u_1(n,y,t) - c(y) - u_0(n,t)) = 0 \\[1em]
u_1(n,y,T) = 0
\end{array}
\right.
$$

Quand G est à support borné [0,τ] on doit ajouter une condition aux limites :

$$
(2.9) \quad u_1(n, \tau, t) = u_1(n-1, 0, t) \quad n \ge 1
$$

[qui traduit le fait qu'en τ il y a nécessairement un départ]

Le même type de raisonnement donne pour $u_0$
$$
(2.10) \quad \left\{
\begin{array}{l}
\displaystyle \frac{\partial u_o}{\partial t} + A_o u_o + f_o \ge 0 \\[2ex]
\displaystyle u_o(n,t) \le c_o + u_1(n,o,t) \\[2ex]
\displaystyle \frac{\partial u_o}{\partial t} + A_o u_o + f_o)(u_o(n,t) - c_o - u_1(n,o,t)) = 0 \\[2ex]
u_o(n,T) = 0
\end{array}
\right.
$$

Remarque 2.2.

On trouvera dans J.L. LIONS [9], l'étude des inéquations du type (2.8) (2.10) (solutions faibles)

Remarque 2.3

Quand le coût est actualisé au taux $\alpha$ il suffit de prendre

$$
\begin{cases}
A_1 u_1 - \alpha u_1 \\
A_o u_o - \alpha u_o
\end{cases}
$$

au lieu de $A_i u_i$ dans (2.8) (2.10).

Remarque 2.4

Quand il y a S serveurs (indépendant), chacun avec une loi de temps de service G(y), on pourrait écrire le problème analogue à celui du § 1.
Mais ici on obtiendrait S + 1 inéquations en $u_i(n,y_1,y_2,\dots,y_i)$ i = 0,1,\dots,S on voit que la dimension du problème devient très vite prohibitive.

<figure><img src="image_8.png" /></figure>
## Politique correspondant aux inéquations

Supposons comme précédemment que l'on parte à $t = 0$ avec le poste ouvert, et l'état $(n,y)$

on note

$$ (2.11) \qquad \left| \begin{array}{l} c_1 = \{(n,y,t) \ u_1(n,y,t) < c(y) + u_0(n,t)\} \\ \bar{c}_1 = \text{le complémentaire} \end{array} \right. $$

$\hat{\theta}^1$ sera le premier instant ou $(N_t, Y_t, t)$ atteint $\bar{c}_1$ de même en définissant

$$ (2.12) \qquad \begin{array}{l} c_o = \{(n,t) ; u_o(n,t) < c_o + u_1(n,o,t)\} \\ \bar{c}_o = \text{le complémentaire,} \end{array} $$

$\hat{\theta}^2$ sera le premier instant $> \hat{\theta}^1$ tel que $(N_t, t)$ atteigne $\bar{c}_o$ et ainsi de suite...

## 2.3. Applications

On a effectué trois types d'expériences numériques sur ce problème

(1) $G'(y)$ a un support borné $[0, \tau]$

(2) $G(y)$ est une loi sur $[0, \infty[$, et $\mu(y) = \frac{G'(y)}{1-G(y)}$ est croissant (cas Loi Gamma)

(3) $G(y)$ est une loi sur $[0, \infty[$ et $\mu(y)$ est décroissant (cas Loi hyperexponentielle)

ceci correspond en gros à la classification que l'on peut faire parmi les distributions classiques (cf. [23]).
[$\mu$](y)s'interprète comme la probabilité que se produise le départ d'un client après un temps de service y (ou entre y,y + dy...) ; dans le cas (2) cette probabilité augmente avec y, elle diminue dans le second.]

2.3.1 Exemple 1

- Loi des temps de service :

On prend $\tau = 0.6$ temps de service maximum
et sur (0,$\tau$) une loi exponentielle "tronquée"

$$
(2.14) \qquad \text{i.e. } G(y) = \frac{(1 - e^{-\mu y})}{(1 - e^{-\mu \tau})}
$$

On a pris des constantes $\mu$, $\lambda$ (taux d'arrivées) qui permettent
d'avoir des moyennes d'arrivées et de temps de service comparables avec les
autres exemples.

Les valeurs numériques étaient :

$$
\lambda = 10. \qquad N_m = 20 \ (\text{nb max de clients})
$$

$$
\mu = 25 \text{ (temps moyen de service } \approx 0.04\text{)}
$$

$\tau = 0,6$

$$
T = 2 \text{ (intervalle d'intégration)}
$$

$$
\Delta t = 0,02 \quad , \quad \Delta y = 0,02
$$

$$
f_1(n,y) = f_{11} \cdot n + f_{12} (y - y_o)^+
$$

$$
c(y) = 0.2 + 5(y - 0.3)^+
$$

$c_o = 1,5$
$$f_{11} = 5$$

$$f_{12} = 3.10^3$$

$$y_o = 0.4$$

### Remarque 2.3

Discrétisation des équations en $u_1$.

On a pris $u_{1i}^k = u_1(i\Delta y, k\Delta t)$

$$\frac{1}{2} \left[ \frac{u_{1i}^{k+1} - u_i^k}{\Delta t} + \frac{u_{1i+1}^{k+1} - u_{1i+1}^k}{\Delta t} \right] \quad \text{pour approcher} \quad \frac{\partial u_1}{\partial t}$$

$$\frac{1}{2} \left[ \frac{k}{\Delta y} [ u_{1i+1}^k - u_{1i}^k ] + \frac{k+1}{\Delta y} [ u_{1i+1}^{k+1} - u_{1i+1}^{k+1} ] \right] \quad \text{pour approcher} \quad \frac{\partial u_1}{\partial y}$$

(i.e les dérivées sont calculées en $(i + \frac{1}{2}, k + \frac{1}{2})$ comme on a pris $\Delta y = \Delta t$ (pour suivre les caractéristiques)

$$\frac{\partial u_1}{\partial t} + \frac{\partial u_1}{\partial y} , \text{ sera approché par} \quad \frac{1}{\Delta t} [ u_{i+1}^{k+1} - u_i^k ]$$

les inéquations sont résolues en "backward" à la fois en t et y.

### - Résultats numériques :

La figure 5 donne le nombre de clients $n_o(t)$ auquel on doit ouvrir le poste de service si celui-ci est formé -i.e- la zone de saturation de la contrainte $C_o(2.12)$ en $(n,t)$.
Les figures 6.7 donnent les zones de saturation de la contrainte $C_1$ pour diverses valeurs de $t$ dans le plan $(n,y)$.

On remarque :

- que l'on ferme le poste de service quand $n = 0$.

- que l'on ferme également le poste de service quand le temps de service devient trop grand ce qui s'explique ici par le fait que $f_1(n,y,t)$ pénalise fortement les grands temps de service.

- si $f_1$ ne dépend pas de $y$, on ne ferme le poste de service que lorsque le système est vide.

Dans ce cas et dans ce cas seulement, on ne perd rien en généralité en restreignant les instants de décisions aux instants de départ d'un client (quand le poste est ouvert) ce qui est fait dans toute la littérature sur le sujet cf. [2], [12] (entre autres).

### Remarque 2.2

Le temps moyen entre deux arrivées est ici $0.1$.

Il est évident que les données numériques sont ici tout à fait artificielles et ont été choisies (notamment les coûts) de façon à obtenir une politique non triviale (en choisissant les coûts de décisions suffisamment grands, on ne passera jamais de la situation poste ouvert à la situation poste fermé, par exemple).

2.3.2 Exemple 2 :

- $G(y)$ est une loi sur $[0,\infty[$
  On prend ici une loi Gamma

$$ (2.15) \qquad \frac{G'(y)}{1-G(y)} = \frac{\beta^2 y}{1+\beta y} $$
On ramarque qu'ici on devrait résoudre les inéquations (2.8) (2.10) sur un domaine non borné en y.

En fait on résoud une variante de ce problème :

On introduit une décision supplémentaire en autorisant le renvoi (définitif) d'un client du système quand son temps de service devient trop grand (ce qui est assez réaliste....)

Ceci se traduit par une inéquation supplémentaire

$$ (2.16) \qquad u_1(n,y,t) \le c_1(y) + u_1(n-1,o,t) $$

signifiant qu'il en coûte $c_1(y)$ de renvoyer un client qui a passé un temps y dans le poste.

Ceci permet de se ramener à un problème sur un borné en y, on prend $y_m$ suffisamment grand et on prend

$$ (2.17) \qquad u_1(n,y_m,t) = c_1(y_m) + u_1(n-1,o,t) $$

en vérifiant a posteriori que cette contrainte est saturée pour des $y < y_m$ (c'est à dire que l'on a rien perdu en faisant l'hypothèse (2.7)).

- **Données numériques :**

$$ \lambda = 10 $$

$$ \beta = 50 $$

$$ y_m = 0.6 $$

$$ c_1(y) = 2 $$

Les autres données sont les mêmes qu'au § 2.3.1. Noter qu'ici le temps moyen de service est 0.04
La figure 8 donne la zone de saturation de la contrainte $C_0$ (2.12) (ouverture du poste de service).

La figure 9 donne (en stationnaire) les zones de saturation de $C_1$ (2.11) : fermeture du poste et (2.16) renvoi du client en cours de service.

Il est bien entendu que l'on a une très faible probabilité d'atteindre un temps de service tel que l'on ait à renvoyer le client.

### 2.3.3 Exemple 3 :

Loi hyperexponentielle.

$$G'(y) = p \cdot \lambda_1 e^{-\lambda_1 y} + (1-p) \lambda_2 e^{-\lambda_2 y}$$

$$\text{On a pris } \lambda_1 = 2 \lambda_2 \qquad p = 0.5$$

le temps de service moyen est alors $\frac{3}{2\lambda_2}$ et on a pris $\lambda_2 = 37.5$ de façon à ce que ce temps de service moyen soit 0.04 comme dans le cas précédent.

Les figures 10,11 donnent respectivement la zone d'ouverture du poste de service en fonction du temps et les zones de fermeture et de rejet dans le cas stationnaire (qui est atteint aux environs de $t = 1$ cf. Figure n°10)

On boserve la similitude des politiques dans le cas Loi Gamma (§ 2.3.2) et le cas présent : Loi hyperexponentielle.

## 2.4 Généralisations diverses

### - Système G/M/S

C'est le cas où les intervalles entre arrivées sont des variables aléatoires de loi quelconque (et non plus exponentielle comme dans le cas M/M/S).
On peut obtenir des résultats analogues à ceux du § 1.2 c'est maintenant le processus $(N_t, Y_t)$ qui est markovien si $Y_t$ est le temps écoulé depuis la dernière arrivée.

Sans entrer dans le détail, les inéquations que l'on obtient sont les suivantes :

$$ egin{cases} 
\frac{\partial u_i}{\partial t} + A_i u_i + f(i,n,t) \ge 0 \\ 
u_i(n,y,t) \le \min_j [c(i,j) + u_j(n,y,t)] \\ 
\text{produit} = 0 
\end{cases} $$

où $A_i$ est l'opérateur défini par

$$ (A_i v)(n,y) = \frac{\partial v}{\partial y} + \frac{G'(y)}{1-G(y)} v(n+1,0) + (n_i) \lambda v(n-1,y) \\ - \left[ \frac{G'}{1-G} + (i_1 n) \lambda \right] v(n,y) $$

## Systèmes M/G/S, G/G/1

Dans le cas du système M/G/S, le processus markovien que l'on doit considérer est $(N_t, Y_t^1, \dots, Y_t^S)$ où $Y_t^i$ est le temps écoulé depuis le début du service du client qui se trouve à t dans le poste i.

La dimension du problème devient prohibitive pour $S > 2$.

Les problèmes correspondant aux systèmes M/G/2 et G/G/1 sont à la limite des possibilités actuelles. (dimension 3 en "espace" pour les inéquations correspondantes).
Mentionnons enfin que les systèmes fermés du type M/M/S ou M/G/1 peuvent être traités sans difficultés supplémentaires avec les méthodes des paragraphes précédents.

## CONCLUSIONS

On a exposé ici une façon de résoudre le problème du nombre optimal de "serveurs" dans des types particuliers de files d'attente. Ce problème apparaît surtout dans les modèles de maintenance ou dans la gestion de production (cf. [12]), ou les coûts d'immobilisation et de décision sont suffisamment importants pour justifier l'optimisation.

Cependant les problèmes de contrôle des taux d'arrivées ou des taux de service (cf. [18], [17]) peuvent être traités avec les mêmes méthodes (sans les hypothèses restrictives de [18], [17]; entre autres, sur les instants de décisions ou sur les coûts).

On peut espérer appliquer ce type de méthode à des problèmes d'optimisation concernant les systèmes informatiques qui présentent de nombreuses files d'attente et où il est important de pouvoir améliorer l'utilisation des machines et le service rendu aux utilisateurs.
<figure><img src="image_9.png" /></figure>

Fig. 5

M/G/1 Ouverture du poste
<figure><img src="image_10.png" /><figcaption>Fig. 7 M/G/1 évolutif
zone de Fermeture</figcaption></figure>

<figure><img src="image_11.png" /></figure>
<figure><img src="image_12.png" /></figure>

Fig. 8

M/G/1 zone d'ouverture (évolutif)
<figure><img src="image_13.png" /><figcaption>Fig. 9 M/G/1
zones de fermeture et de rejet</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Fig. 10
M/G/1 zone d'ouvertur (évolutif)</figcaption></figure>
<figure><img src="image_15.png" /></figure>

Fig. 11

M/G/1 stationnaire

(Service hyperexponentiel)
REFERENCES

[1] BENSOUSSAN-LIONS
a) Nouvelles méthodes en contrôle impulsionnel.
à paraître.

b) C.R.A.S. 1973 Tome 276 Série A
pp. 1184 - 1192
1274 - 1284
1333 - 1338

c) Ouvrage à paraître.

[2] BELL
Op. Research 1971. 19 pp. 208 - 218

[3] CHEONG etc.
Bibliography on Semi markov processes.
Louvain 1974.

[4] CRABILL
Op. Research 1973 pp. 736

[5] CARTER - COOPER
Queues with service in random order.
Op. Research 1971.

[6] GIRMAN - SKOROHOD
Théorie des processus stochastiques.
Tome 2 Chap. 3 (en Russe)

[7] DYNKIN
Markov processes.
Tome 1 Springer-Verlag. (1965)

[8] JACOD
Semi groupe et mesure invariante pour les processus semi markoviens.
Ann. de l'IHP. IX n° 1 1973.

[9] LIONS
Cours au Collège de France.
1973-1974 1974-1975.
[10] MEYER
*Probabilité et potentiel.*
Herman Paris. (1966)

[11] PRABHU
*Mathematical methods in Queuing Theory.*
Lectures Notes in Economics n° 98
Springer 1974.

[12] SOBEL
Op. Research 1969
pp. 145 - 162.

[13] SOBEL
Maths. Method... cf. [11].

[14] STONE
Necessary and suff. Conditions for optimal control
of semi markov jump processes.
SIAM J. Control May 1973.

[15] STROOK - VARADHAN
Diffusion processes with continuous coefficients.
Comm. in Pure and Applied Math. 1969.
XXII, pp. 345-400.

[16] TORBETT
Optimal control of closed markovian queuing systems.
Stanford University 1973.

[17] LOW
Optimal pricing for an unbounded queue.
IBM Research J. 1974 pp. 290.

[18] SABETI
Optimal control of queuing system.
R. Report. Berkeley 1970.

[19] ZABCYK
IFIP Rome 1973
Springer Verlag.

[20] GOURSAT - MAURIN
Colloque IRIA juin 1974.
[21] LEGUAY
Thèse Docteur-Ingénieur
Paris 1975.

[22] GLOWINSKY - LIONS - TREMOLIERE
Approximation des inéquations variationnelles,
à paraître.

[23] LESTER
The investigation of Service distributions.
Tech. Report Univ. of Toronto Avril 1973.

[24] BLACKBURN
Manag. Sc. Vol 19 n° 3 Nov. 1972.

[25] JAISWAL
Prinity Queues
Academic Press. 1968.

[26] TACKACS
Theory of Queues.
Oxford Univ. Press. 1962.