Trajectory Scheduling Methods for minimizing total tardiness in a flowshop

In this paper, Trajectory Scheduling Methods (TSMs) are proposed for the permutation flowshop scheduling problem with total tardiness minimization criterion. TSMs belong to an iterative local search framework, in which local search is performed on an initial solution, a perturbation operator is deployed to improve diversification, and a restart point mechanism is used to select the new start point of another cycle. In terms of the insertion and swap neighborhood structures, six composite heuristics are introduced, which exploit the search space with a strong intensification effect. Based on purely insertion-based or swap-based perturbation structures, three compound perturbation structures are developed that construct a candidate restart point set rather than just a single restart point. The distance between the current best solution and each start point of the set is defined, according to which the diversification effect of TSMs can be boosted by choosing the most appropriate restart point for the next iteration. A total of 18 trajectory scheduling methods are constructed by different combinations of composite heuristics. Both the best and worst combinations are compared with three best existing sequential meta-heuristics for the considered problem on 540 benchmark instances. Experimental results show that the proposed heuristics significantly outperform the three best existing algorithms within the same computation time.