Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
Investigación Operativa Teoría de Colas Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Profesor: Ing. Carlos A. Martin E-mail: ing_carlos_martin@hotmail.com Unidad IX: Teoría de Colas Ing. Carlos Martin • Características de un fenómeno de espera: • Estructura básica de un modelo de colas: • Fuente de entrada (Población potencial). • Cola. Disciplina de cola. • Mecanismo de servicio. • Un proceso de colas elemental. • Terminología y notación. • Relaciones entre L, W, Lq y Wq. • El proceso de llegada. • Proceso de salida o servicio. • Disciplina de la cola. • Modo utilizado por las llegadas para unirse a la cola. • Expresiones y definiciones estándar para líneas de espera: Característica de la población con acceso o en busca del servicio (Tamaño, características y conducta); Características de las colas (Longitud limitada o ilimitada); Características del centro o facilidad de servicio (Distribución física del sistema de colas, La disciplina de la cola y la distribución de probabilidad apropiada que describe los tiempos de servicio). • Ejemplos de sistemas elementales de colas: Tiempos constantes de llegada y de servicio. Modelos de colas de un sólo canal: Llegadas con distribución Poisson y tiempos de servicios distribuidos exponencialmente. Ejemplos de sistemas de colas reales. • La distribución exponencial: Propiedades; Relación con la distribución de Poisson. Proceso de nacimiento y muerte: Cadenas de Markov de parámetros (tiempo) continuos. Ing. Carlos Martin • Modelos con tasa de llegadas y de servicio de tipo Poisson: • Modelo M/M/1. Modelo M/M/s. Modelo M/M/1/K. Modelo M/M/s/K. Modelo M/M/1//H. Modelo M/M/s//H. Modelo M/M/. Modelos de fuente finita: el modelo de reparación de máquina. • Redes de colas: Introducción. Colas infinitas en serie. Redes de Jackson. Ejemplos. • Comportamiento de los costos: Coste de espera en el sistema, coste de proporcionar el servicio: coste fijo, coste variable (Valoración por servicio, valoración por tiempo), coste total. • TRABAJO PRACTICO Nº 9 Ing. Carlos Martin BIBLIOGRAFÍA WINSTON WAYNE L.. “INVESTIGACION DE OPERACIONES. EDITORIAL. GRUPO EDITORIAL IBEROAMERICANA. ©1994 TAHA HAMDY A. “INVESTIGACIÓN DE OPERACIONES”. EDIT. ALFA OMEGA. ©2004 HILLIER FREDERICK S. “INTRODUCCION A LA INVESTIGACION DE OPERACIONES. EDITORIAL. MC GRAW HILL. ©2001 EPPEN G.D. “INVESTIGACION DE OPERACIONES EN LA CIENCIA ADMINISTRATIVA. EDITORIAL PRENTICE. ©2000 ACKOFF L. “FUNDAMENTOS DE INVESTIGACIÓN DE OPERACIONES. EDIT. LIMUSA. ©1994 MATHUR K. “INVESTIGACION DE OPERACIONES”. EDIT. PRENTICE HALL. ©1996 BRONSON R. “INVESTIGACION DE OPERACIONES”. EDIT. MC GRAW HILL. ©1996 KAUFMAN, A. “METODOS Y MODELOS DE LA INVESTIGACIÓN DE OPERACIONES. EDITORIAL C.E.C.S.A.. ©1978 LEVIN, R. I. “ENFOQUES CUANTITATIVOS A LA ADMINISTRACIÓN. EDIT. CECSA. ©1983 GROSS D. “FUNDAMENTALS OF QUEUEING THEORY”. EDIT. JOHN WILEY & SONS. ©1985 ALLEN A. “PROBABILITY, STATISTICS, AND QUEUEING THEORY WITH COMPUTER SCIENCE APPLICATIONS”. ©1979. Ing. Carlos Martin Investigación Operativa Introducción Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Definición de Teoría de Colas • Teoría de colas es el estudio analítico del comportamiento de líneas de espera. • Estas se presentan cuando los “clientes” llegan a un lugar solicitando un servicio a un “servidor” el cual tiene una capacidad de atención. • Si el servidor no está disponible inmediatamente y el cliente decide esperar, entonces se forma la línea de espera. Ing. Carlos Martin Cuando se Genera una Situación de Líneas de Espera? Cuando el cliente llega a la instalación y este esta ocupado, se forma en una línea de espera. El servidor elige a un cliente de la línea de espera para comenzar a prestar el servicio. Al culminarse un servicio, se repite el proceso de elegir a un nuevo cliente (en espera). Se supone que no se pierde tiempo entre el momento en que un cliente ya atendido sale de la instalación y la admisión de un nuevo cliente de la línea de espera. Los protagonistas principales son el cliente y el servidor. En los modelos de espera, la interacción entre el cliente y el servidor sólo es de interés en tanto que se relacione con el periodo que necesita el cliente para completar su servicio. Desde el punto de vista de las llegadas de clientes, nos interesan los intervalos de tiempo que separan llegadas sucesivas. Desde el punto de vista del servicio, es el tiempo de servicio por cliente el que cuenta en el análisis. Ing. Carlos Martin Situaciones en las que se ha aplicado la teoría de colas Congestionamiento del tráfico automotor. Estudio del tráfico aéreo en un aeropuerto. Problemas de almacenamiento. Capacidad de la sala de espera de un hospital. El número de médicos que deben atender en la guardia de un hospital. El número de camas que debe tener un pabellón. El número de cajas que deben operar en un banco o en un supermercado, en función de la hora y el día de la semana. El nº de camiones que deben distribuir productos en una región. La secuenciación automática de encendido de semáforos a lo largo de una avenida. El nº de operadores que atienden llamadas de larga distancia durante un turno. Programas que esperan ser procesados por una computadora digital. Ing. Carlos Martin Fenómenos de Espera Ing. Carlos Martin Fenómenos de Espera Ing. Carlos Martin Ing. Carlos Martin Reseña Histórica • La Teoría de colas es una rama de la matemática aplicada que tiene su origen en un trabajo llevado a cabo en 1910 por A.K. ERLANG sobre un problema de congestión en el tráfico telefónico. • Una situación de este tipo se presenta en el estudio del tráfico telefónico. oLas llamadas constituyen el flujo, que es interrumpido, en la oficina central de teléfono por los operadores, al tratar de comunicarse con los destinatarios. oDurante una hora pico, los que tratan de llamar sufren demoras, ya que los operadores son incapaces de atender las llamadas con la misma rapidez que se producen. Ing. Carlos Martin Reseña Histórica • El problema que originalmente trató ERLANG en su trabajo de 1910 se refería al cálculo de demora en caso de que solo existiese un operador, y en 1917 los resultados obtenidos se extendieron al caso que hubiesen varios operadores. • Los trabajos continuaron la trayectoria marcada por ERLANG siendo más interesantes los publicados por MOLINA en 1927 y FRY en 1928. • Un período de investigación dedicado al aspecto matemático del problema comenzó en 1930 con un trabajo de POLLACZEK. • A éste le siguieron los de KOLMOROGOV en 1931 y los de KHINTCHINE en 1932 y 1933. • Luego hubo un período de inactividad, que se prolongó hasta la última guerra. • Desde entonces se estudió con vista a resolver problemas industriales. Ing. Carlos Martin El Tiempo de Espera • Tener que esperar no sólo es una molestia personal. • El tiempo que la población de un país pierde al esperar en las colas es un factor importante tanto en la calidad de vida como en la eficiencia de su economía. • Por ejemplo, la recompensa de situarnos cerca del escenario en el concierto de nuestro artista favorito puede ser motivo suficiente para guardar cola durante horas, o incluso días. Y, aunque con más desgano, también hacemos cola para tomar el colectivo, en los controles de los aeropuertos, en el supermercado, en la panadería, en el cine, en un restaurante, en el trafico, en un peaje, en la sala de urgencias de un hospital, en un turno médico, en la gasolinera, en el banco, en el cajero, en distintas oficinas haciendo gestiones de estado ... Todos estos y muchísimos otros fragmentos de nuestra cotidianidad son tiempos de espera. Ing. Carlos Martin El Tiempo de Espera • Aunque son sufridas en pequeñas dosis, estas demoras que se repiten a lo largo del día, de las semanas y los meses suman entre dos y cuatro años de la vida laboral de los habitantes de las grandes ciudadesde América latina. • La población que tiene entre 18 y 65 años consume de 6 a 11% de su tiempo de vigilia en pausas y esperas. • Si este tiempo se usara de manera productiva, significarían millones de personas-año de trabajo útil. • Incluso estas asombrosas cifras no cuentan toda la historia del impacto que causa la espera excesiva. • También ocurren grandes ineficiencias debido a otros tipos de espera que no son personas en una cola. Ing. Carlos Martin Por ejemplo, hacer que las maquinas esperen una reparación puede dar como resultado pérdida de producción. Los vehículos (incluso barcos y camiones) que deben esperar la descarga pueden retrasar envíos subsecuentes. Los aviones que esperan despegar o aterrizar pueden desorganizar la programación posterior de vuelos. Los retrasos en las transmisiones de telecomunicaciones por saturación de líneas pueden causar fallas inesperadas en los datos. Cuando los trabajos de manufactura esperan su proceso se puede perturbar la producción subsecuente. El retraso en los trabajos de servicio respecto a su fecha de entrega es una causa de pérdida de negocios futuros. Ing. Carlos Martin ¿Por Qué Estudiar las Colas? Entonces, esperar a que nos atiendan es parte de la vida diaria y además el fenómeno de esperar no se limita a los seres humanos. Eliminar la espera por completo no es una opción factible debido a que el costo de instalación y operación del centro de operación puede ser prohibitivo. Nuestro único recurso es buscar el equilibrio entre el costo de ofrecer un servicio y el de esperar a que lo atiendan. El análisis de las colas es el vehículo para alcanzar esta meta. Ing. Carlos Martin ¿Por Qué Estudiar las Colas? El estudio de las colas tiene que ver con la cuantificación del fenómeno de esperar por medio de medidas de desempeño representativas, tales como: • longitud promedio de la cola, • tiempo de espera promedio en la cola, y • el uso promedio de la instalación. Estas medidas se utilizan para diseñar una instalación de servicio. Por ejemplo, en un restaurante de comida rápida con tres mostradores de servicio, el gerente desea agilizar el servicio. Un estudio revela la siguiente relación entre la cantidad de mostradores y el tiempo de espera para el servicio: Un examen de estos datos revela un tiempo de espera promedio de 7 minutos en la situación actual de tres mostradores. Cinco mostradores reducirían la espera a 3 minutos aproximadamente. Ing. Carlos Martin Cantidad de Cajeros 1 2 3 4 5 6 7 Tiempo de espera promedio (min) 16.2 10.3 6.9 4.8 2.9 1.9 1.3 Modelo Basado en Costos • Los resultados del análisis de colas puede incorporarse a un modelo de optimización de costos que busca minimizar la suma del costo de ofrecer el servicio y la espera por parte de los clientes. • Un análisis más a fondo del restaurante revela los siguientes resultados: Ing. Carlos Martin Cantidad de cajeros 1 2 3 4 5 6 7 Inactividad (%) 0 8 12 18 29 36 42 Modelo basado en costos • Los resultados del análisis de colas puede incorporarse a un modelo de optimización de costos que busca minimizar la suma del costo de ofrecer el servicio y la espera por parte de los clientes. • La figura muestra un modelo de costos típico (en dólares por unidad de tiempo) donde el costo del servicio se incrementa con el aumento del nivel de servicio (por ejemplo la cantidad de mostradores de servicio). • Al mismo tiempo, el costo de esperar se reduce con el incremento del nivel de servicio. • El obstáculo principal al implementar modelos de costos es la dificultad de determinar el costo de la espera, sobre todo la que experimentan las personas. Ing. Carlos Martin Dos Preguntas (a) ¿Cuál es la productividad de la estación (expresada como el porcentaje del tiempo que los empleados están ocupados) cuando el número de cajeros es cinco? (b) El gerente desea mantener el tiempo de espera promedio en alrededor de 3 minutos y, al mismo tiempo, mantener la eficiencia de la instalación aproximadamente a 90%. ¿Pueden alcanzarse las dos metas? Ing. Carlos Martin Cantidad de cajeros 1 2 3 4 5 6 7 Inactividad (%) 0 8 12 18 29 36 42 Cantidad de Cajeros 1 2 3 4 5 6 7 Tiempo de espera promedio (min) 16.2 10.3 6.9 4.8 2.9 1.9 1.3 Modelo Básico de un Sistemas de Colas Ing. Carlos Martin Llegadas Cola Servidor Salidas Elementos de un Modelo de Colas • Los actores principales en una situación de colas son el cliente y el servidor. • Los clientes llegan a una instalación (servicio) desde de una fuente. • Al llegar, un cliente puede ser atendido de inmediato o esperar en una cola si la instalación está ocupada. • Cuando una instalación completa un servicio, “incorpora” de forma automática a un cliente que está esperando en la cola, si lo hay. • Si la cola está vacía, la instalación se vuelve ociosa hasta que llega un nuevo cliente. • Desde el punto de vista del análisis de colas, la llegada de los clientes está representada por el tiempo entre llegadas (tiempo entre llegadas sucesivas), y • El servicio se mide por el tiempo de servicio por cliente. Ing. Carlos Martin • Por lo general, los tiempos entre llegadas y de servicio son: o probabilísticos (por ejemplo, la operación de una dependencia oficial) o o determinísticos (digamos la llegada de solicitantes para una entrevista de trabajo o para una cita con un médico). • El tamaño de la cola es importante en el análisis de colas. oPuede ser finito (como en el área intermedia entre dos máquinas sucesivas), o, o infinita (como en las instalaciones de pedidos por correo). • La disciplina en colas, la cual representa el orden en que se seleccionan los clientes en una cola, es un factor importante en el análisis de modelos de colas. oLa disciplina más común es la de primero en llegar, primero en ser atendido (FCFS, por sus siglas en inglés). oEntre otras disciplinas esta último en llegar primero en ser atendido (LCFS, por sus siglas en inglés) oServicio en orden aleatorio (SIRO, por sus siglas en inglés). oLos clientes también pueden ser seleccionados de entre la cola, con base en algún orden de prioridad. Por ejemplo, los trabajos urgentes en un taller se procesan antes que los trabajos regulares. Ing. Carlos Martin • El comportamiento en colas desempeña un papel en el análisis de líneas de espera. oLos clientes pueden cambiarse de una cola más larga a una más corta para reducir el tiempo de espera, opueden desistir del todo de hacer cola debido a la larga tardanza anticipada, o osalirse de una cola porque han estado esperando demasiado. • El diseño de la instalación de servicio puede incluir: oservidores paralelos (por ejemplo la operación de una dependencia oficial o un banco). oLos servidores también pueden estar dispuestos en serie (a saber, los trabajos procesados en máquinas sucesivas) o oestar dispuestos en red (como una red de computadoras). • La fuente de la cual se generan los clientes puede ser finita o infinita. oUna fuente finita limita la cantidad de clientes que llegan (p. e. las máquinas que solicitan el servicio de un técnico en mantenimiento). oUna fuente infinita es, para todo propósito práctico, por siempre abundante (llamadas que entran a un conmutador telefónico). Ing. Carlos Martin Modelos de Colas y Simulación • Las variaciones en los elementos de una situación de colas originan varios modelos de colas matemáticos. • Veremos ejemplos de Modelos con tasa de llegadas y de servicio de tipo Poisson: Modelo M/M/1. Modelo M/M/s. Modelo M/M/1/K. Modelo M/M/s/K. Modelo M/M/1//H. Modelo M/M/s//H. Modelo M/M/. Modelos de fuente finita: el modelo de reparación de máquina. Modelos de Redes de colas. • Las situaciones de colas complejas que no pueden representarse matemáticamente se suelen analizar por medio de simulación. Ing. Carlos Martin Cual es el Objetivo al Estudiar la Operación de una Instalación de Servicio? Nuestro objetivo al estudiarla operación de una instalación de servicio en condiciones aleatorias es el de asegurar algunas características que midan el desempeño del sistema sometido a estudio. Por ejemplo: o Una medida lógica de desempeño es el tiempo que esperará un cliente antes de ser atendido. o Otra medida es el porcentaje de tiempo que no se utiliza la instalación de servicio. La primera medida vislumbra el sistema desde el punto de vista del cliente La segunda evalúa el grado de uso de la instalación. Podemos advertir intuitivamente que cuanto mayor sea el tiempo de espera del cliente, tanto menor es el porcentaje de tiempo que se mantendría ociosa la instalación, y viceversa. Estas medidas de desempeño pueden utilizarse para seleccionar el nivel de servicio (o tasa de servicio) que producirá un equilibrio razonable entre las dos situaciones en conflicto. Ing. Carlos Martin Objetivo al Estudiar la Operación de una Instalación de Servicio • Se analizaran varios modelos de espera o de líneas de espera que explican una diversidad de operaciones de servicio. • El objetivo final de resolver estos modelos consiste en determinar las características que miden el desempeño del sistema. • Demostraremos cómo se puede utilizar esta información en la búsqueda de un diseño "óptimo" para la instalación de servicio. Ing. Carlos Martin Un Acercamiento a la Teoría de Colas • Muchas industrias de servicio tienen un Sistema de colas, en el que los “productos” (o clientes) llegan a una estación, esperan en una “fila” (o cola), obtienen algún tipo de servicio y luego salen del sistema. • El tener que esperar en una cola es una experiencia cotidiana que normalmente se considera desagradable. • Esperar un ascensor, ser servido en un restaurante o en una cola de un banco es una confrontación con la pérdida de tiempo. • Si la espera es demasiado larga, las personas se vuelven irritables e inquietas; los temperamentos se ofuscan. • Por supuesto, “demasiado larga” es relativo. Por ejemplo, la espera puede hacerse más prolongada si se está sentado (como en un restaurante) que si se está parado (como en un supermercado). Aún así, la paciencia tiene limites. Finalmente, la gente se va a otra parte. Ing. Carlos Martin Un Acercamiento a la Teoría de Colas Aunque sea desagradable esperar, es fácil observar que el proporcionar suficiente capacidad de servicio para eliminar la espera sería muy costoso. Piense cuantas cajeras serían necesarias en un banco ó cuantas cajas en un comercio, para eliminar todas las colas; aún si esto fuera posible, todavía se tendría que esperar mientras se proporciona el servicio. Es claro que se necesita algún tipo de balance para que el tiempo no sea muy largo y el costo de servicio no sea muy alto. Ing. Carlos Martin Los Modelos de Sistemas de Colas se pueden usar para responder preguntas como las siguientes • ¿Qué fracción de tiempo está ocioso cada servidor? • ¿Cuál es el número esperado de clientes presentes en la cola? • ¿Cuál es el tiempo promedio que un cliente espera en una cola? • ¿Cuál es la distribución de probabilidad del número de clientes presentes en una cola? • ¿Cuál es la distribución de probabilidad del tiempo de espera de un cliente? • Si un gerente de banco desea asegurar que sólo el 1% de los clientes tenga que esperar más de 5 minutos su turno, ¿cuántas ventanillas debe habilitar? Ing. Carlos Martin El Problema del Administrador • El problema del administrador es determinar qué capacidad o tasa de servicio proporciona el balance apropiado. • Con experiencia y sentido común, muchos administradores encuentran un equilibrio entre los costos de espera y de servicio sin elaborar ningún cálculo. • Por ejemplo, • El administrador de un supermercado actúa intuitivamente para agregar personal en las cajas cuando las colas se hacen muy largas. • El administrador de un restaurante planea tener más mozos alrededor de las horas de comida, guiándose por la experiencia. • No obstante, hay ocasiones en las que la intuición necesita ayuda, como cuando va de por medio una inversión sustancial de capital o cuando el balance apropiado no es evidente. Ing. Carlos Martin Cualificación y Cuantificación de una Cola de Espera • La situación ideal es cuando los servidores están esperando temporalmente a los clientes y estos sólo esperan servicio momentáneamente. Este es un caso típico de un “sistema balanceado” que tiende a un sistema estable o en equilibrio. • En resumen, lo que algunas veces se denomina crítico para un problema de cola es una decisión de compromiso: comparando el costo de suministrar un nivel de servicio (por ejemplo, 10 líneas telefónicas, 15 reparadores, 4 pistas de aterrizajes, 8 cajeros, y así sucesivamente) con el costo de espera (cliente insatisfecho, líneas de producción detenidas, pérdida de ingresos, etc.) • El análisis cuantitativo con frecuencia es útil en estas situaciones. Ing. Carlos Martin La Teoría de Líneas de Espera Tiene los Siguientes Objetivos • Caracterizar cuantitativa y cualitativamente a una cola. • Determinar los niveles adecuados de ciertos parámetros del sistema que equilibran el costo social de la espera con el costo asociado al consumo de recursos. Ing. Carlos Martin Cuantificación de una Línea de Espera • La cuantificación de una línea de espera se puede hacer a través de un análisis matemático o de un proceso de simulación. • El primer enfoque, de poder aplicarse, produce resultados óptimos. Sin embargo, requiere de suposiciones muy estrictas en cuanto a la naturaleza de las llegadas de clientes, el tipo de servicio, el número de servidores y la estructura del sistema. • El proceso de simulación tiene una aplicación más general que el de análisis matemático, ya que prácticamente se lo puede utilizar para cualquier sistema. Su desventaja es que no produce valores óptimos y es mucho más costoso. Ing. Carlos Martin Los Problemas Administrativos Relacionados con Sistemas de Colas Estos tipos de problema se clasifican en dos grandes grupos básicos: de Análisis y de Diseño. Problemas de Análisis: Si esta interesado en saber si un sistema dado está funcionando satisfactoriamente. Necesita responder una o más de las siguientes preguntas: • ¿Cuál es el tiempo promedio que un cliente tiene que esperar en la fila antes de ser atendido? • ¿Qué fracción del tiempo ocupan los servidores en atender un cliente o en procesar un producto? • ¿Cuáles son los números promedio y máximo de clientes que esperan en la fila? Basándose en estas preguntas, los gerentes tomarán decisiones como: emplear o no a más gente, una estación de trabajo adicional para mejorar el nivel de servicio, o si es necesario o no aumentar el tamaño del área de espera. Ing. Carlos Martin Los Problemas Administrativos Relacionados con Sistemas de Colas Problemas de diseño: Si desea diseñar las características de un sistema que logre un objetivo general. Esto puede implicar el planteamiento de preguntas como las siguientes: • ¿Cuántas personas o estaciones deben emplearse para proporcionar un servicio aceptable? • ¿Deberán los clientes esperar en una sola fila (como se hace en muchos bancos) o en diferentes filas (como en el caso de los supermercados) ? • ¿Deberá haber una estación de trabajo separada que maneje las cuestiones “Especiales” (como el caso del acceso a primera clase en la ventanilla de una aerolínea)? • ¿Qué tanto espacio se necesita para que los clientes o los productos puedan esperar?. Por ejemplo, en un sistema de reservaciones por teléfono. ¿Qué tan grande debe ser la capacidad de retención?. Esto es ¿Cuántas llamadas telefónicas se deben mantener en espera antes de que la siguiente obtenga la señal de ocupado? Ing. Carlos Martin Clientes y Servidores En el Sistema de Colas El Término “Cliente” se usa para Referirse a, Por Ejemplo: • Gente esperando a que se desocupe alguna línea telefónica. • Máquinas que deban ser reparadas. • Aviones esperando autorización para aterrizar. • Gente esperandoen la cola de un cajero de un supermercado; etc. El Término Instalaciones de “Servicio” se Utiliza en Sistemas de Cola para Referirse a, Por Ejemplo: • Líneas telefónicas. • Talleres de reparación. • Pistas de un aeropuerto. • Cajas de pago; etc. Ing. Carlos Martin Tasas de Servicio • Los servicios de cola pretenden a menudo una tasa variable de llegada y una tasa variable de servicio. • Los ejemplos de tasa variable de llegada podrían ser los siguientes: La demanda (tasa de llegada) a una central telefónica es de 60 por minuto. La máquina se descompone (o llegan a una instalación de reparación) a una tasa de 3 por semana o 15 por mes. Los aviones llegan (solicitan pista) entre 6:00 PM y 7:00 PM a una tasa de 1 por minuto. Los clientes llegan a una caja de pago a una tasa de 25 por hora. Ing. Carlos Martin Tasas de Servicio Los Ejemplos de Tasa de Servicio Podrían Ser Los Siguientes: Los sistemas telefónicos entre dos ciudades pueden manejar 90 llamadas por minuto. Una instalación de reparación puede, en promedio, reparar máquinas a una tasa de 4 por día (o 4 en 8 horas) Una pista de aeropuerto puede manejar (aterrizar) dos aviones por minuto o uno cada 30 segundos. En promedio una ventanilla de pago puede procesar un cliente cada 4 minutos. Ing. Carlos Martin Homogeneidad Nótese que las llegadas son homogéneas o vienen de la misma población. • Esta es una limitación importante de la Teoría de colas. Cuando una instalación de servicio, como un aeropuerto, maneja diferentes tipos de llegadas, éstas se deben tratar por separado. • Un ejemplo seria: un sistema para los pasajeros y otro para los aviones en el aeropuerto. • Por supuesto, los dos se relacionan, pero la teoría de colas sólo los puede tratar por separado y en forma independiente. • Si se quisiera analizarlos juntos, se tendría que usar simulación. Ing. Carlos Martin Estructuras Típicas de Sistemas de Colas: Una Línea, Un Servidor Llegadas Sistema de colas Cola Servidor Salidas Ing. Carlos Martin Llegadas Sistema de colas Cola Servidor Salidas Servidor Servidor Salidas Salidas Estructuras Típicas de Sistemas de Colas: Una Línea, Múltiples Servidores Ing. Carlos Martin Llegadas Sistema de colas Cola Servidor Salidas Servidor Servidor Salidas Salidas Cola Cola Ing. Carlos Martin Estructuras Típicas de Colas: Varias Líneas, Múltiples Servidores Llegadas Sistema de colas Cola Servidor Salidas Cola Servidor Estructuras Típicas de Colas: Una Línea, Servidores Secuenciales Ing. Carlos Martin Costos de un Sistema de Colas • Costo de espera: Es el costo para el cliente al esperar o Representa el costo de oportunidad del tiempo perdido o Un sistema con un bajo costo de espera es una fuente importante de competitividad Ing. Carlos Martin Proceso básico de colas El proceso básico supuesto por la mayor parte de los modelos de colas es el siguiente. Los clientes que requieren un servicio se generan a través del tiempo en una fuente de entrada. Estos clientes entran al sistema y se unen a una cola. En determinado momento se selecciona un miembro de la cola, para proporcionarle el servicio, mediante alguna regla conocida como disciplina de cola (o disciplina de servicio). Después, en un mecanismo de servicio se lleva a cabo el servicio requerido por el cliente luego de lo cual el cliente sale del Sistema de colas. Los clientes que se forman en una cola lo hacen en un área de espera. Ing. Carlos Martin Fuente de Entrada (Población Potencial) Una característica de la fuente de entrada es su tamaño. El tamaño es el número total de clientes que pueden requerir servicio en determinado momento, es decir, el número total de clientes potenciales distintos. Puede suponerse que el tamaño es infinito o finito (de modo que también se dice que la fuente de entrada es ilimitada o limitada). Como los cálculos son mucho más sencillos para el caso infinito, esta suposición se hace muy seguido cuando el tamaño real sea un número fijo relativamente grande, y deberá tomarse como una suposición implícita en cualquier modelo que no establezca otra cosa. El caso finito es más difícil analíticamente, pues el número de clientes en la cola afecta el número potencial de clientes fuera del sistema en cualquier momento; pero debe hacerse esta suposición finita si la tasa de llegada de clientes nuevos que se generan en la fuente de entrada queda afectada en forma significativa por el número de clientes en el sistema de líneas de espera. Ing. Carlos Martin Factores Principales en el Análisis de Líneas de Espera En los modelos de espera, las llegadas y los tiempos de servicio de clientes se resumen en términos de distribuciones de probabilidad que normalmente se conocen como distribuciones de llegadas y de tiempo de servicio. Estas distribuciones pueden representar situaciones donde llegan clientes y son atendidos individualmente (por ejemplo, en bancos o supermercados). En otros casos, los clientes pueden llegar y/o ser atendidos en grupos (por ejemplo, en restaurantes). Este último caso se conoce normalmente como líneas de espera masivas. Aunque los patrones de llegadas y salidas son los factores principales en el análisis de las líneas de espera, también pueden figurar otros factores en forma importante en la elaboración de los modelos. Ing. Carlos Martin Llegadas Se debe especificar el patrón estadístico mediante el cual se generan los clientes a través del tiempo. La suposición es que se generan de acuerdo a un proceso Poisson, es decir, el número de clientes que llegan hasta un tiempo específico tiene una distribución Poisson, este caso corresponde a aquel cuyas llegadas al sistema ocurren de manera aleatoria pero con cierta tasa media fija y sin importar cuántos clientes están en el sistema (por lo que el tamaño de la fuente de entrada es infinito). Una suposición equivalente es que la distribución de probabilidad del tiempo que transcurre entre dos llegadas consecutivas es exponencial. Ing. Carlos Martin Tiempo Entre Llegadas Es el tiempo transcurrido entre la llegada de un cliente y el inmediatamente anterior. Este intervalo de tiempo puede ser una constante (determinístico) o una variable aleatoria (probabilístico) cuya distribución de probabilidad se puede conocer o no. El enfoque de análisis matemático de las líneas de espera, está muy bien desarrollado, cuando la distribución de llegada es Poisson. Cuando las llegadas no son independientes (sería el caso de un grupo de pacientes que llegan a un centro de emergencia, cuando éstos sufrieron el mismo accidente) se utiliza el enfoque de la simulación. Ing. Carlos Martin La Tasa Media de Llegadas y El Tiempo Entre Llegadas • La tasa media de llegadas es • El tiempo esperado entre llegadas es 1/ Por ejemplo: Si la tasa media de llegadas es = 20 clientes por hora Entonces el tiempo esperado entre llegadas es 1/ = 1/20 = 0.05 horas o 3 minutos Ing. Carlos Martin Disciplina de Servicio Algunas de las formas más comunes. en que los clientes que esperan son seleccionados para ser atendidos, son: Primero en entrar, primero en salir (FIFO): los clientes son atendidos en el orden en que van llegando a la fila. Los clientes de un banco y de un supermercado, por ejemplo, son atendidos de esta manera. Ultimo en entrar, primero en salir (LIFO): el cliente que ha llegado más recientemente es el primero en ser atendido. Un ejemplo de esta disciplina se da en un proceso de producción en el que los productos llegan a una estación de trabajo y son apilados uno encima de otro. El trabajador elige, para su procesamiento, el producto que está en la cima de la pila, que fue el último que llegó para ser procesado o para brindarle un servicio. Selección de prioridad: a cada cliente que llega se le da una prioridad y se elige según ésta para brindarle el servicio. Un ejemplo de esta disciplina son los pacientes que llegan a la salade urgencias de un hospital. Mientras más severo sea el caso, mayor será la prioridad del cliente. Disciplina SIRO (servicio en orden aleatorio): a veces, el orden en el que llegan los clientes no tiene efecto alguno sobre el orden en el que se les sirve. Este sería el caso si el siguiente cliente en ser atendido se selecciona al azar de entre los que están esperando para ser atendidos. Ing. Carlos Martin Diseño de la Instalación y la Ejecución del Servicio La instalación puede incluir más de un servidor, con lo cual es posible atender a tantos clientes en forma simultánea como número de servidores haya (por ejemplo, los cajeros bancarios). En este caso, todos los servidores ofrecen el mismo servicio y se dice que la instalación tiene servidores paralelos. Por otra parte, la instalación puede comprender un número de estaciones en serie por las que puede pasar el cliente antes de que se complete el servicio (por ejemplo, el procesamiento de un producto "en una serie de máquinas). Las situaciones resultantes se conocen normalmente como líneas de espera en serie o líneas de espera sucesivas. El diseño más general de una instalación de servicio incluye estaciones de procesamiento en serie y en paralelo. Esto da origen a lo que llamamos líneas de espera en red. Ing. Carlos Martin Tipos de Sistemas de Colas Una cola-un servidor. Existe una fuente a partir de la cual fluyen los clientes, una línea de espera (cola) y existe además un único centro de servicio. o Por ejemplo en una boletería de un cine en donde se venden boletos de acuerdo a cómo llegan los espectadores. Mono Cola - Multicanal. Existe una fuente a partir de la cual fluyen los clientes, una sola línea de espera, dos o más canales en paralelos constituyen el centro de servicio, asegura el proceso “Primero en entrar, primero en salir ”. o Por ejemplo en una peluquería con 5 sillones (5 peluqueros) que prestan sus servicios siguiendo una política de atender a los clientes en el orden con que llegan al establecimiento (no se aceptan reservaciones). Ing. Carlos Martin Tipos de Sistemas de Colas MultiCola – Multicanal – Con opción de Cambio. Existe una fuente a partir de la cual surgen los clientes, colas independientes con opción a elección y cambio, canales independientes constituyen el centro de servicio; no asegura el proceso “Primero en entrar primero en salir”. Un ejemplo es el caso de un banco, donde existen 8 cajas y los clientes se forman en la cola que más les convenga, con la opción de cambiarse de una cola a otra. MultiCola – Multicanal – Con opción de Cambio. Es el caso de cualquier trámite burocrático. Por ejemplo, la oficina de préstamos a corto plazo donde existen 5 ventanillas de recepción de documentos, de acuerdo a la inicial del apellido paterno (A-E, F-J, K-O, P-T, U-Z). Ing. Carlos Martin Tipos de Sistemas de Colas Una cola-servidores múltiples en cascada. o Por ejemplo en una embotelladora, las botellas usadas se esterilizan, después pasan al llenado del líquido, tapado, etiquetado y empaquetado. Se cuenta con una sola esterilizadora, una sola máquina de llenado, una tapadora, una etiquetadora y una empaquetadora. Colas múltiples-servidores múltiples en sistema mixto. Existe una fuente a partir de la cual surgen los clientes, líneas en paralelo sin opción a cambio de cola, canales de despacho en paralelo – serie constituyendo el centro de servicio. o Un caso sería el mismo ejemplo anterior, pero con más de una unidad de las diferentes máquinas que se mencionaron. Ing. Carlos Martin Tipos de Sistemas de Colas Ing. Carlos Martin Tamaño de la Línea de Espera El número de clientes que pueden esperar en la cola puede ser finito o infinito. El número de teléfonos al que da servicio un conmutador telefónico es un ejemplo de una fuente inagotable (infinita), mientras que el número de máquinas en una sección de una fábrica es un ejemplo de fuente limitada (finita). En el primer caso, la tasa de llegada difícilmente se verá afectada por el número de teléfonos ocupados en cualquier momento, de manera que es posible considerar que los tiempos entre llegadas forman un proceso de renovación. Sin embargo, en el segundo caso cada máquina que requiere la atención de un operador, es decir, que entra al sistema de líneas de espera, puede reducir en forma significativa la tasa de llegada, y cada máquina que ha recibido servicio, esto es, que sale del sistema, puede aumentar una vez más de manera significativa la tasa de llegada. Ing. Carlos Martin La Espera de los Clientes en Cola Los clientes pueden esperar, en una cola o en varias, en las cuales pueden tener la opción de cambiarse o no. Por ejemplo, en algunos bancos los clientes deben hacer una sola cola, pero en otros, pueden escoger la cola en donde formarse. Si hay varias colas en una instalación, es importante conocer si se permite a los clientes cambiar de cola o no. En la mayor parte de los sistemas con colas múltiples se permite el cambio, pero no se lo recomienda, por ejemplo en una casilla para peaje. Cuando hay varias colas con frecuencia los clientes se forman en la más corta. Desafortunadamente en muchos casos, como en un supermercado, es difícil definir la cola más corta. Ing. Carlos Martin Tiempo de Servicio En general cada cliente que ingresa al sistema de atención no siempre lo hace en búsqueda de un servicio similar al que motivó el ingreso de los otros clientes que lo preceden o lo suceden. El tiempo de servicio puede ser una constante o una variable, puede ser además aleatoria, dependiente o independiente, cuya distribución de probabilidad se puede o no conocer. El enfoque matemático ha proporcionado resultados a las líneas de espera cuando el tiempo de servicio, tiene una distribución exponencial negativa o una distribución de ERLANG. Para otras distribuciones, se utiliza el enfoque de simulación. Se dice que el tiempo de servicio es dependiente, cuando varía (se alarga o se acorta) por factores de presión del sistema (por ejemplo, las quejas de la gente que espera), y es independiente cuando la duración del servicio no se afecta por este tipo de presiones. Ing. Carlos Martin Sistemas de Colas: El Servicio • El servicio puede ser brindado por un servidor o por servidores múltiples • El tiempo de servicio varía de cliente a cliente • El tiempo esperado de servicio depende de la tasa media de servicio () Ing. Carlos Martin Sistemas de Colas: El Servicio • El tiempo esperado de servicio equivale a 1/ • Por ejemplo, si la tasa media de servicio es de 25 clientes por hora • Entonces el tiempo esperado de servicio es 1/ = 1/25 = 0.04 horas, o 2.4 minutos Ing. Carlos Martin Sistemas de Colas: El Servicio • Es necesario seleccionar una distribución de probabilidad para los tiempos de servicio. • Hay dos distribuciones que representarían puntos extremos: oLa distribución exponencial (=media) oTiempos de servicio constantes (=0) Ing. Carlos Martin Investigación Operativa La Distribución Exponencial y la Distribución de Poisson Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR La distribución exponencial, también llamada distribución exponencial negativa, con frecuencia describe el tiempo requerido para atender a un cliente, es una distribución continua. Su función de probabilidad está dada por: f(x) = e - x donde: x = variable aleatoria (tiempos de servicio) = número promedio de unidades que puede manejar la estación de servicio en un periodo específico e = 2.718 (la base del logaritmo natural) Ing. Carlos Martin Valor esperado = 1/ = tiempo de servicio promedio Varianza = 1/2 Al igual que con otras distribuciones continuas, las probabilidades se encuentran determinando el área bajo la curva. La probabilidad de que el tiempo requerido (t), distribuido exponencialmente, para atender a un cliente sea menor o igual que el tiempo t está dada por la fórmula: P (x t) = 1 – e - t Eltiempo utilizado en la descripción de determina las unidades para el tiempo t. Por ejemplo, si es el número promedio atendido por hora, el tiempo t debe darse en horas. si es el número promedio atendido por minuto, el tiempo t debe darse en minutos. Ing. Carlos Martin Ejemplo Un taller instala silenciadores en automóviles y camiones pequeños. El mecánico puede instalar silenciadores nuevos a una tasa aproximada de tres por hora y este tiempo de servicio sigue una distribución exponencial. ¿Cuál es la probabilidad de que el tiempo para instalar un silenciador nuevo sea de ½ hora o menos? A partir de: P (x t) = 1 – e - t x : tiempo de servicio con distribución exponencial : número promedio que se puede atender por periodo = 3 por hora t = 1/2 hora = 0,5 hora P (t 0,5) = 1 – e -3 (0,5) = 1 – e -1,5 = 1 – 0,2231 = 0,7769 Ing. Carlos Martin La figura muestra que el área bajo la curva de 0 a 0,5 es de 0,7769. Entonces, hay una probabilidad cercana a 78% de que el tiempo no sea mayor que 0,5 horas, y de 22% de que el tiempo sea más largo. La probabilidad de que el tiempo sea mayor que un valor dado de t se encuentra observando que estos dos eventos son complementarios. Por ejemplo, para encontrar la probabilidad de que el mecánico del taller tarde más de 0,5 horas, P (t 0,5) = 1 – P (t 0,5) = 1 – 0,7769 = 0,2231 = 22% Ing. Carlos Martin La distribución de Poisson Una distribución de probabilidad discreta importante es la distribución de Poisson. La examinamos porque tiene un rol fundamental para complementar la distribución exponencial en la teoría de líneas de espera. La distribución describe situaciones donde los clientes llegan de manera independiente durante cierto intervalo de tiempo y el número de llegadas depende de la longitud del intervalo de tiempo. Los ejemplos incluyen pacientes que llegan a una clínica de salud, clientes que llegan a la ventanilla de un banco, la llegada de pasajeros a un aeropuerto y las llamadas telefónicas que pasan a través de una central. Ing. Carlos Martin Ing. Carlos Martin Donde: P(X) = probabilidad de que haya exactamente X llegadas u ocurrencias = número promedio de llegadas por unidad de tiempo (tasa media de llegadas) e = 2.718, base del logaritmo natural X = número de ocurrencias (0, 1, 2, . . .) La media y la varianza de la distribución de Poisson son iguales y se calculan simplemente como: Valor esperado = Varianza = La fórmula de la distribución de Poisson es: Por ejemplo, si () = 2, las probabilidades de Poisson de que X sea 0, 1, 2, ….., 9 Ing. Carlos Martin Las distribuciones exponencial y de Poisson están relacionadas. Si el número de ocurrencias por periodo sigue una distribución de Poisson, entonces, el tiempo entre ocurrencias sigue una distribución exponencial. Por ejemplo, si el número de llamadas telefónicas que llegan a un centro de servicio a clientes sigue una distribución de Poisson con media de 10 llamadas por hora, el tiempo entre cada llamada será exponencial con tiempo medio entre llamadas de 1/10 horas (6 minutos). Ing. Carlos Martin Papel de la Distribución Exponencial En la mayoría de las situaciones de colas, las llegadas ocurren al azar. Aleatoriedad significa que la ocurrencia de un evento (por ejemplo la llegada de un cliente o la terminación de un servicio) es independiente del tiempo transcurrido desde la ocurrencia del último evento. Los tiempos aleatorios entre llegadas y de servicio se describen cuantitativamente por medio de una distribución exponencial, la cual se define como: Ing. Carlos Martin La definición de E(t) muestra que es la tasa por unidad de tiempo a la cual se generan los eventos (llegadas o salidas). La distribución exponencial describe un fenómeno totalmente aleatorio. • Por ejemplo, • si en este momento la hora es 8:20 A.M. y la última llegada fue a las 8:02 A.M., la probabilidad de que la siguiente llegada ocurra a las 8:29 es una función sólo del intervalo de las 8:20 a las 8:29, es totalmente independiente del tiempo que ha transcurrido desde la ocurrencia del último evento (8:02 a 8:20). Ing. Carlos Martin Investigación Operativa Modelado de procesos de llegada y servicio Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Modelado de procesos de llegadas Ing. Carlos Martin Modelado de procesos de llegadas Ing. Carlos Martin Ing. Carlos Martin Modelado de procesos de llegadas Ing. Carlos Martin Modelado de procesos de llegadas Papel de la Distribución Exponencial Ing. Carlos Martin Ing. Carlos Martin Papel de la Distribución Exponencial Ing. Carlos Martin Papel de la Distribución Exponencial Ing. Carlos Martin Papel de la Distribución Exponencial Ing. Carlos Martin Papel de la Distribución Exponencial Ing. Carlos Martin Papel de la Distribución Exponencial Ing. Carlos Martin Papel de la Distribución Exponencial Distribución de Erlang Ing. Carlos Martin Ing. Carlos Martin Distribución de Erlang Ing. Carlos Martin Distribución de Erlang Modelo del proceso de servicio Ing. Carlos Martin Nomenclatura de las diferentes líneas de espera El investigador británico D. Kendall introdujo en 1953 una notación pragmática para las diferentes líneas de espera. Lee complementó esta lista en 1966. La notación tiene la siguiente forma general: ( a / b / c ) : ( d / e / f ) donde: a: Distribución de llegada. b: Distribución del servicio. c: Número de servidores en paralelo en el sistema. d: Disciplina del servicio. e: Máximo número de clientes que pueden estar en el sistema (esperando y recibiendo servicio). f: Fuente de generación de clientes. Ing. Carlos Martin Códigos para los símbolos a , b y c Ing. Carlos Martin Códigos para el símbolo d, e y f Ing. Carlos Martin Ejemplos utilizando la notación kendall-Lee Se presentan a continuación algunos ejemplos de posibles modelos de espera utilizando la notación Kendall-Lee: Código (a/b/c): (d/e/f) • (M/M/1): (FCFS/ ∞/ ∞ • (M/M/S): (FCFS/ ∞ / ∞) • (M/M/S): (FCFS/N/ ∞), S < N • (M/M/S): (PRP/ ∞ / ∞) • (M/M/S): (NPRP/ ∞ / ∞) • (M/M/1): (FCFS/N/ ∞) Ing. Carlos Martin Investigación Operativa Proceso de Nacimiento y Muerte Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Ing. Carlos Martin Estado del sistema en el tiempo t • Pij (t) i: estado inicial j: estado actual •j Ing. Carlos Martin Ing. Carlos Martin Relación de la distribución exponencial con los procesos de nacimiento - muerte Ing. Carlos Martin Ing. Carlos Martin Relación de la distribución exponencial con los procesos de nacimiento - muerte Ing. Carlos Martin Relación de la distribución exponencial con los procesos de nacimiento - muerte Ing. Carlos Martin Derivación de las probabilidades de estado estable para procesos de nacimiento y muerte Derivación de las probabilidades de estado estable para procesos de nacimiento y muerte Ing. Carlos Martin Ing. Carlos Martin Derivación de las probabilidades de estado estable para procesos de nacimiento y muerte Investigación Operativa Sistema de colas M/M/1/DG// Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Sistema de colas M/M/1/DG// Ing. Carlos Martin Estado del sistema de colas •El sistema está en un estado inicial •Se supone que el sistema de colas llega a una condición de estado estable (nivel normal de operación) •Existen otras condiciones anormales (horas pico, etc.) •Lo que interesa es el estado estable Ing. Carlos Martin Notación en la teoría de líneas de espera Se designa por al nº promedio de llegadas al sistema por unidad de tiempo (minuto, hora, día, etc.) , al nº promedio de servicios del sistema por unidad de tiempo. El cociente /, denotado por , representa el factor de tráfico. Si > 1, llegan más clientes al sistema por unidad de tiempo de los que se les puede darservicio y, por lo tanto, se forma una línea de espera en crecimiento sin limite. El factor > 1 indica la necesidad de añadir al sistema más servidores, S, hasta que se logre que el factor de utilización (o de uso) del sistema con servidores múltiples, sea menor a uno, es decir: = / s < 1 Esto quiere decir, que el sistema de servidores múltiples podrá dar servicio, por unidad de tiempo, a todas las llegadas en este intervalo de tiempo. Ing. Carlos Martin Cuando un cliente llega a formarse en una cola, se pregunta: • ¿Cuánto tiempo tengo que esperar hasta que me proporcionen servicio (Wq)? • ¿Cuánto tiempo tengo que esperar hasta que salga del sistema (W)? • ¿Cuánta gente está esperando en la cola (Lq)? • ¿Cuánta gente se encuentra en el sistema (L)? Ing. Carlos Martin Notación en la teoría de líneas de espera : N° promedio de llegadas al sistema por unidad de tiempo. : Número promedio de servicios por unidad de tiempo. ρ: Factor de tráfico. S: Número de servidores en el sistema. Wq : Tiempo medio de espera en cola. Ws: Tiempo de espera en el servicio W: Tiempo Total de permanencia del cliente dentro del sistema, conformado por el tiempo de espera en fila más el de servicio. Ing. Carlos Martin Notación en la teoría de líneas de espera Notación en la teoría de líneas de espera Lq: Numero esperado de clientes formados en la cola. LS: Número esperado de clientes recibiendo un servicio L: Número esperado de clientes en el sistema. π0 : Probabilidad de que en el momento t de arribo a la cola, el sistema se encuentre vacío. πn : Probabilidad de que exactamente n clientes se encuentren en el sistema. S: clientes recibiendo servicio n-S: clientes formados en la cola. ts : Tiempo de servicio por cliente. Es el valor inverso a la velocidad de despacho = 1/ ta : Tiempo de llegada o de arribo por cliente. Es el valor inverso a la velocidad de arribo = 1/ Ing. arlos Martin Ing. Carlos Martin Sistema de colas M/M/1/DG// Ing. Carlos Martin Sistema de colas M/M/1/DG// Ing. Carlos Martin Sistema de colas M/M/1/DG// Ing. Carlos Martin Sistema de colas M/M/1/DG// Formulas de línea de espera de Little: L = W Ing. Carlos Martin Ing. Carlos Martin Formulas de línea de espera L = W Ing. Carlos Martin Sistema de colas M/M/1/DG//: W Ing. Carlos Martin Sistema de colas M/M/1/DG//: Wq Nótese que, como lo esperábamos, W y Wq se hacen muy grandes cuando se acerca a 1. Para cercano a cero, Wq tiende a cero, pero para pequeño, W tiende a 1/, el tiempo promedio de servicio. Relación entre y L para un sistema M/M/1/DG/ Ing. Carlos Martin Medidas del desempeño del sistema de colas: ejemplo •Suponga una estación de gasolina a la cual llegan en promedio 45 clientes por hora. •Se tiene capacidad para atender en promedio a 60 clientes por hora •Se sabe que los clientes esperan en promedio 3 minutos en la cola. Ing. Carlos Martin Medidas del desempeño del sistema de colas: ejemplo La tasa media de llegadas = 45 clientes por hora o = 45/60 = 0.75 clientes por minuto La tasa media de servicio = 60 clientes por hora o = 60/60 = 1 cliente por minuto Ing. Carlos Martin Medidas del desempeño del sistema de colas: ejemplo Ing. Carlos Martin Investigación Operativa Modelo para optimizar un sistema de colas Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Ing. Carlos Martin Ejemplo de optimización de un sistema de colas Los mecánicos que trabajan en una planta de troquelado deben sacar herramientas de un almacén. Llega un promedio de diez mecánicos por hora buscando partes. En la actualidad el almacén está a cargo de un empleado a quien se les pagan 6 dólares/h y gasta un promedio de 5 min. para entregar las herramientas de cada solicitud. Como a los mecánicos se les paga 10 dólares/h, cada hora que un mecánico pasa en el almacén de herramientas le cuesta 10 dólares a la empresa. Esta ha de decidir si vale la pena contratar, a 4 dólares/h, un ayudante del almacenista. Si se contrata al ayudante, el almacenista sólo tardará un promedio de 4 min para atender las solicitudes de herramientas. Suponga que son exponenciales tanto los tiempos de servicio como el tiempo entre llegadas. Se debe contratar al ayudante? A los problemas en los que un tomador de decisiones debe escoger entre sistemas alternativos de cola se les llama problemas para optimizar sistemas colas. En este problema, la meta de la empresa es minimizar la suma del costo horario de servicio y del costo horario esperado debido a los tiempos de inactividad de los mecánicos. En los problemas de optimización de colas, el componente del costo debido a clientes que esperan en la cola se llama costo de demora. Así, la empresa desea minimizar Ing. Carlos Martin En general, el cálculo del costo horario de servicio es sencillo. El modo mas fácil de calcular el costo horario de demora es tomando nota de que Ing. Carlos Martin En nuestro problema Así, Ahora podemos comparar el costo esperado por hora, si no se contrata al ayudante con el correspondiente si se le contrata. Si no se contrata, = 10 mecánicos/h, y = 12 mecánicos/h. De la Ec. (31), W = 1/ (12-10) = ½ hora. Como al despachador se le paga 6 dólares por hora, tenemos que Ing. Carlos Martin Así, sin el ayudante, el costo esperado por hora es 6 + 50 = 56 dólares. Con el ayudante, = 15 clientes por hora. Por lo tanto W = 1/ 15-10 = 1/5 hora y Como el costo horario de servicio ahora es 6 + 4 = 10 dólares/h, el costo esperado de servicio con el ayudante es 20 + 10 = 30 dólares. Por lo tanto, se debe contratar al ayudante porque se ahorran 50-20 = 30 dólares/h en costos de demora, lo cual mas que compensa su salario de 4 dólares/h. Investigación Operativa Sistema de colas M/M/1/DG/c/ Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Sistema de colas M/M/1/DG/c/ Este sistema es un M/M/1/DG/c/ con una capacidad total de c clientes. El sistema M/M/1/DG/c/ es idéntico al M/M/1/DG// con excepción de que cuando hay presentes c clientes, todas las llegadas se regresan y el sistema las pierde para siempre. Suponemos que los tiempos entre llegadas son exponenciales con rapidez y que los tiempos de servicio son exponenciales con rapidez . Entonces el sistema M/M/1/DG/c/ se puede modelar (véase Fig.) como proceso de nacimiento y muerte con los siguientes parámetros: Ing. Carlos Martin Como c = 0, el sistema nunca alcanzará el estado c + 1, o cualquier otro estado de número mayor. Sistema de colas M/M/1/DG/c/ Conviene definir = / . Luego aplicamos las Ecs. (16) a (19) para ver que si , las probabilidad de estado estable para el modelo M/M/1/DG/c/ están expresadas por: Ing. Carlos Martin Sistema de colas M/M/1/DG/c/ Ing. Carlos Martin Como el caso del sistema M/M/1/DG//, Ls = 0 0 + 1 (1, + 2 +. . .) = 1- 0 Podemos calcular Lq, mediante Lq = L - Ls El cálculo de W y Wq, a partir de las Ecs. (28) y (29) tiene sus trucos. Recuerde que en las Ecs. (28) y (29), representa el número promedio de clientes que llegan por unidad de tiempo, quienes realmente entran al sistema. En nuestro modelo de capacidad finita, llega un promedio de , pero c, de esas llegadas encuentran al sistema lleno a toda capacidad y se van. (ef): en realidad entrará al sistema un promedio de - c = (1 - c) llegadas por unidad de tiempo. Al combinar este hecho con las Ecs. (28) y (29) se obtiene Ing. Carlos Martin Sistema de colas M/M/1/DG/c/ Para un sistema M/M/1/DG/c/, existirá estado estable aun sil . Esto se debe a que aun cuando , la capacidad finita del sistema evita que "explote" el número de gentes en la cola. Investigación Operativa Sistema de colas M/M/s/DG// Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Suponemos que los tiempos entre llegadas son exponenciales,con rapidez igual a , que los tiempos de servicio son exponenciales, con rapidez , y que hay solo una cola de clientes esperando su servicio en una de las s ventanillas o servidores. • Si hay j s clientes, entonces los j clientes están en el servicio; • Si hay j > s clientes, entonces las s ventanillas están ocupadas, y hay j - s clientes esperando en la cola. Toda llegada que encuentre una ventanilla vacía entra al servicio de inmediato, pero una llegada que no encuentre ventanilla vacía se forma en la cola de clientes que esperan su atención. Los bancos y las oficinas de correos, en los que todos los clientes esperan atención en una sola cola, se pueden modelar con frecuencia con los sistemas de cola M/M/s/DG// Ing. Carlos Martin Sistema de colas M/M/s/DG// Para describir el sistema M/M/s/DG// como modelo de nacimiento y muerte, observe que, como en el modelo M/M/1/DG// j = para j = 0, 1, 2,... Si hay j ventanillas o servidores ocupados, entonces se terminó el servicio con una frecuencia de Siempre que haya j clientes, estarán ocupadas: min (j,s) ventanillas Así, j = min (j, s) Ing. Carlos Martin Sistema de colas M/M/s/DG// En resumen, vemos que el sistema M/M/s/DG// se puede modelar como un proceso de nacimiento y muerte (véase Fig.) con parámetros: Ing. Carlos Martin Sistema de colas M/M/s/DG// Definimos a = /s. Para p < 1,al sustituir la Ec. (38) en (16) a (19) se obtienen las siguientes probabilidades de estado estable: Ing. Carlos Martin Sistema de colas M/M/s/DG// Si p 1, no existe estado estable. En otras palabras, si la frecuencia o rapidez de llegadas es al menos igual a la rapidez máxima posible de servicio = s., "explota" el sistema. De la Ec. (39.2), se puede demostrar que la probabilidad de estado estable de que todas las ventanillas estén ocupadas es: Ing. Carlos Martin Sistema de colas M/M/s/DG// También se puede demostrar que En la Tabla se muestra P (j s) para diversas situaciones. En la Tabla se muestra P (j s) para diversas situaciones. Ing. Carlos Martin Sistema de colas M/M/s/DG// Ing. Carlos Martin Sistema de colas M/M/s/DG// Para calcular L y después W, usamos el hecho de que L = Lq + Ls Como Ws = 1/ , la Ec. (30) muestra que Ls = /. Cuando necesitemos calcular L, Lq, W o Wq, comenzamos por buscar P (j s) en la Tabla. A continuación aplicamos las Ec. (41) a (44) para calcular la cantidad que deseemos. Si nos interesa la distribución probabilidad de estado estable, buscamos P (j s) en la Tabla y luego usamos la Ec. (40) para obtener 0 Así las Ecs (39.1) y (39.2) producen la distribución completa de estado estable. Ing. Carlos Martin Sistema de colas M/M/s/DG// Ing. Carlos Martin Sistema de colas M/M/s/DG// Ing. Carlos Martin Sistema de colas M/M/s/DG// Ing. Carlos Martin Sistema de colas M/M/s/DG// Además del tiempo esperado de un cliente en el sistema, es de interés la distribución del tiempo de espera de un cliente. Por ejemplo, si todos los clientes que tienen que esperar más de 5 minutos en una caja de supermercado deciden cambiar a otra tienda, la probabilidad que un cliente dado cambie a otro almacén es igual a P(W > 5). Para calcular esta probabilidad necesitamos conocer la distribución del tiempo de espera de un cliente. Para un sistema de colas M/M/s/PLPA// (primero en llegar primero en ser servido), se puede demostrar que Investigación Operativa Sistema de colas M/M/c/DG/N/ Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Esta situación de espera difiere de (M/M/c/DG//) en que se impone un límite N sobre la capacidad del sistema (es decir, tamaño máximo de la línea de espera = N - c). n y n, para el modelo actual están dadas por: Ing. Carlos Martin y observando que = /, Nótese que la única diferencia entre Pn, en este modelo y (M/M/c/DG// ocurre en la expresión de Po (0) Obsérvese también que el factor de uso /c no necesita ser menor que 1. Ing. Carlos Martin Investigación Operativa Sistema de colas M/M//DG/ / Modelo de autoservicio Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR En este modelo, el número de servidores es ilimitado porque cada cliente se atiende así mismo. Este es normalmente el caso en los establecimientos de autoservicio. Un ejemplo común es tomar la parte escrita de una prueba para obtener la licencia de conductor. Sin embargo, debemos tener cuidado de que situaciones como las gasolineras de autoservicio o los bancos con servicio las 24 horas no se clasifiquen en esta categoría de modelo. Esta conclusión se obtiene porque en estos casos los servidores son en realidad el surtidor de gasolina y el cajero automático del banco, aunque el cliente es el que opera el equipo. Ing. Carlos Martin Una vez más en términos del modelo generalizado se tiene Entonces: Ing. Carlos Martin que es de Poisson con media E{n} = . También tenemos : Nótese que Wq = 0 porque cada cliente se atiende a sí mismo. Esta es la razón por la que Wq, es igual al tiempo de servicio medio 1/ El modelo (M/M//DG//) se puede utilizar para determinar aproximadamente los de (M/M/c/DG//) cuando c crece "lo suficiente". La ventaja es que las operaciones son más sencillas en el modelo (M/M/). Demostramos la exactitud relativa de la aproximación presentando muestras de las medidas de desempeño de ambos modelos para diferentes valores de c y (= /). En la tabla se presenta un resumen de los resultados. Cuando se hace chico, el modelo (M/M/) es una aproximación bastante exacta del modelo (M/M/c) aun para c tan chica como 10. Ing. Carlos Martin Investigación Operativa Modelos de fuente finita: modelo de reparación de máquinas Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR A excepción del modelo M/M/1/DG/c/, todos los modelos que hemos estudiado han tenido frecuencias de llegada independientes del estado del sistema. Hay dos modelos donde quizá no sea válida la hipótesis de independencia de estado. 1. Si los clientes no desean formarse en colas largas, la frecuencia de llegada puede ser una función decreciente del número de personas presentes en el sistema de colas. 2. Si las llegadas a un sistema se toman de una población pequeña, la frecuencia de llegadas puede depender mucho del estado del Sistema. Por ejemplo, si un banco sólo tiene 10 clientes, entonces en un momento en que los 10 estén en el banco, la frecuencia de llegada debe ser cero, mientras que si hay menos de 10 personas en el banco, la frecuencia de llegadas puede ser positiva. Ing. Carlos Martin Los modelos en los que las llegadas se toman de una población pequeña se llaman modelos de origen finito. Ahora analizamos un modelo importante de origen finito que se conoce como el de reparación de máquinas, o de interferencia de máquinas. En el problema de reparación de máquinas, el sistema consta de K máquinas y R técnicos. En cualquier momento, una máquina determinada está en buen o en mal estado. El intervalo durante el cual una máquina permanece en buen estado sigue una distribución exponencial con rapidez . Siempre que se descompone una máquina, se manda a un centro de reparación que tiene R técnicos. El centro de reparación da servicio a las máquinas descompuestas como si llegaran conforme a un sistema M/M/R/DG// Ing. Carlos Martin Así, si hay j R máquinas en mal estado, una máquina que apenas se acaba de descomponer será enviada de inmediato para que la reparen; Si j > R máquinas están descompuestas, j - R máquinas estarán esperando en una cola para que un técnico se desocupe. Se supone que el tiempo que se necesita para completar la compostura de una maquina es exponencial con rapidez , O sea, que el tiempo promedio de reparación es 1/ . Una vez que se ha reparado una máquina, regresa en buen estado y de nuevo es susceptiblede descomponerse. llegaran conforme a un sistema M/M/R/DG// Ing. Carlos Martin El modelo de reparación de máquinas se puede considerar como proceso de nacimiento y muerte en el que el estado j en cualquier momento es el número de máquinas en mal estado. Con la notación de Kendall-Lee, el modelo que acabamos de explicar se puede expresar como sistema M/M/R/DG/K/K. La primera K indica que en cualquier momento puede haber no más de K clientes (o máquinas), y la segunda K quiere decir que las llegadas se toman de una fuente finita de tamaño K. Ing. Carlos Martin En la Tabla se da la interpretación de cada estado para un modelo de reparación de máquinas con K = 5 y R = 2 G = máquina en buen estado, y B máquina descompuesta. Ing. Carlos Martin Para determinar los parámetros de nacimiento y muerte para el modelo de reparación de máquinas (véase Fig), nótese que un nacimiento corresponde a una máquina que se descompone, y una muerte es una máquina que acaba de llegar ya reparada. Ing. Carlos Martin Para determinar los parámetros de nacimiento y muerte para el modelo de reparación de máquinas (véase Fig.), nótese que un nacimiento corresponde a una máquina que se descompone, y una muerte es una máquina que acaba de llegar ya reparada. Para calcular la frecuencia de natalidad en el estado J, debemos determinar la rapidez a la que se descomponen las máquinas cuando el estado del sistema es j. Cuando es así, hay K - j máquinas en buen estado. Como cada máquina se descompone con una frecuencia o rapidez , la frecuencia total a la que suceden las descomposturas cuando el estado es j es: Ing. Carlos Martin Definimos que = / Aplicando las Ecs. (16) a (18) se obtiene la siguiente distribución de probabilidades de estado estable: En la Ec. (52). donde 0! = 1, y n! = n (n - 1) . . . (2) (1) para n 1. Para usar la Ec. (52) comenzamos calculando 0 partiendo del hecho de que: 0 + 1 + . . . + n = 1 Ing. Carlos Martin Mediante las probabilidades de estado estable de la Ec. (52), podemos calcular las siguientes cantidades de interés: L = número esperado de máquinas descompuestas Lq = número esperado de máquinas que esperan servicio W = tiempo promedio que una maquina esta descompuesta Wq = tiempo promedio que una máquina espera servicio Desafortunadamente, no hay fórmulas sencillas para L, Lq, W y Wq. Lo mejor que podemos hacer es expresar estas cantidades en términos de las j ‘s: Ing. Carlos Martin Ing. Carlos Martin Si se aplica la Ec. (28) a las máquinas que se reparan y a las que esperan su turno, obtenemos: Aplicando la Ec. (29) a las máquinas que esperan campos fuera, tenemos Investigación Operativa Redes de colas Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Damos una introducción a los sistemas de redes que forman cola Veremos algunos conceptos básicos y ejemplos, en algunos casos nos limitaremos a presentar las medidas de eficiencia sin su demostración y en otros veremos directamente ejemplos. Haremos referencia a: 1.- Redes de colas (descripción y características) 2.- Colas en serie, es decir líneas de espera sucesivas o en tándem 2.1.- Modelos en serie de k estaciones con capacidad de línea de espera infinita (sin bloqueo) 2.2.- Modelos en serie de k estaciones con capacidad de línea de espera cero (con bloqueo) 3.- Redes abiertas de Jackson 4.- Redes cerradas de Jackson 4.1.- Colas cíclicas Ing. Carlos Martin Ing. Carlos Martin Hasta ahora se han tomado en cuenta nada mas que los sistemas de colas que tienen una instalación de servicio con uno o más servidores, pero los sistemas de colas que se encuentran en los estudios de I.O., en realidad a veces son redes de colas, es decir, redes de instalaciones de servicio en las que los clientes solicitan el servicio de algunas o todas ellas. Por ejemplo, las órdenes que se procesan en un taller se deben programar a través de una secuencia de maquinas entre un grupo (instalaciones de servicio). Es necesario, entonces, estudiar toda Ia red para obtener información sobre: el tiempo esperado total, el número esperado de clientes en todo el sistema, etc. Debido a la importancia de las redes de colas, hay mucha actividad de investigación en esta área. Sin embargo, es un campo difícil y aquí se dará sólo una breve introducción. Ing. Carlos Martin • Los sistemas de colas son muy comunes en la sociedad. • La adecuación de estos sistemas puede crear un efecto importante sobre la calidad de vida y Ia productividad. • Para estudiar estos sistemas, Ia teoría de colas formula modelos matemáticos que representan su operación y luego los usa para obtener medidas de desempeño. • Este análisis proporciona información vital para diseñar, de manera efectiva, sistemas que logren un balance apropiado entre el costo de proveer el servicio y el asociado con la espera por ese servicio. Ing. Carlos Martin Ing. Carlos Martin Introducción a las redes de colas Hasta ahora los clientes demandaban del sistema una sola operación de servicio. Los sistemas son de un solo nodo, donde quizá podía haber varios servidores idénticos paralelos. Ahora nos interesan sistemas con múltiples nodos en los que el cliente requiere servicio en más de uno. Los clientes pueden: Entrar al sistema por varios nodos, Encolarse para ser servidos y salir de un nodo dado para: o entrar en otro y recibir servicio adicional o o abandonar el sistema definitivamente. No todos los clientes entran y salen del sistema por los mismos nodos necesariamente, o siguen el mismo camino una vez en el sistema. Los clientes pueden regresar a nodos previamente visitados, saltarse algunos e incluso escoger permanecer en el sistema para siempre. Ing. Carlos Martin Redes de Colas Las redes de colas son un conjunto de nodos interrelacionados que funcionan de forma asíncrona (entradas y salidas de clientes no tienen que estar sincronizadas) y concurrente (simultáneamente). Po ejemplo, la mayoría de los sistemas informáticos son sistemas con múltiples nodos. Pueden tener terminales on-line, líneas de comunicación, impresoras, controladores de comunicación y el propio ordenador. Las redes de colas se clasifican en dos grupos. redes abiertas los clientes pueden entrar y salir del sistema. redes cerradas no entran nuevos clientes y los existentes nunca salen. El n° de clientes es constante a lo largo del tiempo (reparación de máquinas). La estructura topológica de la red es importante porque describe las transiciones admisibles entre nodos. También deben describirse los caminos recorridos por los clientes y los procesos estocásticos que configuran el flujo que circula por la red. Ing. Carlos Martin Teorema de Burke El proceso de salidas de clientes de un sistema M/M/s estable (λ/sµ < 1) con tasa de llegadas λ es un proceso de Poisson de tasa λ. La distribución del tiempo entre salidas consecutivas de un M/M/s es idéntica a la distribución del tiempo entre llegadas, es decir, es exponencial con parámetro λ. La distribución de las salidas es como la de las llegadas y no se ve afectada por el mecanismo de servicio exponencial. Se puede demostrar además que los tiempos entre salidas consecutivas son independientes entre si. Ing. Carlos Martin Propiedad de equivalencia El descubrimiento e implicaciones de un resultado de importancia fundamental para las redes de colas ameritan atención especial. Se rata de la propiedad de equivalencia para el proceso de entrada de los clientes y el proceso de salida de los que se van, en ciertos sistemas de colas. Propiedad de equivalencia: • suponga que una instalación de servicio tiene s servidores, un proceso de entradas Poisson con parámetro y la misma distribución de los tempos de servicio para cada servidor con parámetro (el modelo M/ M/s), en donde s > . • Entonces, la salida en estado estable de esta instalaciónde servicio también es un proceso Poisson con parámetro . Ing. Carlos Martin Observe que esta propiedad no hace suposiciones sobre el tipo de disciplina de la cola que usa. Ya sea primero en entrar, primero en salir, aleatorio o incluso una disciplina de prioridades, los clientes servidos dejarán Ia instalación de servicio de acuerdo a un proceso Poisson. La implicación esencial de este hecho para las redes de colas es que si estas unidades tienen que pasar a otra instalación para continuar su servicio, esta segunda instalación también tendrá entradas Poisson. Con una distribución exponencial para los tiempos de servicio la propiedad de equivalencia se cumplirá también para esta instalación que puede proporcionar entradas Poisson para una tercera instalación, y así sucesivamente. Se presentaran las consecuencias de dos tipos básicos de redes: • Colas Infinitas en Serie • Redes abiertas de Jackson Ing. Carlos Martin Investigación Operativa Colas Infinitas en Serie Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Suponga que todos los clientes deben recibir servicio en una serie de m instalaciones, en una secuencia fija. Suponga que cada instalación tiene una cola infinita (sin límite en el número de clientes que acepta), de manera que las instalaciones en serie forman un sistema de colas infinitas en serie. Suponga, además, que los clientes llegan a la primera instalación de acuerdo a un proceso Poisson con parámetro y que cada instalación (i = 1,2,.., m) tiene la misma distribución exponencial de tiempos de servicio con parámetro i, para sus Si servidores, en donde Si i > Por la propiedad de equivalencia se puede decir que (en condiciones de estado estable) cada instalación de servicio tiene entrada Poisson con parámetro . Entonces, se puede usar el modelo elemental M/M/s (o su contraparte con disciplina de prioridades) para analizar cada instalación de servicio en forma independiente de las otras. Ing. Carlos Martin Colas Infinitas en Serie Al poder usar el modelo M/ M/s para obtener las medidas de desempeño para cada instalación independiente, en lugar de analizar la interacción entre las instalaciones, se tiene una simplificación enorme. Por ejemplo, Ia probabilidad de tener n clientes en una instalación en particular está dada por la fórmula de n para el modelo M/ M/s. La probabilidad conjunta de n1 clientes en Ia instalación 1, n2 clientes en la instalación 2, etcétera, es entonces, el producto de las probabilidades individuales obtenidas de esta manera sencilla. En particular, esta probabilidad conjunta se puede expresar como: Ing. Carlos Martin Esta forma sencilla de solución se llama solución en forma de producto. De manera similar, el tiempo de espera total esperado y el número esperado de clientes en el sistema completo se pueden obtener con sólo sumar las cantidades correspondientes obtenidas para cada instalación. Desafortunadamente, la propiedad de equivalencia y sus implicaciones no se cumplen para el caso de colas finitas. De hecho, este caso es importante en la práctica, ya que con frecuencia se tienen limitaciones definidas para la longitud de la cola que admite cada instalación de servicio de una red. Por ejemplo, es común que se proporcione sólo un pequeño espacio para almacenaje en cada instalación (estación de trabajo) de una línea de producción. Para este tipo de sistemas de colas finitas en serie no se dispone de una solución en forma de producto sencilla. En su lugar, se deben analizar las instalaciones en forma conjunta y sólo se han obtenido resultados limitados. Ing. Carlos Martin En los modelos de cola que hemos estudiado hasta aquí, todo el tiempo de servicio a un cliente se gasta con un solo servidor. En muchos casos, como en la producción de un articulo en una línea de montaje, los trámites del cliente no se terminan si no hasta que haya intervenido más de un servidor. Al entrar al sistema de la Fig. el cliente pasa por la etapa 1 de servicio, después de esperar en una cola si todos los servidores de la etapa 1 están ocupaos cuando llega. Después de terminar la etapa 1 de servicio, el cliente espera y pasa a la etapa 2 de servicio. Este proceso sigue hasta que el cliente termina la etapa k de servicio. Un sistema como el de la Fig. se llama sistema de colas de k etapas en serie, o en tándem. Ing. Carlos Martin Colas exponenciales en serie Ing. Carlos Martin Teorema de Jackson Contamos con un notable teorema debido a Jackson (1957), que es el siguiente: Si: ( 1) los tiempos de llegada a un sistema de colas en serie son exponenciales con rapidez , (2) los tiempos de servicio para cada tramite en la etapa i son exponenciales, y (3) toda etapa tiene sala de espera de capacidad infinita, entonces los tiempos entre llegada para alcanzar cada etapa del sistema de colas son exponenciales con rapidez . Ing. Carlos Martin Para que este resultado sea válido, cada etapa debe tener capacidad suficiente para dar servicio a una corriente de llegadas que entre con rapidez ; si no es así, el sistema "explotaría" en la etapa que tuviera capacidad insuficiente. De acuerdo con el análisis del sistema M/M/s/DG//, vemos que cada etapa tendrá capacidad suficiente para manejar una corriente de llegadas de rapidez o frecuencia , si y sólo si: < sj j, cuando j = 1, 2, . . . , k Si < sj j, el resultado de Jackson quiere decir que la etapa j del sistema de la Fig. se puede analizar como un sistema M/M/s/DG// con tiempos exponenciales entre llegadas que tienen la rapidez y tiempos exponenciales de servicio con un promedio 1/. Ing. Carlos Martin Podemos analizar a cada estación separadamente como un modelo de formación de colas de nivel único (no en serie). En estas condiciones puede comprobarse que para i, la salida de la estación i ( o equivalente, la entrada a la estación i+1) es de Poisson con tasa media y que cada estación puede tratarse independientemente como M/M/s/DG// , por lo tanto se puede utilizar a dicho modelo para su resolución. Para cada instalación se puede obtener: • i, Lqi, Wqi • La probabilidad individual de tener n clientes en una instalación en particular i y que esta dada por la formula de Pn y según sea el caso M/M/1; M/M/s; M/M/ Ing. Carlos Martin Para el sistema completo se puede obtener: • La probabilidad conjunta de tener n1 clientes en Ia instalación 1, n2 clientes en la instalación 2, etcétera, como el producto de las probabilidades individuales obtenidas de esta manera sencilla: • El tiempo medio total esperado en la cola como la suma de los tiempos de espera para cada estación: Wq = σ𝒊=𝟏 𝒌 𝑾𝒒𝒊 Wqi = 𝑳𝒒𝒊 • El numero esperado total de clientes en el sistema de colas como la suma del numero promedio de clientes que esperan en cada estación de servicio: L = σ𝒊=𝟏 𝒌 𝑳𝒊 Lq=σ𝒊=𝟏 𝒌 𝑳𝒒𝒊 • El tiempo promedio que pasa un cliente en el sistema: W = 𝑳 Ing. Carlos Martin Investigación Operativa Modelo en serie de dos estaciones con capacidad de líneas de espera cero Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Como un ejemplo del análisis de filas en serie, considere un sistema de colas de un canal simplificado que consiste en dos estaciones en serie como se muestra en la figura. Un cliente que llega para ser atendido debe pasar por la estación 1 y la 2. Los tiempos de servicio en cada estación están exponencialmente distribuidos con la misma tasa de servicio . Las llegadas ocurren según una distribución de Poisson con tasa . No se permite ninguna cola enfrente de las estaciones 1 o 2. La construcción del modelo requiere primero identificar los estados del sistema en cualquier punto en el tiempo. Esto se logra como sigue: Cada estación puede estar libre u ocupada. La estación 1 se dice que está bloqueada si el cliente en esta estación completa su servicio antes
Compartir