# Proof for optimal interval scheduling using a Greedy Approach

You are given a set of n jobs, where each job j is associated with a size s(how much time it takes to process the job) and a weight w(how important the job is). Suppose you have only one machine that can process one unit of jobs per time slot. Assume all jobs are given at time t = 0 and are to be processed one by one using this machine. Let C > to be the time that job j is completed. The goal is to find a schedule (of all the jobs) that minimizes the weighted completion time, i.Σ(j=1 to n) wj * Cj

• Approach 1: Process Jobs according to the highest weight first
• Approach 2: Process jobs in ascending order of their size
• Approach 3: Process jobs in descending order of their density (w/s)

So basically, I need to find out which approach is optimal and why the other 2 wouldn't work. My understanding is as follows:

• Approach 1 wouldn't be optimal if the higher weights(w) have a greater size(s).
• Approach 3 wouldn't work if the weight was equal to the size in case of all the jobs. If w=s for all the jobs, you wouldn't be able to determine what to chose first.
• Hence, my answer is that Approach 2 would be the optimal choice out of the 3 as it focuses on minimizing w*c. Is this answer correct? Is there a better way to prove why approach 2 is the optimal choice in this question?

• Please don't delete your question once it has been answered. Answers are for everyone, even someone who has a similar question in the future. Apr 11, 2019 at 14:19

Let's consider two jobs in the sequence you obtained:

• $$A$$, of weight $$w_A$$ begins at $$t_0$$ and finish at $$t_0 + s_A$$
• $$B$$ coming just after $$A$$, of weight $$w_B$$ begins at $$t_0 + s_A$$ and finish at $$t_0 + s_A + s_B$$

If we compute only $$K_{A, B}$$ the contribution of $$A$$ and $$B$$ in $$K = \sum_j w_j C_j$$:

$$K_{A, B} = w_A (t_0 + s_A) + w_B (t_0 + s_A + s_B)$$

If A and B are inversed in the sequence, we have $$K'_{A, B}$$:

$$K'_{A, B} = w_A (t_0 + s_A + s_B) + w_B (t_0 + s_B)$$

The difference is:

$$\Delta K_{A, B} = K'_{A, B} - K_{A, B}$$

$$= w_A s_B - w_B s_A$$

$$= (w_A/s_A - w_B/s_B) \times (s_A s_B)$$

The switch should be done if and only if $$\Delta K_{A, B}$$ is negative in order to minimize $$K$$. Only the approach 3 provides you a sequence where no more switch is worth.

If two jobs have the same $$w/s$$ ratio, just take them in any order, the final $$K$$ would remain unchanged.

• I'm a little confused about your conclusion. I don't seem to understand what you mean. "Only approach 3 provides you a sequence where no more switch is worth". Apr 2, 2019 at 2:24
• Approach 3 is decreasing $w/s$, thus for any pair of subsequent tasks A and B, $w_A/s_A - w_B/s_B > 0$ => $\Delta K_{A, B} > 0$. Switching A and B would necessarly increase $K$. Apr 2, 2019 at 7:14
• Could you perhaps give me a counterexample where Approach 2 wouldn't work Apr 2, 2019 at 12:12