Effective heuristics and an iterated greedy algorithm to schedule identical parallel machines subject to common restrictive due windows

Abstract

In this paper, we address a variant of the identical parallel machines scheduling problem subject to common restrictive due windows. The performance measure adopted is the minimization of total weighted earliness and tardiness. Since the variant under study is an NP-hard problem for two or more machines, we develop a family of constructive heuristics, which are comprised of four phases. First, jobs are sequenced according to priority rules. Second, jobs are assigned to machines using a greedy strategy. Third, a local search is performed to find a better distribution of jobs into machines. Fourth, two heuristics are applied for individually sequencing jobs in each machine, namely RN-RGH and RN-SEA. In addition, we also propose an iterated greedy algorithm to improve the solutions of the best performing heuristic. The computational experiments were carried out to prove the ability of these heuristics to find high-quality solutions in acceptable CPU time. More specifically, the RN-SEA family of algorithms stands out as the most efficient for the problem, however, with a higher computational effort. We also confirm that the IG algorithm has the potential for improving existing solutions, specially for problems with two machines and instances with up to 100 jobs in size.