An efficient heuristic for scheduling on identical parallel machines to minimize total tardiness

Abstract This paper deals with the identical parallel machine scheduling problem to minimize total tardiness where each machine cannot have more than one job at a time. An efficient heuristic algorithm is proposed. It relies on a simulated annealing algorithm aimed at searching for a better solution during the schedule construction stage. The heuristic uses some well-known dominance properties for this problem which are usually used by exact methods and particularly by branch and bound algorithms. Some instances of the literature are used to show the effectiveness of this heuristic on computational results.