Algoritmos de aproximación para la programación de trabajos divisibles con tiempos de instalación en máquinas paralelas

Abstract

En este trabajo se estudian problemas de programación de tareas en un entorno de máquinas paralelas. A diferencia de la literatura clásica, asumimos que los trabajos pueden ser divididos en distintas partes, cada una de las cuales puede ser procesada en distintas máquinas. Antes de procesar cualquier parte de un trabajo, la máquina debe prepararse y requiere un tiempo de instalación. Primero se estudia el problema de minimizar la suma ponderada de tiempos de completación, para el cual se obtiene una $(2+\varepsilon)$-aproximación cuando los tiempos de instalación son todos iguales. Este resultado corresponde al primer algoritmo de aproximación de factor constante para este problema. Usando técnicas similares se diseña una 2-aproximación para el caso de una ponderación uniforme de los trabajos, que en particular mejora el factor 2.781 obtenido por Schalekamp et al. Finalmente, con un algoritmo de {\it programación en lista}, se obtiene una 4-aproximación para el problema original con tiempos de instalación dependientes del trabajo. Posteriormente se estudia el problema en máquinas no relacionadas, donde los tiempos de proceso e instalación dependen de cada máquina. Los algoritmos diseñados en esta sección están basados en técnicas de redondeo de relajaciones lineales. La primera relajación que se estudia permite diseñar una 3-aproximación para el problema. Al realizar un paso de {\it lift and project} sobre una restricción es posible fortalecer la relajación, lo que permite diseñar una $(1+\phi)$-aproximación, donde $\phi=\frac{\sqrt{5}+1}{2}$. Respecto a la inaproximabilidad del problema se demuestra una cota inferior igual a $\frac{e}{e-1}$ basada en un resultado de Feige para {\it Max-$k$-Cover}. Usando la relajación lineal fuerte se muestra una 2-aproximación para la versión del problema en que cada trabajo posee un conjunto restringido de máquinas en las que puede ser procesado, teniendo igual tiempo de instalación y procesamiento en todas ellas. Finalmente, se estudia relajaciones basadas en {\it configuraciones} sobre trabajos, es decir, las variables corresponden a vectores que representan la asignación de un trabajo a máquinas en una cierta programación. El programa lineal de configuraciones de trabajos posee una cantidad infinita de variables, sin embargo, se demuestra que es posible restringirse a una cantidad finita de ellas y que además es posible aproximar este programa lineal en tiempo polinomial a un factor de $1+\varepsilon$. Determinar el gap de integralidad de esta relajación queda como una pregunta abierta.