A hybrid iterated greedy algorithm for total tardiness minimization in permutation flowshops

Abstract

The permutation flowshop scheduling problem is an NP-hard problem that has practical applications in production facilities and in other areas. An iterated greedy algorithm for solving the permutation flow shop scheduling problem with the objective of minimizing total tardiness is presented in this paper. The proposed iterated greedy algorithm uses a new formula for temperature calculation for acceptance criterion and the algorithm is hybridized with a random search algorithm to further enhance the solution quality. The performance of the proposed method is tested on a set of benchmark problems from the literature and is compared to three versions of the traditional iterated greedy algorithm using the same problem instances. Experimental results show that the proposed algorithm is superior in performance to the other three iterated greedy algorithm variants. Ultimately new best known solutions are obtained for 343 out of 540 problem instances. (C) 2016 Elsevier Ltd. All rights reserved.