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 就如剛剛那幾頁一看，很簡單的。
你真的要解問題，很簡單。
對吧？所以要證明它很有效這種 麻煩的事情就交給學者去解決。
這全世界只要有一個人解這個問題就好了。
至於做應用，人人都做得到，只要你會寫程式， 看得懂剛剛的演算法，就可以解這個問題。
孔令傑助理教授(Assistant Professor)
