I Simposio de Postgrado 2023. Ingeniería, ciencias e innovación

MÓDULO_ 07 Matemáticas aplicadas y Modelación matemática 142 ALGORITMOS DE BALANCEO DE CARGA EN PROBLEMAS DE AGENDAMIENTO BAJO UNA FUNCIÓN CÓNCAVA DE LA CARGA RESUMEN 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 proble- ma de balanceo de carga, el cual consiste en encontrar una asig- nación de trabajos a máquinas maximizando la suma de una función cóncava creciente 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 co- rresponde a la productividad de una máquina y los trabajos a recursos. Otra aplicación en Economía proviene de ver a los tra- bajos como objetos de valor y a las máquinas como personas con funciones de utilidad. Se obtiene un PTAS ( Polynomial-time Approximation Scheme ), adaptando una técnica de Makespan [1], que consiste en un re- dondeo de tamaños para luego usar programación dinámica. Esto es esencialmente lo mejor posible dado que el problema es fuertemente NP -difícil [2]. Para la versión online enordenadversarial,donde los trabajos se van revelandouno a uno y deben ser asignados sinarrepentimientos, se prueba que el algoritmo glotón List Scheduling [3] es 3/4-competiti- vo. Se exhibe además una cota superior constante sobre la competi- tividadde cualquier algoritmo de Φ /2 ≈ 0.809, con Φ el número de oro. Finalmente, como respuesta parcial se propone un algoritmo que alcanza dicha cota para el caso de dos máquinas. Cristian Palma 1* , José Soto 1 1 Departamento de Ingeniería Matemática, Universidad de Chile. *Email: cpalma@dim.uchile.cl REFERENCIAS [1] D. S. a. S. D. B. Hochbaum, “ Using dual approximation algorithms for scheduling problems theoretical and practical results ,” Journal of the ACM (JACM), vol. 34, no. 1, pp. 144-162, 1987. [2] M. R. a. J. D. S. Garey, Computers and intractability , vol. 174, Freeman San Francisco, 1979. [3] R. L. Graham, Bounds on multiprocessing timing anomalies , vol. 17, SIAM journal on Applied Mathematics, 1969, pp. 416-429. AGRADECIMIENTOS Este trabajo es financiado por CMM ANID BASAL FB210005.