Algoritmos para variantes del problema de minimizar la suma de los k mayores retrasos de trabajos en agendamientos en una máquina

Abstract

El problema de minimizar k-sum lateness en una máquina es una generalización de los problemas de minimizar maximum lateness y total lateness, casos que se recuperan cuando k=1 y k=n respectivamente, y consiste en encontrar un agendamiento de n trabajos en una máquina, que minimice la suma de los k mayores lateness. Podemos resolver el problema de minimizar maximum lateness en tiempo polinomial mediante una regla de despacho simple que prioriza los trabajos de menor a mayor deadline, mientras que para resolver el problema de minimizar total lateness se priorizan los trabajos de acuerdo a sus tiempos de proceso, de menor a mayor. A diferencia de los casos particulares anteriores, para el problema general del k-sum lateness mostramos que no existen reglas de despacho simples que permitan encontrar un agendamiento óptimo priorizando los trabajos ni según sus tiempos de proceso ni según sus deadlines. En esta tesis realizamos un estudio robusto del problema de k-sum lateness y presentamos algoritmos polinomiales para tres variantes importantes del problema. Cuando k es una constante fija, mostramos que el problema puede ser resuelto en tiempo O(n^{2k-1}) extendiendo el trabajo de Woeginger para k-sum tardiness. Cuando hay a lo más una cantidad P constante de tiempos de proceso distintos, reformulamos el problema de k-sum lateness como uno de optimización a dos niveles que puede ser resuelto en tiempo O(n^{2P+5}). Finalmente, cuando hay a lo más una cantidad D constante de deadlines distintos, mostramos una serie de resultados estructurales de agendamientos óptimos que nos permiten resolver el problema en tiempo O(n^{3D+1}D).