No-wait flowshop scheduling problem with two criteria; total tardiness and makespan

We consider the m-machine no-wait flowshop scheduling problem with respect to two performance measures; total tardiness and makespan. Our objective is to minimize total tardiness subject to the constraint that the makespan is not larger than a given value. We develop dominance relations and propose an algorithm, called Algorithm AA, which is a combination of simulated annealing and insertion algorithm. Moreover, we adapt five existing algorithms, including three well performing algorithms known to minimize total tardiness, to our problem. We conduct extensive computational experiments to compare the performance of the proposed Algorithm AA with the existing algorithms under the same CPU times. We also evaluate the effect of the dominance relations. The computational analysis indicates that the proposed Algorithm AA performs significantly better than the existing algorithms. Specifically, the relative error of the Algorithm AA is about 60% less than that of the best algorithm among the five existing algorithms considered. All the results are statistically verified. Hence, the proposed Algorithm AA is recommended for the considered problem.