If you want to make money online : Register now

# [Solved]: 2 approximation algorithm for the single machine scheduling problem

, ,
Problem Detail:

We are given one machine and $n$ jobs that we want to process.

For the $n$ jobs we have the following data:

$r_{1}, ... , r_{n}$ are the release times

$p_{1}, ... , p_{n}$ are the processing times

$d_{1}, ... , d_{n}$ are the deadlines/due dates

$c_{1}, ... , c_{n}$ are the completion times(when the jobs are finished executing)

$l_{1}, ... , l_{n}$ are the latenesses achieved where $l_{j} = c_{j} - d_{j}$

Our goal is to find a schedule that minimizes the maximum lateness achieved ($L^{*}_{max}$)

Since even deciding whether there is a schedule such that $L^{*}_{max} \leq 0$ is np hard, this implies that we can not come up with an approximation algorithm of any ratio $\rho > 0$ that runs in polynomial time and produces a schedule with maximum lateness at most $\rho L^{*}_{max}$. So this is why we make the assumption that the due dates are negative, ie $d_{i} < 0$

Before trying to come up with an algorithm, we can prove that for any subset $S$ of jobs, $L^{*}_{max} \geq r(S) + p(S) - d(S)$ where $r(S) = min_{j\in S}r_{j}$, $p(S) = \sum_{j\in S}p_{j}$ and $d(S) = max_{j \in S} d_{j}$.

To prove this what we have to do is look at the last job of the optimal schedule and try to find its lateness, which will also be a lower bound for the maximum lateness achieved.

Now, having this as a fact for any schedule, assume our algorithm produces a schedule as follows. At each moment the machine is idle, start processing next the available job with the earliest due date.

The analysis I have in my book (the design and analysis of algorithms by Williamson and Shmoys) is as follows:

We consider the schedule produced by our algorithm and let $j$ be the job of maximum lateness in the schedule. That is $L_{max} = c_{j} - d_{j}$. We focus on the time $c_{j}$ in this schedule and try to find the earliest point in time $t \leq c_{j}$ such that the machine was processing without any idle time for the entire period $[t, c_{j})$. Let $S$ be the set of jobs that are processed in that interval. From the bound about the maximum lateness we found before, we have that $L^{*}_{max} \geq r(S) + p(S) -d(S) \geq r(S) + p(S) \geq c_{j} - r(s) + r(s) = c_{j}$

Then we only focus at the last job $j$, so we get $L^{*}_{max} \geq r_{j} + p_{j} - d_{j} \geq -d_{j}$

combining both the equations we get $c_{j} - d_{j} \leq 2L^{*}_{max}$

what I don't understand is, where do we actually need the earliest due time rule? Where do we use it in the analysis? What would happen if we used the longest due time rule? Could we then apply the same analysis to come up with the same approximation ratio?

This is an error in the book. The earliest deadline condition is not used any where in the analysis. This means that we can achieve the 2-approximation algorithm even if we drop this condition.