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