A Heuristic Solution Procedure to Minimize T on a Single Machine

Abstract

In this paper, a heuristic procedure utilizing the adjacent pairwise interchange (API) methodology to minimize mean tardiness () in single-machine scheduling is presented. Results indicate that it provides a much better solution than does the Wilkerson-Irwin heuristic algorithm, which also tries to minimize . Experimental results suggest that the heuristic solution is not affected by problem size, which is important if larger problems are to be solved. Also, the heuristic is not affected by the tightness of due dates.

Keywords:

• adjacent
• average tardiness
• local optima
• pairwise interchange
• single-machine scheduling