Heuristics for the early/tardy scheduling problem with release dates

In this paper, we consider the single machine earliness/tardiness scheduling problem with release dates and no unforced idle time. We analyse the performance of a varied set of heuristics. This set includes simple scheduling rules, early/tardy dispatching heuristics, a greedy procedure and a decision theory heuristic. Two different approaches are considered to calculate a lookahead parameter used in the early/tardy dispatching heuristics, and extensive experiments were performed to determine an appropriate value for this parameter. We also propose an improvement procedure that uses some dominance rules to improve the solution obtained by the heuristics. The computational results show that the use of the improvement step is recommended, since it reduces the objective function value with little additional computational effort. The best results were given by the decision theory heuristic, but this procedure is computationally expensive and therefore limited to small and medium size instances. For large instances, one of the early/tardy dispatching heuristics is then the heuristic of choice.