Teoria de cues

La teoria de cues és l'estudi matemàtic de les línies d'espera (o cues) permetent l'anàlisi de diversos processos relacionats com: l'arribada al final de la cua, l'espera a la cua, o també matemàtica, etc.

La teoria de cues generalment és considerada una branca d'investigació operativa perquè els seus resultats sovint són aplicables a una àmplia varietat de situacions com: negocis, comerç, indústria, enginyeries, transport i telecomunicacions.

En el context de la informàtica i de les noves tecnologies aquestes situacions d'espera són més freqüents. Així, per exemple, els processos enviats a un servidor per a execució formen cues d'espera mentre no són atesos, la informació sol·licitada, a través d'Internet, a un servidor web pot rebre amb retard a causa de la congestió en la xarxa, també es pot rebre el senyal de línia de la qual depèn el nostre telèfon mòbil ocupada si la central està col·lapsada en aquell moment, etc.

Camps d'utilització: logística dels processos industrials de producció, enginyeria de xarxes i serveis, enginyeria de sistemes informàtics, elaboració de projectes sostenibles, etc.

Història

Agner Krarup Erlang, un matemàtic danès que va treballar per a la Copenhagen Telephone Exchange, va publicar el primer article sobre la teoria de cues a 1909. Es va encarregar de l'estudi del problema de dimensionament de línies i centrals de commutació telefònica per al servei de trucades.

Model de formació de cues

Es formen a causa d'un desequilibri temporal entre la demanda del servei i la capacitat del sistema per subministrar.

En les formacions de cues es parla de clients, com ara màquines danyades a l'espera de ser rehabilitades. Els clients poden esperar en cua, ja que els mitjans existents siguin inadequats per a satisfer la demanda del servei, en aquest cas, la cua tendeix a ser explosiva, és a dir, a ser cada vegada més llarga a mesura que transcorre el temps. Els clients pot ser que esperin temporalment, encara que les instal·lacions de servei siguin adequades, perquè els clients arribats anteriorment estan sent atesos.

Objectius

Els objectius de la teoria de cues consisteixen en:

• Identificar el nivell òptim de capacitat del sistema que minimitza el cost.
• Avaluar l'impacte que les possibles alternatives de modificació de la capacitat del sistema tindrien en el cost total.
• Establir un balanç equilibrat ("òptim") entre les consideracions quantitatives de costos i les qualitatives de servei.
• Prestar atenció al temps de permanència en el sistema o en la cua.

Elements existents en la teoria de cues

Figura 1.

o Procés bàsic de cues : Els clients que requereixen un servei es generen en una fase d'entrada. Aquests clients entren al sistema i s'uneixen a una cua. En determinat moment es selecciona un membre de la cua, per proporcionar-li el servei, mitjançant alguna regla coneguda com a disciplina de servei. Després, es porta a terme el servei requerit pel client en un mecanisme de servei, després del qual el client surt del sistema de cues.

o Font d'entrada o població potencial : Una característica de la font d'entrada és la seva mida. La grandària és el nombre total de clients que poden requerir servei en determinat moment. Pot suposar que la mida és infinit o finit.

o Client : És tot individu de la població potencial que demana servei com ara una llista de treball esperant per imprimir.

o Capacitat de la cua : És el màxim nombre de clients que poden estar fent cua (abans de començar a ser servits). De nou, pot suposar finita o infinita.

o Disciplina de la cua : La disciplina de la cua es refereix a l'ordre en què se seleccionen els seus membres per rebre el servei. Per exemple, pot ser:

• FIFO (first in first out) primer a entrar, primer a sortir, segons la qual s'atén primer al client que abans hagi arribat.
• LIFO (last in first out) també coneguda com a pila que consisteix a atendre primer al client que ha arribat l'últim.
• RSS (random selection of service) que selecciona els clients de manera aleatòria, d'acord amb algun procediment de prioritat o algun altre ordre.
• Processor Sharing - serveix als clients igualment. La capacitat de la xarxa es comparteix entre els clients i tots experimenten amb eficàcia el mateix retard.

o Mecanisme de servei : El mecanisme de servei consisteix en una o més instal·lacions de servei, cadascuna d'elles amb un o més canals paral·lels de servei, anomenats servidors.

o Xarxes de cues . Sistema on existeixen diverses cues i els treballs flueixen d'una a una altra. Per exemple: les xarxes de comunicacions o els sistemes operatius multitasca.

o Cua : Una cua es caracteritza pel nombre màxim de clients que pot admetre. Les cues poden ser finites o infinites.

o El procés de servei : Defineix com són atesos els clients.

Notació Kendall

David G. Kendall va introduir una notació de cues A/B/C a 1953. La notació de Kendall per descriure les cues i les seves característiques pot trobar-se en Tijms, HC, Algorithmic Analysis of Queue , capítol 9 a A First Course in Stochastic Models, Wiley, Chichester, 2003. Ha estat des de llavors estesa a 1/2/3/(4/5/6) on els números es reemplacen amb:

1. Un codi que descriu el procés d'arribada. Els codis usats són:
2. * M per "markovià" (la taxa d'arribades segueix una distribució de Poisson), significant una distribució exponencial per als temps entre arribades.
3. * D per uns temps entre arribades "determinístiques".
4. * G per a una "distribució general" dels temps entre arribades, o del règim d'arribades.
5. Codi semblant que representa el procés de servei (temps de servei). Es fan servir els mateixos símbols.
6. El nombre de canals de servei (o servidors).
7. La capacitat del sistema, o el nombre màxim de clients permesos en el sistema incloent aquests en servei. Quan el número està al màxim, les arribades següents són rebutjades. Un cas particular d'aquesta situació és el model M/M/n/no Erlang-B, en el qual no hi ha cua d'espera, sinó núm recursos (servidors) i fins an usuaris com a màxim, si arriba l'usuari n+1, és rebutjat. Aquest últim model és el que s'aplica en telefonia convencional. Un altre cas particular és el model Erlang-C o M/M/n, on la capacitat del sistema és il limitada, encara que hi hagi només n recursos, en cas d'arribar el recurs nombre n+1, passarà a una cua d'espera, però no és rebutjat.
8. L'ordre de prioritat en la qual els treballs a la cua són servits:
9. * First Come First Served ( FCFS ) o First In First Out ( FIFO ),
10. * Last Come First Server ( LCFS ) o Last In First Out ( LIFO ),
11. * Service In Random Order ( SIRO ) i
12. * Processor Sharing.
13. La mida de l'origen de les trucades. La mida de la població des d'on els clients venen. Això limita la taxa d'arribades.

Estructures típiques

Figura 2.

El primer sistema que es mostra a la figura, es diu un sistema d'un servidor i una cua. El segon, una línia amb múltiples servidors. El tercer sistema, aquell en que cada servidor té una línia de separació. El quart sistema, és una línia amb servidors en sèrie. Aquest model pot aplicar-se a treballs ordinador que esperen temps de processador.

Les limitacions de l'aproximació matemàtica

La teoria de formació d'una cua és sovint massa restrictiva matemàticament per ser capaç de modelar totes les situacions veritables a nivell mundial. Per exemple, els models matemàtics sovint assumeixen com infinits el nombre de clients, o la capacitat de la cua, quan és evident que aquests "nombres" han d'estar limitats. Els mitjans alternatius de l'anàlisi de la teoria de cues consisteixen generalment en simulacions d'ordinador i/o en l'anàlisi de dades experimentals.

Aplicació a la telefonia

Les xarxes telefòniques es dissenyen per acomodar la intensitat oferta del trànsit amb només una petita pèrdua. El funcionament dels sistemes depèn de si la trucada és rebutjada, de si està perduda, etc. Normalment els sistemes de desbordament fan ús de rutes alternatives i fins i tot aquests sistemes tenen una capacitat de càrrega finita o màxima de trànsit. No obstant això, l'ús de les cues permet que els sistemes esperin per les peticions del seu client fins que els recursos lliures estiguin disponibles. Això vol dir que si els nivells de la intensitat del trànsit excedeixen de la capacitat disponible, les trucades del client es perdrien. La disciplina de cues determina la manera de com manejar les trucades dels clients. Defineix la manera en què els serviran, l'ordre de les quals es serveixen, i la manera en què els recursos es divideixen entre els clients. Fer cua és dirigit per processos de control dins dels intercanvis, que es poden modelar utilitzant equacions d'estat com les cadenes de Markov. El trànsit entrant a aquests sistemes es modela mitjançant la distribució de Poisson.

Referències

• Tijms, HC, "Algorithmic Analysis of Queue", capítol 9 a A First Course in Stochastic Models, Wiley, Chichester, 2003
• Moskowitz, H. i Wright G.P. Investigació d'Operacions. Prentice_Hall Hispanoamericana S.A. 1991.
• Bose SJ, Chapter 1 - An Introduction to Queueing Systems, Kluwer/Plenum Publishers, 2002.
• Cohen, JW, The Single Server Queue, North Holland, 1969 (1a ed.)

Vegeu també

• Distribució d'Erlang
• Distribució Exponencial
• Cua (estructura de dades)
• Cua de prioritat (estructura de dades)
• Congestió de xarxa

Enllaços externs

• hlynka/queue.html Myron Hlynka's Queueing Theory Page Arxivat 2010-05-14 a Wayback Machine.
• Queueing Theory Basics