¿Qué propiedad de los sistemas de colas maximiza el "orden de llegada"?

Question

El "orden de llegada" es una forma muy común de organizar el acceso a un recurso o servicio limitado en el mundo real. Puede explicarse diciendo que siempre que el recurso está disponible se atiende a la persona que lleva más tiempo esperando, y se visualiza pensando en personas de pie en una fila única, en la que la persona que está al frente es siempre la siguiente en ser atendida y los recién llegados se incorporan al final de la cola.

Si se le pregunta a alguien por qué este sistema es el mejor, es posible que diga instintivamente que "es el más justo". Pero, ¿podemos expresar lo que significa esta equidad en términos de alguna propiedad, que se maximiza para este sistema y no para otro? No significa, por ejemplo, que todas las personas esperen el mismo tiempo, o incluso que las personas que llegan casi al mismo tiempo no sean atendidas con mucho tiempo de diferencia.

¿O bien optimiza alguna otra propiedad, como el incentivo de llegar lo antes posible o el incentivo de no llegar en horas punta?

¿Podemos formalizar por qué se debe preferir a otros acuerdos? ¿O es sólo una tendencia humana a hacer algo sencillo/algo que la mayoría de la gente considera justo/algo que todos conocemos?

Answer 1

La teoría de colas se ocupa principalmente de los procesos que tienen variabilidad en la llegada de trabajos al sistema. Por ejemplo, los trabajos pueden ser personas que necesitan un servicio. El tiempo que se tarda en atender estos trabajos también suele ser variable. El resultado es la congestión o la cola de espera. Esto puede medirse por el número medio de trabajos en la cola y por el tiempo medio de espera de las llegadas. Hay costes asociados a la espera de los trabajos. También hay costes asociados a la adición de más capacidad de servicio. Por lo tanto, el reto consiste en equilibrar estos costes. La teoría de colas puede utilizarse para determinar el número óptimo de, por ejemplo, ventanillas de servicio para una oficina de correos, médicos disponibles para las llamadas de la clínica, número de dependientes para un mostrador de recambios, etc. También puede utilizarse para decidir el orden en el que se debe procesar a los clientes, para responder a preguntas como "¿debería haber un carril exprés? FIFO (First in First Out) es una disciplina de colas que se utiliza en la teoría de colas por su comodidad de modelado. Pero puede haber un servicio exprés o prioritario para algunos trabajos; un ejemplo es el carril exprés de muchos supermercados para clientes con 10 artículos o menos, en cuyo caso el servicio puede ser en orden aleatorio. El FIFO es una comodidad de modelado.

1) FIFO (First In First Out) también llamado FCFS (First Come First Serve) - cola ordenada.

2) LIFO (Last In First Out) también llamado LCFS (Last Come First Serve) - pila.

3) SIRO (Servir en orden aleatorio).

4) Cola prioritaria, que puede ser vista como un número de colas para varias prioridades.

5) Muchos otros métodos de colas más complejos que suelen cambiar la posición del cliente en la cola en función del tiempo que lleva en ella, la duración prevista del servicio y/o la prioridad. Estos métodos son típicos de los sistemas informáticos de acceso múltiple.

La mayoría de los parámetros cuantitativos (como la longitud media de las colas o el tiempo medio de permanencia en el sistema) no dependen de la disciplina de las colas. Por eso, la mayoría de los modelos no tienen en cuenta la disciplina de las colas o asumen la cola normal FIFO . De hecho, el único parámetro que depende de la disciplina de las colas es la varianza (o desviación estándar) del tiempo de espera. Existe esta importante regla (que puede utilizarse, por ejemplo, para verificar los resultados de un experimento de simulación):

Los dos valores extremos de la varianza del tiempo de espera son para la cola FIFO (mínimo) y la cola LIFO (máximo)

Answer 2

El orden de llegada garantiza que, siempre que el tiempo entre clientes atendidos esté acotado, cualquier cliente que entre en la cola estará dentro de un tiempo de espera en el peor de los casos que puede determinarse en función del número de clientes precedentes. Incluso si el tiempo entre clientes está acotado sólo probabilísticamente, el tiempo de espera seguirá teniendo un límite probabilístico razonable. Por ejemplo, si se lanza una moneda una vez por segundo, y cada "cara" significa que alguien entra en la cola y cada "cruz" significa que alguien es atendido (a menos que la cola esté vacía, en cuyo caso no ocurre nada), alguien que entre cuando hay 39 personas delante de él sabrá que el tiempo hasta que sea atendido será el necesario para que aparezcan un total de 40 colas. Eso podría ocurrir o no en 80 segundos, pero probablemente ocurrirá en 90. Aunque sería posible que la persona tuviera que esperar una hora o más, sería excepcionalmente improbable. La probabilidad de que una persona no haya sido atendida en un tiempo determinado será rápidamente se acercan a cero a medida que aumenta el tiempo.

Supongamos que se aplican los mismos parámetros con una pila LIFO. Mientras que alguien que entrara en la pila tendría un 50% de posibilidades de ser atendido en un segundo, tendría 3/8 de posibilidades de no ser atendido en 3 segundos (frente a 1/8 de posibilidades si hubiera sido el primero en la cola), 5/16 de posibilidades de no ser atendido en 5 (frente a 1/32) y 35/128 de no ser atendido en 7 (frente a 1 en 128). La probabilidad de no ser atendido en N segundos disminuye a medida que N aumenta, pero muy lentamente. La probabilidad de tener que esperar un minuto es de 1 entre 9, la de tener que esperar una hora es de 1 entre 75 y la de tener que esperar una semana o más es de 1 entre 251.

Si se asignan prioridades a los distintos elementos, entonces resultan prácticas otras órdenes de servicio, pero el modelado del comportamiento es mucho más apto para centrarse en la heurística que en el cálculo de probabilidades absolutas.