New efficient heuristics for scheduling open shops with makespan minimization

Abstract

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.