In this paper, we study the problem of scheduling n jobs on a single machine. Each job j has a target starting processing time aj, a processing time pj while its due date dj = aj + kpj + d has to be decided by k and d where k ≥ 0 and d are decision variables which we need to determine. The objective is to minimize the maximum absolute lateness. In this paper we discuss certain results of this question under some special conditions first, we then show it is solvable by a graphical approach in O(n log(n)) time under strong uniformness condition.
