Accelerated methods for total tardiness minimisation in no-wait flowshops

For the minimisation of total tardiness in no-wait flowshops, objective incremental properties are investigated in this paper to speed up the evaluation of candidate solutions. To explore the properties, we introduce a new concept of sensitive jobs and identify through experiments that the proportion of such jobs is very small. Instead of evaluating the tardiness of each job, we focus on the evaluation of sensitive jobs which will help to reduce the computational efforts. With these properties, the time complexity of the NEH-insertion procedure is reduced from O(n2)$ O(n^2) $ to approximately O(n)$ O(n) $ in average. Then, an accelerated NEH algorithm and an accelerated iterated greedy algorithm are designed for the problem. Since the NEH-insertion procedure constitutes the main computational burden for both algorithms, these algorithms will benefit directly from the speedup. Numerical computations show that the accelerated algorithms perform 10–40 times faster than the original algorithms on the middle- and large-sized instances. In addition, comparisons show that the proposed algorithms perform more efficiently and effectively than the existing heuristics and meta-heuristics.