Cotas para el precio de la anarquía de juegos de Scheduling

Abstract

El objetivo principal del presente trabajo de memoria de título es el cálculo de cotas para precio de la anarquía de algunos juegos asociados a problemas de scheduling. Se comienza realizando una revisión general de lo que son los problemas de scheduling, un algoritmo de aproximación y la relación que existe entre teoría de juegos y los problemas de scheduling. Ahí se identifica el cuociente de aproximación del algoritmo de Smith para problemas de scheduling, con el precio de la anarquía de un juego asociado. Se realiza también una revisión de los principales resultados conocidos útiles para el presente trabajo. Más adelante se calcula el precio de la anarquía para ciertos juegos de scheduling donde la función objetivo es la suma ponderada de los tiempos de completación. Se demuestra que en el caso de máquinas idénticas, el precio de la anarquía en estrategias mixtas es 3/2. Se demuestra también que en máquinas paralelas con velocidades, el precio de la anarquía es mayor o igual a 2. Por último, se prueba acá que en el caso en que todos los trabajos tienen el mismo tamaño, el precio de la anarquía del juego de scheduling en máquinas paralelas con velocidades y suma ponderada de los tiempos de completación como función objetivo es 1. Para seguir se estudia el juego asociado al problema de scheduling en el cual la función objetivo es la suma de los tiempos de completación, y las máquinas son todas excepto una idénticas entre sí, la máquina restante es de velocidad mayor a las demás, y las máquinas que son más lentas son una cantidad suficientemente grande. Para este juego de scheduling se demuestra que el precio de la anarquía es e/(e-1). Después se estudia el juego mencionado anteriormente en su caso más general, en el cual la cantidad de máquinas lentas no está restringida a ser suficientemente grande. Para este problema se demuestra que el precio de la anarquía está acotado superiormente por 5/3. Se muestra además un problema de programación lineal cuyo óptimo acota superiormente el precio de la anarquía del juego de scheduling de máquinas paralelas con velocidades y suma de los tiempos de completación como función objetivo. Finalmente, se plantea como conjetura que el precio de la anarquía del juego asociado al problema de scheduling más general antes mencionado es efectivamente e/(e-1), y se muestran pruebas computacionales que fueron realizadas, con las cuales se justifica el plantear esta conjetura.