# Sur le nombre d'unités servies lors d'une période de service ininterrompu pour une file d'attente simple

J. P. Imhof

► To cite this version:

J. P. Imhof. Sur le nombre d'unités servies lors d'une période de service ininterrompu pour une file d'attente simple. Annales de l'ISUP, 1964, XIII (4), pp.181-190. hal-04085222

HAL Id: hal-04085222

https://hal.science/hal-04085222

Submitted on 28 Apr 2023

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
SUR LE NOMBRE D'UNITÉS SERVIES
LORS D'UNE PÉRIODE DE SERVICE ININTERROMPU
POUR UNE FILE D'ATTENTE SIMPLE

J. P. IMHOF (1)

# 1. Introduction.

Dans la littérature relative aux files d'attente, les méthodes utilisant la transformation de Laplace ont longtemps joué un rôle prédominant. Un argument combinatoire a été employé pour la première fois par Champernowne [1] qui obtint pour une file simple avec arrivées Poissonniennes et durées de service exponentielles-négatives la probabilité conditionnelle d'avoir une file de longueur j au temps t étant donné que la longueur de la file au temps 0 égale i. Le résultat utilisé par Champernowne est relatif aux chemins dans le plan formés de pas ascendants (joignant un point $(m,n)$ au point $(m+1, n+1)$ et de pas descendants (joignant un point $(m,n)$ au point $(m+1, n-1)$ mis bout à bout ; le nombre de chemins distincts issus de l'origine, comportant a pas ascendants et b pas descendants, et qui atteignent l'horizontale d'ordonnée $h$ $(-b \le h \le 0)$ est :

$$ \binom{a+b}{b+h} = \frac{(a+b)!}{(a-h)!(b+h)!} \quad (1) $$

Un autre type de résultat combinatoire est applicable sous sa forme la plus simple, dans le contexte statistique, dans le test du rang de Galton [2] : si $a=b$, le nombre des chemins allant du point $(0,0)$ au point $(2a, 0)$ sans jamais toucher autrement l'axe horizontal est $a^{-1}(2a^{-2})$. Ce résultat est, lui, susceptible de généralisations étendues dont certaines ont été données récemment par Hobby et Pyke [3]. Celles qui sont utiles pour la théorie des files d'attente sont cependant essentiellement des cas particuliers relatifs à des variables aléatoires discrètes d'un théorème de Dwass [4]. Takacs, les démontrant indépendamment, en a le premier fait usage pour l'étude des périodes de service ininterrompu [5, 6]. Dans la présente

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

<footnote n="1">1) Travail effectué durant un séjour au Département de Statistique de l'Université de Californie, Berkeley, avec l'appui du contrat ONR-222-43.</footnote>
note, nous étendons des résultats de Takacs relatifs au nombre d'unités (clients) servies au cours d'une période de service interrompu.

Soient s et t deux entiers, s > 0, t ≥ 0. Considérons des variables aléatoires $X_1, X_2, ..., X_{s+t}$ dont les valeurs possibles sont -1, 0, 1, 2, 3, ..., et qui sont cycliques :

$$P[X_i = j_i, i = 1, 2, ..., s+t] = P[X_{\sigma_i} = j_i, i = 1, 2, ..., s+t]$$

pour toute permutation circulaire ($\sigma_1, \sigma_2, ..., \sigma_{s+t}$) de (1, 2, ..., s+t). Il en est ainsi en particulier si ces variables sont échangeables, et à fortiori si elles sont indépendantes et suivent toutes la même loi de probabilité. Ecrivons $S_k = X_1 + X_2 + ... + X_k$ ($S_0 = 0$). Alors

$$P[S_k > -s, k = 1, 2, ..., s+t-1 | S_{s+t} = -s] = \frac{s}{s+t} \quad (2)$$

Ce résultat se justifie en considérant un ensemble $(x_1, x_2, ..., x_{s+t})$ de valeurs possibles de $(X_1, X_2, ..., X_{s+t})$, tel que $\sum_{i=1}^{s+t} x_k = -s$. Π y correspond dans le plan un chemin formé des segments joignant les points $(k-1, s_{k-1})$ et $(k, s_k)$, $k=1, 2, ..., s+t$, $s_k = \sum_{i=1}^{k} s_i$, $s_0 = 0$. Si ce chemin atteint le niveau $-s$ avant le point terminal B (figure 1a), soit $P_0$ le point le plus à gauche où ce chemin atteint son niveau le plus bas. La permutation circulaire qui amène en B le point $P_0$ donne un chemin situé jusqu'en B entièrement au-dessus du niveau $-s$ (figure 1b). Il en va de même des permutations circulaires qui amènent en B les points $P_1, ..., P_{s-1}$ où ce nouveau chemin atteint pour la première fois les niveaux $-s+1, -s+2, ..., -1$, et de celles-là seulement. Ceci établit (2). Une

<figure><img src="image_3.png" /><figcaption>Fig. 1</figcaption></figure>
formulation équivalente est obtenue si $Y_1, Y_2, ..., Y_{s+t}$ sont des variables aléatoires cycliques dont les valeurs possibles sont $0,1,2,...$. Si $T_k = \sum_{1}^{k} Y_j$,

$$P[T_{s+k} > k, k = 0,1,..., t-1 | T_{s+t} = t] = \frac{s}{s+t}. \quad (3)$$

On le voit en posant $X_j = Y_j - 1$ et remarquant que les conditions $T_1 > -s+1, ..., T_{s-1} > -1$ sont superflues.

## 2. Nombre d'unités servies durant une période de service ininterrompu.

Nous envisageons le modèle suivant. Les arrivées à un dispositif de service se font selon un schéma de Poisson de paramètre $\lambda$. Donc

$$P[k \text{ arrivées dans le temps } T] = \frac{(\lambda T)^k}{k!} e^{-\lambda T}, \quad k = 0,1,2,...$$

Chaque arrivée est celle d'un lot comportant U unités ($U=0,1,2,...$). La loi du nombre des unités U dans un lot est la même pour chaque lot, et il y a indépendance de lot à lot. Les durées de service pour les unités sont des variables indépendantes ayant même loi exponentielle-négative de paramètre $\mu > 0$. Leur densité de probabilité est donc $f(t) = \mu \exp(-\mu t)$, $t \ge 0$, et tant que dure une période de service ininterrompu (une période durant laquelle le dispositif de service n'est jamais au repos) les fins de service se produisent selon un schéma de Poisson de paramètre $\mu$. Les unités constituant un lot arrivant sont mises en attente dans une file unique. L'une d'entre elles est immédiatement prise en charge s'il s'agit d'un lot non-vide qui ouvre une période de service ininterrompu. La longueur de la file est le nombre d'unités en attente, y compris celle en train d'être servie. Soit $p(m|s)$ la probabilité, étant donné qu'une file de longueur $s \ge 1$ existe au temps 0, que la période de service ininterrompu en cours au temps 0 se termine par le $(m+s)$-ième service compté à partir du temps 0 ($m \ge 0$). C'est donc la probabilité que m unités arrivent encore durant cette période de service ininterrompu. Si l'on se place à un instant arbitraire de cette période (instant qu'on peut en particulier choisir comme étant celui où une arrivée, ou un départ, s'est produit) la probabilité que dans le processus simultané des arrivées (de lots) et départs (fins de service d'unités) le prochain événement soit une arrivée est $p = \lambda(\lambda+\mu)^{-1}$; celle que le prochain événement soit un départ est $q = 1-p$. Posons $U_0 = 0$. Soit $X_i = U_{i-1}$ si le i-ème
événement postérieur au temps 0 est l'arrivée d'un $j_i$-ème lot d'effectif $U_{j_i}$, $X_i = -1$ si ce i-ème événement est un départ. L'événement dont la probabilité est $p(m|s)$ peut se réaliser avec l'arrivée de n lots ($n=0,1,2,...$) d'effectif total $\sum_{j=0}^{n} U_j = m$. On a alors à considérer les variables $X_{1s}, X_2, ..., X_{s+m+n}$ et la période de service ininterrompu prend fin avec le $(s+m)$-ème service $(S_{s+m+n} = -s)$ si $S_j > -s$, $j=1,2,...,s+m+n-1$. Appliquant (2),

$$p(m|s) = \sum_{n=0}^{\infty} \frac{s}{s+m+n} P[S_{s+m+n} = -s],$$

soit :

$$p(m|s) = \sum_{n=0}^{\infty} \frac{s}{s+m+n} b(s+m+n, n; p) P\left[\sum_{j=0}^{n} U_j = m\right], \quad (4)$$

où $b(r,k; p)$ désigne la probabilité binomiale

$$b(r, k; p) = \binom{r}{k} p^k q^{r-k},$$

et où $U_1, ..., U_n$ sont des variables indépendantes qui suivent toutes la même loi que U. En fixant le temps 0 à l'instant immédiatement postérieur à l'arrivée d'un lot non-vide qui ouvre une période de service ininterrompu, on obtient pour la probabilité que m unités soient servies durant une période de service ininterrompu l'expression

$$p(m) = \sum_{s=1}^{m} P[U=s] p(m-s|s).$$

Examinons divers cas particuliers.

A. U est une variable de Bernoulli,

$$P[U=1] = \bar{p} > 0, \quad P[U=0] = \bar{q} = 1 - \bar{p}.$$

Dans ce cas

$$P\left[\sum_{i=1}^{n} U_i = m\right] = \begin{cases} 0, & \text{si } n < m, \\ b(n, m; \bar{p}) & \text{si } n \ge m. \end{cases}$$

La substitution dans (4) donne après quelque calcul

$$p(m|s) = \frac{s}{s+2m} b(s+2m, m; p_0)$$
où

$$P_0 = \frac{p\bar{p}}{1 - p\bar{q}} = \frac{p\bar{p}}{p\bar{p} + q}.$$

Tout se passe comme si l'on avait des arrivées d'unités isolées (B ci-dessous pour r = 1), l'intensité de trafic originelle ρ = λ / μ étant remplacée par ρ₀ = p̄ρ.

B. Les lots arrivants comportent r unités chacun. L'expression (4) n'a de sens que si m = rm* où m* est entier, et seul le terme correspondant à n = m* subsiste :

$$p(rm^*|s) = \frac{s}{s+m+m^*} b(s+m+m^*, m^*; p).$$

Si en particulier l'origine du temps est l'instant qui suit immédiatement l'arrivée d'un lot de r par lequel débute une période de service ininterrompu, donc si l'on pose s = r, on obtient la probabilité que m* + 1 lots (m + r unités) soient servis au cours d'une période de service ininterrompu.

C. Les arrivées se font par unités isolées, mais la loi des durées de service est une loi gamma correspondant au modèle d'Erlang : on imagine que chaque service est constitué par la succession de r services partiels (indiscernables) indépendants de loi exponentielle-négative pour le paramètre μᵣ = rμ. Tout se passe donc comme si chaque r-ème départ était une fin de service effective, les autres étant fictifs. La loi des durées de service est donnée dans ce cas par la densité de probabilité

$$f(t) = \mu_r^{-t} t^{r-1} \exp(-\mu_r t) / (r-1)! , \quad t \ge 0.$$

L'espérance mathématique de la durée d'un service égale comme précédemment μ⁻¹, mais la variance devient r⁻¹μ⁻², alors qu'elle égalait μ⁻² pour le service exponential-négatif. La situation peut être assimiliée à celle des arrivées par lots de r, où μ est remplacé par μᵣ, et où il correspond à une file de longueur s au temps 0 un total de rs services partiels, à condition que le temps 0 soit choisi comme étant l'instant immédiatement postérieur à la fin du service qui ramène la longueur de la file à s. La probabilité qu'une période de service ininterrompu se termine à la fin du (s + m*) -ème service compté à partir de l'instant où la file vient d'être réduite à la longueur s est ainsi, pour le service r-Erlangien,
$$p_{\bar{\epsilon}_r}(m^*|s) = \frac{rs}{rs+m+m^*} b(rs+m+m^*, m^*; p_r), \quad (5)$$

où $p_r = \lambda/(\lambda + r\mu)$, $m = rm^*$. Lorsque $r \to \infty$, on obtient à la limite la probabilité que pour les services de durée constante $\mu^{-1}$ une période de service ininterrompu se termine avec le $(s+m^*)$-ème service à partir du temps 0 où la longueur de la file vient d'être réduite à s, à savoir

$$\frac{s}{(s+m^*) m^*!} [(s+m^*) \rho]^m \exp\{-(s+m^*) \rho\}, \quad \rho = \lambda/\mu.$$

Ce résultat s'obtient aussi directement par l'application de (3).

Envisageons maintenant la probabilité conditionnelle $\bar{p}_{\epsilon_r}(m|s)$ qu'une période de service ininterrompu se termine avec le $(m+s)$-ème service à partir du temps 0 où la longueur de la file est s (pour simplifier, nous écrivons m en lieu et place de $m^*$), lorsque le temps 0 est un instant choisi au hasard, indépendemment de l'instant où la longueur de la file a passé de s+1 à s. L'unité en train d'être servie a donc probabilité $1/r$ de se trouver au temps 0 durant le j-ème des services partiels dont la succession constitue le service d'une unité ($j=1,2,...,r$). On voit facilement que l'analogue de (5) est dans ce cas

$$\bar{p}_{\epsilon_r}(m|s) = \frac{1}{r} \sum_{i=0}^{r-1} \frac{rs - i}{r(s+m) + m - i} b(r(s+m) + m - i, m; p_r). \quad (6)$$

Ici encore, le passage à la limite pour $r \to \infty$ fournira cette même probabilité dans le cas des services de durée constante $\mu^{-1}$. Ecrivons

$$\bar{p}_{\epsilon_r}(m|s) = \frac{1}{r} \sum_{i=0}^{r-1} \frac{s - i/r}{s + m - (i - m)/r} b(n_r(i), m; p_r)$$

où $n_r(i) = r(s + m) + m - i$. On a

$$\begin{aligned} n_r(i)p_r &= s + m - \frac{i - m}{r} \frac{\rho}{1 + \rho/r} \\ &= \rho \left(s + m - \frac{i - m}{r}\right) + o\left(\frac{1}{r}\right) \end{aligned}$$

où le développement $(1 + \rho/r)^{-1} = 1 - \rho/r + \xi(\rho/r)^2$, $|\xi| \le 1$, donne $c = m - (s+m)\rho$. On peut donc écrire pour $r$ assez grand
$$b(n_r(i), m; p_r) \approx P(m; \rho(s+m - \frac{i}{r})),$$

où $P(m; \theta) = \theta^m \exp(-\theta)/m!$ est la probabilité de Poisson. Ceci suggère que

$$\lim_{r \to \infty} \bar{p}_{E_r}(m|s) = \frac{\rho^m}{m!} \int_0^1 \frac{s-t}{s+m-t} (s+m-t)^m \exp\{-\rho(s+m-t)\} dt.$$

Ce passage à la limite peut être justifié en toute rigueur et un changement de variable permet alors d'écrire la probabilité qu'une période de service ininterrompu se termine avec le $(s+m)$-ème service à partir d'un instant initial où la longueur de la file est $s$, pour des services de durée constante $\mu^{-1}$, sous la forme

$$\frac{\rho^m}{m!} \int_{s+m-1}^{s+m} (t-m)t^{m-1} e^{-\rho t} dt, \quad \rho = \lambda/\mu.$$

Pour de petites valeurs de $m$, il est aisé de vérifier ce résultat par un calcul direct.

### 3. Cas du service par lots, et des arrivées Erlangiennes.

On peut traiter de manière analogue un cas où les arrivées sont individuelles tandis que le service est effectué par lots de V unités ($V = 0,1,2,...$). Supposons que la loi de V est la même pour chaque lot, et qu'il y a indépendance de lot à lot. Supposons aussi que les arrivées se produisent selon un schéma de Poisson de paramètre $\lambda$ et les départs (fins de services de lots), tant que dure une période de service ininterrompu, selon un schéma de Poisson de paramètre $\mu$. Soit $p^*(n)$ la probabilité que n lots soient servis au cours d'une période de service ininterrompu, $n \ge 1$. Un schéma peut nous aider à déterminer $p^*(n)$.

<figure><img src="image_4.png" /><figcaption>Fig. 2</figcaption></figure>
Le produit $pp^*(n)$ est la probabilité que le prochain événement (à partir d'un instant arbitraire où la file est nulle) soit une arrivée (segment AA') qui initie une période de service ininterrompu se terminant avec le service d'un n-ème lot (segment BB'). Soient $V_1, V_2, \dots, V_n$ les nombres d'unités servies dans les lots 1, 2, ..., $n$, et soit $V_0 = 0$. L'événement dont la probabilité est $pp^*(n)$ est réalisé si

i) le chemin A'B ne tombe pas au-dessous de l'ordonnée 1 (ordonnée de A'),

$$ii) \sum_{0}^{n-1} V_k = m, m \ge 0,$$

iii) le nombre des arrivées de A à B est $m + j + 1$, où $j + 1 > 0$ est l'ordonnée de B,

iv) les $m + n + j$ arrivées et départs du chemin AB sont suivies d'un n-ème départ, et $V_n > j$.

La proportion des chemins AB satisfaisant à i) est, d'après (2), $(j+1)/(m+n+j)$. Ainsi,

$$pp^*(n) = q \sum_{m=0}^{\infty} \sum_{j=0}^{\infty} \frac{j+1}{m+n+j} b(m+n+j, n-1; q) P\left[\sum_{0}^{n-1} V_i = m \right] P\left[V_n > j\right].$$

Le facteur q au second membre correspond à la condition exprimée dans iv) que le point B doit être suivi d'un départ.

Un cas particulier est celui du service par lots de dimension fixée r, considéré déjà par Takács [6] et Fabens [7]. On a alors nécessairement $m = (n-1)r$ et les valeurs possibles de j sont 0, 1, ..., $r-1$. De plus $P\left[\sum_{0}^{n-1} V_i = (n-1)r \right] = P\left[V_n > j\right] = 1$. La probabilité $p^*(n,r)$ que n lots de r soient servis au cours d'une période de service ininterrompu est alors donné par

$$pp^*(n,r) = q \sum_{j=0}^{r-1} \frac{j+1}{(n-1)(r+1)+j+1} b((n-1)(r+1)+j+1, n-1; q),$$
ou encore, posant $j = r - j' + 1$ et omettant le "prime",

$$p^*(n,r) = \frac{q}{p} \sum_{j=1}^{r} \frac{r-j+1}{nr-j+n} b(nr-j+n, n-1; q). \quad (7)$$

Pour $r=1$, ce résultat coincide avec (6) où $m+1=n$, $s=r=1$.
La formule (7) s'applique directement au modèle avec arrivées Erlangiennes : si les durées séparant des arrivées consécutives d'unités sont des variables indépendantes de densité

$$g(t) = \lambda_r^r t^{r-1} \exp(-\lambda_r t)/(r-1)! , \quad t \ge 0,$$

où $\lambda_r = r\lambda$ de sorte que l'espérance mathématique de la durée séparant deux arrivées consécutives est encore $\lambda^{-1}$, la substitution de $p_r = r\lambda/(r\lambda+\mu)$ à p et $q_r = 1 - p_r$ à q dans (7) donne la probabilité que n unités soient servies au cours d'une période de service ininterrompu. Nous l'écrirons

$$p_{\lambda r}^*(n) = \frac{1}{\rho r} \sum_{j=1}^{r} \frac{1 - j/r}{n - (j-n)/r} b(nr - j + n, n - 1; q_r).$$

Le passage à la limite, lorsque $r \to \infty$, peut s'effectuer exactement comme pour (6). On obtient sans peine pour la probabilité que n unités soient servies au cours d'une période de service ininterrompu, lorsque les arrivées ont lieu à intervalles constants de $\lambda^{-1}$, l'expression

$$\frac{1}{(n-1)! \rho^n} \int_{n-1}^{n} (t - n + 1) t^{n-2} e^{-t/\rho} dt.$$

Ici encore, pour les petites valeurs de n, un calcul direct permet de trouver le résultat et fournit ainsi une vérification.

D'une manière générale, il est clair que tout résultat relatif à des chemins dans le plan tels que ceux envisagés précédemment se transcrit en un résultat relatif aux périodes de service ininterrompu pour une file d'attente simple. Par exemple, Gnedenko et Rvaceva [8] ont déterminé, pour les chemins considérés en rapport avec (1), le nombre de ceux qui restent compris entre deux horizontales données. Dans le cas de la file avec arrivées et départs individuels correspondant aux paramètres $\lambda$ et $\mu$, on en déduit pour la probabilité conditionnelle que la longueur de la file soit constamment inférieure à l'entier $l \ge 3$, étant donné qu'une période de service ininterrompu comporte n services, l'expression

$$\left\{ \sum_{i=-[\frac{n-2}{l}]}^{[\frac{n-2}{l}]} (\frac{2n-4}{n-2-i})^i - \sum_{i=1}^{[\frac{n}{l}]} (\frac{2n-4}{n-i})^i - \sum_{i=1}^{[1+(n-4)/l]} (\frac{2n-4}{n+1-4-i})^i \right\} \frac{n}{(\frac{2n-2}{n-1})}$$

où $[x]$ est la partie entière de x et où il y a lieu, cas échéant, d'ignorer les sommes pour lesquelles la limite supérieure des valeurs de i est zéro. Il est cependant à remarquer que ce résultat ne permet pas d'obtenir aisément la probabilité que durant une
période de service ininterrompu, la longueur de la file soit cons-
tamment inférieure à l. La méthode élégante développée par Karlin
et McGregor [9] est, en ce cas, beaucoup plus efficace.

REFERENCES

[1] CHAMPERNOWNE (D. G.) : An elementary method of solution of the queuing problem with a single server and constant parameter, *J. Roy. Stat. Soc., Série B.* **18** (1956), 125-128.

[2] HODGES (J. L., Jr.) : Galton's rank order test, *Biometrika* **42** (1955), 261-262.

[3] HOBBY (Ch.) et PYKE (R.) : A combinatorial theorem related to comparisons of empirical distribution functions, *Zeitschr. Wahrscheinlichkeitstheorie* **2** (1963), 85-89.

[4] DWASS (M.) : A fluctuation theorem for cyclic random variables, *Ann. Math. Statist.* **33** (1962), 1450-1454.

[5] TAKÁCS (L.) : The probability law of the busy period for two types of queuing processes, *Operations Research*, **9** (1961), 402-407.

[6] TAKACS (L.) : A generalization of the ballot problem and its application in the theory of queues, *J. Amer. Statist. Assoc.* **57** (1962), 327-337.

[7] FABENS (A. J.) : The solution of queuing and inventory models by semi-Markov processes, *J. Roy. Stat. Soc., Série B* **23** (1961), 113-127.

[8] GNEDENKO (B. V.) et RVAČERA (E. L.) : On a problem of the comparison of two empirical distribution functions, *Selected Translations in Mathematical Statistics and Probability* **1** (1961).

[9] KARLIN (S.) et McGREGOR (J.) : Many server queuing processes with Poisson input and exponential service times, *Pacific J. Math.* **8** (1958), 87-118.

Université de Lausanne
Lausanne, Suisse

Reçu le 10 octobre 1964