給定兩台servers以及一個task array,每一個task都包含兩個時間,第一個時間是在第一台server需要處理的時間,第二個時間是在第二台server需要處理的時間,兩台servers有著不同的特性,第一台server一次只能處理一個task,第二台server可以平行處理任意數量的tasks,所有tasks必須先經過第一台server處理後,才能進第二台server處理,請問如何安排tasks的執行順序,可以得到minimum time to finish all tasks?
給定兩台servers以及一個task array,每一個task都包含兩個時間,第一個時間是在第一台server需要處理的時間,第二個時間是在第二台server需要處理的時間,兩台servers有著不同的特性,第一台server一次只能處理一個task,第二台server可以平行處理任意數量的tasks,所有tasks必須先經過第一台server處理後,才能進第二台server處理,請問如何安排tasks的執行順序,可以得到minimum time to finish all tasks?
此題可以分為兩個部分
第一部分是如何決定task的執行順序?
假如只有第一台server,tasks只需要在第一台server處理,那麼因為第一台server是one-by-one處理tasks,所以不管怎麼安排tasks的執行順序,得到的時間都一定是所有tasks在第一台server執行時間的總和。用此觀念延伸,把第二台server加進來,如果讓在第二台server執行時間最久的task先跑第一台server,那麼它就可以早點在第二台server執行,也會可以早點結束,這個選擇會比「讓一個在第二台server執行時間比它短的task先跑」還要更好,所以可以先對task array在第二台server的執行時間做descending order的排序
第二部分是如何計算出time to finish all tasks?
結合第一部分的執行順序,可以計算每一個task的結束時間,以此決定最終所有tasks的結束時間。實際實作可以自己想想看,不難