• Author / Uploaded
• indira

Citation preview

UNIVERSIDAD DE SAN MARTIN DE PORRES FACULTAD DE INGENIERIA Y ARQUITECTURA

TEORIA DE COLAS Monografía que se presenta como parte del curso de INVESTIGACION OPERATIVA I INTEGRANTES: Cabrejos Alvarez, Danpne Córdova De Paz, Carla Gonzáles Fernández, Geraldine Gutiérrez Beltrán, Indira Gandy Vicuña Solórzano, Katzy PROFESOR: Ing. José Villanueva SECCION: 33G 2008

INTRODUCCION

En la presente monografía trataremos el tema sobre TEORIA DE COLAS, que pertenece al programa WINQSB, con el que se trabajara en el desarrollo de esta. Todos hemos experimentado en alguna ocasión la sensación de estar perdiendo el tiempo al esperar en una cola. El fenómeno de las colas nos parece natural: esperamos en el coche al estar en un tapón, o un semáforo mal regulado, o en un peaje; esperamos en el teléfono a que nos atienda un operador y en la cola de un supermercado para pagar.... Como clientes no queremos esperar, los gestores de los citados servicios no quieren que esperemos.... ¿Por qué hay que esperar? La respuesta es casi siempre simple, en algún momento la capacidad de servicio ha sido, o es menor que la capacidad demandada. Generalmente esta limitación se puede eliminar invirtiendo en elementos que aumenten la capacidad. En estos casos la pregunta es: ¿Compensa invertir? La teoría de colas intenta responder a estas preguntas utilizando análisis matemáticos detallados. El programa WINQSB trata de es un sistema interactivo de ayuda a la toma de decisiones que contiene herramientas muy útiles para resolver distintos tipos de problemas en el campo de la investigación operativa.

¿QUE ES TEORIA DE COLAS? La teoría de colas es el estudio matemático de las líneas de espera (o colas) permitiendo el análisis de varios procesos relacionados como: la llegada al final de la cola, la espera en la cola, etc. La teoría de colas generalmente es considerada una rama de investigación operativa porque sus resultados a menudo son aplicables en una amplia variedad de situaciones como: negocios, comercio, industria, ingenierías, transporte y telecomunicaciones. En el contexto de la informática y de las nuevas tecnologías estas situaciones de espera son más frecuentes. Así, por ejemplo, los procesos enviados a un servidor para ejecución forman colas de espera mientras no son atendidos, la información solicitada, a través de Internet, a un servidor Web puede recibirse con demora debido a la congestión en la red, también se puede recibir la señal de línea de la que depende nuestro teléfono móvil ocupada si la central está colapsada en ese momento, etc. Campos de utilización: logística de los procesos industriales de producción, ingeniería de redes y servicios, ingeniería de sistemas informáticos, etc. Agner Krarup Erlang, un matemático danés que trabajó para la Copenhagen Telephone Exchange, publicó el primer artículo sobre la teoría de colas en 1909. Se encargó del estudio del problema de dimensionamiento de líneas y centrales de conmutación telefónica para el servicio de llamadas.

OBJETIVO DE LA TEORIA DE COLAS: Los objetivos de la teoría de colas consisten en: • • • •

Identificar el nivel óptimo de capacidad del sistema que minimiza el costo del mismo. Evaluar el impacto que las posibles alternativas de modificación de la capacidad del sistema tendrían en el costo total del mismo. Establecer un balance equilibrado (“óptimo”) entre las consideraciones cuantitativas de costes y las cualitativas de servicio. Prestar atención al tiempo de permanencia en el sistema o en la cola.

DE QUE TRATA UN SISTEMA DE COLAS: Un sistema de colas se puede describir como: “clientes” que llegan buscando un servicio, esperan si este no es inmediato, y abandonan el sistema una vez han sido atendidos. En algunos casos se puede admitir que los clientes abandonan el sistema si se cansan de esperar.

El término “cliente” se usa con un sentido general y no implica que sea un ser humano, puede significar piezas esperando su turno para ser procesadas o una lista de trabajo esperando para imprimir en una impresora en red. Servicio clientes que abandonan clientes llegando clientes servidos. Un sistema de cola típico:

Aunque cualquier sistema se puede representar como en esta figura, debe quedar claro que una representación detallada exige definir un número elevado de parámetros y funciones.

TIPOS DE COLAS: Según el tipo de sistema de colas, tenemos varios tipos de éstas, las cuales son: • Una línea, un servidor El primer sistema que se muestra se llama un sistema de un servidor y una cola o puede describir una consulta de un médico. • Una línea, múltiples servidores. El segundo, una línea con múltiples servidores, es típico de una peluquería o una panadería en donde los clientes toman un número al entrar y se les sirve cuando les llega el turno. • Varias líneas, múltiples servidores El tercer sistema, en que cada servidor tiene una línea separada, es característico de los bancos y las tiendas de autoservicio. Para este tipo de servicio pueden separarse los servidores y tratarlos como sistemas independientes de un servidor y una cola. Esto sería válido sólo si hubiera muy pocos intercambios entre las colas. Cuando el intercambio es sencillo y ocurre con frecuencia, como dentro de un banco, la separación no sería válida.

CARACTERISTICAS DE LA TEORIA DE COLAS: Seis son las características básicas que se deben utilizar para describir adecuadamente un sistema de colas: • • • • • •

Patrón de llegada de los clientes Patrón de servicio de los servidores Disciplina de cola Capacidad del sistema Número de canales de servicio Número de etapas de servicio

Algunos autores incluyen una séptima característica que es la población de posibles clientes. •

Patrón de llegada de los clientes.En situaciones de cola habituales, la llegada depende de una cierta variable aleatoria, en este caso es necesario conocer la distribución probabilística entre dos llegadas de cliente sucesivas. Además habría que tener en cuenta si los clientes llegan independiente o simultáneamente. En este segundo caso (es decir, si llegan lotes) habría que definir la distribución probabilística de éstos.

También es posible que los clientes sean “impacientes”. Es decir, que lleguen a la cola y si es demasiado larga se vayan, o que tras esperar mucho rato en la cola decidan abandonar. Por último es posible que el patrón de llegada varíe con el tiempo. Si se mantiene constante le llamamos estacionario, si varía con las horas del día es no-estacionario. •

Patrones de servicio de los servidores.Los servidores pueden tener un tiempo de servicio variable, en cuyo caso hay que asociarle, para definirlo, una función de probabilidad. También pueden atender en lotes o de modo individual. El tiempo de servicio también puede variar con el número de clientes en la cola, trabajando más rápido o más lento, y en este caso se llama patrones de servicio dependientes. Al igual que el patrón de llegadas el patrón de servicio puede ser no-estacionario, variando con el tiempo transcurrido.

•

Disciplina de cola.La disciplina de cola es la manera en que los clientes se ordenan en el momento de ser servidos de entre los de la cola. Cuando se piensa en colas se admite que la disciplina de cola normal es FIFO (atender primero a quien llegó primero) Sin embargo en muchas colas es habitual el uso de la disciplina LIFO (atender primero al último). También es posible encontrar reglas de secuencia con prioridades, como por ejemplo secuenciar primero las tareas con menor duración o según tipos de clientes. En cualquier caso dos son las situaciones generales en las que trabajar. En la primera, llamada en inglés “preemptive”, si un cliente llega a la cola con una orden de prioridad superior al cliente que está siendo atendido, este se retira dando paso al más importante. Dos nuevos subcasos aparecen: el cliente retirado ha de volver a empezar, o el cliente retorna donde se había quedado. La segunda situación es la denominada “nopreemptive” donde el cliente con mayor prioridad espera a que acabe el que está siendo atendido.

•

Capacidad del sistema.Existe una limitación respecto al número de clientes que pueden esperar en la cola. A estos casos se les denomina situaciones de cola finitas. Esta limitación puede ser considerada como una simplificación en la modelización de la impaciencia de los clientes.

•

Número de canales del servicio.Es evidente que es preferible utilizar sistemas multiservidos con una única línea de espera para todos que con una cola por servidor. Por tanto, cuando se habla de canales de servicio paralelos, se habla generalmente de una cola que alimenta a varios servidores mientras que el caso de colas independientes se asemeja a múltiples sistemas con sólo un servidor.

Sistema de cola MONOCANAL

•

Sistema de cola MULTICANAL

Etapas de servicio.Un sistema de colas puede ser unietapa o multietapa. En los sistemas multietapa el cliente puede pasar por un número de etapas mayor que uno. Una peluquería es un sistema unietapa, salvo que haya diferentes servicios (manicura, maquillaje) y cada uno de estos servicios sea desarrollado por un servidor diferente. En algunos sistemas multietapa se puede admitir la vuelta atrás o “reciclado”, esto es habitual en sistemas productivos como controles de calidad y reprocesos. SISTEMA MULTIETAPA CON RETROALIMENTA CIÓN.

WINQSB – QUEUING ANALYSIS (QA) El programa WINQSB esta conformado por 20 aplicativos, en el cual, en esta presente monografía, nos centraremos en uno de ellos el “QUEUING ANALYSIS”. El aplicativo QUEUING ANALYSIS se basa en la TEORIA DE COLAS, que es un análisis de los instrumentos más importantes para quienes participan con equipo y análisis de redes. El número de preguntas que pueden abordarse en un análisis de cola es interminable y afecta prácticamente todas las áreas en ciencias. La capacidad de hacer un análisis de este tipo es una herramienta esencial para quienes participan en este campo. Aunque la teoría de la cola es matemáticamente compleja, la aplicación de cola la teoría al análisis de los resultados es, en muchos casos, muy sencilla. Un conocimiento elemental de los conceptos estadísticos (medias y desviaciones estándar) y una base comprensión de la aplicabilidad de la teoría de colas es todo lo que se requiere.

CAPACIDADES ESPECÍFICAS DEL QUEUING ANALYSIS: Las capacidades específicas de QA incluyen: • • • • • • • • •

Análisis de la actuación de la cola Análisis de sensibilidad para los parámetros del sistema Análisis de capacidad para colas y capacidad de servicio Aproximación si no existiese una forma similar Simulación - la alternativa para la evaluación de la actuación 15 distribuciones de probabilidad para el tiempo de servicio, los tiempos entre llegadas, y tamaño de lote de llegada Muestra la actuación de la cola y análisis del costo Muestra un gráfico que muestra el análisis de sensibilidad Entrada de los datos simple para los sistemas M/M

ANÁLISIS DE SENSIBILIDAD: QA realiza el análisis de sensibilidad según un rango especificado de número de servidores. QA resuelve y compara las actuaciones según la entrada, salida, y valores del paso del parámetro seleccionado. ANÁLISIS DE CAPACIDAD: Dos capacidades básicas del sistema de colas son consideradas en QA: • •

Número de servidores La capacidad de la cola.

Después de especificar los rangos del número de servidores y la capacidad de la cola, QA realiza la comparación del costo para una combinación de capacidades diferentes. FORMULA DE APROXIMACIÓN: Cuando el problema de la formación de colas no tiene ninguna solución aproximada, QA resuelve el Lq como un modelo de G/G/s para la aproximación siguiente Lq= (Lq de M/M/s) [var. (Tiempo de servicio)µ² + var. (Tiempo entre llegadas)λ²]/2

Donde: Var. representa la varianza. El resto de las medidas de la actuación de la cola siguen la fórmula de M/M/s.

SIMULACION, SIMULACION MONTE CARLO, SIMULACION DE EVENTOS DISCRETOS: La simulación es la imitación de un proceso del mundo-real o sistema a lo largo del tiempo. Genera eventos artificiales o procesos para el sistema y recolecta las observaciones para dibujar cualquier inferencia sobre el sistema real. Una simulación de los eventos discretos simula sólo eventos que cambian el estado de un sistema. QA realiza la simulación de eventos discretos simulando los dos eventos mayores en el sistema de colas: • •

Llegada del cliente Realización de servicio.

El método de Monte Carlo emplea los modelos matemáticos o la transformación inversa para generar variables del azar para los eventos artificiales y colecciona observaciones. QA también acostumbra usar la transformación inversa para generar el tiempo de servicio, el tiempo entre llegadas, y tamaño del lote que guía el evento del sistema de formación de colas. DESCRIPCION DE ALGUNOS APLICATIVOS DEL QUEUING ANALYSIS:

Este comando inicia un nuevo problema de colas. La entrada para el nuevo problema incluye nombre del problema, unidad de tiempo, número de servidores, la proporción de servicio (µ) con una distribución de tiempo de servicio, coeficiente de presión de servicio, proporción de la llegada (λ) con una distribución de tiempo entre llegadas, el tamaño del lote (volumen) con una distribución de tamaño de lote, etc. Este comando inicia una ventana de dialogo para abrir un archivo guardado previamente. El diálogo le permite tanto seleccionar un archivo de datos en directorio en particular, o entrar una especificación de un archivo completo de datos incluyendo la ruta.

Este comando permite salir del programa BARRA DE TAREAS: La barra de tareas es similar a la que existe en los otros módulos del WINQSB, diferenciándose solamente en algunos botones, por lo cual solo se explicará a aquellos que diferencian a este de los otros módulos:

Este comando resuelve la actuación de la cola. Si no existe ninguna fórmula aproximada para el problema, el programa preguntará si para resolverlo desea hacerlo por aproximación o por la simulación de Monte Carlo.

Este orden realiza la simulación de eventodiscreto de Monte Carlo para evaluar la actuación de la cola.

Esta orden realiza el análisis de sensibilidad del problema de colas para un rango especificado de número de servidores, coeficiente de retardación de llegada, el tamaño de lote (volumen), la capacidad de la cola, población del cliente, costo de servidor ocupado, del servidor ocioso, costo de cliente en espera, costo de cliente servido, costo por cliente sin atender, costo unitario de la capacidad de la cola. Todos por unidad de tiempo. Esta orden realiza el análisis de capacidad del problema de colas con un número diferente de servidores y capacidad de la cola.

Este comando dispone de las siguientes opciones: •

Performance Summary.- Esta orden muestra la actuación del problema de colas. Incluye todas las medidas populares de la formación de colas.

•

Probability Summary.- Este comando muestra la probabilidad del sistema de colas. Muestra P(n), la probabilidad de que existan n clientes en el sistema, donde n puede ser desde 0 a 200, y la probabilidad acumulativa.

•

Show Capacity Analysis.- Este comando muestra los resultados del análisis de capacidad del problema colas con un número diferente de servidores y capacidad de la cola. Todos los elementos del costo relacionados están incluidos.

VENTAJAS DEL QUEUING ANALYSIS: •

La teoría de colas hace posible estudiar y trabajar en la realidad con las interacciones complejas de un sistema dado.

•

A través de la teoría de colas podemos estudiar el efecto de cambios ambientales, organizacionales de cierta información, en la operación del sistema.

•

La observación detallada del sistema, nos permite tener una mejor comprensión del mismo.

•

La teoría de colas nos permite trabajar con situaciones nuevas, para los cuales no solo se requiere de información sino que también se necesita los estudios reales para el manejo de los mismos.

DESVENTAJAS DEL QUEUING ANALYSIS: •

Se requiere gran cantidad de corridas para encontrar “soluciones óptimas”.

•

Se pueden tener limitaciones o restricciones en la disponibilidad del software requerido.

PROBLEMA: El gerente del banco FIA, desea saber cuántos cajeros deberán estar en ventanilla los fines de semana para la atención al público. El gerente sabe que cada servidor en promedio tarda dos minutos por cliente, cada servidor recibe $6 por hora, además se sabe que el costo por tiempo ocio de los servidores es de $1 por hora. Los clientes generan en su espera una perdida de $0.06 por hora al banco, si un cliente no es atendido a tiempo nos cuesta $1. El banco FIA tiene capacidad para 120 personas. Se sabe que por minuto llegan en promedio 2 clientes, dando un costo de atención de $3. a) ¿Cuántos cajeros contratara el gerente?

b) ¿Será necesario adquirir dos servidores mas que comparaciones podemos obtener?

Podemos apreciar en este cuadro, una vez abierto el programa WINQSB, se elige el aplicativo QUEUING ANALYSIS y se ingresa el titulo del problema.

Podemos apreciar en este cuadro, una vez abierto el aplicativo QUEUING ANALYSIS, se ingresan los datos del problema.

Al momento de ingresar los datos del problema, se procede a resolver el problema con la opción “SOLVE THE PROBLEM” y se apreciara los siguientes resultados.

En este cuadro se apreciara la probabilidad para una cierta cantidad de clientes, en un tiempo de simulación de 24 horas.

En este cuadro se aprecia el análisis de sensibilidad del problema

Si se toma análisis de sensibilidad, seleccionando como parámetro de análisis a la tasa de llegadas, se selecciona la opción que se aprecia en el grafico.

En este grafico podemos observar que el uso del sistema incrementa en 10, el sistema, también verifica que la cantidad de cajeros, en este caso es suficiente para poder recepcionar a todos los clientes.

Para poder visualizar una grafica se eligen las siguientes opciones.

Esta es la grafica de nuestro problema.

CONCLUSIONES

•

Este programa, Análisis de Colas (QA), resuelve y evalúa la actuación de un sistema de colas y costos.

•

Este programa resuelve la actuación de una sola fase de un sistema de colas.

•

La fase única que hace cola en un sistema tiene elementos mayores incluso una población del cliente, una cola, y uno o varios servidores (canales).

•

Tres métodos son incluidos para evaluar cada situación de la formación de colas: fórmula de cercanía, aproximación, y la simulación de Monte Carlo.

•

Si ninguna forma está disponible para un problema de colas particular, usted puede especificar una aproximación o simularla para poder resolverla.

BIBLIOGRAFIA 1.- TITULO: "ANALISIS CUANTITATIVO PARA LA TOMA DE DESICIONES". AUTORES: Bierman,Harold; Bonini, Charles P; Hausman, Worren H. EDITORIAL: Delaware, Add, Son-Wesley Iberoamericana 1994 (CODIGO DE LA BIBLIOTECA: 658.40352/B48). 2.- TITULO: "INVESTIGACION DE OPERACIONES" AUTORES: Moskowitz; Herber Wright. P; Gordon. EDITORIAL: Mexico, Prentice Hall Hispanoamericana 1993 (CODIGO DE LA BIBLIOTECA: 658.403/M81).