4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 18 '15 at 18:15
  • $\begingroup$ 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\}$ $\endgroup$ – jsguy Oct 18 '15 at 18:52
  • $\begingroup$ Tried to re read the proof and still don't get it. $\endgroup$ – jsguy Oct 24 '15 at 10:58
  • $\begingroup$ 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 $\endgroup$ – Belgi Apr 3 '18 at 8:14
  • $\begingroup$ 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) $\endgroup$ – Mengfan Ma Sep 21 at 12:42
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jacob Denson Jun 23 '17 at 3:22
  • $\begingroup$ @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. $\endgroup$ – Mengfan Ma Sep 21 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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