Variable Neighborhood Search for Uniform Parallel Machine Makespan Scheduling Problem with Release Dates

In this study, the uniform parallel machine makespan problem with release dates is considered. The problem consists of a set of independent jobs with distinct processing times and release dates to be scheduled on a set of uniform parallel machines to minimize the makespan. This problem is proved to be an NP-hard problem, rendering it a challenging area for meta-heuristic approaches. Four methods are used to generate initial solutions for small and large problems and obtained the results by variable neighborhood search. Computational tests are performed on problems with up to 30 machines and 400 jobs, and indicate that the quality of VNS depend on the quality of initial solutions, therefore a robust VNS algorithm is presented. The proposed VNS approach yields high quality results for 2000 random instances.