排程問題1：晚了就不要

更新於 2023/07/24發佈於 2023/06/30閱讀時間約 9 分鐘

前言

當主管突然交代一堆工作時，我們通常會先估算各項工作需要的時間，然後按部就班執行。但當主管為各項工作設定了 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

為什麼會看到廣告

#scheduling

JN的沙龍計算機

JN的沙龍

62會員

21內容數

個人網誌啦~ 內容包含但不限於學習筆記、心情抒發、火星廢文...

留言0

查看全部

發表第一個留言支持創作者！

JN的沙龍的其他內容