Diseño y Simulación de Sistemas de Colas con e-Motions

Diseño y Simulación de Sistemas de Colas con e-Motions José M. Bautista, Javier Troya, and Antonio Vallecillo GISUM/Atenea Research Group. Universidad de Málaga (Spain). {jmbautista,javiertc,av}@lcc.uma.es Resumen Este trabajo propone el uso de un lenguaje de dominio especíco de alto nivel y ejecutable para analizar el rendimiento de un sistema de colas implementado mediante diferentes estrategias. En concreto se utiliza un enfoque basado en el Desarrollo del Software Dirigido por Modelos (DSDM) para modelar el comportamiento del sistema de facturación de una aerolínea y obtener datos relativos a su rendimiento en cuanto a costes y tiempos de espera, dependiendo de la estrategia utilizada. Para lograr ese propósito se utiliza e-Motions , una herramienta que permite al usuario modelar y analizar sistemas en tiempo real de forma gráca. 1. Introducción Los sistemas de colas son ampliamente usados, tanto en nuestra vida cotidiana, como en el ámbito de la Ingeniería Software. Existe una gran variedad de situaciones reales que se pueden modelar utilizando la Teoría de Colas, desde comprar entradas en las taquillas de un cine a acceder a los servidores de una página web. Por este motivo es interesante analizar la calidad de servicio que proporciona este tipo de sistemas. Estudiando los resultados obtenidos del análisis se pueden modicar o implementar mejores sistemas de control de congestión u optimizar la planicación de procesos que gestionan las colas. En este trabajo mostramos un enfoque DSDM para diseñar y modelar un sistema de colas de modo preciso y ecaz con un alto nivel de abstracción. Para llevar a cabo nuestro propósito hemos empleado e-Motions , un lenguaje que permite especicar, analizar y simular sistemas en tiempo real. Mediante su interfaz gráca es posible denir el comportamiento de un lenguaje de dominio especíco de manera intuitiva. Para ilustrar nuestro enfoque hemos utilizado como ejemplo el sistema de colas de facturación de una aerolínea. Hemos estudiado diferentes estrategias con el n de optimizar el tiempo de espera de los pasajeros en las colas manteniendo un coste razonable para la aerolínea. La estructura de este artículo es la siguiente. La Sección 2 introduce el caso de estudio en el que se basa nuestro análisis y los parámetros de calidad estudiados. A continuación, la Sección 3 describe el comportamiento dinámico de dicho sistema para su simulación y análisis, como posteriormente comentamos en la Sección 4. Por último, la sección 5 presenta las conclusiones. Jos´e M. Bautista, Javier Troya, Antonio Vallecillo Jornadas de Ingenier´ıa del Software y Bases de Datos (JISBD) A Coru˜na, 5–7 Septiembre 2011 769 2. Caso de estudio Un ejemplo típico de los sistemas de colas que pretendemos analizar se encuentra en los mostradores de facturación de una aerolínea. Los parámetros de calidad en este tipo de sistemas dependen fundamentalmente de dos factores: el tiempo medio de espera de los pasajeros, y el coste asociado al número de mostradores abiertos (cada mostrador tiene un coste a pagar al aeropuerto). Encontrar el óptimo en cada caso es importante para las compañias aéreas. Una de las primeras decisiones a tomar en el diseño de este tipo de sistemas es la relativa al modelo a escoger. Podemos por ejemplo seguir un modelo español, en donde cada mostrador tiene asociada una cola, o bien un modelo anglosajón, en donde hay una cola común para todos los mostradores. Los españoles siempre nos hemos quejado que nuestro sistema es peor. En este trabajo analizamos ambos sistemas y comparamos los resultados obtenidos. 2.1. Planteamiento del problema Se supone que el vuelo lo componen T= 240 viajeros. El periodo de facturación es de dos horas y todos los pasajeros llegan a la zona de facturación en ese periodo. La frecuencia con que lo hacen sigue una campana de Gauss, llegando el mayor número de pasajeros justo una hora antes del cierre. Supongamos que la aerolínea dispone de un máximo de N= 5 mostradores de facturación. Cada mostrador tiene asociada una cola de pasajeros a los que atender. El tamaño máximo de la cola viene determinado por una variable maxSize i, i = 1..N (cada mostrador puede tener un tamaño de cola distinto). Asimismo, el tiempo de servicio de cada mostrador viene determinado por una distribución exponencial de media serviceTime i(i= 1..N) puesto que cada mostrador puede tardar más o menos en servir a los clientes (esto modela, por ejemplo, que la persona atendiendo el mostrador tenga más o menos experiencia, o que sea más o menos espabilado). Inicialmente supondremos que todos los mostradores siguen la misma distribución, de media serviceTime i= 60 segundos. En el sistema anglosajón, cuando un pasajero llega un encargado de la aerolínea (el gestor del embarque, o dispatcher ) le indica a cuál de los mostradores ha de dirigirse para facturar. Los pasajeros esperan en una cola a que el dispatcher los redirija a uno de los mostradores abiertos. En este caso, el tamaño máximo de la cola asociada a cada mostrador es 1, y la cola del dispatcher se supone no acotada. En el sistema español, por contra, el tamaño máximo de la cola asociada a cada mostrador es no acotada. El número de mostradores abiertos puede ser jo a lo largo de todo el embarque, o bien irse abriendo o cerrando dependiendo de las decisiones del dispatcher (que puede seguir diferentes algoritmos). Por ejemplo, en el sistema español el dispatcher siempre remite a los pasajeros a la cola menos poblada, y ordena abrir un mostrador cuando el tamaño de alguna de las colas de los mostradores abiertos sobrepasa un cierto umbral. Igualmente, cuando alguna de las colas baja de otro umbral determinado el dispatcher ordena cerrarla. El mostrador cerrado sigue operando hasta servir a los viajeros que tenía en la cola, aunque no admite Dise˜no y Simulaci´on de Sistemas de Colas con ¡i¿e-Motions¡/i 770 Jornadas de Ingenier´ıa del Software y Bases de Datos (JISBD) A Coru˜na, 5–7 Septiembre 2011 Figura 1. Metamodelo Airport . a nuevos viajeros (a menos que lo abran otra vez mientras servía a los viajeros que estaban en su cola, algo que puede suceder). El tiempo que trascurre entre que se ordena abrir un mostrador y éste se abre es constante (supongamos que es de 5 minutos). También vamos a suponer que de los 240 pasajeros hay algunos de ellos que pueden dar problemas, añadiendo algunos minutos a su tiempo de servicio (por ejemplo porque han olvidado el pasaporte, no encuentran el billete o llevan equipaje de más). Supongamos que este tiempo añadido se distribuye según una distribución exponencial de parámetro 5 (es decir, que en media va a relentizar 5 minutos el procesado de sus billetes). Esto le puede pasar a cualquier pasajero, independientemente de cuando llegue. 2.2. Modelado del sistema El metamodelo del sistema se muestra en la gura 1. En un aeropuerto hay personal de gestión de embarque, representado aquí por la clase Dispatcher , y mostradores de facturación ó CheckInDesk . Para tomar decisiones el dispatcher cuenta con unos umbrales prejados, uno mínimo y uno máximo, de tamaño de la cola ( thresholdMin y thresholdMax ). Los mostradores cuentan con un atributo, open , para indicar si están abiertos o cerrados al público. En caso de estar abiertos tendrán una cola de pasajeros cuyo tamaño máximo vendrá determinado por el atributo maxSize . Cada mostrador empleará por defecto un tiempo, denido a partir del atributo serviceTime , en atender a cada pasajero. Para facilitar la labor de control de congestión de las colas, se establece para cada mostrador unos umbrales mínimo y máximo de tamaño de cola ( thresholdMin y thresholdMax ). Los pasajeros de la aerolínea almacenan en el atributo arrival el instante de llegada al aeropuerto, momento en el cual se dirigen al gestor de embarque, Jos´e M. Bautista, Javier Troya, Antonio Vallecillo Jornadas de Ingenier´ıa del Software y Bases de Datos (JISBD) A Coru˜na, 5–7 Septiembre 2011 771 que les informa del mostrador al que deben acudir. Una vez que el pasajero se presenta en la cola del mostrador que le ha sido asignado se registra tanto el instante en que llega a dicha cola, mediante el atributo arrivalCheckIn , como el momento en que abandona el mostrador una vez realizada la facturación, en el atributo departure . Para identicar a los pasajeros problemáticos se emplea el atributo troublemaker . 2.3. Parámetros a analizar. Observadores Para analizar el mejor sistema es preciso determinar un criterio de funcionamiento óptimo. En nuestro caso hemos tratado de buscar un equilibrio entre el tiempo medio de servicio de los clientes y el coste que supone a la compañía el embarque. Para ello nos hemos centrado en los siguientes parámetros: Tiempo medio de servicio . Tiempo medio transcurrido desde que un pasajero entra en la zona de facturación hasta que abandona el mostrador con los billetes. Coste . Coste total del proceso de embarque. Es el producto de la suma de las unidades de tiempo que cada mostrador ha estado abierto durante la facturación y el coste por unidad de tiempo que supone a la aerolínea un mostrador abierto. Hemos considerado que cada minuto que un mostrador está abierto cuesta 5 euros (variable cpu en la g. 8). Tiempo máximo de espera . Máximo de los tiempos de espera de los pasajeros. Para medir estos parámetros utilizamos los observadores , elementos que permiten monitorizar sistemas modelados con lenguages especícos de dominio [1]. Para ello basta con denir un metamodelo con los observadores que queremos incluir, y añadirlo al del propio sistema. En e-Motions , esto es posible hacerlo de forma no-intrusiva, es decir, sin modicar el metamodelo de nuestro sistema. La gura 2 muestra el metamodelo de los observadores denidos en este caso para poder medir las propiedades de calidad de servicio mencionadas anteriormente. A continuación se describen brevemente los tres observadores utililizados: GeneralOb . Observador general para contar los pasajeros que llegan, los que ya han facturado, su tiempo medio de espera, el tiempo máximo de espera, el coste total del sistema y el tiempo total que han tardado todos en facturar. DispacherOb . Observador asociado al dispatcher del sistema. Cuenta el número de pasajeros que ha atendido, el tiempo medio que los pasajeros han estado esperando a ser atendidos y la longitud media de la cola del dispatcher. DeskOb . Hay un observador de este tipo asociado a cada mostrador, para contar el número de pasajeros atentidos en el mostrador, el tiempo de apertura, la longitud media de la cola del mostrador y el tiempo medio que los pasajeros han estado esperando en la cola a ser atendidos. Dise˜no y Simulaci´on de Sistemas de Colas con ¡i¿e-Motions¡/i 772 Jornadas de Ingenier´ıa del Software y Bases de Datos (JISBD) A Coru˜na, 5–7 Septiembre 2011 Figura 2. Metamodelo de observadores. 3. Modelado del comportamiento del sistema 3.1. e-Motions. e-Motions [2] es una herramienta que permite especicar, simular y analizar sistemas en tiempo real de forma precisa e intuitiva. e-Motions ha sido desarrollado para la plataforma Eclipse. El comportamiento dinámico de un Lenguaje de Modelado de Dominio Especíco se especica en e-Motions mediante transformaciones in-place . Este tipo de transformaciones están formadas por un conjunto de reglas, cada una de las cuales representa una posible acción del sistema. Estas reglas son de la forma l: [ NAC ]∗× LHS → RHS, donde l es el nombre de la regla y LHS (left-hand side), RHS (right-hand side) y NAC (negative application conditions) son patrones de modelos que representan ciertos estados del sistema. Una regla se aplica si en el modelo existe una coincidencia con el patrón LHS y no aparece ninguna con los posibles NAC que tenga dicha regla. En el caso de que aparezcan varios patrones coincidentes con LHS se selecciona uno aleatoriamente y se aplica la regla sobre él, de modo que dicho patrón es sustituido por una instancia del modelo representado en RHS. Las reglas se aplican en un orden no determinístico hasta que ninguna es aplicable aunque este comportamiento puede ser modi- cado mediante algunos mecanismos de control de ejecución como por ejemplo estrategias [3]. Es importante resaltar que e-Motions soporta el uso de expresiones OCL a través de mOdCL [4], el cual implementa y da semántica a OCL en Maude [3]. e-Motions permite generar de forma automatizada (mediante transformaciones implementadas en ATL [5]) las correspondientes especicaciones en Maude del modelo diseñado. Maude se utiliza como una notación formal para dar una semántica precisa a las especicaciones de e-Motions [6]. De este modo, se podrán realizar tareas de análisis formal y simulación a partir de las especicaciones. Jos´e M. Bautista, Javier Troya, Antonio Vallecillo Jornadas de Ingenier´ıa del Software y Bases de Datos (JISBD) A Coru˜na, 5–7 Septiembre 2011 773 Figura 3. Conguración inicial. e-Motions facilita la representación explícita de las acciones que modelan las reglas. Incluyendo un objeto denominado Action Execution podemos especicar una acción concreta y el conjunto de objetos involucrados en ella. Este mecanismo es útil para comprobar si un objeto participa en una acción o si una acción ya ha sido ejecutada. Un tipo especial de objeto, Clock , representa el paso del tiempo. Dicho objeto permite conocer la cantidad de tiempo transcurrido en cualquier instante. 3.2. Comportamiento del sistema de facturación El comportamiento del sistema se ha especicado mediante un conjunto de reglas que describen cada una de las posibles acciones que pueden llevarse a cabo. Distinguiremos dos estrategias de gestión, la primera basada en una cola (que modela el sistema anglosajón) y la segunda basada en múltiples colas (que se corresponde con el modelo español). Estrategia de una sola cola (modelo anglosajón ). Esta estrategia establece que en cada mostrador sólo podrá haber un pasajero, el cual será atendido de inmediato. Los pasajeros que van llegando al aeropuerto forman una cola delante del gestor de embarque que redirige a cada cliente a un mostrador vacío. En primer lugar, para implementar este funcionamiento, es necesario especi- car una conguración inicial del sistema. La regla Initial , mostrada en la gura 3, se encarga de generar el modelo inicial sobre el que se simulará el sistema. La Dise˜no y Simulaci´on de Sistemas de Colas con ¡i¿e-Motions¡/i 774 Jornadas de Ingenier´ıa del Software y Bases de Datos (JISBD) A Coru˜na, 5–7 Septiembre 2011 Figura 4. Regla NewPassenger . inclusión del NAC evita que la regla se lance si ya se ha ejecutado con anterioridad. El LHS no contiene ningún elemento puesto que no es necesaria ninguna condición para que esta regla se ejecute. Como se observa en la imagen, el modelo de inicio está compuesto por un gestor de embarque y cinco mostradores de facturación. Los atributos thresholdMin y thresholdMax del gestor de embarque denen unos umbrales mínimo y máximo que se utilizan como referencia del tamaño de la cola a la hora de tomar decisiones para organizar a los pasajeros. Los mostradores se inicializan con un valor máximo de cola ( maxSize ) de un pasajero y con un tiempo medio de atención para cada pasajero ( serviceTime ) de 60 segundos (las unidades de tiempo consideradas en este sistema son los segundos). La regla NewPassenger (gura 4) simula la llegada de pasajeros al aeropuerto. El observador general llevará la cuenta del número de pasajeros que han llegado a la terminal de salida en su atributo arrivalCounter . Con ello controlamos que el embarque se realice para el número de pasajeros jado, en este caso 240. El nuevo pasajero, que automáticamente se coloca en la cola frente al gestor de embarque, almacena el instante de llegada en el atributo arrival . El atributo troublemaker determina si el pasajero será problemático, retrasando en tal caso el tiempo total en que se realiza su facturación. Como mencionamos anteriormente, hemos considerado que la llegada de pasajeros al aeropuerto seguirá una distribución de Gauss, donde el mayor número de pasajeros llega a la mitad del tiempo de embarque. Es decir, los pasajeros comenzarán llegando poco a poco dos horas antes del vuelo, la frecuencia de llegada irá incrementando hasta alcanzar su pico una hora antes del vuelo, para de nuevo empezar a decrementar hasta poco antes de la hora del vuelo, momento en que llega el último pasajero. Mediante esta distribución intentamos modelar la forma en que, normalmente, los pasajeros llegan para hacer su facturación en la vida real. La duración de la regla la determina la variable ArrivalRate . El cálculo que se observa sobre dicha variable es una simplicación de la función de distribución de la campana de Gauss. El siguiente paso es indicar a cada pasajero el mostrador que va a atenderle, para ello hemos diseñado la regla AssignCheckInDesk (gura 5). Para que la regla se dispare deben darse dos condiciones. Por un lado, el pasajero que va a ser asignado a un mostrador debe ser el primero de la cola, y por otro lado Jos´e M. Bautista, Javier Troya, Antonio Vallecillo Jornadas de Ingenier´ıa del Software y Bases de Datos (JISBD) A Coru˜na, 5–7 Septiembre 2011 775 Figura 5. Regla AssignCheckInDesk . Figura 6. Regla CheckInPassenger . el mostrador debe tener un número de pasajeros en espera menor al tamaño máximo de cola denido para ese mostrador (para esta estrategia hemos jado dicho tamaño máximo a uno). El que el atributo open haya de valer true hace necesario que el mostrador esté abierto para poder recibir al pasajero. Dado que el dispatcher sólo puede atender a un pasajero a la vez, hemos añadido un NAC que evitará que esta regla se active simultáneamente para el mismo dispatcher y diferentes pasajeros. Cuando la acción se lleva a cabo, el pasajero pasará a colocarse en el mostrador que le ha sido asignado. Su atributo arrivalCheckIn almacena el instante en que esto se produce. Por último, incluimos un observador que almacena y calcula una serie de datos para obtener el tiempo medio de espera en la cola del dispatcher , así como la longitud media de la cola. La duración de esta regla es constante puesto que la acción que representa es la de indicar al pasajero el mostrador que le atenderá. La variable assignment almacena dicho valor que se ha jado a un segundo. Dise˜no y Simulaci´on de Sistemas de Colas con ¡i¿e-Motions¡/i 776 Jornadas de Ingenier´ıa del Software y Bases de Datos (JISBD) A Coru˜na, 5–7 Septiembre 2011 Figura 7. Reglas OpenCheckInDesk y CloseCheckInDesk . Una vez que un pasajero llega a alguno de los mostradores, podrá obtener su tarjeta de embarque. Esta acción se representa mediante la regla CheckInPassenger , mostrada en la gura 6. Una vez que el pasajero ha facturado se dirigirá a su puerta de embarque, desapareciendo de nuestro sistema. En la parte RHS de la regla se actualizan los valores de los observadores. El tiempo de servicio de cada mostrador es denido por una distribución exponencial cuyo valor medio es determinado mediante el atributo serviceTime de cada mostrador. En nuestro ejemplo, el tiempo de servicio de los pasajeros en los mostradores se distribuye con una función exponencial de media un minuto. En la conguración inicial de nuestro sistema sólo había abierto un mostrador. Durante la facturación se habilitarán el resto según las necesidades. Para ello se siguen diferentes criterios según la estrategia. Las reglas OpenCheckInDesk y CloseCheckInDesk (gura 7) especican estas acciones. En la estrategia de una sola cola se abre un nuevo mostrador cuando el tamaño de la cola formada frente al gestor de embarque sea mayor que el producto entre el número de mostradores abiertos y el umbral máximo denido en el atributo thresholdMax . En nuestro modelo inicial el umbral se ha jado a 12. Además, el atributo open toma el valor false para que esta regla sólo se ejecute sobre mostradores que no estén abiertos. En el RHS el mostrador pasará a cambiará el estado del atributo open , permaneciendo abierto a partir de ese instante para atender pasajeros. Además, el correspondiente observador almacena el instante de apertura y el número de eventos de apertura y cierre que se han producido sobre el actual mostrador para posteriormente poder calcular el tiempo total que ha estado abierto. La duración de esta acción tiene un val- or constante de 5 minutos. Con ello se contempla desde que se da la orden de apertura hasta que el empleado activa el mostrador. El cierre de los mostradores viene especicado por la regla CloseCheckInDesk . Esta acción se lleva a cabo cuando el tamaño de la cola sea menor o igual al Jos´e M. Bautista, Javier Troya, Antonio Vallecillo Jornadas de Ingenier´ıa del Software y Bases de Datos (JISBD) A Coru˜na, 5–7 Septiembre 2011 777