注意，完全不嚴謹，只是概念
有M個機器，N個工作(job)，每個工作各自要花S時間(job time)完成且不能平行處理(分割)
OPT為最佳解(optimal solution)，
alg 會輸出 (消耗時間最大的那個機器的) 時間
<=是小於等於
且有幾個前情提要
- alg所輸出的結果會 大於等於 OPT (顯而易見)
- OPT會 大於等於 平均 (即所有工作時長 除以 機器數)
- OPT會 大於等於 單一工作 (即工作不可拆分)
- 工作 大於等於 機器數+1 (避免問題過於簡單)
開始分析
所以肯定會有一個alg輸出，那個機器就叫Mh好了 (取High的開頭)
在Mh(未)成為Mh之前肯定會放入某個S長度的時間，就叫他SL好了 (取Last的開頭)
最後一個放入Mh的時間S
所以
alg = Mh在加入最後一個S之前 + SL ， SL會讓Mh(未)成為Mh
因為是用greedy的方法，Mh在加入最後一個S之前必然是比其他機器花的時間少
演算法才會挑中它
<=(S1+S2+S3+...SL-1)/m + SL
<=(S1+S2+S3+...SN) /m - SL/m+ SL
<=全部時間/m - SL/m+ SL
根據第二條前情提要 OPT會 大於等於 平均
<=OPT - SL/m+ SL
<=OPT +( 1- 1/m )SL
根據第三條前情提要 OPT會 大於等於 單一工作 所以SL<=OPT
<= ( 2- 1/m )OPT
所以
alg <= ( 2- 1/m )OPT
在沒有排序時間的greedy且m趨於無限時，這個演算法數字是2倍的OPT
那有排序時間由大到小的greedy呢?
S1大於等於S2大於等於S3大於等於S4大於等於S5.....到SN 因為有N個工作
會需要新增前情提要
5.OPT 大於等於 SM+S(M+1) M是機器數
6.Mh只有1個job的時候是最佳解OPT
想一下你有十個工作，5台機器
OPT沒有規定怎麼放，沒有規定要用greedy，沒有規定要從大到小輸入
你要怎麼做出第五項前情提要?
這是一個general的case喔，不能先假設由大到小放入
.
.
.
.
.
.
沒錯拿前六個大的工作，5台機器出來比較
可能覺得在公沙小，不過你肯定能比較這六個工作與十個工作的OPT
肯定是 OPT(十)大於等於OPT(六)
前六個大的工作，5台機器 肯定可以用鴿籠原理 M=5
不管哪種演算法必先將所有機器先塞一個job
至少有一台機器會塞兩個job，最小就是=最小的兩個job time相加
也就是第M個與M+1個
OPT(十) 大於等於 OPT(六) 大於等於 S五+S(五+1)
至於第六點，用第一、三條前情提要就可以推出來
Mh = alg >= OPT
OPT >= job
Mh只有1個job Mh=job
想一想，是不是夾起來了
開始分析
alg = Mh在加入最後一個S之前 + SL ， SL會讓Mh(未)成為Mh
- L小於等於M，代表L是第一個放入Mh的
依照定義L是最後一個放入Mh的
Mh只有一個job
直接用第六個前情提要
Mh只有1個job的時候是最佳解OPT
- L大於等於M+1，代表L是第一個放入Mh的
alg = Mh在加入最後一個S之前 + SL ， SL會讓Mh(未)成為Mh
<=(S1+S2+S3+...SL-1)/m + SL
<=(S1+S2+S3+...SN)/m - SL/m+ SL
<=全部時間/m - SL/m+ SL
根據第二條前情提要 OPT會 大於等於 平均
<=OPT - SL/m+ SL
根據第五條前情提要 OPT 大於等於 SM+S(M+1) M是機器數
OPT 大於等於 S(M+1)+S(M+1)
L大於等於M+1
OPT 大於等於 2SL
1/2 OPT 大於等於 SL
所以SL<=OPT/2
alg <= ( 1.5- 1/2m )OPT
在有 排序時間的greedy且m趨於無限時，這個演算法數字最多就是1.5倍的OPT
在沒有排序時間的greedy且m趨於無限時，這個演算法數字最多就是2.0倍的OPT
