Comparative study of trajectory metaheuristics for the resolution of scheduling problem of unrestricted parallel identical machines

Abstract

In this paper we present a comparative study of four trajectory metaheuristics or single-solution based metaheuristics (S-meta heuristics): Iterated Local Search (ILS), Greedy Randomized Adaptive Search Procedure (GRASP), Variable Neighborhood Search (VNS) and Simulated Annealing (SA). The metaheuristics were used to minimize the Maximum Tardiness (Tmax) for unrestricted parallel identical machine scheduling (Pm) problem, which is considered as NP-Hard problem. The results obtained through experimentation show that SA was the best behaved.