# 5.5. Scheduling: Minimizing Total Time in the System

alg

Problem
- Consider a system in which a server is about to serve n clients. Let T = {t_1, t_2, ..., t_n} be a set of positive numbers, where ti is the estimated time-to-completion for the ith client. What is the optimal order of service where the total (wait+service) time in the system is minimized?
- Hair stylist with waiting clients, pending operations on a shared hard disk, etc.
Example
- T = {t_1, t_2, t_3} = {5, 10, 4} | Schedule | Total Time in the System | | --------- | --------------------------------- | | [1, 2, 3] | 5 + (5 + 10) + (5 + 10 + 4) = 39 | | [1, 3, 2] | 33 | | [2, 1, 3] | 10 + (10 + 5) + (10 + 5 + 4) = 44 | | [2, 3, 1] | 43 | | [3, 1, 2] | ☞ 4 + (4 + 5) + (4 + 5 + 10) = 32 | | [3, 2, 1] | 37 |
A naïve approach
- Enumerate all possible schedules of service, and select the optimal one. → O(n!)
A greedy approach
- Algorithm
  - Sort T in nondecreasing order to get the optimal schedule. - → O(n \log n)
- Correctness : 귀류법 (Proof by contradiction)
  - Does the greedy approach always find a schedule that minimizes the total time in the system?
  - Let S = [s_1, s_2, ..., s_n] be an optimal schedule, and C(S) be the total time for S.
  - C(S) = s_1 + (s_1 +s_2) + (s_1 + s_2 + s_3) + ... + (s_1 + s_2 + ... + s_n) \\ = n \cdot s_1 + (n-1) \cdot s_2 + ... + 2 \cdot s_{n-1} + 1 \cdot s_n \\ = \Sigma_{i=1}^{n}{(n+1-i)\cdot s_i} \\ = (n+1) \Sigma_{i=1}^{n}{s_i}-\Sigma_{i=1}^{n}{i \cdot s_i}
  - If they are not scheduled in nondecreasing order, then, for at least one i(1≤i≤n-1),s_i >s_{i+1}.
  - Now consider the schedule S’ = [s_1, s_2, ..., s_{i+1}, si, ..., sn] that is obtained by interchanging s_i and s_{i+1}.
  - Then,C(s) - C(s') \\ = (i \cdot s_{i+1} + (i+1) \cdot s_i) - (i \cdot s_i + (i+1) \cdot s_{i+1}) \\ = s_i - s_{i+1} >0.
  - Therefore, ...

alg