Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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 '13 at 17:53
    
Preemption is required; otherwise the problem is NP-hard. –  SamM Jan 12 '13 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 '13 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 '13 at 22:52
1  
@mayank By reduction to Partition (unless I'm misunderstanding your problem), your problem is NP-hard for two or more processors. On a single processor, EDF is best, which actually implies that preemption is not necessary. (If you process a job with the earliest deadline, that job's deadline remains earliest until it is finished). –  SamM Jan 12 '13 at 23:25

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.