Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional Revisado por pares

BIBTEX RIS

New efficient heuristics for scheduling open shops with makespan minimization

2022; Elsevier BV; Volume: 142; Linguagem: Inglês

10.1016/j.cor.2022.105744

1873-765X

Levi Ribeiro de Abreu, Bruno de Athayde Prata, José M. Framiñán, Marcelo Seido Nagano,

Optimization and Packing Problems

This paper deals with the so-called Open Shop Scheduling Problem (OSSP) with makespan objective, which consists of scheduling a set of jobs that must visit a set of machines in no established order so the maximum completion time among the jobs is minimized. This problem is known to be NP-hard, and the absence of specific routes for the processing of the jobs makes its solution space extremely large. In this work we propose several efficient constructive heuristics that exploit some specific properties of the OSSP. We carry out an extensive computational experience using problem instances taken from the related literature to assess the performance of the proposed algorithms as compared to existing ones with respect to the quality of the solutions and the CPU time required. The extensive computational tests show the excellent performance of the heuristics proposed, resulting in the best-so-far heuristics for the problem.