Preemptive Single Processor Scheduling with Distinct Due Windows and Minimization of Maximum Earliness and Tardiness

Problem of scheduling n preemptive jobs on a single processor is studied, in which for each job a distinct due window is given in advance. If a job is completed within its due window, then it incurs no penalty. Otherwise, it incurs a job-independent earliness or tardiness cost. The objective is to find a job schedule such that a maximum of weighted costs associated with earliness and tardiness is minimized. Properties of optimal solutions of this problem are established and an algorithm based on them is presented. It is proved that the analysed problem is solvable in O(n2) time.