排程問題2：早晚都要

前言

看著認真、認命上班的人越來越多，感觸良多，​我就提醒一句，

「不要瞎忙，以終為始，」

「begin with the end in mind」

懂的就懂。

排程問題進入第二集，相信會往下看的讀者， 不是看過前一集 排程問題1：晚了就不要，就是被類似問題困擾，不然大部分人應該看不下去才是。那就不囉嗦，直接進入主題，速戰速決不嘴砲。

情境 - 早晚都要

描述

主管交代了 N 個專案，每一個專案可以遲交，不能沒交，早晚都要做完交出去，否則客戶會發飆，大家就倒大楣了。然而，雖然專案可以遲交，但每項專案都有自己的 deadline，每遲交一天，都要繳給客戶額外的遲交補償金。

那麼，我們該如何規劃這些專案的 schedule？哪些專案先做、哪些後做？雖然遲交不可避免，有的同事天天熬夜加班，最後公司仍要繳給客戶高額補償金，但也有同事總是能幫公司省下許多補償金，是如何辦到的？

目標

為手上 N 個非做完不可的專案規劃好執行順序 (schedule)，使得最後給客戶的遲交補償金最少。

舉個例子

如圖，

4 個專案 A, B, C, D 的期限和每天的遲交補償金

今天 7/1，

專案A，耗時3天，期限7/4，每遲交一天罰9110元，

專案B，耗時2天，期限7/7，每遲交一天罰2913元，

專案C，耗時3天，期限7/8，每遲交一天罰2206元，

專案D，耗時1天，期限7/3，每遲交一天罰0422元。

三種排程 1, 2, 3

排程 1，專案 C 遲交 1 天，專案 D 遲交 7 天，補償金共：

2206元 * 1天 + 422元 * 7天 = 5160元。

排程2，只有一項，專案 A 遲交 6 天，補償金共：

9110元 * 6天 = 54660元。

排程3，專案 A 遲交 1 天，專案 C 遲交 2 天，補償金共：

9110元 * 1天 + 2206元 * 2天 = 13522元。

本例為方便理解，僅以四個專案來舉例，頭腦靈活一點的人，可直接窮舉四個專案的所有排序 (P四取四，共24種排序)，找到補償金最小的排序。但當專案數量稍多一點，排序方法就會暴增，例如五個專案有120種排序，六個專案有720種排序。數量越多，越難窮舉，除非已經財富自由，把上班當交朋友，不然實在不建議把時間揮霍在這種地方。

解題思路

一、簡化問題

觀察上圖可以發現，因為 A B C D 四個專案都要做完，所以不論何種排程，最後一天一定是 7/10。這題就可以簡化為，從最後一天7/10開始往前排，每次都找出補償金最小的專案排入行程表。

二、排程方法

簡化後變得很簡單，就直接演示一次了。

7/10，

若排入專案A，補償金為 9110元 * 6天 = 54660元，

若排入專案B，補償金為 2913元 * 3天 = 8739元，

若排入專案C，補償金為 2206元 * 2天 = 4412元，

若排入專案D，補償金為 422元 * 7天 = 2954元，

所以 7/10 排入專案D。

7/9，

若排入專案A，補償金為 9110元 * 5天 = 45550元，

若排入專案B，補償金為 2913元 * 2天 = 5826元，

若排入專案C，補償金為 2206元 * 1天 = 2206元，

所以 7/9 排入專案C。

再來從 7/6 繼續往前排

7/6，

若排入專案A，補償金為 9110元 * 2天 = 18220元，

若排入專案B，補償金為 2913元 * 0天 = 0元，

所以 7/6 排入專案B。

7/4，

排入最後一個，專案A，輕鬆完成。

補償金最小的排程

專案A 準時，專案B 準時，專案C 遲交 1 天，專案D 遲交 7 天，補償金共：

2206元 * 1天 + 422元 * 7天 = 5160元。

總結

化繁為簡，從最後一天開始往前排，每次都找出補償金最小的專案排入行程表。

延伸思考：如果像是這篇 混亂的約會行程，竟是學妹給的智力測驗！？ 裡的工具人JN 一樣，被要求某些專案要在某些專案前完成，(例如，B要在A之前、C要在要AD之前..)，可以怎麼排？

其實排法都差不多，有興趣的拿紙筆寫寫看就知道了。

附件

太累，有機會再補上解題程式碼..