scheduling

專著

已有熱心人士撰寫了排程問題的專著:

《Scheduling Algorithms》

《Scheduling: Theory, Algorithms, and Systems》

已有熱心人士彙整了排程演算法的參考文獻:

導讀

多種產品、多種設備。找到最佳製程,儘快完成所有產品。

製程必須遵守規則。比方來說:

一、簡單起見,每種產品各一份,每種設備各一臺。

二、一份產品經由一臺設備加工,需要一段時間。

三、一種產品,擁有特殊的加工工序。一份產品,經過一連串指定設備,得到成品。

四、一種設備,同時間只能加工一份產品。一份產品,經過一臺設備,完成一道步驟。

不同產品可能需要相同設備。一個產品可能需要排隊等待某個設備。產品儘量不等待、設備儘量不停歇,以便儘快完成所有產品。

製程可以畫成圖表。最經典的圖表是「甘特圖Gantt chart」:橫軸是時間,橫向區間是加工時間,縱軸是產品或設備。

scheduling

上述詞彙都有專業術語:產品稱作「工作job」,設備稱作「機器machine」,加工稱作「操作operation」,製程稱作「排程scheduling」。

job        J₀ J₁ J₂ ...    工作
machine    M₀ M₁ M₂ ...    機器
operation  (j,m,t)         操作(工作編號、機器編號、時刻)
scheduling (j₀,m₀,t₀) ...  排程(操作的集合)

規則可以自由創作。給定特定規則,求得最佳排程。

機器順序的規則,可以自由創作。以下只列舉其中幾項:

open shop scheduling  每種工作在每種機器各做一次,機器順序隨便。
 job shop scheduling  每種工作有特定的機器順序。
flow shop scheduling  每種工作的機器順序都一模一樣。

操作的規則,可以自由創作。以下只列舉其中幾項:

operation sequence   Oᵢⱼ   機器順序(工作對機器)
processing time      pᵢⱼ   操作時間(工作對機器)
release time         rᵢ    工作發生時間(工作)
precedence relation  βᵢⱼ   工作優先順序(工作對工作)
transportation time  tᵢⱼₖ  工作換機時間(工作對兩機器)(額外工作時間)
changeover time      sᵢⱼₖ  機器換工時間(機器對兩工作)(額外機器時間)

最佳化目標,可以自由創作。以下只列舉其中幾項:

completion time      Cᵢ                    完工時間
due time             dᵢ                    完工期限
earliness            Eᵢ = max(0, dᵢ - Cᵢ)  提前時間
tardiness            Tᵢ = max(0, Cᵢ - dᵢ)  延誤時間
makespan             max Cᵢ                完工時間最大值
total flow time      sum Cᵢ                完工時間總和

排程問題,幾乎都是NP-hard問題,沒有快速的演算法。常見解法是整數規劃、啟發式演算法。

擁有特殊限制的排程問題,才有快速的演算法。常見解法是貪心法、動態規劃。

以下章節將介紹幾個特殊的排程問題,其解法都是貪心法。

UVa 452 690 863 1194 1380 12228

single-machine scheduling: Moore–Hodgson algorithm

minimize the number of tardy jobs(1||∑Ui)

有一位苦命上班族,要馬上處理臨時指派的N份工作。經驗老到的他,馬上就精準的估計出每份工作各要花掉多少時間,可是每份工作都有不同的完工期限,這造成有些工作可能會來不及完成。他做事專心,要求品質,一次只處理一份工作,一份一份接著做;來不及完成的工作,乾脆放棄不做。

請找出一種排程,讓如期完成的工作最多(也就是讓逾期完成的工作最少),順便讓總工時越短越好。

合理排程之相鄰交換性質

一個合理排程,其中某兩個如期完成的工作A與B,A與B緊鄰完成,A早做B晚做,A期限晚B期限早(或期限相同),則A與B對調位置之後,仍是一個合理排程。分析如下:

A與B視作一體進行交換:排程裡的其他工作皆不受影響。
A放到B的位置:A的期限比B還晚,B都能如期完成了,所以A也能如期完成。
B放到A的位置:B提早做,更能如期完成。

一個合理排程,不斷地進行相鄰交換,終會形成「工作依照期限排序」的合理排程!反之亦然!小心,不相鄰則不可貿然交換。

因此,我們只需著眼於「工作依照期限排序」的合理排程。

UVa 10026 11389

演算法(Moore–Hodgson algorithm)

所有工作依照期限排序,依序加入排程。一次加入一個工作,一旦發現逾期,立即從排程當中抽掉工時最長的工作。

已經加入N個工作,排程裡有M個工作。
排程裡的工作,是前N個工作的最佳解。也就是說:
α. 這M個工作,全部如期完成。
β. 前N個工作之中,如期完成的工作數量最多就是M。
γ. 前N個工作之中,這M個工作總工時最短。

以數學歸納法證明之。假設N成立,當第N+1個工作加入排程,有兩種情況。

一、沒有發生逾期:

這M個工作,本來就是如期完成、工作數量最多、總工時最短的最佳選擇。第N+1個工作加入之後,αβγ依然成立。

二、發生逾期,立即抽出工時最長的工作:

這M個工作,已經能如期完成。抽出工時最長的工作,補上工時稍短(或相等)的第N+1個工作,更能如期完成了。α成立。

這M個工作,總工時已經是最短了,還是無法添加第N+1個工作,不得已抽掉一個工作,工作數量已經盡量多了。β成立。

抽出工時最長的工作,總工時下降最多。γ成立。

UVa 10154 ICPC 3277 4850 8046

single-machine scheduling: Lawler's algorithm

minimize the bottleneck objective(1|prec|Fmax)

方才那位苦命上班族,又要馬上處理臨時指派的N份工作。本次任務更加艱辛刻苦、錯綜複雜。

一、每份工作都要確實完成。形成一個排列。

二、每份工作都有誤點賠償機制。完工時間越晚、賠償金額越大。形成N個遞增函數。

三、每份工作都有優先順序機制。有必須更早完成的工作、也有必須更晚完成的工作。形成一張有向無環圖。

請找出一種排程,讓賠償金額最高的工作,賠償金額越小越好。

演算法(Lawler's algorithm)

排程從尾到頭,一次加入一個工作:賠償金額最小的工作。

two-machine flowshop scheduling: Johnson's algorithm

minimize the makespan(F2||Cmax)

兩臺機器,N份工作,一臺機器一次只能處理一個工作。每份工作必須先經過初號機處理一段時間,再經過貳號機處理一段時間,才算處理完畢。

請找出一種排程,迅速完成所有工作。

演算法(Johnson's algorithm)

1. 建立兩個空的list,叫做L1和L2。
2. 從N個工作、2N個工時當中,不斷挑出工時最短的工作。
   如果最短工時是初號機的工時,該工作加到L1前端。
   如果最短工時是貳號機的工時,該工作加到L2後端。
3. L1 L2,即是排程。
1. 建立兩個空的list,叫做L1和L2。
2. 對每一個工作,若初號機工時小於貳號機工時,該工作加到L1,反之則加到L2。
3. L1照初號機工時由小到大排序。
   L2照貳號機工時由大到小排序。
4. L1 L2,即是排程。

UVa 11269 11729