# About the existence of a certain optimal schedule for the $1|\text{ } | \sum w_j T_j$ problem

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.

• 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. – Mike Spivey Mar 9 '11 at 17:04
• @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$. – Stijn Mar 9 '11 at 18:18
• I've entered the correct lemma. Again, I'm sorry for my mistake. – Stijn Mar 9 '11 at 18:24

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}$.