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

• A novel temperature calculation formula for total tardiness minimization objective.
• A local search that is a random search with insertion and swap neighborhoods.
• Adaption of speedup method for total flow time objective to total tardiness.
• 343 new best permutations out of 540 instances of the problem set has been found.

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 flowshop 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.