A composite heuristic for the single machine early/tardy job scheduling problem

The single machine early/tardy job scheduling problem (SMETP) is an NP-hard problem for which most properties of optimal solutions for single machine problems with regular objective function do not hold. In this paper we present a new composite heuristic for the SMETP that combines tabu search, simulated annealing and steepest descent techniques to generate near optimal schedules. Computational experience is reported for a set of randomly generated test problems.