前往
大廳
主題

簡易 排程總製造時間 (Makespan) 分析

山上樵夫 | 2024-03-06 18:58:58 | 巴幣 0 | 人氣 68

注意,完全不嚴謹,只是概念


有M個機器,N個工作(job),每個工作各自要花S時間(job time)完成且不能平行處理(分割)
OPT為最佳解(optimal solution),
alg 會輸出 (消耗時間最大的那個機器的) 時間
<=是小於等於

在使用Greedy alg條件下
且有幾個前情提要
  1. alg所輸出的結果會 大於等於 OPT   (顯而易見)
  2. OPT會 大於等於  平均                     (即所有工作時長 除以 機器數)
  3. OPT會 大於等於  單一工作              (即工作不可拆分)
  4.   工作   大於等於  機器數+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



創作回應

更多創作