GATE IT 2007 | Question: 26

Question

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?

• A. Non-decreasing order of $t_i$
• B. Non-increasing order of $w_i$
• C. Non-increasing order of $w_it_i$
• D. Non-increasing order of $w_i/t_i$

Comments

Remember fractional knapsack problem.

---

so, here $\frac{w_{i}}{t_{i}}$ is the profit ratio

---

This Can be also be understood as : 

Since the denominator of the given formula, $\sum_{i=1}^n w_i$, is simply the sum of all weights and remains constant regardless of the schedule, our goal is to minimize the numerator: $\sum_{i=1}^n w_i T_i$.

1) If All Processes had same executiion time (ti) : 

               Then process with higher weights are chosen (should be chosen) because making a higher weighted process wait (when factors like Execution time are same for all) , would rather increase the the weighted mean completion time of the jobs
 

2) If All Processes Had Same Weights , But different Execution Times , : 

               Then choosing the shorter jobs would decrease the avg waiting time else , it would have a convoy effect on the shorter jobs (where many short processes are stuck waiting behind a single large, CPU bound proces) 

So : 

• All else being equal, prioritize jobs with higher weights (Non-increasing order of $w_i$).
• All else being equal, prioritize jobs with shorter execution times to prevent bottlenecking the queue

3) Also , To Minimize the term $\sum_{i=1}^n w_i T_i$. : Avoid scheduling Processes with both higher weights are higher execution time , rather execting shorter processes with higher weihgts is more optimal 

Answer 1

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. 

Comments

Can the answer also be “increasing order of wi*ti”, isn’t it same like option d: “decreasing order of wi/ti”? @GO Classes

---

can someone pls explain the calculation part

---

@puspeshsrivastava yes I think option  c would also be correct if increasing of wi*ti given instead of non-increasing

Answer 2

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)

 

 

Comments

thank you @Ayush Upadhyaya!!!!

---

in option A)'s explanation : 

Okay, this policy will decrease the waiting time of longer jobs and average waiting time would decreas.....

by prioritising shorter jobs, how will this policy decrease the waiting time of longer job ? 

---

best explanation never been so happy.

Answer 3

(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

Answer 4

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 5

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.

Answer 6

The contribution of Ji is Wi*Ti .  So to reduce mean , the numerator should be the minimum as Dr is const .

Assume , we already know the optimal sequence represented with time as below

Now , say : t1<t2 <t3 .......<tn . This will be our order sequence(ie the optimal sequence) and we will select the weights for each time .The time can be fixed because because we know time of job 2 will be more than job1 and hence time of job i+1 will be more than job i .

Now we select the weights as it is the only remaining variable from Nr . So how would we get optimal soln for the mean : using the least variance . That is the lowest time multiples with highest weight and highest weight with lowest ( u can think that highest* lowest and 2nd highest*2nd lowest .......and i highest * n-i lowest would yield the least variance , because every term is closest to avg thus we will get the smallest mean as it is the avg value)

So , w1 >w2 > w3 ......>wn

Hence option a,b can be eliminated

OPTION C , means : wn.tn , wn-1.tn-1 ........,w2.t2, w1.t1   ; which is obviously incorrect ordering of our assumed ti . Here, we determined order using three cases. Case 1 ,  w dominates t  then u can easliy ignore t for comparison and get the order. Case 2 , t dominates w , we still get the same order . There is the other case when neither term dominates , then we would genearate a scrambled order , for ex : w1.t1 , w3.t3 , wn.tn , w4.tn ......etc hence all the n! -1 sequencing in case three would be suboptimal plus 1 optimal sequence.

 

OptionD , as we can se this option generates our required optimal sequence , t1 then t2 ....then tn .

There is no loss of genrality because , if u look closely at the assumption of t and w , every case is considered because the method of avging couples ti and wi , as a single entity because of the constraints . So , we just need to observe and maintain the sequence of ti , from the options.