排程問題1：晚了就不要

前言

情境 - 晚了就不要

• 每項工作一樣重要。
• 主管只在意期限內完成的工作。
• 逾期的工作就不要了，沒人在意。

解題思路

一、簡化問題

由上述例子我們知道，這種問題可能不是唯一解，所以我們只要像大A 或老G 一樣，找出其中一種解即可。

先不考慮工作之間的排假，要排最後再排就好。我們來觀察大A 和老G 兩人的 schedule，可以發現一個特性...

「在最佳的 schedule 中，兩個相鄰的工作 U 與工作 V， 若先做 U 但 U 的期限較晚 (意即，後做 V 但 V 的期限較早)，則 U 與 V 對調位置之後，仍是一個最佳 schedule。」

以上圖來說，工作 U 可想成洗碗，工作 V 可想成掃地，在老G 的行程表中，洗碗與掃地相鄰，且 先做洗碗但洗碗的期限較晚，後做掃地但掃地的期限較早，因此若將洗碗和掃地對調，仍然還是一個最佳排程。

任何一個最佳排程，都能基於這個特性，不斷地將相鄰的工作對調，最終將能使排程中的工作順序跟期限順序相同。

因此，這題最初的目標：

找到一種 schedule，讓按時完工的任務數量越多越好，來不及處理的任務就果斷放棄。

可以簡化為：

找到一種按照工作期限順序的 schedule，讓按時完工的任務數量越多越好，來不及處理的任務就果斷放棄。

二、排程方法

由簡化後的目標可知，我們要找的排程 (schedule)，上面的工作順序要跟期限順序相同。那麼解法就能簡單分成三個步驟：

1. 將所有工作按 deadline 早晚排序
2. 依序將排序好的工作，一次一個排入行程表
3. 若排入的工作逾期，就從行程表中刪掉耗時最長的工作

一樣用上面的例子來演示

第一步，將所有工作按 deadline 排序為：

1. 送餐 (7/3)
2. 擦窗 (7/4)
3. 掃地 (7/7)
4. 洗碗 (7/8)

第二步、第三步一起做。依序將排序好的工作，一次一個排入行程表。若排入的工作逾期，就從行程表中刪掉耗時最長的工作。

排入第一個工作，送餐，沒有逾期。

排入第二個工作，擦窗，逾期了。

逾期了，那就刪掉行程表中最耗時的工作，剛好也是擦窗。

排入第三個工作，掃地，沒有逾期。

排入第四個工作，洗碗，沒有逾期。

四個工作都排完，最佳的排程就完成了！放棄擦窗，依序做了送餐、掃地、洗碗，三件工作。(需要在工作間請假的，可以輕鬆地以相反的順序洗、掃、送，以不造成逾期的前提下去規劃。)

話說，

不幸地(?)，這個解跟大A 的一樣，而不是老G...，說好給自己一個成為老G 的機會，怎麼變大A 了？

因為我寫完文才發現圖畫反了= =

其實不用太在意，兩者都是最佳解...

結論

1. 將所有工作按 deadline 早晚排序
2. 依序將排序好的工作，一次一個排入行程表
3. 若排入的工作逾期，就從行程表中刪掉耗時最長的工作

附件

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