Artículo publicado por los investigadores Luis Osorio-Valenzuela (1), Jorge Pereira (2), Franco Quezada(3) y Óscar C. Vásquez (4).
En este documento, consideramos un problema de programación de máquinas paralelas en el que las máquinas tienen una capacidad de carga de trabajo limitada y los trabajos tienen fechas límite y fechas de lanzamiento. El problema está motivado por el funcionamiento de sistemas de gestión de almacenamiento de energía para microrredes en condiciones de emergencia y generaliza algunos problemas que ya han sido estudiados en la literatura por su valor teórico. En este trabajo, proponemos algoritmos heurísticos y exactos para resolver el problema. Las heurísticas son adaptaciones de las heurísticas clásicas de empaquetado en contenedores en las que se imponen condiciones adicionales sobre la viabilidad de una solución, mientras que el método exacto es un enfoque de sucursales y precios. Los resultados muestran que el enfoque de sucursales y precios es capaz de resolver de manera óptima instancias aleatorias con hasta 250 trabajos en un límite de tiempo de una hora, mientras que los procedimientos heurísticos brindan una solución casi óptima en tiempos de ejecución reducidos. Finalmente, también proporcionamos resultados de complejidad adicional para un caso especial del problema.
In this paper, we consider a parallel machine scheduling problem in which machines have a limited workload capacity and jobs have deadlines and release dates. The problem is motivated by the operation of energy storage management systems for microgrids under emergency conditions and generalizes some problems that have already been studied in the literature for their theoretical value. In this work, we propose heuristic and exact algorithms to solve the problem. The heuristics are adaptations of classical bin packing heuristics in which additional conditions on the feasibility of a solution are imposed, whereas the exact method is a branch-and-price approach. The results show that the branch-and-price approach is able to optimally solve random instances with up to 250 jobs within a time limit of one hour, while the heuristic procedures provide near optimal solution within reduced running times. Finally, we also provide additional complexity results for a special case of the problem.