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

Question

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.

Answer 1

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$.

Answer 2

Here is a simple proof that the additional criteria that job need not be completed in one go is actually not necessary:

suppose the input is a sequence of tasks $\{(d_i, m_i)\}$, where $d_i$ is the deadline of task $i$ and $m_i$ is the duration of task $i$, for $i$ = 1, 2, ...,$n$. We can transform the input into another instance, where each task $i$ is replaced by $m_i$ "subtasks" $(d_i, 1)$. The optimal solution for the original problem cannot be better than the optimal solution for the transformed problem, as schedule of the original $n$ tasks is also a valid schedule of the transformed problem; on the other hand, if we run the algorithm in the book of Kleinberg and Tardos on the transformed problem (which would produce the optimum schedule for the transformed input), it would naturally put all subtasks consecutively as they have the same deadlines, which in turn is a valid schedule for the original input.