A hybrid discrete differential evolution algorithm to minimise total tardiness on identical parallel machines

Abstract

This paper presents a hybrid discrete differential evolution (HDDE) algorithm to solve the Pm// problem. The coding and decoding scheme based on job permutation is applied in the algorithm. The algorithm employs several efficient heuristics in the initialisation phase and incorporates an insertion-based local search. To validate the proposed algorithm, computational experiments are conducted on a benchmark problem set from the literature. Computational results show that the HDDE algorithm outperforms the existing state-of-the-art algorithms for the Pm// problem.

Keywords:

• scheduling
• parallel machines
• meta-heuristics
• tardiness

Acknowledgements

Special thanks are given to Shunji Tanaka for providing the B&B code. The authors appreciate the support of National Natural Science Foundation of China (Grant No. 61174040), National High Technology Research and Development Program of China (863 Program) (No. 2009AA04Z141), Fundamental Research Funds for the Central Universities and Doctor Foundation of Ministry of Education of China (Grant No. 200802510010).