Trois fondements de la théorie des files d'attente. Les systèmes de file d'attente les plus simples, exemples d'utilisation pour résoudre des problèmes économiques

Très souvent, lors de l'analyse des systèmes économiques, il faut résoudre les soi-disant problèmes faire la queue survenant dans la situation suivante. Laissez le système être analysé Entretien voitures, composé d'un certain nombre de stations de capacités différentes. A chaque station (élément du système), au moins deux situations typiques peuvent se présenter :

1. le nombre de demandes est trop élevé pour cette station, il y a des files d'attente et vous devez payer les retards de service ;
2. la station reçoit trop peu de requêtes et maintenant il faut déjà tenir compte des pertes causées par l'indisponibilité de la station.

Il est clair que l'objectif l'analyse du système dans ce cas est de déterminer un rapport entre la perte de revenu due à files d'attente et les pertes dues à juste moi gares.

Théorie des files d'attente– une section spéciale de théorie des systèmes est une section de théorie des probabilités dans laquelle les systèmes de file d'attente sont étudiés à l'aide de modèles mathématiques.

Système de file d'attente (QS)- il s'agit d'un modèle qui comprend : 1) un flux aléatoire de demandes, d'appels ou de clients nécessitant un service ; 2) l'algorithme de mise en œuvre de ce service ; 3) canaux (dispositifs) pour la maintenance.

Des exemples de CMO sont les caisses, les stations-service, les aéroports, les vendeurs, les coiffeurs, les médecins, les centraux téléphoniques et d'autres installations qui desservent certaines applications.

Problème de la théorie des files d'attente consiste à élaborer des recommandations pour la construction rationnelle des QS et l'organisation rationnelle de leur travail afin d'assurer haute efficacité prestation au meilleur prix.

La principale caractéristique des tâches cette classe– une dépendance claire des résultats de l'analyse et des recommandations reçues sur deux facteurs externes: la fréquence de réception et la complexité des ordres (et donc le moment de leur exécution).

L'objet de la théorie de la file d'attente est l'établissement d'une relation entre la nature du flux d'applications, la performance d'un canal de service distinct, le nombre de canaux et l'efficacité du service.

Comme Caractéristiques QS considéré:

• le pourcentage moyen de candidatures qui sont rejetées et laissent le système sans service ;
• temps d'arrêt moyen des canaux individuels et du système dans son ensemble ;
• temps d'attente moyen dans la file d'attente ;
• la probabilité que l'application reçue soit immédiatement traitée ;
• loi de distribution de longueur de file d'attente et autres.

Nous ajoutons que les demandes (exigences) entrent dans le QS de manière aléatoire (à des moments aléatoires), avec des points de condensation et de raréfaction. Le temps de service de chaque exigence est également aléatoire, après quoi le canal de service est libéré et prêt à répondre à l'exigence suivante. Chaque QS, en fonction du nombre de canaux et de leurs performances, a une certaine capacité. Bande passante CMO Peut être absolu(nombre moyen de requêtes servies par unité de temps) et relatif(rapport moyen du nombre de demandes servies au nombre de soumissions).

3.1 Modèles de systèmes de files d'attente.

Chaque QS peut être caractérisé par l'expression : (a B c d e F) , où

un - répartition du flux entrant des candidatures ;

b - répartition du flux de sortie des candidatures ;

c – configuration du mécanisme de service;

ré – discipline de file d'attente;

e – bloc d'attente;

F est la capacité de la source.

Examinons maintenant de plus près chaque fonctionnalité.

Flux d'entrée des candidatures- le nombre de candidatures reçues par le système. Caractérisé par l'intensité du flux d'entrée je.

Flux de sortie des applications– le nombre d'applications desservies par le système. Caractérisé par l'intensité du flux de sortie m.

configuration du système implique nombre total canaux et points de service. SMO peut contenir :

1. un canal services (une piste, un fournisseur);
2. un canal de service, y compris plusieurs nœuds série(cantine, clinique, convoyeur);
3. plusieurs canaux similaires services connectés en parallèle (stations-service, bureau d'aide, gare).

Ainsi, les QS monocanal et multicanal peuvent être distingués.

D'autre part, si tous les canaux de service du QS sont occupés, l'application approchée peut rester dans la file d'attente ou quitter le système (par exemple, une caisse d'épargne et un central téléphonique). Dans ce cas, nous parlons de systèmes avec une file d'attente (en attente) et de systèmes avec des échecs.

Tour est un ensemble d'applications qui sont entrées dans le système pour le service et sont en attente de service. La file d'attente est caractérisée par la longueur de la file d'attente et sa discipline.

Discipline de la file d'attente est la règle de traitement des requêtes de la file d'attente. Les principaux types de files d'attente sont les suivants :

1. PERPPO (premier arrivé, premier servi) est le type le plus courant ;
2. POSPPO (dernier arrivé - premier servi);
3. SOP (sélection aléatoire d'applications) - à partir de la banque de données.
4. PR - service prioritaire.

Longueur de la file d'attente Peut être

• illimité - on parle alors d'un système à attente pure ;
• égal à zéro - alors ils parlent d'un système avec des échecs ;
• limité en longueur (système de type mixte).

bloc d'attente– "capacité" du système - le nombre total d'applications dans le système (dans la file d'attente et en service). De cette façon, e=c+ré.

Capacité source qui génère des demandes de service est le nombre maximum de demandes qui peuvent entrer dans le QS. Par exemple, dans un aéroport, la capacité de la source est limitée par le nombre de tous les avions existants, et la capacité de la source d'un central téléphonique est égale au nombre d'habitants de la Terre, c'est-à-dire il peut être considéré comme illimité.

Le nombre de modèles QS correspond au nombre de combinaisons possibles de ces composants.

3.2 Flux d'entrée des exigences.

Avec chaque période de temps un, un+ J ], associons une variable aléatoire X, égal au nombre de requêtes reçues par le système pendant le temps J.

Le flux de demandes est appelé Stationnaire, si la loi de distribution ne dépend pas du point initial de l'intervalle un, mais ne dépend que de la longueur de l'intervalle donné J. Par exemple, le flux des demandes au central téléphonique pendant la journée ( J\u003d 24 heures) ne peut pas être considéré comme stationnaire, mais de 13 à 14 heures ( J\u003d 60 minutes) - vous pouvez.

Le flux s'appelle pas de séquelle, si l'historique du flux n'affecte pas la réception des besoins dans le futur, c'est-à-dire les exigences sont indépendantes les unes des autres.

Le flux s'appelle ordinaire, si pas plus d'une requête ne peut entrer dans le système en très peu de temps. Par exemple, le flux vers le coiffeur est ordinaire, mais pas vers le bureau d'état civil. Mais si comme Variable aléatoire X considérer des paires de demandes entrant au bureau d'enregistrement, alors un tel flux sera ordinaire (c'est-à-dire qu'un flux extraordinaire peut parfois être réduit à un flux ordinaire).

Le flux s'appelle le plus simple, s'il est stationnaire, sans séquelle et ordinaire.

Théorème principal. Si le débit est le plus simple, alors le r.v. X [ un . un + J] est distribué selon la loi de Poisson, c'est-à-dire .

Corollaire 1. Le flux le plus simple est aussi appelé flux de Poisson.

Conséquence 2. M(X)= M(X [ un , un + J ] )= jeJ, c'est à dire. durant J jeJ applications. Ainsi, pour une unité de temps, le système reçoit en moyenne je applications. Cette valeur est appelée intensité flux d'entrée.

Considérez EXEMPLE .

Le studio reçoit en moyenne 3 candidatures par jour. En supposant que le flux soit le plus simple, trouvez la probabilité que le nombre de demandes soit d'au moins 5 dans les deux prochains jours.

La solution.

Selon la tâche, je=3, J=2 jours, flux d'entrée de Poisson, n ³5. lors de la résolution, il convient d'introduire l'événement inverse, qui consiste dans le fait que pendant le temps J moins de 5 candidatures seront reçues. Par conséquent, d'après la formule de Poisson, on obtient

^

3.3 État du système. Matrice et graphique des transitions.

A un moment aléatoire, le QS passe d'un état à un autre : le nombre de canaux occupés, le nombre de requêtes et de files d'attente... changent. Ainsi, le QS avec n canaux et une longueur de file d'attente égale à m, peut être dans l'un des états suivants :

E 0 – toutes les chaînes sont gratuites ;

E 1 – un canal est occupé;

E n– tous les canaux sont occupés;

E n +1 – tous les canaux sont occupés et une demande est dans la file d'attente;

E n + m– tous les canaux et toutes les places de la file d'attente sont occupés.

Un système similaire avec des échecs peut être dans des états E 0 – E n .

Pour un QS avec une espérance pure, il existe un ensemble infini d'états. De cette façon, condition E n QS à l'heure t est la quantité n applications (exigences) présentes dans le système à un moment donné, c'est-à-dire n= n(t) - valeur aléatoire, E n (t) sont les résultats de cette variable aléatoire, et P n (t) est la probabilité que le système soit dans l'état E n .

Nous connaissons déjà l'état du système. Notez que tous les états du système ne sont pas équivalents. L'état du système est appelé la source si le système peut quitter cet état mais ne peut pas y revenir. L'état du système est appelé isolé, si le système ne peut pas sortir ou entrer dans cet état.

Pour visualiser les images des états du système, on utilise des diagrammes (appelés graphes de transition), dans lesquels les flèches indiquent les transitions possibles du système d'un état à un autre, ainsi que les probabilités de telles transitions.

Figure 3.1 - graphe de transition

Comp.	E 0	E 1	E 2
E 0	P 0,0	P 0,1	P 0,2
E 1	P 1.0	R 1.1	R 1.2
E 2	R 2.0	R 2.2	R 2.2

Il est aussi parfois commode d'utiliser la matrice de transition. Dans ce cas, la première colonne signifie les états initiaux du système (courant), puis les probabilités de transition de ces états à d'autres sont données.

Puisque le système passera nécessairement d'un

état à un autre, alors la somme des probabilités de chaque ligne est toujours égale à un.

3.4 QS monocanal.

3.4.1 QS monocanal avec pannes.

Nous considérerons les systèmes qui répondent aux exigences:

(P/E/1):(–/1/¥) . Supposons également que le temps de service d'un client ne dépende pas du nombre de clients entrant dans le système. Ici et ci-dessous, "P" signifie que le flux d'entrée est distribué selon la loi de Poisson, c'est-à-dire le plus simple, "E" signifie que le flux de sortie est distribué de manière exponentielle. Aussi ici et ci-dessous, les principales formules sont données sans démonstration.

Pour un tel système, deux états sont possibles : E 0 - le système est gratuit et E 1 – le système est occupé. Créons une matrice de transition. Prenons rét est un temps infinitésimal. Soit l'événement A consister dans le fait que dans le système pendant le temps rét reçu une demande. L'événement B consiste dans le fait que pendant le temps rét une demande a été servie. Événement MAIS je , k- durant rét le système passera de l'état E je dans un état E k. Car je est l'intensité du flux d'entrée, puis pendant le temps rét entre dans le système en moyenne l*Dt conditions. Autrement dit, la probabilité de recevoir une réclamation P(A)=l* rét, et la probabilité de l'événement inverse Ð(À)=1-l*Dt.P(B)=F(rét)= P(b< ré t)=1- e - m ré t = m rét- la probabilité de répondre à la demande à temps rét. Ensuite, A 00 - la demande ne sera pas reçue ou sera reçue, mais sera signifiée. A 00 \u003d  + A * V. R 00 \u003d 1 - l*Dt. (nous avons pris en compte que (rét) 2 est une valeur infinitésimale)

A 01 - la demande sera reçue, mais ne sera pas signifiée. A 01 = A * . R 01 = l*Dt.

Et 10 - la demande sera servie et il n'y en aura pas de nouvelle. A 10 \u003d B * un. R 10 = Marylandt.

Et 11 - la demande ne sera pas servie ou une nouvelle arrivera qui n'a pas encore été servie. A 11 = +V * A. R 01 = 1- Marylandt.

Ainsi, on obtient la matrice de transition :

Comp.	E 0	E 1
E 0	1-l * Dt	je * Dt
E 1	m * Dt	1 m * Dt

Probabilité d'indisponibilité et de panne du système.

Trouvons maintenant la probabilité que le système soit dans l'état E 0 à tout moment t(ceux. R 0 ( t) ). Graphique de fonction
illustré à la figure 3.2.

L'asymptote du graphique est une droite
.

Évidemment, à partir d'un certain point t,

1

Illustration 3.2

On comprend enfin ça
et
, où R 1 (t) est la probabilité qu'au moment t le système est occupé (c'est-à-dire qu'il est dans un état E 1 ).

Il est évident qu'au début de l'opération QS, le processus en cours ne sera pas stationnaire : il s'agira d'un mode « transitoire », non stationnaire. Après un certain temps (qui dépend des intensités des flux d'entrée et de sortie), ce processus s'éteindra et le système passera à un état de fonctionnement stationnaire et stable, et les caractéristiques probabilistes ne dépendront plus du temps.

Mode de fonctionnement stationnaire et facteur de charge du système.

Si la probabilité que le système soit dans un état E k, c'est à dire. R k (t), ne dépend pas du temps t, alors ils disent que le QS a établi mode stationnaire travailler. Dans le même temps, la valeur
appelé facteur de charge du système(ou la densité réduite du flux de candidatures). Alors pour les probabilités R 0 (t) et R 1 (t) on obtient les formules suivantes :
,
. Vous pouvez également conclure : plus le facteur de charge du système est élevé, plus le système est susceptible de tomber en panne (c'est-à-dire la probabilité que le système soit occupé).

Le lave-auto a une unité pour l'entretien. Les voitures arrivent dans une distribution de Poisson avec un taux de 5 voitures/heure. Le temps de service moyen pour une voiture est de 10 minutes. Trouvez la probabilité qu'une voiture qui approche trouve le système occupé si le QS est en mode stationnaire.

La solution. Selon la tâche, je=5, m y =5/6. Il faut trouver la probabilité R 1 est la probabilité de défaillance du système.
.

3.4.2 QS monocanal avec longueur de file d'attente illimitée.

Nous considérerons les systèmes qui satisfont aux exigences : (Р/Е/1):(d/¥/¥). Le système peut être dans l'un des états E 0 , …, E k, … L'analyse montre qu'après un certain temps, un tel système commence à fonctionner en mode stationnaire si l'intensité du flux de sortie dépasse l'intensité du flux d'entrée (c'est-à-dire que le facteur de charge du système est inférieur à un). En tenant compte de cette condition, on obtient le système d'équations

résoudre ce que nous trouvons que. Ainsi, à condition que y<1, получим
Pour terminer,
et
est la probabilité que le QS soit dans l'état E kà un moment aléatoire.

Caractéristiques moyennes du système.

En raison de la réception inégale des exigences dans le système et des fluctuations du temps de service, une file d'attente se forme dans le système. Pour un tel système, vous pouvez explorer :

• n – le nombre d'exigences dans le QS (en file d'attente et en service);
• v – longueur de file d'attente;
• w – temps d'attente de début de service;
• w 0 est le temps total passé dans le système.

nous serons intéressés caractéristiques moyennes(c'est-à-dire que nous prenons valeur attendue sur les variables aléatoires considérées, et rappelez-vous que y<1).

est le nombre moyen d'applications dans le système.

est la longueur moyenne de la file d'attente.

est le temps d'attente moyen pour le début du service, c'est-à-dire temps d'attente en ligne.

- le temps moyen que l'application passe dans le système - dans la file d'attente et pour le service.

Au lave-auto, il y a un bloc pour le service et il y a une place pour la file d'attente. Les voitures arrivent dans une distribution de Poisson avec un taux de 5 voitures/heure. Le temps de service moyen pour une voiture est de 10 minutes. Trouvez toutes les caractéristiques QS moyennes.

La solution. je=5, m=60min/10min = 6. Facteur de charge y =5/6. Ensuite, le nombre moyen de voitures dans le système
, longueur moyenne de la file d'attente
, le temps d'attente moyen pour le démarrage du service
heures = 50 minutes, et enfin le temps moyen passé dans le système
heure.

3.4.3 QS monocanal de type mixte.

Supposons que la longueur de la file d'attente soit m conditions. Ensuite, pour tout s£ m, la probabilité de trouver le QS dans l'état E 1+ s, est calculé par la formule
, c'est à dire. une demande est servie et une autre s les candidatures sont dans la file d'attente.

La probabilité d'indisponibilité du système est
,

et la probabilité de défaillance du système est
.

Trois systèmes à canal unique sont donnés, pour chacun je=5, m =6. Mais le premier système est avec des échecs, le second avec une attente pure et le troisième avec une longueur de file d'attente limitée, m=2. Trouvez et comparez les probabilités d'indisponibilité de ces trois systèmes.

La solution. Pour tous les systèmes facteur de charge y=5/6. Pour un système avec des défaillances
. Pour un système avec une attente pure
. Pour un système avec une longueur de file d'attente limitée
. La conclusion est évidente : plus il y a d'applications dans la file d'attente, moins il y a de probabilité d'indisponibilité du système.

3.5 QS multicanal.

3.5.1 QS multicanal avec échecs.

Nous considérerons les systèmes (Р/Е/s):(-/s/¥) sous l'hypothèse que le temps de service ne dépend pas du flux d'entrée et que toutes les lignes fonctionnent indépendamment. Les systèmes multicanaux, en plus du facteur de charge, peuvent également être caractérisés par le coefficient
, où s– nombre de canaux de service. En explorant le QS multicanal, nous obtenons les formules suivantes (formules d'Erlang) pour la probabilité que le système soit dans l'état E k au hasard:

, k=0, 1, …

fonction de coût.

Comme pour les systèmes à canal unique, une augmentation du facteur de charge entraîne une augmentation de la probabilité de défaillance du système. D'autre part, une augmentation du nombre de lignes de service entraîne une augmentation de la probabilité d'indisponibilité du système ou des canaux individuels. Ainsi, il est nécessaire de trouver le nombre optimal de canaux de service pour ce QS. Le nombre moyen de lignes de service gratuites peut être trouvé par la formule
. Introduisons C( s) – fonction de coût QS en fonction de Avec 1 – le coût d'un refus (pénalité pour une demande non satisfaite) et de Avec 2 - le coût d'indisponibilité d'une ligne par unité de temps.

Pour trouver l'option optimale, vous devez trouver (et cela peut être fait) la valeur minimale de la fonction de coût : DE(s) = avec 1* je * p s +c 2*, dont le graphique est représenté sur la Figure 3.3 :

Illustration 3.3

La recherche de la valeur minimale de la fonction de coût consiste à trouver ses valeurs d'abord pour s =1, alors pour s =2, alors pour s =3, etc... jusqu'à ce qu'à un certain pas la valeur de la fonction С( s) ne sera pas plus grand que le précédent. Cela signifie que la fonction a atteint son minimum et a commencé à croître. La réponse est le nombre de canaux de service (valeur s) pour lequel la fonction de coût est minimale.

EXEMPLE .

Combien de lignes de service doivent contenir QS avec des échecs, si je\u003d 2reb / ​​​​heure, m\u003d 1reb / ​​​​heure, la pénalité pour chaque panne est de 7 000 roubles, le coût des temps d'arrêt pour une ligne est de 2 000 roubles. en heure ?

La solution. y = 2/1=2. Avec 1 =7, Avec 2 =2.

Supposons que le QS dispose de deux canaux de service, c'est-à-dire s =2. Alors
. Par conséquent, C(2) = c 1 *l*p 2 +c 2 *(2- y*(1-r 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Faisons comme si s =3. Alors
, C(3) = c 1 *l*p 3 +c 2 *
=5.79.

Supposons qu'il y ait quatre canaux, c'est-à-dire s =4. Alors
,
, C(4) = c 1 *l*p 4 +c 2 *
=5.71.

Supposons que le QS dispose de cinq canaux de service, c'est-à-dire s =5. Alors
, C(5) = 6,7 - plus que la valeur précédente. Par conséquent, le nombre optimal de canaux de service est de quatre.

3.5.2 QS multicanal avec file d'attente.

Nous considérerons les systèmes (Р/Е/s):(d/d+s/¥) sous l'hypothèse que le temps de service ne dépend pas du flux d'entrée et que toutes les lignes fonctionnent indépendamment. Nous dirons que le système s'est installé fonctionnement stationnaire, si le nombre moyen de sinistres entrants est inférieur au nombre moyen de sinistres servis sur toutes les lignes du système, c'est-à-dire je

P(w>0) est la probabilité d'attendre le démarrage du service,
.

La dernière caractéristique permet de résoudre le problème de la détermination du nombre optimal de canaux de service de telle manière que la probabilité d'attendre le début de service soit inférieure à un nombre donné. Pour cela, il suffit de calculer successivement la probabilité d'espérance pour s =1, s =2, s=3 etc...

EXEMPLE .

SMO - une station d'ambulance d'un petit microdistrict. je=3 appels par heure, et m= 4 appels par heure pour une équipe. Combien d'équipages doivent être à la station pour que la probabilité d'attendre une sortie soit inférieure à 0,01 ?

La solution. Facteur de charge du système y =0,75. Supposons qu'il y ait deux équipes disponibles. Trouvons la probabilité d'attendre que le service démarre à s =2.
,
.

Supposons qu'il y ait trois brigades, c'est-à-dire s=3. D'après les formules, on obtient que R 0 =8/17, P(w>0)=0.04>0.01 .

Supposons qu'il y ait quatre équipes à la station, c'est-à-dire s=4. Alors on obtient ça R 0 =416/881, P(w>0)=0.0077<0.01 . Par conséquent, il devrait y avoir quatre brigades à la station.

3.6 Questions pour la maîtrise de soi

1. Le sujet et les tâches de la théorie de la file d'attente.
2. QS, leurs modèles et désignations.
3. Flux d'entrée des exigences. L'intensité du flux d'entrée.
4. État du système. Matrice et graphique des transitions.
5. QS monocanal avec échecs.
6. QS monocanal avec file d'attente. Les caractéristiques.
7. Mode de fonctionnement stationnaire. Facteur de charge du système.
8. QS multicanal avec échecs.
9. Optimisation de la fonction de coût.
10. QS multicanal avec file d'attente. Les caractéristiques.

3.7 Exercices pour le travail indépendant

1. Le snack-bar de la station-service a un comptoir. Les voitures arrivent selon une distribution de Poisson, avec une moyenne de 2 voitures toutes les 5 minutes. En moyenne, 1,5 minutes suffisent pour finaliser une commande, même si la durée de service est répartie selon une loi exponentielle. Trouver : a) la probabilité que le décrochage soit inactif ; b) performances moyennes ; c) la probabilité que le nombre de voitures arrivant soit au moins 10.
2. L'appareil à rayons X permet d'examiner en moyenne 7 personnes par heure. L'intensité des visiteurs est de 5 personnes par heure. En supposant un fonctionnement stationnaire, déterminer les caractéristiques moyennes.
3. Le temps de service dans QS obéit à une loi exponentielle,
   m = 7besoins par heure. Trouvez la probabilité que a) le temps de service soit compris entre 3 et 30 minutes ; b) la réclamation sera signifiée dans l'heure. Utiliser le tableau des valeurs de fonction e X .
4. Il y a un poste à quai dans le port fluvial, l'intensité du flux d'entrée est de 5 navires par jour. L'intensité des opérations de chargement et de déchargement est de 6 navires par jour. En gardant à l'esprit le mode de fonctionnement stationnaire, déterminez toutes les caractéristiques moyennes du système.
5. je=3, m=2, la pénalité pour chaque panne est de 5 et le coût d'indisponibilité par ligne est de 2 ?
6. Quel est le nombre optimal de canaux de service qu'un QS devrait avoir si je=3, m =1, la pénalité pour chaque panne est de 7 et le coût d'indisponibilité par ligne est de 3 ?
7. Quel est le nombre optimal de canaux de service qu'un QS devrait avoir si je=4, m=2, la pénalité pour chaque panne est de 5 et le coût d'indisponibilité par ligne est de 1 ?
8. Déterminer le nombre de pistes pour les aéronefs, sous réserve que la probabilité d'attente soit inférieure à 0,05. Dans le même temps, l'intensité du flux entrant est de 27 avions par jour, et l'intensité de leur service est de 30 avions par jour.
9. De combien de lignes de convoyage indépendantes équivalentes un atelier doit-il disposer pour assurer un rythme de travail auquel la probabilité d'attente pour le traitement des produits doit être inférieure à 0,03 (chaque produit est fabriqué par une ligne). On sait que l'intensité de réception des commandes est de 30 produits par heure et que l'intensité de traitement d'un produit sur une ligne est de 36 produits par heure.
10. Une variable aléatoire continue X est distribuée selon une loi exponentielle de paramètre l=5. Trouvez la fonction de distribution, les caractéristiques et la probabilité de toucher la v.r. X compris entre 0,17 et 0,28.
11. Le nombre moyen d'appels arrivant au PBX en une minute est de 3. En supposant que le flux est de Poisson, trouvez la probabilité qu'en 2 minutes il y aura : a) deux appels ; b) moins de deux appels ; c) au moins deux appels.
12. Il y a 17 pièces dans une boîte dont 4 défectueuses. L'assembleur tire 5 pièces au hasard. Trouvez la probabilité que a) toutes les pièces extraites soient de haute qualité ; b) parmi les pièces extraites 3 défectueuses.
13. Combien de canaux un QS avec des échecs devrait-il avoir si je\u003d 2reb / ​​​​heure, m\u003d 1reb / ​​​​heure, la pénalité pour chaque panne est de 8 000 roubles, le coût des temps d'arrêt pour une ligne est de 2 000 roubles. en heure ?

Image 0 - 2 Flux d'événements (a) et flux le plus simple (b)

10.5.2.1. stationnarité

Le flux est dit stationnaire , si la probabilité de rencontrer tel ou tel nombre d'événements dans une période de temps élémentaire longueur τ (

Illustration 0-2 , un) dépend uniquement de la longueur de la section et ne dépend pas de l'endroit exact sur l'axe t cette zone est située.

La stationnarité du flux signifie son uniformité dans le temps ; les caractéristiques probabilistes d'un tel écoulement ne changent pas avec le temps. En particulier, la soi-disant intensité (ou "densité") du flux d'événements, le nombre moyen d'événements par unité de temps pour un flux stationnaire, doit rester constante. Ceci, bien sûr, ne signifie pas que le nombre réel d'événements apparaissant par unité de temps est constant ; le flux peut avoir des concentrations et des raréfactions locales. Il est important que pour un écoulement stationnaire ces concentrations et raréfactions ne soient pas régulières, et que le nombre moyen d'événements tombant sur un même intervalle de temps reste constant sur toute la période considérée.

En pratique, il existe souvent des flux d'événements qui (au moins pendant une période de temps limitée) peuvent être considérés comme stationnaires. Par exemple, le flux d'appels arrivant au central téléphonique, disons, dans l'intervalle de 12 à 13 heures peut être considéré comme stationnaire. Le même flux ne sera plus stationnaire toute une journée (la nuit, l'intensité du flux d'appels est bien moindre que le jour). Notez qu'il en va de même pour la plupart des processus physiques que nous appelons "stationnaires" en fait, ils ne sont stationnaires que pendant une période de temps limitée, et l'extension de cette période à l'infini n'est qu'une astuce pratique utilisée pour la simplification.

10.5.2.2. Pas de séquelle

Le flux des événements s'appelle un flux sans séquelle , si pour tout intervalle de temps non chevauchant, le nombre d'événements tombant sur l'un d'eux ne dépend pas du nombre d'événements tombant sur l'autre (ou sur d'autres, si plus de deux sections sont considérées).

Dans de tels flux, les événements qui forment le flux apparaissent à des instants successifs indépendamment les uns des autres. Par exemple, le flux de passagers entrant dans la station de métro peut être considéré comme un flux sans séquelle, car les raisons qui ont provoqué l'arrivée d'un passager individuel à ce moment particulier, et pas à un autre, en règle générale, ne sont pas liées à des raisons similaires pour les autres passagers. Si une telle dépendance apparaît, la condition d'absence de séquelle est violée.

Considérons, par exemple, le flux de trains de marchandises circulant sur une ligne de chemin de fer. Si, pour des raisons de sécurité, ils ne peuvent se succéder plus souvent qu'à des intervalles de temps t0 , il existe alors une dépendance entre les événements du flux et la condition d'absence d'effet secondaire n'est pas respectée. Cependant, si l'intervalle t0 est faible par rapport à l'intervalle moyen entre les trains, alors une telle violation est insignifiante.

Image 0 - 3 Loi de Poisson

Considérer sur l'axe t le flux le plus simple d'événements d'intensité λ. (Figure 0-2b) . On s'intéressera à un intervalle de temps aléatoire T entre événements adjacents dans ce flux ; trouver sa loi de distribution. Trouvons d'abord la fonction de distribution :

F(t) = P(T ( 0-2)

c'est-à-dire la probabilité que la valeur de T aura une valeur inférieure àt. Mis à part le début de l'intervalle T (points t0) segment t et trouver la probabilité que l'intervalle T sera moins t . Pour ce faire, il faut que pour une section de longueur t , adjacent à un point t0 , au moins un événement de thread atteint. Calculons la probabilité de cela F(t) par la probabilité de l'événement inverse (par segment t aucun événement de flux ne touchera) :

F (t) \u003d 1 - P 0

Probabilité P 0 on trouve par la formule (1), en supposantm = 0:

d'où la fonction de répartition de la valeur T sera :

(0-3)

Pour trouver la densité de distribution f(t) Variable aléatoire T, il faut différencier l'expression (0‑1) part:

0-4)

La loi de distribution de densité (0-4) est dite exponentielle (ou exponentielle ). La valeur λ est appelée le paramètre loi exemplaire.

Figure 0 - 4 Distribution exponentielle

Trouver les caractéristiques numériques d'une variable aléatoire J- espérance mathématique (valeur moyenne) M[t]=mt , et la dispersion D t . Nous avons

( 0-5)

(intégration par parties).

La dispersion de la valeur de T est :

(0-6)

En prenant la racine carrée de la variance, on trouve la moyenne écart-type Variable aléatoire T

Ainsi, pour une distribution exponentielle, l'espérance mathématique et l'écart type sont égaux et sont inverses du paramètre λ, où λ. l'intensité du flux.

Ainsi, l'apparition m événements dans un intervalle de temps donné correspond à la distribution de Poisson, et la probabilité que les intervalles de temps entre les événements soient inférieurs à un certain nombre prédéterminé correspond à la distribution exponentielle. Ce ne sont que des descriptions différentes du même processus stochastique.

Exemple QS-1 .

Prenons l'exemple d'un système bancaire en temps réel desservant un grand nombre de clients. Aux heures de pointe, les requêtes des caissiers qui travaillent avec les clients forment un flux de Poisson et arrivent en moyenne deux par 1 s (λ = 2).Le flux est constitué de requêtes arrivant au rythme de 2 requêtes par seconde.

Calculer la probabilité P ( m ) occurrences m messages en 1 s. Puisque λ = 2, à partir de la formule précédente, nous avons

Substituant m = 0, 1, 2, 3, on obtient les valeurs suivantes (jusqu'à quatredécimales):

Figure 0 - 5 Exemple de flux le plus simple

Plus de 9 messages en 1 s sont également possibles, mais la probabilité est très faible (environ 0,000046).

La distribution résultante peut être représentée sous forme d'histogramme (illustré sur la figure).

Exemple de CMO-2.

Un appareil (serveur) qui traite trois messages en 1s.

Soit un équipement capable de traiter trois messages en 1 s (µ=3). En moyenne, deux messages sont reçus en 1s, et conformément c Distribution de Poisson. Quelle proportion de ces messages sera traitée immédiatement après réception ?

La probabilité que le taux d'arrivée soit inférieur ou égal à 3 s est donnée par

Si le système peut traiter un maximum de 3 messages en 1 s, alors la probabilité qu'il ne soit pas surchargé est

En d'autres termes, 85,71 % des messages seront servis immédiatement et 14,29 % avec un certain retard. Comme vous pouvez le voir, un retard dans le traitement d'un message pendant un temps supérieur au temps de traitement de 3 messages se produira rarement. Le temps de traitement d'1 message est en moyenne de 1/3 s. Par conséquent, un retard supérieur à 1 s sera rare, ce qui est tout à fait acceptable pour la plupart des systèmes.

Exemple de CMO 3

· Si un caissier de banque est occupé pendant 80% de son temps de travail, et qu'il passe le reste du temps à attendre les clients, alors il peut être considéré comme un appareil avec un facteur d'utilisation de 0,8.

· Si le canal de communication est utilisé pour transmettre des symboles de 8 bits à un débit de 2400 bps, c'est-à-dire qu'un maximum de 2400/8 symboles sont transmis en 1 s, et que nous construisons un système dans lequel la quantité totale de données est de 12000 symboles envoyés de divers appareils via le canal par minute occupée (y compris la synchronisation, les caractères de fin de message, les caractères de contrôle, etc.), alors le taux d'utilisation des équipements du canal de communication pendant cette minute est égal à

· Si le moteur d'accès aux fichiers aux heures de pointe effectue 9 000 accès aux fichiers et que le temps par accès est de 300 ms en moyenne, l'utilisation du matériel du moteur d'accès aux heures de pointe est

Le concept d'utilisation de l'équipement sera utilisé assez souvent. Plus l'utilisation de l'équipement est proche de 100 %, plus le retard est important et plus la file d'attente est longue.

En utilisant la formule précédente, vous pouvez compiler des tables de valeurs de fonction de Poisson, à partir desquelles vous pouvez déterminer la probabilité de recevoirm ou plusieurs messages dans un laps de temps donné. Par exemple, si une moyenne de 3,1 messages par seconde [c'est-à-dire e.λ = 3.1], alors la probabilité de recevoir 5 messages ou plus dans une seconde donnée est de 0,2018 (pourm = 5 dans le tableau). Ou sous forme analytique

À l'aide de cette expression, l'analyste système peut calculer la probabilité que le système ne réponde pas à un critère de charge donné.

Souvent, des calculs initiaux peuvent être effectués pour les valeurs de charge de l'équipement.

p ≤ 0,9

Ces valeurs peuvent être obtenues à l'aide de tables de Poisson.

Soit à nouveau le taux d'arrivée moyen des messages λ = 3,1 messages/s. Il ressort des tableaux que la probabilité de recevoir 6 messages ou plus en 1 s est de 0,0943. Par conséquent, ce nombre peut être pris comme critère de charge pour les calculs initiaux.

10.6.2. Défis de conception

Avec la nature aléatoire de l'arrivée des messages sur l'appareil, ce dernier passe une partie du temps à traiter ou à traiter chaque message, ce qui entraîne la formation de files d'attente. La file d'attente à la banque attend la libération du caissier et de son ordinateur (terminal). La file d'attente des messages dans le tampon d'entrée de l'ordinateur attend d'être traitée par le processeur. La file d'attente des demandes de tableaux de données attend la libération des canaux, etc. Des files d'attente peuvent se former dans tous les goulots d'étranglement du système.

Plus le taux d'utilisation des équipements est élevé, plus les files d'attente résultantes sont longues. Comme on le verra ci-dessous, il est possible de concevoir un système qui fonctionne de manière satisfaisante avec un facteur d'utilisation de ρ = 0,7, mais un facteur supérieur à ρ > 0,9 peut entraîner une mauvaise qualité de service. En d'autres termes, si une liaison de données en bloc a une charge de 20 %, il est peu probable qu'elle ait une file d'attente. Si chargement ; est de 0,9, alors, en règle générale, des files d'attente se forment, parfois très grandes.

Le coefficient d'utilisation de l'équipement est égal au rapport de la charge de l'équipement sur la charge maximale que cet équipement peut supporter, ou est égal au rapport du temps d'occupation de l'équipement sur le temps total de son fonctionnement.

Lors de la conception d'un système, il est courant d'estimer le facteur d'utilisation pour différents types d'équipements ; des exemples pertinents seront donnés dans les chapitres suivants. La connaissance de ces coefficients permet de calculer les files d'attente pour les équipements correspondants.

· Quelle est la longueur de la file d'attente ?

· Combien de temps cela prendra?

On peut répondre à des questions de ce type en utilisant la théorie des files d'attente.

10.6.3. Les systèmes de file d'attente, leurs classes et leurs principales caractéristiques

Pour QS, les flux d'événements sont des flux de requêtes, des flux de requêtes "servicing", etc. Si ces flux ne sont pas de Poisson (processus de Markov), la description mathématique des processus intervenant dans QS devient incomparablement plus complexe et nécessite un appareillage plus encombrant, le ramener à des formules analytiques n'est possible que dans les cas les plus simples.

Cependant, l'appareil de la théorie des files d'attente "markovienne" peut également être utile dans le cas où le processus se produisant dans le QS est différent de celui de Markov ; avec son aide, les caractéristiques d'efficacité du QS peuvent être estimées approximativement. Il convient de noter que plus le QS est complexe, plus il contient de canaux de service, plus les formules approchées obtenues à l'aide de la théorie de Markov sont précises. De plus, dans un certain nombre de cas, pour prendre des décisions éclairées sur la gestion du fonctionnement du QS, il n'est pas du tout nécessaire d'avoir une connaissance exacte de toutes ses caractéristiques, souvent assez approximatives, indicatives.

Les QS sont classés en systèmes avec :

les échecs (avec pertes). Dans de tels systèmes, une demande qui arrive au moment où tous les canaux sont occupés reçoit un "refus", quitte le QS et ne participe pas au processus de service ultérieur.

attendre (avec file d'attente). Dans de tels systèmes, une demande qui arrive lorsque tous les canaux sont occupés est mise en file d'attente et attend jusqu'à ce que l'un des canaux se libère. Lorsque le canal est libre, l'une des applications de la file d'attente est acceptée pour le service.

Le service (discipline de file d'attente) dans un système d'attente peut être

ordonné (les demandes sont signifiées dans l'ordre de réception),

· désordonné(les demandes sont servies dans un ordre aléatoire) ou

empiler (la dernière application est sélectionnée en premier dans la file d'attente).

Priorité

o avec priorité statique

o avec priorité dynamique

(dans ce dernier cas a priori tet peut par exemple augmenter avec le temps d'attente de la requête).

Les systèmes avec une file d'attente sont divisés en systèmes

· avec attente illimitée et

· avec un nombre limité attendre.

Dans les systèmes à attente illimitée, chaque demande qui arrive au moment où il n'y a pas de canaux libres entre dans la file d'attente et attend "patiemment" la libération du canal qui l'acceptera pour le service. Toute demande reçue par le CMO sera tôt ou tard signifiée.

Dans les systèmes à attente limitée, certaines restrictions sont imposées au maintien de l'application dans la file d'attente. Ces restrictions peuvent s'appliquer

· la longueur de la file d'attente (le nombre d'applications simultanément dans le système de file d'attente avec une longueur de file d'attente limitée),

· le temps que l'application reste dans la file d'attente (après un certain temps de séjour dans la file d'attente, l'application sort de la file d'attente et le système sort avec un temps d'attente limité),

· temps total passé par l'application dans le QS

etc.

Selon le type de QS, lors de l'évaluation de son efficacité, certaines valeurs (indicateurs de performance) peuvent être utilisées. Par exemple, pour un QS avec des échecs, l'une des caractéristiques les plus importantes de sa productivité est la soi-disant bande passante absolue le nombre moyen de requêtes que le système peut traiter par unité de temps.

Avec l'absolu est souvent considéré débit relatif CMO est la part moyenne des requêtes entrantes servies par le système (le rapport du nombre moyen de requêtes traitées par le système par unité de temps au nombre moyen de requêtes reçues pendant cette période).

Outre les débits absolus et relatifs dans l'analyse des QS avec défaillances, on pourra, selon la tâche de l'étude, s'intéresser à d'autres caractéristiques, par exemple :

· nombre moyen de canaux occupés ;

· temps d'arrêt relatif moyen du système dans son ensemble et d'un canal individuel

etc.

Les QS en attente ont des caractéristiques légèrement différentes. Évidemment, pour un QS avec un temps d'attente illimité, les débits absolu et relatif perdent leur sens, puisque chaque réclamation arrive tôt.ou plus tard sera servi. Pour un tel QS, les caractéristiques importantes sont :

· le nombre moyen de candidatures dans la file d'attente ;

· le nombre moyen d'applications dans le système (en file d'attente et en service) ;

· temps d'attente moyen pour une application dans la file d'attente ;

· temps moyen passé par une application dans le système (en file d'attente et en service) ;

ainsi que d'autres caractéristiques de l'attente.

Pour un QS avec attente limitée, les deux groupes de caractéristiques sont intéressants : le débit absolu et relatif, et les caractéristiques d'attente.

Pour analyser le processus se produisant dans le QS, il est essentiel de connaître les principaux paramètres du système : le nombre de canaux P, intensité du débit d'applicationλ , les performances de chaque canal (le nombre moyen de requêtes µ servies par le canal par unité de temps), les conditions de constitution de la file d'attente (restrictions éventuelles).

En fonction des valeurs de ces paramètres, les caractéristiques de l'efficacité de fonctionnement QS sont exprimées.

10.6.4. Formules de calcul des caractéristiques QS pour le cas d'un service avec un seul appareil

Figure 0 - 6 Modèle d'un système de file d'attente avec une file d'attente

De telles files d'attente peuvent être créées par des messages en entrée du processeur en attente de traitement. Ils peuvent survenir lors du fonctionnement des postes d'abonnés connectés à un canal de communication multipoint. De même, des files de voitures se forment dans les stations-service. Cependant, s'il y a plus d'une entrée au service, nous avons une file d'attente avec de nombreux appareils et l'analyse devient plus compliquée.

Considérons le cas du flux le plus simple de demandes de service.

Le but de la théorie des files d'attente présentée ici est d'estimer la taille moyenne des files d'attente, ainsi que le temps moyen passé par les messages en attente dans les files d'attente. Il est également souhaitable d'estimer la fréquence à laquelle la file d'attente dépasse une certaine longueur. Ces informations nous permettront de calculer, par exemple, la quantité de mémoire tampon requise pour stocker les files d'attente de messages et les programmes associés, le nombre requis de lignes de communication, les tailles de tampon requises pour les concentrateurs, etc. Il sera possible d'estimer les temps de réponse.

Chacune des caractéristiques varie selon les moyens utilisés.

Considérez une file d'attente avec un seul serveur. Lors de la conception d'un système informatique, la plupart des files d'attente de ce type sont calculées à l'aide des formules ci-dessus. facteur de variation du temps de service

La formule de Khinchin-Polachek est utilisée pour calculer les longueurs de file d'attente dans la conception des systèmes d'information. Elle s'applique dans le cas d'une distribution exponentielle de l'heure d'arrivée pour toute distribution de temps de service et toute discipline de commande, tant que le choix du prochain message à desservir ne dépend pas de l'heure de service.

Lors de la conception de systèmes, il existe de telles situations où des files d'attente surviennent lorsque la discipline de contrôle dépend sans aucun doute du temps de service. Par exemple, dans certains cas, nous pouvons choisir d'utiliser d'abord des messages plus courts pour le service afin d'obtenir un temps de service moyen plus rapide. Lors de la gestion d'une ligne de communication, il est possible d'attribuer une priorité plus élevée aux messages d'entrée qu'aux messages de sortie, car les premiers sont plus courts. Dans de tels cas, il n'est plus nécessaire d'utiliser l'équation de Khinchin

La plupart des temps de service dans les systèmes d'information se situent quelque part entre ces deux cas. Les temps de service constants sont rares. Même le temps d'accès au disque dur n'est pas constant en raison de la position différente des tableaux de données sur la surface. Un exemple illustrant le cas du temps de service constant est l'occupation de la ligne de communication pour la transmission de messages d'une longueur fixe.

D'autre part, l'étalement du temps de service n'est pas aussi grand que dans le cas d'une distribution arbitraire ou exponentielle, c'est-à-dire,σs atteint rarement les valeurst s. Ce cas est parfois considéré comme le "pire des cas" et c'est pourquoi des formules sont utilisées qui se réfèrent à la distribution exponentielle des temps de service. Un tel calcul peut donner des tailles de file d'attente et des temps d'attente quelque peu surestimés, mais cette erreur n'est au moins pas dangereuse.

La distribution exponentielle des temps de service n'est certainement pas le cas le plus défavorable auquel on doit faire face dans la réalité. Cependant, si les temps de service issus du calcul des files d'attente s'avèrent être moins bien distribués que les temps exponentiellement distribués, c'est souvent un signal d'alarme pour le développeur. Si l'écart type est supérieur à la valeur moyenne, il est généralement nécessaire de corriger les calculs.

Prenons l'exemple suivant. Il existe six types de messages avec des durées de service de 15, 20, 25, 30, 35 et 300. Le nombre de messages pour chaque type est le même. L'écart type de ces temps est quelque peu supérieur à leur moyenne. La dernière valeur de temps de service est beaucoup plus grande que les autres. Cela entraînera des messages dans la file d'attente beaucoup plus longtemps que si les temps de service étaient du même ordre. Dans ce cas, lors de la conception, il est conseillé de prendre des mesures pour réduire la longueur de la file d'attente. Par exemple, si ces nombres sont liés à la longueur des messages, les messages très longs doivent peut-être être divisés en plusieurs parties.

10.6.6. Exemple de calcul

Lors de la conception d'un système bancaire, il est souhaitable de connaître le nombre de clients qui devront faire la queue pour un caissier pendant les heures de pointe.

Le temps de réponse du système et son écart type sont calculés en tenant compte du temps de saisie des données depuis le poste de travail, d'impression et de traitement des documents.

Les actions du caissier étaient chronométrées. Le temps de service ts est égal au temps total passé par le caissier chez le client. Le taux d'utilisation ρ du caissier est proportionnel à la durée de son emploi. Si λ est le nombre de clients aux heures de pointe, alors ρ pour le caissier est

Disons qu'il y a 30 clients par heure pendant les heures de pointe. En moyenne, un caissier passe 1,5 minutes par client. Alors

ρ = (1,5 * 30) / 60 = 0,75

c'est-à-dire que la caissière est utilisée à 75 %.

Le nombre de personnes en ligne peut être rapidement estimé à l'aide de graphiques. Il en résulte que si ρ = ​​0,75, alors le nombre moyen nq de personnesen ligne en caisse est compris entre 1,88 et 3,0 selon l'écart type pour t s .

Supposons que la mesure de l'écart type pour ts a donné une valeur de 0,5 min. Alors

σ s = 0,33 t s

D'après le graphique de la première figure, nous constatons que nq = 2,0, c'est-à-dire qu'en moyenne, deux clients attendront à la caisse.

Le temps total qu'un client passe à la caisse peut être trouvé comme

t ∑ = t q + t s = 2,5 min + 1,5 min = 4 min

où t s est calculé à l'aide de la formule de Khinchin-Polachek.

10.6.7. facteur de gain

En analysant les courbes des figures, on constate que lorsque l'équipement desservant la file d'attente est utilisé à plus de 80%, les courbes commencent à croître à un rythme alarmant. Ce fait est très important dans la conception des systèmes de transmission de données. Si nous concevons un système avec plus de 80% d'utilisation du matériel, une légère augmentation du trafic peut entraîner une baisse drastique des performances du système ou même le faire planter.

Une augmentation du trafic entrant d'un petit nombre de x %. entraîne une augmentation de la taille de la file d'attente d'environ

Si le taux d'utilisation des équipements est de 50%, alors cette augmentation est égale à 4ts% pour la distribution exponentielle du temps de service. Mais si l'utilisation de l'équipement est de 90 %, l'augmentation de la taille de la file d'attente est de 100 %, soit 25 fois plus. Une légère augmentation de la charge à 90 % d'utilisation de l'équipement entraîne une multiplication par 25 de la taille des files d'attente par rapport au cas d'une utilisation de l'équipement à 50 %.

De même, le temps d'attente augmente de

Avec un temps de service exponentiellement distribué, cette valeur vaut 4 t s2 pour une utilisation des équipements égale à 50% et 100 t s2 pour un coefficient de 90%, soit encore 25 fois pire.

De plus, pour les petits facteurs d'utilisation des équipements, l'effet des changements de σs sur la taille de la file d'attente est insignifiant. Cependant, pour les grands coefficients, le changement σ s affecte grandement la taille de la file d'attente. Par conséquent, lors de la conception de systèmes avec une utilisation élevée de l'équipement, il est souhaitable d'obtenir des informations précises sur le paramètreσ s. Inexactitude de l'hypothèse concernant l'exponentielle de la distribution de tsest plus perceptible aux grandes valeurs de ρ. De plus, si le temps de service augmente soudainement, ce qui est possible dans les canaux de communication lors de la transmission de messages longs, alors dans le cas d'un grand ρ, une file d'attente importante se forme.

Objet mathématique (abstrait) dont les éléments sont (Fig. 2.1):

• flux d'entrée (entrant) d'applications (exigences) pour le service ;
• dispositifs de service (canaux);
• une file d'attente d'applications en attente de service ;
• flux de sortie (sortant) des requêtes traitées ;
• le flux de demandes de suivi après interruption de service ;
• flux de demandes non satisfaites.

Demande(demande, exigence, appel, client, message, package) - un objet entrant dans le QS et nécessitant un service dans l'appareil. L'ensemble des applications consécutives réparties sous forme temporelle flux d'entrée des applications.

Riz. 2.1.

appareil de service(appareil, appareil, canal, ligne, outil, voiture, routeur, etc.) - élément QS, dont le but est de répondre aux demandes.

Service- retard de la demande dans l'appareil de service pendant un certain temps.

Durée de la prestation- temps de retard (service) de l'application dans l'appareil.

Périphérique de stockage(tampon, tampon d'entrée, tampon de sortie) - un ensemble de places pour attendre les applications devant le dispositif de service. Nombre de places d'attente - capacité de stockage.

Une candidature reçue par le CMO peut être dans deux états :

• 1) service(dans l'appareil);
• 2) attentes(dans l'accumulateur), si tous les appareils sont occupés à répondre à d'autres requêtes.

Les réclamations dans l'accumulateur et le formulaire de service en attente tour applications. Le nombre d'applications dans l'accumulateur en attente de service - longueur de la file d'attente.

Discipline tampon(discipline de mise en file d'attente) - la règle d'entrée des applications entrantes dans le lecteur (tampon).

Discipline de service- la règle de sélection des demandes de la file d'attente pour le service dans l'appareil.

Une priorité- droit de préemption (pour capturer des ressources) pour entrer dans l'accumulateur ou sélectionner dans la file d'attente pour le service dans les applications de l'appareil d'une classe par rapport aux applications des autres classes.

Il existe de nombreux systèmes de file d'attente qui diffèrent par leur organisation structurelle et fonctionnelle. Dans le même temps, le développement de méthodes analytiques pour calculer les indicateurs de performance QS implique dans de nombreux cas un certain nombre de restrictions et d'hypothèses qui réduisent l'ensemble des QS à l'étude. C'est pourquoi il n'existe pas de modèle analytique général pour une structure complexe arbitraire QS.

Le modèle analytique QS est un ensemble d'équations ou de formules qui permettent de déterminer les probabilités des états du système au cours de son fonctionnement et des indicateurs de performance en fonction des paramètres connus des flux entrants et des canaux de service, de la mise en mémoire tampon et des disciplines de service.

La modélisation analytique du QS est grandement facilitée si les processus intervenant dans le QS sont markoviens (le flux des applications est le plus simple, les temps de service sont distribués de façon exponentielle). Dans ce cas, tous les processus du QS peuvent être décrits par des équations différentielles ordinaires, et dans le cas limite - pour les états stationnaires - par des équations algébriques linéaires et, après les avoir résolues par toutes les méthodes disponibles dans les progiciels mathématiques, déterminer les indicateurs de performance sélectionnés .

Dans les systèmes de messagerie instantanée, lors de la mise en œuvre de QS, les restrictions et hypothèses suivantes sont acceptées :

• demande saisie dans le système immédiatement entre en service s'il n'y a pas de requêtes dans la file d'attente et que l'appareil est libre ;
• dans l'appareil pour l'entretien à tout moment ne peut être une demande;
• après la fin du service de toute demande dans le dispositif, la demande suivante est sélectionnée dans la file d'attente pour un service instantané, c'est-à-dire le dispositif ne tourne pas au ralenti s'il y a au moins une application dans la file d'attente ;
• la réception des candidatures dans le QS et la durée de leur service ne dépendent pas du nombre de candidatures déjà dans le système, ni de tout autre facteur ;
• la durée des demandes de service ne dépend pas de l'intensité des demandes entrant dans le système.

Arrêtons-nous plus en détail sur certains éléments de QS.

Flux d'entrée (entrant) des candidatures. Le flux des événements s'appelle une séquence d'événements homogènes se succédant les uns aux autres et se produisant dans certains, d'une manière générale, Aléatoire points dans le temps. Si l'événement consiste en l'apparition de sinistres, on a flux de candidature. Pour décrire le flux des candidatures dans cas général il est nécessaire de définir des intervalles de temps t = t k - t k-1 entre moments adjacents t k _ k et t k réception des demandes avec numéros de série à - 1 et à respectivement (à - 1, 2, ...; t 0 - 0 - instant initial).

La principale caractéristique du flux de candidature est sa Intensité X- le nombre moyen de candidatures arrivant à l'entrée du QS par unité de temps. Valeur t = 1 FOIS définit l'intervalle de temps moyen entre deux commandes consécutives.

Le flux s'appelle déterministe si intervalles de temps t à entre applications adjacentes prennent certaines valeurs pré-connues. Si les intervalles sont les mêmes (x à= t pour tout k = 1, 2, ...), alors le flux est appelé habituel. Pour une description complète du flux régulier de demandes, il suffit de paramétrer l'intensité du flux X soit la valeur de l'intervalle t = 1 FOIS.

Un flux dans lequel des intervalles de temps x k entre les applications adjacentes sont des variables aléatoires, appelées Aléatoire. Pour une description complète d'un flux aléatoire d'applications dans le cas général, il est nécessaire de fixer les lois de distribution F fc (x fc) pour chacun des intervalles de temps x k, k = 1,2,....

Flux aléatoire dans lequel tous les intervalles de temps x b x 2,... entre clients consécutifs adjacents sont des variables aléatoires indépendantes décrites par des fonctions de distribution FjCij), F 2 (x 2), ... respectivement, est appelé un flux avec séquelle limitée.

Le flux aléatoire est appelé récurrent, si tous les intervalles de temps x b t 2 , ... distribué entre les applications sous la même loi F(t). Il existe de nombreux flux récurrents. Chaque loi de distribution génère son propre flux récurrent. Les flux récurrents sont également connus sous le nom de flux Palm.

Si l'intensité X et la loi de distribution F(t) des intervalles entre requêtes successives ne change pas avec le temps, alors le flux de requêtes est appelé Stationnaire Sinon, le flux de candidature est non stationnaire.

Si à chaque instant t k un seul client peut apparaître en entrée du QS, alors le flux de clients est appelé ordinaire. Si plusieurs candidatures peuvent apparaître à tout moment, le flux des candidatures est extraordinaire, ou groupe.

Le flux de demandes s'appelle un flux aucune séquelle, si les candidatures sont reçues quel que soit les uns des autres, c'est-à-dire le moment de réception de la prochaine candidature ne dépend pas du moment et du nombre de candidatures reçues avant ce moment.

Un écoulement ordinaire stationnaire sans séquelle est appelé le plus simple.

Les intervalles de temps t entre les requêtes dans le flux le plus simple sont distribués selon exponentiel (exemplaire) droit: avec fonction de répartition F(t) = 1 - e~m; densité de distribution/(f) = Hé~"l, où X > 0 - paramètre de distribution - l'intensité du flux de candidatures.

Le flux le plus simple est souvent appelé Poisson. Le nom vient du fait que pour ce flux la probabilité P fc (At) d'occurrence exactement à demandes pour un certain intervalle de temps At est déterminé Loi de Poisson :

A noter que le flux de Poisson, contrairement au plus simple, peut être :

• Stationnaire, si intensité X ne change pas avec le temps;
• non stationnaire, si le débit dépend du temps : X= >.(t).

En même temps, le flux le plus simple, par définition, est toujours stationnaire.

Les études analytiques des modèles de file d'attente sont souvent menées sous l'hypothèse du flux de requêtes le plus simple, ce qui est dû à un certain nombre de caractéristiques remarquables qui lui sont inhérentes.

1. Sommation (unification) des flux. Le flux le plus simple de la théorie QS est similaire à la loi de distribution normale de la théorie des probabilités : le passage à la limite pour un flux qui est la somme de flux avec des caractéristiques arbitraires avec une augmentation infinie du nombre de termes et une diminution de leur intensité conduit au flux le plus simple.

Somme Nécoulements ordinaires stationnaires indépendants avec des intensités x x x 2 ,..., XN forme le flux le plus simple avec intensité

X=Y,^ià condition que les flux ajoutés aient plus ou

moins d'impact tout aussi faible sur le débit total. En pratique, le débit total est proche du plus simple à N > 5. Alors lors de la sommation des flux les plus simples indépendants, le flux total sera le plus simple pour n'importe quelle valeur N

• 2. Raréfaction probabiliste du flux. probabiliste(mais non déterministe) raréfaction le flux le plus simple applications, dans lesquelles toute application au hasard avec une certaine probabilité R est exclue du flux, que d'autres applications soient exclues ou non, conduit à la formation le flux le plus simple avec intensité X* = pX, où X- intensité du flux initial. Le flux des candidatures exclues avec intensité X** = (1 - p)X- aussi protozoaire couler.
• 3. Efficacité. Si les canaux de diffusion (appareils) sont conçus pour le flux le plus simple de demandes avec intensité X, puis la desserte d'autres types de flux (avec la même intensité) sera assurée avec non moins d'efficacité.
• 4. Simplicité. L'hypothèse du flux d'applications le plus simple permet à de nombreux modèles mathématiques d'obtenir sous une forme explicite la dépendance des indicateurs QS aux paramètres. Le plus grand nombre les résultats analytiques ont été obtenus pour le flux le plus simple d'applications.

L'analyse de modèles avec des flux applicatifs différents des plus simples complique généralement les calculs mathématiques et ne permet pas toujours d'obtenir une solution analytique explicite. Le flux "le plus simple" tire son nom précisément de cette fonctionnalité.

Les applications peuvent avoir des droits différents pour démarrer le service. Dans ce cas, les applications sont dites hétérogène. Les avantages de certains flux d'applications par rapport à d'autres en début de service sont fixés par des priorités.

Une caractéristique importante du flux d'entrée est le coefficient de variation

où t int - espérance mathématique de la longueur de l'intervalle ; sur- écart type de la longueur de l'intervalle x int (variable aléatoire) .

Pour le flux le plus simple (a = -, m = -) nous avons v = 1. Pour la plupart

flux réels 0

Canaux de service (appareils). La principale caractéristique de la chaîne est la durée de service.

Durée de la prestation- le temps passé par l'application dans l'appareil - dans le cas général, la valeur est aléatoire. Dans le cas d'une charge inhomogène du QS, la durée des demandes de service différentes classes peuvent différer dans les lois de distribution ou seulement dans les valeurs moyennes. Dans ce cas, on suppose généralement que les temps de service pour les demandes de chaque classe sont indépendants.

Souvent, les praticiens supposent que la durée des demandes de service est répartie sur loi exponentielle ce qui simplifie grandement les calculs analytiques. Cela est dû au fait que les processus se produisant dans les systèmes avec une distribution exponentielle des intervalles de temps sont Markov processus :

où c- intensité de service, ici p = _--; t 0 bsl - maths-

tic temps d'attente pour le service.

En plus de la distribution exponentielle, il existe des distributions Erlang /c, des distributions hyperexponentielles, des distributions triangulaires et quelques autres. Ceci ne doit pas nous dérouter, puisqu'il est montré que la valeur du critère d'efficacité QS dépend peu de la forme de la loi de distribution du temps de service.

Dans l'étude du QS, l'essence du service, la qualité du service, n'est plus prise en compte.

Les chaînes peuvent être absolument fiable ceux. n'échouez pas. Au contraire, il peut être accepté dans l'étude. Les chaînes peuvent avoir fiabilité ultime. Dans ce cas, le modèle QS est beaucoup plus compliqué.

L'efficacité QS dépend non seulement des paramètres des flux d'entrée et des canaux de service, mais également de la séquence dans laquelle les demandes entrantes sont traitées, c'est-à-dire des moyens de gérer le flux des applications lorsqu'elles entrent dans le système et sont envoyées pour service.

Les modalités de gestion du flux de candidatures sont déterminées par les disciplines :

• mise en mémoire tampon ;
• service.

Les disciplines de tamponnage et de maintenance peuvent être classées selon les critères suivants :

• disponibilité des priorités entre les applications de différentes classes ;
• un procédé pour pousser les applications hors de la file d'attente (pour les disciplines de mise en mémoire tampon) et attribuer des demandes de service (pour les disciplines de service) ;
• une règle de préemption ou de sélection des demandes de service ;
• capacité à changer les priorités.

Une variante de la classification des disciplines de mise en mémoire tampon (file d'attente) conformément aux caractéristiques énumérées est illustrée à la fig. 2.2.

En fonction de la disponibilité ou manque de priorités entre les applications de différentes classes, toutes les disciplines tampons peuvent être divisées en deux groupes : non prioritaires et prioritaires.

Par méthode de poussée des applications hors du stockage les classes suivantes de disciplines tampons peuvent être distinguées:

• sans évincer les demandes - les demandes qui sont entrées dans le système et qui ont trouvé que le lecteur était complètement rempli sont perdues ;
• avec le déplacement de l'application de cette classe, c'est-à-dire la même classe que la demande reçue ;
• avec le déplacement de l'application de la classe de priorité la plus basse ;
• avec le déplacement de l'application du groupe des classes de faible priorité.

Riz. 2.2.

Les disciplines tampons peuvent utiliser les éléments suivants règles d'expulsion des requêtes de l'accumulateur :

• déplacement accidentel;
• exclusion de la dernière commande, c'est-à-dire entré dans le système plus tard que tous ;
• l'éviction d'une commande "longue", c'est-à-dire situé dans l'accumulateur plus longtemps que toutes les demandes reçues précédemment.

Sur la fig. 2.3 montre la classification des disciplines pour les applications de maintenance selon les mêmes caractéristiques que pour les disciplines de mise en mémoire tampon.

Parfois, la capacité de stockage des modèles est considérée comme illimitée, alors que dans un système réel, elle est limitée. Une telle hypothèse est justifiée lorsque la probabilité de perdre une commande dans un système réel à cause d'un débordement de capacité de stockage est inférieure à 10 _3 . Dans ce cas, la discipline n'a pratiquement aucun effet sur la performance des requêtes.

En fonction de la disponibilité ou manque de priorités entre les demandes de classes différentes, toutes les disciplines de service, ainsi que les disciplines tampons, peuvent être divisées en deux groupes : non prioritaires et prioritaires.

Par comment les tickets de service sont attribués les disciplines de service peuvent être divisées en disciplines :

• mode unique ;
• mode groupe ;
• mode combiné.

Riz. 2.3.

Dans les disciplines de service mode unique service à chaque fois un seul assigné requête, pour laquelle les files d'attente sont analysées après la fin du traitement de la requête précédente.

Dans les disciplines de service mode groupe service à chaque fois un groupe de requêtes est affecté une file d'attente, pour laquelle les files d'attente sont analysées uniquement après que toutes les demandes du groupe précédemment affecté ont été traitées. Le groupe de tickets nouvellement attribué peut comprendre tous les tickets de la file d'attente donnée. Demandes de groupe assignées séquentiellement sélectionné dans la file d'attente et sont desservis par le dispositif, après quoi le groupe suivant d'applications d'une autre file d'attente est affecté pour le service conformément à la discipline de service spécifiée.

Mode combiné- une combinaison des modes simple et groupe, lorsqu'une partie des files d'attente de demandes est traitée en mode simple et l'autre partie - en mode groupe.

Les disciplines de service peuvent utiliser règles suivantes sélection des demandes de service.

Non prioritaire(les applications n'ont pas de privilèges de service anticipé - capture de ressources) :

• service premier arrivé premier servi FIFO (premier en -premier sorti, premier entré, premier sorti)
• service inverse- l'application est sélectionnée dans la file d'attente en mode LIFO (dernier dans - premier sorti, dernier entré, premier sorti)
• service aléatoire- l'application est sélectionnée dans la file d'attente en mode RAND (Aléatoire- au hasard);
• service cyclique- les applications sont sélectionnées dans le processus d'interrogation cyclique des lecteurs dans l'ordre 1, 2, H DE H- le nombre de lecteurs), après quoi la séquence spécifiée est répétée ;

Priorité(les applications ont des privilèges pour le service précoce - capture de ressources) :

• Avec priorités relatives- si en cours entretien courant les applications avec des priorités plus élevées entrent dans le système, le service de l'application actuelle même non prioritaire n'est pas interrompu et les applications reçues sont envoyées dans la file d'attente; les priorités relatives ne jouent un rôle qu'à la fin du service courant de l'application lorsqu'une nouvelle demande de service est sélectionnée dans la file d'attente.
• Avec priorités absolues- à réception d'une requête de haute priorité, le service d'une requête de faible priorité est interrompu et la requête reçue est envoyée pour traitement ; une application interrompue peut être renvoyée dans la file d'attente ou supprimée du système ; si l'application est renvoyée dans la file d'attente, son service ultérieur peut être exécuté à partir de l'endroit interrompu ou à nouveau ;
• co priorités mixtes- des restrictions strictes sur le temps d'attente dans la file d'attente pour le traitement des applications individuelles nécessitent de leur attribuer des priorités absolues ; en conséquence, le temps d'attente pour les applications à faible priorité peut s'avérer trop long, bien que les applications individuelles aient une marge de temps d'attente ; pour respecter les restrictions sur tous les types de requêtes, ainsi que les priorités absolues, certaines requêtes peuvent se voir attribuer des priorités relatives, et les autres peuvent être servies en mode non prioritaire ;
• Avec priorités alternées- un analogue des priorités relatives, la priorité n'est prise en compte qu'aux moments d'achèvement du service en cours d'un groupe de demandes d'une file d'attente et d'affectation d'un nouveau groupe pour le service ;
• service programmé- les réclamations de différentes classes (situées dans différents stockages) sont sélectionnées pour le service selon un certain calendrier qui spécifie la séquence d'interrogation des files d'attente d'applications, par exemple, dans le cas de trois classes d'applications (magasins), le calendrier peut regarder comme (2, 1, 3, 3, 1, 2) ou (1, 2, 3, 3, 2, 1).

Dans les systèmes de messagerie instantanée informatique, en règle générale, la discipline est implémentée par défaut FIFO. Cependant, ils disposent d'outils qui offrent à l'utilisateur la possibilité d'organiser les disciplines de service dont il a besoin, y compris en fonction de l'horaire.

Les demandes reçues par le CMO sont divisées en catégories. Dans QS, qui est un résumé modèle mathématique, les candidatures sont pour différentes classes dans le cas où ils diffèrent dans le système réel simulé par au moins l'un des les signes suivants:

• durée de service;
• priorités.

Si les applications ne diffèrent pas par leur durée de service et leurs priorités, elles peuvent être représentées par des applications de même classe, y compris lorsqu'elles proviennent de sources différentes.

Pour une description mathématique des disciplines de service avec des priorités mixtes, nous utilisons matrice de priorité, représentant Matrice Carrée Q = (q, ;), je, j - 1,..., I, I - le nombre de classes d'applications entrant dans le système.

Élément q(j la matrice définit la priorité des demandes de classe je en ce qui concerne les demandes de classe ; et peut prendre les valeurs suivantes :

• 0 - pas de priorité ;
• 1 - priorité relative ;
• 2 - priorité absolue.

Les éléments de la matrice de priorité doivent satisfaire aux critères suivants conditions:

• q n= 0, car aucune priorité ne peut être définie entre les requêtes de la même classe ;
• si q (j = 1 ou 2 alors q^ = 0, puisque si applications de classe je prendre le pas sur les demandes de cours j, alors ces derniers ne peuvent prévaloir sur les prétentions de classe je (je, j = 1, ..., I).

En fonction de la opportunités de changer les priorités Lors de l'exploitation du système, les disciplines prioritaires de la mise en mémoire tampon et de l'entretien sont divisées en deux classes :

• 1) avec priorités statiques, qui ne changent pas avec le temps ;
• 2) avec priorités dynamiques, qui peut changer pendant le fonctionnement du système en fonction de divers facteurs, par exemple, lorsqu'une certaine valeur critique de la longueur de la file d'attente des applications d'une classe qui n'a pas de priorité ou qui a une priorité faible est atteinte, on peut lui attribuer une valeur plus élevée priorité.

Dans les systèmes informatiques de messagerie instantanée, il existe nécessairement un seul élément (objet) par lequel, et uniquement par lui, les demandes sont entrées dans le modèle. Par défaut, toutes les candidatures saisies sont non prioritaires. Mais il existe des possibilités d'assigner des priorités dans la séquence 1, 2, ..., y compris lors de l'exécution du modèle, c'est-à-dire en dynamique.

Flux sortant est le flux de requêtes traitées quittant le QS. Dans les systèmes réels, les applications passent par plusieurs QS : communication de transit, pipeline de production, etc. Dans ce cas, le flux sortant est le flux entrant pour le prochain QS.

Le flux entrant du premier QS, ayant traversé les QS suivants, est déformé, ce qui complique la modélisation analytique. Cependant, il convient de garder à l'esprit que avec le flux d'entrée le plus simple et le service exponentiel(ceux. dans les systèmes de Markov), le flux de sortie est également le plus simple. Si le temps de service a une distribution non exponentielle, alors le flux sortant n'est non seulement pas simple, mais également non récurrent.

Notez que les intervalles de temps entre les requêtes sortantes ne sont pas les mêmes que les intervalles de service. Après tout, il se peut qu'après la fin du prochain service, le QS soit inactif pendant un certain temps en raison du manque d'applications. Dans ce cas, l'intervalle de flux sortant se compose du temps d'inactivité du QS et de l'intervalle de service de la première demande arrivée après le temps d'arrêt.

Dans le QS, en plus du flux sortant de demandes traitées, il peut y avoir flux de demandes non satisfaites. Si un tel QS reçoit un flux récurrent, et que le service est exponentiel, alors le flux de clients non desservis est également récurrent.

Files d'attente de chaînes gratuites. Dans le QS multicanal, des files d'attente de canaux libres peuvent être formées. Le nombre de canaux libres est une valeur aléatoire. Les chercheurs pourraient être intéressés diverses caractéristiques cette variable aléatoire. En règle générale, il s'agit du nombre moyen de canaux occupés par le service par intervalle d'enquête et de leurs facteurs de charge.

Comme nous l'avons noté précédemment, dans les objets réels, les requêtes sont traitées séquentiellement dans plusieurs QS.

Un ensemble fini de QS séquentiellement interconnectés qui traitent les applications qui y circulent est appelé réseau de file d'attente (Sémo) (figure 2.4, un).

Riz. 2.4.

SEMO est aussi appelé QS multiphase.

Nous examinerons un exemple de construction d'un QEMO IM plus tard.

Les principaux éléments de QS sont les nœuds (U) et les sources (générateurs) de requêtes (G).

Nouer les réseaux sont un système de file d'attente.

La source- un générateur d'applications entrant dans le réseau et nécessitant certaines étapes de service dans les nœuds du réseau.

Un graphique est utilisé pour une image simplifiée de QEMO.

Comte Semo - Graphique dirigé(digraphe), dont les sommets correspondent aux nœuds QEM, et les arcs représentent les transitions d'applications entre les nœuds (Fig. 2.4, b).

Ainsi, nous avons considéré les concepts de base de QS. Mais dans le développement des systèmes informatiques pour la GI et leur amélioration, l'énorme potentiel créatif actuellement contenu dans la modélisation analytique des QS est aussi nécessairement utilisé.

Pour une meilleure compréhension de ce la créativité en première approximation, arrêtons-nous sur la classification des modèles QS.

Ci-dessous, nous examinerons des exemples des systèmes de file d'attente (QS) les plus simples. Le concept de "simple" ne signifie pas "élémentaire". Les modèles mathématiques de ces systèmes sont applicables et utilisés avec succès dans les calculs pratiques.

SMO monocanal avec échecs

Donné: le système dispose d'un canal de service, qui reçoit le flux de demandes le plus simple avec intensité. Le flux de services a une intensité. Une requête qui trouve le système occupé le quitte immédiatement.

Trouver: le débit absolu et relatif du QS et la probabilité qu'une réclamation arrivant à l'instant t soit rejetée.

Le système pour tout t> 0 peut être dans deux états : S 0 – le canal est libre ; S 1 - le canal est occupé. Transition de S 0 dans S 1 est associé à l'apparition d'une requête et au démarrage immédiat de son service. Transition de S 1 po S 0 est effectué dès que le prochain entretien est terminé (Fig. 4).

Fig.4. Graphique des états d'un QS monocanal avec pannes

Les caractéristiques de sortie (caractéristiques d'efficacité) de ce QS et d'autres seront données sans conclusions ni preuves.

Bande passante absolue(nombre moyen de candidatures servies par unité de temps) :

où - l'intensité du flux de candidatures (l'inverse de l'intervalle de temps moyen entre les candidatures entrantes -);

– l'intensité du flux de services (l'inverse du temps moyen de service)

Bande passante relative(part moyenne des applications desservies par le système) :

Probabilité d'échec(probabilité que la demande laisse le CMO non servi):

Les relations suivantes sont évidentes : i.

Exemple. Le système technologique se compose d'une machine. La machine reçoit des applications pour la fabrication de pièces en moyenne 0,5 heure. Le temps moyen de fabrication d'une pièce est égal. Si la machine est occupée lorsqu'une demande de fabrication d'une pièce est reçue, alors elle (la pièce) est envoyée à une autre machine. Trouvez le débit absolu et relatif du système et la probabilité de défaillance dans la fabrication de la pièce.

Ceux. en moyenne, environ 46 % des pièces sont traitées sur cette machine.

.

Ceux. en moyenne, environ 54 % des pièces sont envoyées vers d'autres machines pour traitement.

N - canal smo avec échecs (problème Erlang)

C'est l'un des premiers problèmes de la théorie des files d'attente. Il est né des besoins pratiques de la téléphonie et a été résolu au début du XXe siècle par le mathématicien danois Erlang.

Donné: le système a n– les canaux qui reçoivent un flux de requêtes avec intensité. Le flux de services a une intensité. Une requête qui trouve le système occupé le quitte immédiatement.

Trouver: capacité absolue et relative de QS ; la probabilité qu'une commande arrive à un moment t, sera refusé ; le nombre moyen de requêtes servies simultanément (ou, en d'autres termes, le nombre moyen de canaux occupés).

La solution. État du système S(QS) est numéroté en fonction du nombre maximum de requêtes dans le système (il coïncide avec le nombre de canaux occupés) :

S 0 - il n'y a pas de candidatures dans le CMO ;

S 1 - il y a une demande dans le QS (un canal est occupé, les autres sont libres) ;

S 2 - il y a deux applications dans le QS (deux canaux sont occupés, les autres sont libres) ;

S n - dans le QS est n- candidatures (toutes n– les canaux sont occupés).

Le graphique d'état QS est illustré à la fig. 5

Fig.5 Graphe d'état pour QS canal n avec échecs

Pourquoi le graphe d'état est-il marqué de cette façon ? Hors de l'état S 0 pour indiquer S 1 le système est transféré par un flux de candidatures avec intensité (dès qu'une candidature arrive, le système bascule de S 0 dans S une). Si le système était dans l'état S 1 et qu'une autre requête est arrivée, elle passe à l'état S 2 etc

Pourquoi de telles intensités pour les flèches inférieures (arcs du graphe) ? Que le système soit dans l'état S 1 (un canal fonctionne). Il produit des services par unité de temps. Par conséquent, la transition passe de l'état S 1 par état S 0 est chargé d'intensité. Maintenant, laissez le système être dans l'état S 2 (deux canaux fonctionnent). Pour qu'elle aille S 1 , vous devez terminer le service du premier canal ou du second. L'intensité totale de leurs flux est égale à, etc.

Les caractéristiques de sortie (caractéristiques d'efficacité) d'un QS donné sont définies comme suit.

Absoludébitaptitude:

où n– nombre de canaux QS;

est la probabilité que le QS soit dans l'état initial lorsque tous les canaux sont libres (la probabilité finale que le QS soit dans l'état S 0);

Fig.6. Graphe d'état pour le schéma de décès et de reproduction

Afin d'écrire une formule pour déterminer , considérons la Fig. 6

Le graphe représenté sur cette figure est également appelé graphe d'état pour le schéma « mort et reproduction ». Écrivons d'abord la formule générale de (sans preuve) :

Soit dit en passant, les probabilités finales restantes des états QS s'écriront comme suit.

S 1 lorsqu'un canal est occupé :

La probabilité que le QS soit dans l'état S 2, c'est-à-dire lorsque deux canaux sont occupés :

La probabilité que le QS soit dans l'état S n , c'est-à-dire lorsque tous les canaux sont occupés.

Maintenant pour QS canal n avec échecs

Débit relatif :

Rappelons qu'il s'agit de la part moyenne des applications desservies par le système. Où

Probabilitééchec:

Rappelez-vous qu'il s'agit de la probabilité que l'application laisse le CMO non desservi. Il est évident que .

Nombre moyen de canaux occupés (nombre moyen de requêtes servies simultanément) :