edited by
14,456 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

0 votes
0 votes
I think i can add a good perspective hence here’s my take:

If we only consider $w_i$ to set priorities then among the processes with same $w_i$, all processes will be given same priority. hence it may so happen that longer jobs r executed first and we know that this is not optimum as if the shorted jobs r executed first then average waiting times are minimised. Hence we need to prioritize smaller $t_i$ among equal $w_i$ hence we get to $\frac{ w_i}{t_i }$.

Now similarly if u only take $t_i$ then among the processes with same $t_i$ all r given same priority hence it may so happen that processes with bigger weights are executed last. Now these will be multiplied with $T_i$ given in the question which depends on waiting time(refer to Ayush sir’s ans for how this is true). hence basically if the bigger wieghts are executed later (among the same $t_i$ processes) then they will have to wait more. Hence it will be worse than executing the smaller $w_i$ processes first.
–2 votes
–2 votes

Answer is (A)

The execution must follow SJF.

Since we have to minimize Wi *Ti where wi is a constant , so we can only minimize the product by atleast decreasing the Ti for a job by executing shorter jobs first because that will reduce  completion time for the jobs that follow.

Answer:

Related questions