An effective heuristic algorithm for the partial shop scheduling problem. (May 2018)

• Record Type: Journal Article
• Authors: Zubaran, Tadeu K.; Ritt, Marcus
• Is Part Of: Computers & operations research. Volume 93(2018)
• Page Start: 51
• Page End: 65
• Publication Date: 2018-05
• Subjects: Partial shop scheduling -- Mixed shop scheduling -- Group shop scheduling -- Open shop scheduling -- Heuristic -- Iterated tabu search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.01.015
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We present an iterated tabu search for the partial shop scheduling problem. We propose a new constructive heuristic and a neighbourhood with a pruning technique. We demonstrate that a single algorithm can solve effectively many special cases. These special cases include group shop, mixed shop, and open shop scheduling. In experiments the algorithm can compete with all state-of-the-art heuristics. 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 an algorithm which is able to find solutions for the partial shop scheduling problem. In computational experiments we find that the proposed single heuristic can compete with the state-of-the-art heuristics for the partial shop, group shop, mixed shop, and open shop, and in many cases, improves the state of the art. The main contribution of this paper is the demonstration that a single algorithm can solve effectively many special cases of the partial shop without taking into consideration their particular structure. We highlight the contribution of the main novel components of the algorithm, namely the initial solution generator, neighbourhood structure, and the lower bound for new solutions generated by such neighbourhood.