上一篇，我們談了 Bin Packing。
假設每台貨車的容量有限：
capacity = 10
而所有箱子都必須送走，我們要思考的是：
怎麼把這些箱子分配到有限容量的貨車裡？
這時候，有限的是 空間。
但現實生活中，還有另一種我們每天都在面對，而且永遠不夠用的資源：
時間
一天就只有 24 小時。
如果只算工作時間，也許更有感覺，09:00 ~ 18:00 扣掉午休之後，真正能安排工作的時間可能只有八小時。
問題也就從 東西要放進哪個箱子？ 變成：
事情到底要排在什麼時間？
這就是今天要談的：
排程 Scheduling
假設今天有四件工作：
如果我們只記錄工作名稱，也許還不夠完整，因為每件工作的時間條件可能完全不同。
例如：
這裡已經出現幾種不同資訊：
它們描述的其實都是：
這件工作可以怎麼占用時間
先看最明顯的：
這代表每件工作都有自己的時長 duration。
如果今天可用時間只有 8 小時，而工作總時間是：
2 + 3 + 1 = 6 小時
至少從總量來看，好像放得下。
這跟上一篇 Bin Packing 已經有一點相似。
但 Scheduling 比 Bin Packing 多了一個很重要的問題。
箱子放進貨車時，我們通常不太在意：
它是上午放進去，還是下午放進去
時間卻先天存在：
先後順序
假設「產品會議」已經確定 14:00 ~ 15:00。
那我們就不能把一個三小時、而且不能中斷的工作安排成：
13:00 ~ 16:00
因為它會跟會議重疊：
13:00 ---------------- 16:00
14:00 -- 15:00
這就是 Scheduling 裡非常常出現的考量：
衝突 conflict
兩個工作如果占用了同一段不可共享的時間，就產生衝突。
如果一個工作有明確的開始與結束時間：
會議 A：09:00 ~ 10:00
會議 B：10:30 ~ 11:30
會議 C：11:00 ~ 12:00
我們可以把每個工作想成一段：
interval
例如：
A [09:00 ------ 10:00]
B [10:30 -------- 11:30]
C [11:00 -------- 12:00]
A 和 B 沒有重疊。
但是 B 和 C 有一部分使用了相同時間：
10:30 -------- 11:30
11:00 -------- 12:00
所以 B ↔ C 存在衝突。
這也是為什麼 Scheduling 問題常常不只是問：
有多少工作？
還要去問：
這些工作占用了哪些時間區間？
想像公司只有一間會議室。
今天有人想預約：
A：09:00 ~ 10:00
B：09:30 ~ 11:00
C：11:00 ~ 12:00
D：13:00 ~ 14:00
如果會議室同一時間只能給一場會議使用，那麼 A 和 B 就不能同時成立。
我們還是必須做選擇，這時候問題就變成：
要選哪一個？
假設我們想讓：
一天可以安排最多場會議
這是一種最佳化目標。
但也有可能我們真正想要的是：
安排總時間最長的會議
或者：
優先保留重要會議
甚至：
儘量滿足最多部門
同一組 interval，只要最佳化目標改變，最後的排程結果就可能完全不同。
看到時間問題時，我們很容易第一個想到：
按照開始時間排序
例如：
09:00
10:00
11:00
13:00
但排序只能告訴我們：
誰比較早開始
它沒有直接回答：
哪些工作應該被安排
例如：
A：09:00 ~ 17:00
B：09:00 ~ 10:00
C：10:00 ~ 11:00
D：11:00 ~ 12:00
E：12:00 ~ 13:00
如果我們只是看到最早開始的 A 就先選 A：09:00 ~ 17:00，那剩下所有工作可能都無法安排。
但如果選 B、C、D、E，反而可以完成四件事情。
所以排程的目的不只是單純的排序，是去權衡：
在時間限制與衝突之下，哪些安排符合我們真正想追求的目標？
現在加入另一種常見條件：
A：需要 2 小時，12:00 前完成
B：需要 3 小時，17:00 前完成
C：需要 1 小時，沒有特別期限
這裡的 12:00 和 17:00 就是 deadline。
Deadline 跟固定 開始/結束 不太一樣。
例如：
A：12:00 前完成 不代表一定要：10:00 ~ 12:00，它也可以是 09:00 ~ 11:00，只要完成時間沒有超過 deadline 即可。
所以現在我們不只是問：
工作會不會互相重疊？
還得考慮：
怎麼安排，才能讓重要工作在 deadline 以前完成？
再把問題變得更貼近現實一點，今天有：
假設時間不夠全部完成。
那我們可能會給工作不同的 priority：
priority = 10
priority = 2
priority = 5
priority = 3
這時 Scheduling 就不只是專注在塞進最多工作。
因為 5 個低優先工作 未必比 1 個重大 Production Bug 更值得先處理。
這其實又回到了我們前幾篇一直遇到的問題：
最佳化目標到底是什麼？
對一個 Scheduling 問題來說，「最佳安排」可能代表：
所以當 PM 說：
幫我把工作排到最好
其實這需求仍然不完整，我們至少還得知道：
這些條件沒有定義清楚以前，我們其實連問題都還沒描述完整。
很多不必要的爭吵都在這裡，專案開發時工程師要連續這樣問，你的經理可能已經覺得你態度不好了，但在他的邏輯裡可能根本不知道會有這些情況，下次再遇到類似的問題可以推薦他這篇文章。
這個認知很重要：
Scheduling 是一類問題，不是某一個固定演算法
因為只要條件稍微改變，問題就可能變成完全不同的形狀。
例如：
一間會議室
+ 一堆固定時間的會議
+ 希望安排最多場
是一種問題。
但：
一個工程師
+ 每件工作有 duration
+ 每件工作有 deadline
+ 希望減少逾期
又是另一種問題。
如果再變成：
五個工程師
+ 每個人能力不同
+ 工作彼此有 dependency
+ 有 priority
+ 有 deadline
問題又會立刻複雜很多。
所以現實中的 Scheduling 系統，很少只靠一句：
把工作排序一下
就能解決。
回頭看最近幾篇，我們其實一直在處理同一個更大的主題。
表面上的故事完全不同，一個是 行李、一個是 貨車、一個是 行事曆。
但它們背後其實都在問：
當資源有限時，我們要怎麼分配？
而 Scheduling 讓我們多看見了一件事情：
時間不只有限，還具有順序
一個小時用掉之後，就不能再拿來做另一件互相衝突的工作。
所以在 Scheduling 裡，我們不只要考慮資源上限 resource capacity，還得考慮：
這也是為什麼「今天到底該先做什麼」看似只是日常生活的小問題，背後卻其實是一個非常典型的演算法問題。
Scheduling 的核心並不是背某一套排程演算法。
而是先學會辨認：
所以今天最重要的一句話是：
「時間」本身也是有限資源
而一旦我們開始把時間當成資源，原本一句很普通的：
今天工作怎麼排？
背後就開始出現：
這些我們前幾篇已經慢慢建立起來的概念。
但是到目前為止，我們大部分還是假設：
只有一個人，或一個資源，在處理這些工作
如果公司有很多工程師呢？
如果每件工作除了時間之外，還必須找到一個適合的人負責呢？
問題就會從 工作 → 時間 再多出另一種關係：
工作 → 人
於是下一個問題就變成：
如果問題不只是安排工作時間，還要決定每一件工作應該交給誰，會多出什麼新的關係？
iThome鐵人賽
看影片追技術