Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling

The scheduling literature is abundant on approximate methods for permutation flowshop scheduling, as this problem is NP-hard for the majority of objectives usually considered. Among these methods, some of the most efficient ones use an insertion-type of neighbourhood to construct high-quality solutions. It is not then surprising that using accelerations to speed up the computation of the objective function can greatly reduce the running time of these methods, since a good part of their computational effort is spent in the evaluation of the objective function. Undoubtedly, the best-known of these accelerations has been employed for makespan minimisation (commonly denoted as Taillard’s accelerations). These accelerations have been extended to other related problems, but they cannot be employed for the classical permutation flowshop problem if the objective is other than the makespan. In these cases, other types of accelerations have been proposed, but they are not able to achieve a substantial reduction of the computational effort.