0
$\begingroup$

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?

    $\endgroup$
    • 2
      $\begingroup$ 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. $\endgroup$ – Gilles Apr 11 at 14:19
    1
    $\begingroup$

    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.

    $\endgroup$
    • $\begingroup$ 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". $\endgroup$ – user4062969 Apr 2 at 2:24
    • $\begingroup$ 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$. $\endgroup$ – Vince Apr 2 at 7:14
    • $\begingroup$ Could you perhaps give me a counterexample where Approach 2 wouldn't work $\endgroup$ – user4062969 Apr 2 at 12:12

    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.