2 approximation algorithm for the single machine scheduling problem

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?

• One of your inequalities (you say which) holds due to the earliest due time rule. If you chose a different rule then probably you will get a worse approximation ratio. Try it out and see. – Yuval Filmus Oct 18 '15 at 18:15
• unfortunately I can't see the reason. For any schedule we have that $L^{*}_{max} \geq r(S) + p(S) - d(S)$. Since $d(S) < 0$ by simple calculus we have $L^{*}_{max} \geq r(S) + p(S)$. Then by looking at the set S we picked, $c_{j}-r(S) = p(S)$ so we get the first inequality. The last one seems to be the same but now assuming that $S = \{j\}$ – jsguy Oct 18 '15 at 18:52
• Tried to re read the proof and still don't get it. – jsguy Oct 24 '15 at 10:58
• Is it really an error in the book? This seems strange since I'm sure there is significance in using the EDD rule, but I too can't see any use of it in the proof – Belgi Apr 3 '18 at 8:14

• Why can't we use the earliest due date to achieve a 1-approximation (I know this is impossible, but where am I wrong?). Consider the job $j$ and set $S$, as in the book. Isn't the due date $d(S) = d_j$, because otherwise we would have processed job $j$ before any other element in $S$, and as such the lemma gives $L^* \geq C_j - d_j$, which is the output of our algorithm? – Jacob Denson Jun 23 '17 at 3:22