A speed-up procedure for the hybrid flow shop scheduling problem

Abstract

During the last decades, hundreds of approximate algorithms have been proposed in the literature addressing flow-shop-based scheduling problems. In the race for finding the best proposals to solve these problems, speedup procedures to compute objective functions represent a key factor in the efficiency of the algorithms. This is the case of the well-known Taillard’s accelerations proposed for the traditional flow shop with makespan minimisation or several other accelerations proposed for related scheduling problems. Despite the interest in proposing such methods to improve the efficiency of approximate algorithms, to the best of our knowledge, no speed-up procedure has been proposed so far in the hybrid flow shop literature. To tackle this challenge, we propose in this paper a speed-up procedure for makespan minimisation, which can be incorporate in insertion-based neighbourhoods using a complete representation of the solutions. This procedure is embedded in the traditional iterated greedy algorithm. The computational experience shows that even incorporating the proposed speed-up procedure in this simple metaheuristic results in outperforming the best metaheuristic for the problem under consideration.