# Scheduling algorithm to minimize maximum deadline overshoot in pre-emptive scheduler

Suppose there are $n$ tasks, which need to be scheduled by a pre-emptive scheduler. Each task $T_i$ has a deadline $d_i$ and a total processing time $t_i$ associated with it. Now, all $n$ tasks are given a priory to the scheduler. The scheduler can run a task for 1 unit of time in one go. After each unit of time, it can schedule any process (including the current one) for the next 1 unit of time.

The goal of the scheduler is to minimize the maximum overshoot of its deadline by any process. For example, for tasks $T_1: (2, 2)$, $T_2: (1, 1)$ and $T_3: (4, 3)$ are the 3 tasks with their respective $(d_i, t_i)$, then a schedule of $T_2, T_1, T_3, T_1, T_3, T_3$ gives a maximum overshoot of 2. No other schedule can reduce the maximum overshoot.

My solution is to use "Earliest Deadline First Scheduling", with tie-breaks based on most time/work remaining. Further ties are broken arbitrarily. Basically, after each unit of time, the task with the earliest deadline is scheduled first. Any ties are decided on which task has the most work remaining. Further ties are broken arbitrarily. This seems to work on a few small hand-constructed cases. But I could not prove or disprove it.

To make the question more than a yes/no question, I would really appreciate it if someone could prove if this is correct, or provide a correct and efficient (sub-quadratic time) algorithm for this. This is not homework. It was presented to me by someone, and I suspect it might be a popular interview question or a question on a programming forum.

-

The problem minimizing maximal lateness is discussed in the algorithm book by Kleinberg and Tardos under greedy algorithms. The solution is like yours, ordering the tasks by their deadline. Indeed the length of the tasks is not relevant.

The main ingredient of the proof is that any optimal solution $O$ can be transformed into this greedy one $G$ by swapping two adjacent tasks that do not agree on the greedy ordering.

Assume we have two tasks $(t_i,d_i)$ and $(t_j,d_j)$ with $d_i\le d_j$ and $O$ has scheduled task $j$ just before $i$, while the greedy algorithm wants it the other way. Assume task $i$ starts at time $t$ in $O$. The lateness in $O$ is the maximum $m$ of $t+t_j-d_j$ and $t+t_j+t_i-d_i$.

After swapping we have the maximum of $t+t_i-d_i$ and $t+t_i+t_j-d_j$. This cannot be worse then the performance of $O$ since both these two numbers are at most $t+t_i+t_j-d_i \le m$ (using $d_i\le d_j$). As $O$ is optimal, so must the swapped version, but it looks more like $G$.

This is not the complete proof. E.g., we have to show that always such a pair $i,j$ can be found, to iterate and obtain $G$ from $O$ by swapping. Also we have to consider 'negative values', when actually $i$ or $j$ meet their deadline, and $m=0$.

-
 I see. Thank you for this proof and the name of the problem. However, the question has the added criteria that jobs need not be completed in one go. They can be swapped out after any unit of time, and some other job can be scheduled. Does this still hold in such a pre-emptive scheduler? – mayank Jan 12 at 17:53 Preemption is required; otherwise the problem is NP-hard. – SamM Jan 12 at 18:09 @mayrank. I cannot see how partialy completing a job does help to improve max lateness. But you are right, it does need a formal argument. – Hendrik Jan Jan 12 at 22:04 @HendrikJan I suppose one could argue that the start of each time step can be treated as a new start time $t_0$ for a new input set. And we always start with the best possible task for the first minute, before the process is interrupted. The argument feels right, but it might be missing some pieces. – mayank Jan 12 at 22:52 @SamM All the documents I found online for this problem tend to schedule all tasks in one go, without preemption. So I do not think this is NP-hard. – mayank Jan 12 at 22:57