Efficient variable neighborhood search for identical parallel machines scheduling

In this paper, a novel variable neighborhood search (VNS) algorithm is proposed for identical parallel machines scheduling problem with the objective of minimizing makespan criterion. To speed up the convergence rate and enhance the quality of the final solution, a machine-based encoding method and four neighborhood structures are introduced in VNS. It is demonstrated that the proposed VNS algorithm can efficiently improve the searching quality when compared with other classical meta-heuristics through a large scale of examinational instances.