Théorie du renouvellement et des files d'attente
La théorie du renouvellement analyse les processus qui redémarrent de manière probabiliste à des instants de récurrence, et la théorie des files d'attente l'applique aux systèmes où les clients arrivent, attendent et sont servis.
Definition
La théorie du renouvellement étudie les processus de comptage dont les temps inter-arrivées sont indépendants et identiquement distribués, généralisant le processus de Poisson, tandis que la théorie des files d'attente modélise les systèmes de service en combinant les processus d'arrivée et de service pour étudier les temps d'attente, les longueurs de file et l'utilisation.
Scope
Ce domaine couvre les processus de renouvellement et la fonction de renouvellement, les théorèmes élémentaire et clé du renouvellement, les processus régénératifs et le cadre de renouvellement-récompense, la structure et l'équilibre des files d'attente markoviennes telles que M/M/1 et M/M/c, la loi de Little reliant les nombres moyens et les temps d'attente, ainsi que les réseaux de files d'attente en interaction avec des solutions de forme produit.
Sub-topics
Core questions
- Comment la généralisation des temps inter-arrivées exponentiels à des distributions arbitraires étend-elle le processus de Poisson ?
- Que disent les théorèmes de renouvellement sur les taux à long terme et le comportement asymptotique ?
- Comment la longueur moyenne de la file d'attente et le temps d'attente sont-ils liés à l'équilibre ?
- Quand les réseaux de files d'attente admettent-ils des solutions de forme produit traitables ?
Key theories
- Théorèmes de renouvellement et renouvellement-récompense
- Les théorèmes élémentaire et clé du renouvellement donnent le taux de renouvellement à long terme et le comportement limite des solutions de l'équation de renouvellement, et le théorème de renouvellement-récompense exprime la récompense moyenne à long terme comme la récompense espérée par cycle divisée par la longueur espérée du cycle.
- Loi de Little
- Dans tout système de files d'attente stable, le nombre moyen de clients présents à long terme est égal au taux d'arrivée multiplié par le temps moyen que chaque client passe dans le système, une identité indépendante de la distribution reliant le débit, l'occupation et le délai.
Clinical relevance
La théorie du renouvellement et des files d'attente est à la base de la conception et de l'analyse des réseaux téléphoniques et de données, des centres d'appels, des lignes de production, des systèmes informatiques, des transports et de la capacité des services de santé, quantifiant les retards, le débit et l'utilisation des ressources dans les systèmes à demande aléatoire.
History
Erlang a fondé la théorie des files d'attente entre 1909 et 1920 avec ses formules de trafic téléphonique, la théorie du renouvellement a été développée par Feller, Smith et Cox dans les années 1940 et 1950, et la preuve par Little en 1961 de l'identité de la longueur de file ainsi que les résultats de Jackson sur les réseaux en 1957 ont étendu la théorie aux systèmes de service complexes.
Key figures
- Agner Krarup Erlang
- William Feller
- David Cox
- John Little
Related topics
Seminal works
- asmussen2003
Frequently asked questions
- Comment la théorie du renouvellement généralise-t-elle le processus de Poisson ?
- Elle remplace les temps inter-arrivées exponentiels du processus de Poisson par des temps arbitraires indépendants et identiquement distribués, de sorte que le processus conserve la structure de renouvellement mais perd la propriété d'absence de mémoire.
- Qu'est-ce que la loi de Little ?
- Elle stipule que le nombre moyen de clients dans un système stable est égal au taux d'arrivée multiplié par le temps moyen qu'un client y passe, indépendamment des distributions d'arrivée ou de service.