Single machine scheduling to minimize mean absolute lateness: A heuristic solution

This paper presents a heuristic solution procedure based on the well known methodology of adjacent pairwise interchange to minimize mean absolute lateness (MAL) on a single machine. MAL is a nonregular measure of performance and schedules with inserted machine idle time may contain the global optimal solution. The heuristic solution is compared to the optimal solution for 192 randomly generated problems to investigate the effects of problem size, due date coefficient of variation, and due date lightness on the quality of the heuristic. Results indicate that none of the treatments tested significantly affected the heuristic solution. The heuristic solution was found to average about 2.49% greater than the optimal. Also, the heuristic found the optimal for 122 of the 192 randomly generated test problems.