前言
當主管突然交代一堆工作時，我們通常會先估算各項工作需要的時間，然後按部就班執行。但當主管為各項工作設定了 deadline，我們對於如何安排一個有效率的執行順序 (排程)，往往百思不得其解。這類問題變化非常多，本篇文章將以其中一種常見的情境來分享解題思路。(即前文主管都不一定懂的工作排程技巧！序言中提到的第一集)
情境 - 晚了就不要
情境重點：- 每項工作一樣重要。
- 主管只在意期限內完成的工作。
- 逾期的工作就不要了，沒人在意。
目標：
找到一種排程 (schedule)，讓按時完工的任務數量越多越好，來不及處理的任務就果斷放棄。
舉個例子：
7月1日！主管交代大家四項工作，擦窗、掃地、洗碗、送餐，並說明若期限內沒做完就算了，他會花錢請工讀生處理。四項工作的期限和處理時間如下圖。
四項工作的期限和處理時間
五位員工，收到任務後便開始在行事曆上規劃自己的 schedule。
五位員工各自的行程表
苦幹實幹的 JN，無腦地把四件事情依序排進行程表，即使逾期還是照做，大概是在想：沒有功勞也有苦勞。(醒醒吧...) 最後花了九天，只按時完成了擦窗和掃地兩件工作。
聰明機伶的阿金，看著 JN 的行程表暗笑他的迂。既然洗碗和送餐確定逾期，根本就不用排進去，阿金將行程表稍作優化，只花了五天，就按時完成了擦窗和掃地兩件工作。
時間很貴的小歐，看到大家都只完成兩件事，乾脆將最輕鬆的送餐和掃地排進行程表，如此便只需要短短三天就能做完兩件工作，其他時間他要請假看房發大財。
悟性極高的大A，在紙上窮舉各種排列組合，最終找到一種期限內完成三件工作的排法，考績直接吊打所有人！開心之餘，還在中間排了一天空檔出去上課。
運籌帷幄的老G...應該不用我多說了吧！部門中總是有這麼一位，辦事迅速、聰明可靠的同仁，羽扇綸巾，談笑間，強虜灰飛煙滅，倏地排好了行程。在高效處理完三件工作後，打算來個小旅行。
這個例子，完成三件工作就是最佳解了，先恭喜大A、老G 今年考績得第一！
看到這麼簡單的例子，也許你開始後悔，浪費十分鐘看這種低能問題，那很棒，表示你頭腦靈活。但當工作數量不是 4 而是 40，甚至 400 呢？該排入哪些工作？哪些工作又該被果斷放棄？這是不是就成了一個很燒腦的問題呢。
如果你有這種困擾，
或是會造成這種困擾的主管，
真心推薦繼續看下去，
給自己一個...
成為老G 的機會。
解題思路
提醒，繼續往下看前，可以先睡個覺...
一、簡化問題
由上述例子我們知道，這種問題可能不是唯一解，所以我們只要像大A 或老G 一樣，找出其中一種解即可。
先不考慮工作之間的排假，要排最後再排就好。我們來觀察大A 和老G 兩人的 schedule，可以發現一個特性...
先將大A在七月五日的請假拿掉
「在最佳的 schedule 中，兩個相鄰的工作 U 與工作 V， 若先做 U 但 U 的期限較晚 (意即，後做 V 但 V 的期限較早)，則 U 與 V 對調位置之後，仍是一個最佳 schedule。」
以上圖來說，工作 U 可想成洗碗，工作 V 可想成掃地，在老G 的行程表中，洗碗與掃地相鄰，且 先做洗碗但洗碗的期限較晚，後做掃地但掃地的期限較早，因此若將洗碗和掃地對調，仍然還是一個最佳排程。
任何一個最佳排程，都能基於這個特性，不斷地將相鄰的工作對調，最終將能使排程中的工作順序跟期限順序相同。
因此，這題最初的目標：
找到一種 schedule，讓按時完工的任務數量越多越好，來不及處理的任務就果斷放棄。
可以簡化為：
找到一種按照工作期限順序的 schedule，讓按時完工的任務數量越多越好，來不及處理的任務就果斷放棄。
二、排程方法
由簡化後的目標可知，我們要找的排程 (schedule)，上面的工作順序要跟期限順序相同。那麼解法就能簡單分成三個步驟：
- 將所有工作按 deadline 早晚排序
- 依序將排序好的工作，一次一個排入行程表
- 若排入的工作逾期，就從行程表中刪掉耗時最長的工作
一樣用上面的例子來演示
第一步，將所有工作按 deadline 排序為：
- 送餐 (7/3)
- 擦窗 (7/4)
- 掃地 (7/7)
- 洗碗 (7/8)
第二步、第三步一起做。依序將排序好的工作，一次一個排入行程表。若排入的工作逾期，就從行程表中刪掉耗時最長的工作。
排入第一個工作，送餐，沒有逾期。
排入送餐
排入第二個工作，擦窗，逾期了。
排入擦窗
逾期了，那就刪掉行程表中最耗時的工作，剛好也是擦窗。
刪掉擦窗
排入第三個工作，掃地，沒有逾期。
排入掃地
排入第四個工作，洗碗，沒有逾期。
排入洗碗
四個工作都排完，最佳的排程就完成了！放棄擦窗，依序做了送餐、掃地、洗碗，三件工作。(需要在工作間請假的，可以輕鬆地以相反的順序洗、掃、送，以不造成逾期的前提下去規劃。)
話說，
不幸地(?)，這個解跟大A 的一樣，而不是老G...，說好給自己一個成為老G 的機會，怎麼變大A 了？
因為我寫完文才發現圖畫反了= =
其實不用太在意，兩者都是最佳解...
結論
記重點就好，不論多少工作，只要符合本文 晚了就不要了 的情境，就能照這三個步驟：
- 將所有工作按 deadline 早晚排序
- 依序將排序好的工作，一次一個排入行程表
- 若排入的工作逾期，就從行程表中刪掉耗時最長的工作
找到最佳解。
附件
附上程式碼給有興趣的人參考，
但還沒 debug，有發現問題可以留言叫我修，或一起討論，教學相長！
schedule_case1.py
import datetime
import heapq
TODAY = '2023-07-01'
TASKS = [
('Clean Windows', 3, '2023-07-04'), # (task_name, days, deadline)
('Sweep Floor', 2, '2023-07-07'),
('Wash Dishes', 3, '2023-07-08'),
('Deliver Food', 1, '2023-07-03'),
]
# preprocess
today = datetime.date.fromisoformat(TODAY)
tasks = [(t[0], t[1], datetime.date.fromisoformat(t[2])) for t in TASKS]
# step 1, sort by deadline
tasks.sort(key=lambda task: task[2])
# step 2 and 3
schedule = []
begin_date = today + datetime.timedelta(days=1)
for task in tasks:
heapq.heappush(schedule, (-task[1], task))
begin_date += datetime.timedelta(days=task[1])
print('Add: ', task[0])
if (begin_date - datetime.timedelta(days=1) > task[2]):
removed_task = heapq.heappop(schedule)
begin_date = begin_date - datetime.timedelta(days=task[1])
print('Remove:', task[0])
# print schedule
begin_date = today + datetime.timedelta(days=1)
schedule.sort(key=lambda t: t[1][2])
print('My schedule:')
for task in schedule:
print(begin_date, 'start to:', task[1][0])
begin_date += datetime.timedelta(days=task[1][1])
執行結果 (理論上跟本文演示的例子會一樣)
$ python schedule_case1.py
Add: Deliver Food
Add: Clean Windows
Remove: Clean Windows
Add: Sweep Floor
Add: Wash Dishes
My schedule:
2023-07-02 start to: Deliver Food
2023-07-03 start to: Sweep Floor
2023-07-05 start to: Wash Dishes