Posted by: atri | October 23, 2009

## Lect 20: Scheduling to minimize lateness

(Guest post by Ryan Dolce)

Today we started off by finishing off our run-time analysis discussion.

We review the run-time of the following algorithm:

1. Set $A$ to be the empty set
2. While $R$ is not empty
• Choose $i \in R$ with the earliest start time
• Add $i$ to $A$
• Remove all requests that conflict with $i$ from $R$
3. return $A$

Before this takes place, we spend $O(n)$ time to build an array $s$ that stores $s[1\dots n]$ elements, $s[i]$ is the start time for a particular job.

These jobs are sorted by their finishing time. This is so that $f(i) \le f(i + 1)$.

As we proceed through the algorithm, we need to check if there are any conflicts with the first selected job. This is done by checking if the start time of the next job is greater than the finish time of the selected job. If we select job $1$, then all conflicts can be shown by $s[i] < f(1)$. This check can be performed in $O(1)$ time.

Next we discussed a new proof technique for the end of semester blues problem. The idea of durations and deadlines were added. The goal of this new technique [problem actually–Atri] is to minimize the maximum lateness. That is, we want to have as little lateness as possible. Basically, all of the jobs are scheduled and then we check how late we are.

The new input for the algorithm is: $n$ jobs $(t_i ,d_i )$ where $1 \le i \le n$.

• $t_i$ = the duration of the job
• $d_i$ = the deadline for the job
• $\ell_i$ = lateness of a job = $\max(0,f_i - d_i )$

The output is still a schedule where no two jobs conflict.

In order to compute an optimal schedule, greedy algorithms need to be used. First, we need to order the jobs, and then schedule them in that order. Also, there can not be a gap between any of the jobs.

For example: Acceptable:  [ job 1 ][ job 2 ][ job 3 ]

Not Acceptable: [ job 1 ] ______ [ job 2 ]

There were three different approaches that could be used with this scenario.

Order by increasing $t_i$

job1: $t_1 = 1$; $d_1 = 100$

job2: $t_2 = 10$; $d_2 = 10$

So the obvious choice here would to be to schedule job 1 before job 2. However, although job 1 is done way before it deadline, job 2 ends late. This results in a lateness of 1. So technically, it would be better to schedule job 2 before job1. This is because job 1 has a slack of 99 and job 2 has a slack of 0.

Schedule jobs in the order of the least amount of slack

job1: $t_1 = 1$; $d_2 = 2$ implies  slack = $1$

job2: $t_2 = 10$; $d_2 = 10$ implies slack = $0$

If job 2 is scheduled first, then it results in a lateness of $9$. This is because job 1 now ends at $11$ instead of $2$, so $11- 2 = 9$.

If job 1 is scheduled first, then it results in a lateness of $1$. This is because job 2 now ends at $11$ instead of $10$, so $11 - 10 = 1$. This case actually is more acceptable because the maximum lateness is minimized.

Order by increasing $d_i$

For this scenario, the jobs will be sorted by their deadlines in increasing order.

(i.e  $d_1 \le d_2 \le \dots\le d_n$ )

1. $f = 1$
2. For $i = 1 \cdots n$
• Schedule job $latex i$ from $latex s_i = f$ to $latex f_i = f + t_i$.
• $f \leftarrow f + t_i$
3. return schedule $[s_i ,f_i ]$; ($i = 1 \dots n$) => A (the schedule)

To wrap class up, we began going over the proof for these scenarios. Only the proof ideas were laid down and the proof will be continued next class. Here is the proof thus far:

Theorem: Schedule output by the algorithm is optimal.

There exists some $\mathcal O$; The minimum lateness of  $A$ is the same as $\mathcal O$.

This proof will be done by “exchange argument.”

Proof Idea: We will start with $\mathcal O$ and go through some transitions until we reach a final schedule.

ex. $\mathcal O=T_1\to T_2\to\dots\to T_m=A$ ; where $A$ is the final schedule and  $T_m$ is the final transition made to obtain the final schedule. Note that $T_m$ and $A$ are the same.