A heuristic for single machine scheduling with early and tardy costs

The problem of scheduling jobs with distinct ready times and due dates in a single machine to minimise the total earliness and tardiness penalties is considered. A constructive heuristic, which determines the sequence of jobs and simultaneously inserts idle times, is proposed. Adjacent pairwise interchange is then applied to the schedule obtained. For problems involving at most 12 jobs the heuristic solutions are compared to optimal solutions. For larger problems with up to 80 jobs the heuristic is tested against a local search based on pairwise interchanges and four dispatching rules presented in the literature. In each case, idle times are optimally inserted.