OK,那,那麼呢,就讓我們來 implement LPT。
然後呢,我們為了簡單起見呢,咱們就跳過這個 sorting step。
那 sorting 如果真的要 sort 的話呢,基本上你也不會自己來。
你大概會呼叫一個函數啊什麼之類的, 所以有興趣的話,去
Google,Python,Sorting,Blah blah blah blah,剩下就交給你們自己啦。
咱們來試試剩下的部分。
好,首先呢,我要請使用者輸入這個一些 基本上題目要有的相關資訊。
所以我要先請使用者輸入 n,m, 和 p。
p 是什麼呢?p 是這個 p1,p2,p3,就是 processing time。
n 是 job 數,m 是 machine 數,所以這兩個大概沒有問題。
你請使用者輸入了 job 數, 輸入了 machine 數,然後 n 跟 m 它們就分別被取得 value 啦。
然後呢,這個 input processing time 的話,就需要多做點 處理。
我們請使用者按照空白鍵隔開一連串的數字, 因此我們這個
pStr,我們把它拿來 split,變成了小 p 以後, 我們把裡面的每一個東西,一個一個地拿出來。
然後, 拿出來了以後呢,就把它轉成 int 再復寫回去。
那麼到我們這個 for 迴圈跑完的時候,
我們就知道,到此為止,n, m, p 就算是準備好了。
那另外呢,我們要準備兩個 list,這兩個 list 是要裝答案的。
就是我們要有一個 list 是 loads,就是 loading,
也就是說這個 machine,目前為止被分配到的 job 會耗它多少時間。
這個 loading 的這個一個 list,所以它 的長度是 m,一開始都是 0。
另外呢,有一個叫做 assignment 的這個 list,它呢,是 n 個。
它等一下要記的是第一個 job 要分給 machine 3,第二個 job 要分給 machine 2,以此類推。
所以是有 n 個欄位要寫入資料。
好,那接下來呢,我們就要來做我們的 iterative 的 process 了。
每一個迴圈我們要分配一個工作, 那換句話說,如果我有 n 個工作,我這個迴圈就要跑 n 次。
那我當然就要用 for,就不會用 file 了,這樣比較自然。
好,所以在 iteration j,我要 assign job j 去給 least loaded machine。
那我們來試試看。
首先呢,我必須要 find the least loaded machine,對吧?迴圈,每一圈,每一圈,每一圈在跑。
跑到任意一圈的時候,我都知道我的 loads
的 這個,呃,list,裡面裝著若干個數字,我要挑出最小的哪一個。
而且我還要知道它在哪裡。
那這件事有很多做法啦,那我們就用最簡單的方式,就是一行一行 code 自己寫。
我呢,先假設我不知道這傢伙是誰,所以有一個 list loaded machine,目前編號是 0。
然後呢,我們先假設它是第 0 臺,因此我們就說,
那它的 list load 就是第 0 臺 machine 的 loads,在這裡。
好,接下來呢,從第 1 臺,第 2 臺,第 3 臺,一直到 n-1 臺。
哦,0,1,2 一直到 m-1,我們呢,一個一個去算,它的 loading 是多少。
它的 loading 是多少,它的 loading 是多少。
把這每一個 loading 都拿來跟目前的 list
load 比較,如果比贏了, 就是比較小。
那麼呢,就知道這傢伙現在要當 candidate 了。
這第 i 臺 machine 就要來把它暫時登上這個 list loaded machine 的寶座。
然後呢,把 list load update 成它的 loading, 然後就把這個迴圈跑一遍。
跑完了以後我們就會看,哦,現在這個 listed loaded machine 是誰。
我們呢就知道要對它做事情啦。
接著我們要 schedule a job,那我們的任務無非就是 對於那個
list loaded machine 的 loads,我們要幫它往上加,我們要把這個
machine,這個 job 的 loading 加到那一臺 machine 上面去。
這樣在下一圈算的時候才會正確。
那另外呢,是這個 assignment。
assignment 是我們要記答案的地方,所以我們要 把第 j 個 job 要 assign
給誰要記起來,然後是 list loaded machine, 那這裡要不要加 1 呢,看你的設計。
比如說,我們知道我們 index 是 0、 1、 2、 3、 4、 5 這樣排,
那如果我們虛擬的編號是 1、 2、 3、 4、 5,那你這裡就加 1,以便你看得出來你在講誰。
那麼以上的事情都做完了以後呢,最後就把結果印出來,看一看就可以啦。
好,把 assignment 印出來,把 loads 印出來,大概就是這麼一回事。
好,那我們來試試看這個程式。
那麼這個程式呢,我們已經把剛剛三段這個 程式碼都複製貼上,貼在一起了,所以這現在合起來是一個程式。
這裡是剛剛的第一段,讀資料並且做前置處理。
這裡是第二段,每一個迴圈的
iteration,我們會做一次 assignment。
最後這裡是印結果的。
那我們來看看。
好,Number of jobs 就 10 個吧,Number of machines 就 3 個,
那 processing times 就 3,3, 3, 4, 4, 5, 5, 6,
7 ,8, 比如說像這個樣子好啦!好,那我們一跑下去就發現,欸,看到了結果。
那看到的結果之中呢,有一部分是這裡。
這個圖 check the process, 剛剛在投影面上沒有,是我們自己加上去的。
就是讓我們看迴圈每一圈跑完,我們就來看一下 這個 job 被分給誰,以及分到此刻的狀態為何。
所以你可以看到第 1 個 job,是這個 3 工作量,被分給
machine 1, 然後 machine 2,然後 machine
3,然後因為平手,平手分給這個編號最小的,然後就是 7,然後就是 7, 那 5 呢就分給 3,就是 8。
那接著又要再分的時候,這個人最輕鬆,就分給他 6, 分給 7,7 分給 8,然後 8 再分給它,以此類推。
最後我們就得到了 20,13,15。
換句話說,我們的這個 machine 的 work loads 就是 20 是最大的。
那它就是 makespan,所以這樣子的演算法, 在這一題裡面,我們就得到了 20 這樣子的答案。
那 1 ,2,3,1,2,3,1 就恰好就是我們 job 的 assignment。
job 1 要分給 machine 1,job 2 要分給 machine 2,job 4 要分給 machine 1,以此類推。
大概是這個樣子。
好,那我們再試一次,那我們來把它排序看看,所以我等一下要打 8,7,6,5,5,4,4,3,3,3。
好,8,7,6,5,5,4,4,
3,3,3,那么如果我們這麼做的話呢,噼里啪啦地跑完了,你發現,欸,表現果然是變得- 好一點了。
對吧?就是我們的 machine loads 會變成 18,15,15。
那 18 當然是比剛剛的 solution 來的好很多。
好,所以加上排序果然是有用的。
好,那麼不管是有排序還是沒排序,其實你都還是會問你自己一個問題。
就是欸, 這個真的是最佳解嗎?那其實你也知道,這一題是有辦法排除
16,16,16的, 所以 18, 15, 15 並不是最佳解。
LPT 不能保證給你最佳解,那這個呢是 所有的 heuristic
演算法的必然會發生的事情,就是你本來就不能保證會得到最佳解。
OK,那剛剛的問題因為太難了,就是我們說它是 NP-hard,
所以呢,我們不 care 最佳解,我們只要盡量找到好的解 就可以了。
那至於好的解,到底怎樣是好,怎樣是不好,那這個就是實物上要去煩惱的事情。
好,就是通常都好。
好的程度夠了嗎,演算法 OK 嗎,可能這就是實物上的事情啦! 那我們最後 Remark 一下這個演算法。
LPT 就是我們所說,它不一定能得到最佳解。
但有趣的是呢,它有一個很好的理論性質,就是它可以保證 worst-case 的 performance。
意思就是說,像這樣。
假設我給你一個題目, 它呢,在 optimal solution
的底下有一個 z *, 就是最小可以小到那個程度的 makespan。
那我們的 LPT somehow 會 to 另外一個 solution,所以你有另一個值。
就是它會,比如說,剛剛那個例子的話,z * 是 16, 而我們的 z LPT 是 18,這樣子。
剛剛是這樣,然後呢,在這個例子里,18 跟 16 很接近。
但你不知道別的例子里會不會也很接近,對吧?不過,LPT 演算法可以被證明。
就是說,不論你的 instance 長成怎樣,也不會差超過三分之一。
換句話說呢,我們就說,它 LPT 可以做良好的 approximation。
我們可以近似最佳解,而近似的程度不超過三分之四。
換句話說就是,我知道 LPT 不一定是最佳解,但是它再爛也有個限度。
以這個例子來講,再爛就是三分之一。
好,那這樣你用起來當然就會有信心多了。
事實上,就算你不排序,再爛也不會爛超過兩倍。
它還是有限度的,那我們必須強調, 這個所謂的分析和證明是非常困難的。
通常是研究所 等級的學生也不一定會去學這件事情,是很理論、 很困難的事情。
但好消息是,implementation 就如剛剛那幾頁一看,很簡單的。
你真的要解問題,很簡單。
對吧?所以要證明它很有效這種 麻煩的事情就交給學者去解決。
這全世界只要有一個人解這個問題就好了。
至於做應用,人人都做得到,只要你會寫程式, 看得懂剛剛的演算法,就可以解這個問題。