Propagación del caos en el modelo del supermercado

Ponente(s): Sergio I López O, María Clara Fittipaldi, Matthieu Jonckheere

El modelo del supermercado, es un modelo estudiado en el área de Investigación de Operaciones Estocástica. Consiste en lo siguiente. Suponiendo que tenemos una red en paralelo con N servidores (que puede ser pensada como un conjunto de cajas atendiendo en un supermercado), cada que un nuevo usuario llega eligen D servidores de forma aleatoriamente uniforme entre los N posibles. Entre los D servidores elegidos, se elige aquel que tiene el menos número de tareas actuales por atender (se elige la caja en donde hay un menor número de clientes formados). Note que este modelo es una técnica híbrida de asignación entre la optimización total y la aleatoriedad total: podría elegirse sencillamente el servidor con menor número de tareas entre todos los N posibles (optimización total) o bien mandar a cada cliente de forma aleatoria uniforme sobre los N posibles servidores (aleatoriedad total). La alternativa de optimización total no es aplicable en la mayoría de los casos prácticos pues requiere computar la información de cuántas tareas hay en todos los servidores en el instante en que llega una nueva tarea (en el ejemplo del supermercado, un usuario tendría que recorrer todas las filas para elegir en cuál de ellas formarse) lo cuál tiene un costo elevado en un sistema con un gran número de servidores. Los resultados concernientes al modelo del supermercado señalan que existe una mejora sustancial en el tamaño de las filas al utilizar la estrategia híbrida respecto a la aleatoriedad total, y que la mejora es marginal al ir aumentando el tamaño de D, cuando D es mayor o igual a 2. En esta charla explicaremos a detalle el modelo del supermercado. Revisaremos algunos resultados existentes y conjeturas fundamentales para el modelo. Explicaremos en que consiste la técnica de Propagación del Caos para modelos de partículas teóricos y los resultados obtenidos para nuestro modelo particular utilizando tal técnica. Finalmente mostraremos cómo tales resultados se pueden traducir en cuantificaciones aplicables a sistemas reales.