Minimizing the Maximum Tardiness on an m-Machine reentrant Permutation Flowshop Problem

This investigation considers a reentrant permutation flowshop scheduling problem whose performance criterion is maximum tardiness. The reentrant flowshop (RFS) is a natural extension of the classical flowshop by allowing a job to visit certain machines more than once. The RFS scheduling problem, in which the job order is the same for each machine in each layer, is called a reentrant permutation flowshop (RPFS) problem. In this paper, a mathematical model is extended to solve the given problem minimizing the maximum tardiness on an m-machine RPFS problem. This problem is solved by three meta-heuristic algorithms, namely genetic algorithm, simulated annealing and tabu search. The results of these algorithms are compared to the optimal solutions obtained by the integer programming approach. The experimental results show that the genetic algorithm has a better performance than the others tested.