Minimizing total earliness and tardiness on a single machine using a hybrid heuristic

This paper focuses on scheduling jobs with different processing times and distinct due dates on a single machine with no inserted idle time as to minimize the sum of total earliness and tardiness. This scheduling problem is a very important and frequent industrial problem that is common to most just-in-time production environments. This NP hard scheduling problem is herein solved using a hybrid heuristic which combines local search heuristics (dispatching rules, hill climbing and simulated annealing) and an evolutionary algorithm based on genetic algorithms. The heuristic involves low and high, relay and teamwork hybridization. Computational results reflect the sizeable solution quality improvement induced by hybridization, and assess the impact of each type of hybridization on the efficiency of the hybrid heuristic. (c) 2005 Elsevier Ltd. All rights reserved.