Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach

This work proposes a hybrid metaheuristic (HMH) approach which integrates several features from tabu search, simulated annealing (SA) and variable neighbourhood search (VNS) in a new configurable scheduling algorithm. In particular, either a deterministic or a random candidate list strategy can be used to generate the neighbourhood of a solution, both a tabu list mechanism and the SA probabilistic rule can be adopted to accept solutions, and the dimension of the explored neighbourhood can be dynamically modified. The considered class of scheduling problems is characterized by a set of independent jobs to be executed on a set of parallel machines with non-zero ready times and sequence dependent setups. In particular, the NP-hard generalized parallel machine total tardiness problem recently defined by Bilge et al. is faced. Several alternative configurations of the HMH have been tested on the same benchmark set used by Bilge et al. The results obtained highlight the appropriateness of the proposed approach. The proposed HMH approach is applied to the difficult problem of minimizing the total tardiness in parallel machines scheduling; in particular, a generalized version of such a problem has been considered, which makes it closer to several real industrial applications since it takes into account non-zero ready times, distinct due dates, uniform machines and setup times, recently proposed by Bilge et al. To evaluate the effectiveness of the HMH for the generalized parallel machine total tardiness scheduling problem, a relevant benchmark available from the literature has been considered.