Consider n jobs J1, J2,......Jn such that job Ji has execution time ti and a…
2007
Consider n jobs J1, J2,......Jn such that job Ji has execution time ti and a non-negative integer weight wi. The weighted mean completion time of the jobs is defined to be
, where Ti is the completion time of job Ji. 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 ti
- B.
Non-increasing order of wi
- C.
Non-increasing order of witi
- D.
None-increasing order of wi/ti
Attempted by 78 students.
Show answer & explanation
Correct answer: D
Answer: Schedule jobs in non-increasing order of w_i / t_i (highest weight per unit processing time first).
Key idea: use an exchange argument comparing any two adjacent jobs.
Consider two jobs i and j with processing times t_i, t_j and weights w_i, w_j.
If i is scheduled before j, the contribution of these two jobs to the total weighted completion time is (w_i + w_j) * t_i + w_j * t_j.
If j is scheduled before i, their contribution is (w_i + w_j) * t_j + w_i * t_i.
The difference (cost with i before j) - (cost with j before i) simplifies to t_i * w_j - t_j * w_i.
Therefore, placing i before j is no worse than the reverse when t_i * w_j - t_j * w_i <= 0, which is equivalent to w_i / t_i >= w_j / t_j.
Applying this comparison repeatedly (or sorting by the ratio) yields a schedule that minimizes the total weighted completion time.
Note: If several jobs have the same ratio w_i / t_i, their relative order does not affect the optimal value, so ties can be broken arbitrarily.
A video solution is available for this question — log in and enroll to watch it.