Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints

Luis Osorio-Valenzuela, Jordi Pereira, Franco Quezada, Óscar C. Vásquez

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

3 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Páginas (desde-hasta)512-527
Número de páginas16
PublicaciónApplied Mathematical Modelling
Volumen74
DOI
EstadoPublicada - oct. 2019
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints'. En conjunto forman una huella única.

Citar esto