Algoritmos de balanceo de carga en problemas de agendamiento bajo una función cóncava de la carga

Abstract

En el área de algoritmos combinatoriales de optimización, los problemas de agendamiento buscan asignaciones de trabajos a máquinas. La carga de una máquina es la suma de los tiempos de proceso de sus trabajos asignados. En este estudio se busca analizar la complejidad y desarrollar algoritmos para un problema de balanceo de carga, el cual consiste en encontrar una asignación de trabajos a máquinas maximizando la suma de una función cóncava no negativa evaluada en la carga.

La principal motivación detrás de este problema está en el área de Investigación de Operaciones, donde la función cóncava corresponde a la productividad de una máquina y los trabajos a recursos. Otra aplicación en Economía proviene de ver a los trabajos como objetos de valor y a las máquinas como personas con funciones de utilidad.

El problema fue considerado por primera vez por Alon et al., donde se obtiene un EPTAS (esquema de aproximación a tiempo polinomial eficiente) para la versión \emph{offline}. Esto es esencialmente lo mejor posible dado que el problema es fuertemente NP-difícil. En este trabajo se prueba que en este contexto regla \textit{Longest Processing Time} alcanza una $2(\sqrt{2}-1) \approx 0.828$-aproximación. Se conjetura que este análisis no es ajustado, teniendo solo una cota superior de $11/12 \approx 0.916$. Para el caso de dos máquinas, un análisis ajustado muestra que esta regla es exactamente una $11/12$-aproximación.

En la versión \emph{online} de este problema los trabajos se van revelando uno a uno y deben ser asignados sin arrepentimientos. En orden adversarial, se prueba que el algoritmo glotón \textit{List Scheduling} es exactamente $3/4$-competitivo. Se prueba además que esto es óptimo para algoritmos online deterministas que no evalúen la función cóncava. Se exhibe una cota superior constante sobre la competitividad de cualquier algoritmo determinista de $\phi/2 \approx 0.809$, con $\phi$ el número de oro y se propone un algoritmo que la alcanza en dos máquinas. Como siguiente paso en búsqueda de un algoritmo óptimo se encuentran cotas que aplican para más de dos máquinas. Se obtienen también cotas para algoritmos aleatorios y en orden aleatorio.

In the field of combinatorial optimization algorithms, scheduling problems consider the assignment of jobs to machines. The load on a machine is the sum of the processing times of the assigned jobs. This study aims to analyze the complexity and develop algorithms for a load balancing problem, which involves finding an assignment of jobs to machines that maximizes the sum of a non-negative concave function valuation of the load. The main motivation behind this problem lies in the field of Operations Research, where the concave function corresponds to the productivity of a machine, and the jobs to resources. Another application in Economics arises from viewing jobs as valuable objects and machines as individuals with utility functions. The problem was first considered by Alon et al. [2], where an EPTAS (Efficient PolynomialTime Approximation Scheme) is obtained for the offline version. This is essentially the best possible since the problem is strongly NP-hard [12]. In this work, we prove that in this context, the Longest Processing Time rule [13] achieves a 2(√ 2 − 1) ≈ 0,828 approximation. It is conjectured that this analysis is not tight, having only an upper bound of 11/12 ≈ 0,916. For the case of two machines, a tight analysis shows that this rule is exactly an 11/12- approximation. In the online version of this problem jobs are revealed one by one and must be assigned without regrets. In adversarial order, it is proven that the greedy algorithm List Scheduling [13] is exactly 3/4-competitive. It is also proven that it is optimal for deterministic online algorithms that do not evaluate the concave function. A constant upper bound on the competitiveness of any deterministic algorithm of ϕ/2 ≈ 0,809 is exhibited, with ϕ being the golden ratio, and an algorithm that achieves it on two machines is given. As a next step towards an optimal algorithm, bounds are obtained that apply to more than two machines. Bounds for random and arbitrary order algorithms are also derived.