Abstract

In a partial shop scheduling problem the operations of each job have to respect a partial order, which can be different for each job. We study the problem of finding a solution of minimal makespan in partial shops. This problem generalizes many problems which have been studied independently in the literature, such as the group shop scheduling problem, the mixed shop scheduling problem, and the open shop scheduling problem. In this paper we propose a single algorithm which is able to find solutions for the partial shop scheduling problem, including all the above special cases. It combines an effective constructive heuristic, a solution perturbation based on deconstruction and reconstruction, and an improvement method based on the transposition of operations in an iterated tabu search. In computational experiments we evaluate the performance of the algorithm on the partial shop, the group shop, the mixed shop, and the open shop, and compare it to the current best algorithms which have been proposed specifically for these problem variants. We find that the proposed single heuristic can compete with all these heuristics, and for several variants improves the state of the art.