1
$\begingroup$

There's a homework exercise I have to do for my scheduling course about which I have some questions. The exercise is this:

Consider the $1|\text{ }|\sum w_jT_j$ problem. (This means that we look at one machine which has to process a number of jobs and where the objective function is the total weighted tardiness of a schedule.)

Prove that if for jobs $j$ and $k$ we have that $\frac{w_j}{p_j} > \frac{w_k}{p_k}$, $d_j < d_k$ and $p_j < p_k$ then there exists an optimal schedule where job $j$ is scheduled before $k$.

The tardiness of job $i$ is defined as $T_i := \max\{0,C_i-d_i\}$ where $C_i$ is the completion time of job $i$ and each tardiness has an associated weight $w_i$. Furthermore, $p_i$ and $d_i$ denote the processing time and due date of job $i$, respectively.

I have been able to prove a lemma in the course notes, which is a weaker version of the statement in the exercise. The lemma states that

If there are jobs $j,k$ such that $d_j \leq d_k$, $p_j \leq p_k$ and $w_j \geq w_k$ then there exists an optimal schedule for $1|\text{ } | \sum w_jT_j$ in which job $j$ is scheduled before job $k$

I've proved this lemma (correctly, I hope) by contradiction: I assumed an optimal schedule has job $k$ scheduled before job $j$ and showed that the weighted tardiness of this schedule is bigger than the schedule with job $j$ scheduled before job $k$.

My question is: is there an easy way to use the lemma to prove the statement in the exercise? Does the condition $\frac{w_j}{p_j} > \frac{w_k}{p_k}$ imply anything useful that we can use? Thanks in advance.

The thing about this lemma is that, while we have stronger conditions on $d_j,d_k$ and $p_j,p_k$ we only have that $w_j > \frac{p_j}{p_k} w_k$. Since $\frac{p_j}{p_k} < 1$ this does not imply that $w_j > w_k$.

PS: there was no "scheduling" tag so I put this question under "optimization". I hope that's ok.

$\endgroup$
  • $\begingroup$ I don't think that the lemma you quote, at least as it is stated, is true. For example, consider the problem with two jobs, $d_1 = 2, p_1 = 3, w_1 = 10$, and $d_2 = 1, p_2 = 2, w_2 = 1$. Then $d_2 \leq d_1$ and $p_2 \leq p_1$, but the unique optimal schedule has $d_1$ scheduled first with a cost of 14, whereas the schedule with $d_2$ first has a cost of 31. $\endgroup$ – Mike Spivey Mar 9 '11 at 17:04
  • $\begingroup$ @Mike Spivey: You're completely right. The lemma hold for $\sum T_j$ but not for $\sum w_j T_j$, my appologies. There is such a lemma for the weighted tardiness case, though. But one has to require that $w_j \geq w_k$. $\endgroup$ – Stijn Mar 9 '11 at 18:18
  • $\begingroup$ I've entered the correct lemma. Again, I'm sorry for my mistake. $\endgroup$ – Stijn Mar 9 '11 at 18:24
1
$\begingroup$

I don't know that the lemma, per se, can be used to prove the stronger result, but I suspect that the ideas you used in proving it will also apply.

That said, your question seems essentially to be about the effect of the condition $\frac{w_j}{p_j} > \frac{w_k}{p_k}$.

Suppose you have some optimal schedule with task $k$ occurring before task $j$. Then consider the schedule in which you swap $j$ and $k$ in the order in which you do the tasks. Ignoring what happens with the tasks and times in between $j$ and $k$, the effect of this swap is that task $k$ is completed $p_j$ time units later and task $j$ is completed $p_k$ time units earlier. If both tasks are tardy this means that the overall tardiness of this new schedule is changed by $w_k p_j - w_j p_k$. Since $\frac{w_j}{p_j} > \frac{w_k}{p_k}$, this quantity will be negative. So the new schedule will have smaller overall tardiness, which is a contradiction.

This isn't the full argument, since you do have to worry about the intervening tasks and about the cases in which $j$ and $k$ are not tardy, but this is the essence of the argument, and it explains the effect of the condition $\frac{w_j}{p_j} > \frac{w_k}{p_k}$.

$\endgroup$

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.