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.

  • 0
    I've entered the correct lemma. Again, I'm sorry for my mistake.2011-03-09

1 Answers 1

1

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