# 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})$$. By our choice of $$t$$, we have $$r(S)=t$$. 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) = t+p(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. Oct 18, 2015 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\}$ Oct 18, 2015 at 18:52
• Tried to re read the proof and still don't get it. Oct 24, 2015 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 Apr 3, 2018 at 8:14
• I encountered this problem too and I also believe EDD rule has nothing to do with the 2-approximation proof. Can anyone verify it? (The accepted answer doesn't seem very persuasive to me) Sep 21, 2019 at 12:42

• 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? Jun 23, 2017 at 3:22
• @JacobDenson Note that at each moment the machine is idle, the available job of earliest deadline is loaded, that is, the algorithm selects next job based on not only its deadline but also its release time. Thus $d(S)$ is not necessarily equal to $d_j$ since job $j$ may be of a late release time but an early deadline. Sep 21, 2019 at 12:57