In this paper the problem of minimizing the mean absolute deviation of job completion times about a given common due date with different sizes of tolerance in an n-job, single-machine scheduling environment is considered. The authors describe some optimality conditions and show that the problem is NP-complete. A heuristic algorithm is proposed to find an approximate solution to the problem. A pseudo-polynomial dynamic programming algorithm is also proposed to optimally solve the problem if the agreement condition defined in the paper holds. The dynamic programming algorithm can also be used to find a lower bound for the problem by adjusting the tolerances of some jobs. An example is provided to illustrate the proposed methods. A computational study on randomly generated test problems is conducted to investigate the performance of the proposed heuristic and the quality of lower bounds generated by the dynamic programming method. Computational results are reported.
