edited by
14,441 views
60 votes
60 votes

Consider $n$ jobs $J_1, J_2 \dots J_n$ such that job $J_i$ has execution time $t_i$ and a non-negative integer weight $w_i$. The weighted mean completion time of the jobs is defined to be $\frac{\sum_{i=1}^{n}w_iT_i}{\sum_{i=1}^{n}w_i}$, where $T_i$ is the completion time of job $J_i$. Assuming that there is only one processor available, in what order must the jobs be executed in order to minimize the weighted mean completion time of the jobs?

  1. Non-decreasing order of $t_i$
  2. Non-increasing order of $w_i$
  3. Non-increasing order of $w_it_i$
  4. Non-increasing order of $w_i/t_i$
edited by

6 Answers

Best answer
130 votes
130 votes

Lets take an example:
$$\begin{array}{|c|c|c|}\hline \textbf{Process} & \textbf{Weight} & \textbf{Execution time}  \\ \hline {P_1} & \text{1} & \text{3}\\\hline {P_2} & \text{2} & \text{5}\\\hline  {P_3} & \text{3} & \text{2}\\\hline {p4} & \text{4} & \text{4}\\\hline \end{array}$$
For option 1 non decreasing $t_i$

$\qquad= (3\times 2+1\times 5+4\times 9+2\times 14)/10 = (6+5+36+28)/10= 7.5$

For option 2 non increasing $w_i$ 

$\qquad= (4\times 4+3\times 6+2\times 11+1\times 14)/10 = (16+18+22+14)/10 =7$

For option 3 non increasing $w_i t_i$

$\qquad= (16+2\times 9+3\times 11+1\times 14)/10 =  (16+18+33+14)/10 = 8.1$

For option 4 non increasing $w_i /t_i$

$\qquad= (3\times 2+4\times 6+2\times 11+1\times 14) /10 = (6+10+22+14)/10 =  6.6$

Minimum weighted mean obtained from non increasing $w_i /t_i$ (option D)


The solution above is a classical example of greedy algorithm - that is at every point we choose the best available option and this leads to a global optimal solution. In this problem, we require to minimize the weighted mean completion time and the denominator in it is independent of the order of execution of the jobs. So, we just need to focus on the numerator and try to reduce it. Numerator here is a factor of the job weight and its completion time and since both are multiplied, our greedy solution must be

  • to execute the shorter jobs first (so that remaining jobs have smaller completion time) and
  • to execute highest weighted jobs first (so that it is multiplied by smaller completion time)

So, combining both we can use $w_i/t_i$ to determine the execution order of processes - which must then be executed in non-increasing order. 

edited by
54 votes
54 votes

Well, this question indeed depicts the importance of Shortest Job First Scheduling algorithm and proving why it is optimal.

The weighted mean completion time is given by

$W_m=\frac{\sum_{i=1}^nw_iT_i}{\sum_{i=1}^nw_i}$

For a given set of processes($P_1,P_2...P_n)$, the term $\sum_{i=1}^{n}w_i$ will be a constant and hence the only variable part in the weighted mean expression is the nominator part and that is $\sum_{i=1}^nw_iT_i$

So to minimize $W_m$, we need to minimize $\sum_{i=1}^nw_iT_i$ where $T_i=$ Completion time (or Turnaround time) of Job $J_i$.

TurnAround Time comprises of the time spent by the job in CPU + time doing I/O+ Time waiting in the ready queue

Now here assuming all processes to be CPU bound only, I can say for all processes my Turnaround time = Waiting time+Burst Time.

Since, when all processes are submitted to the system, in which order the processes may be executed, their burst time remains a constant and hence the variable term in the Turn Around time is the waiting time.

So, for the purpose of simplicity, I can safely assume that $T_i$ (Completion Time) for all processes is directly proportional to the waiting time of the Job $J_i.$

Now in the expression $\sum_{i=1}^nw_iT_i$, $w_i$ is a constant, and so to reduce the whole expression $T_i$ must be as minimum as possible and hence that implies waiting time of the process must be as minimum as possible.

Which in effect will reduce $W_m$.

Now consider options one by one

(A)Non-decreasing order of $t_i$: Means shorter jobs are given preference irrespective of what the weight the job has. Okay, this policy will decrease the waiting time of longer jobs and average waiting time would decrease, but that if each longer job had maximum possible weights. In that case product $W_iXT_i$ would be large and $W_m$ would increase.

(B)Non-increasing order of $w_i$: No preference being given to the jobs based on their CPU time. Absolutely a nonsense choice because to reduce the turnaround time, you have to consider the burst time of jobs.Reject this option now.

(C)Non-increasing order of $w_it_i$: Consider a scenario where longer jobs are given higher weights than shorter jobs, then longer jobs would be executed first followed by shorter jobs, consequently the waiting time of shorter jobs would increase, and $T_i$ for longer jobs won't be affected much, but for shorter jobs, it will add up hugely because of increased waiting time!!.This option is also a big NO-NO.

(D)Non-increasing order of $\frac{w_i}{t_i}$ : Here jobs which have more weight but less CPU burst will be given more preference than jobs with the same amount of weight but more CPU burst. Clearly, this approach works as a priority calculator for each job giving preference to the more weighted job with less CPU burst, and consequently, the waiting time of other jobs will decrease and hence $T_i$ for each job would be as minimum as possible and hence $W_m$ would be minimum.

Comparing (d) and (a), (d) is better because it is also taking into account the weight of the job. Consider weight as a penalty imposed and then you'll come to know why (d) is any day a better choice than (a).

Answer(D)

 

 

14 votes
14 votes

(D)

working same like operating system concept.

Execute job which have more completion time in 1 sec.

i.e. find $\frac{wi}{ti}$ for every process then arrange in decreasing order so always get completion time minimum.

hence ans should be

None-increasing order of wi/ti

0 votes
0 votes
We need a sequence wherein we take jobs in a sequence such that it takes less time to execute (ti should be increasing) and gives more profit(wi should be decreasing).

To take into account both the factors, if we keep wi to be in decreasing manner, then how to adjust ti ? ti should be in increasing order, that means 1/ti must be in decreasing order, overall combining the two, (wi/ti ) should be in decreasing order.

Considering also the same values, we precisely call it non-increasing. So, non-increasing order of wi/ti is much beneficial, i.e Larger profit in less time is the order we need.
Answer:

Related questions