Single Machine Scheduling - Shortest Processing Time

Shortest Processing Time (SPT) 是用來處理當任務被完成之前我們必須為之付出代價(Inventory Cost)。因此我們要盡早完成他們，也就是讓他們的Flow Time最小。

(Flow Time 為完成時間減去任務出現的時間。也就是Fi = Ci - ri, Fi as Flow time, Ci as Completion time, ri as release time.)

假設我們有任務:

Job	1	2	3	4	5
Process Time:	4	2	3	6	1

此時如果我們的Sequence是照著1-2-3-4-5
那麼Flow Time就會是Job1的完成時間+Job2的完成時間+.....Job5的完成時間
也就是 4 + (4+2) + (4+2+3) + (4+2+3+6) + (4+2+3+6+1) = 50

如果我們從最小的work time開始選擇(SPT) 也就是照著 5-2-3-1-4的順序
(SPT的概念就是擁有最短Process Time的先處理)
那麼Flow Time就會變成 1 +  (1+2) + (1+2+3) + (1+2+3+4) + (1+2+3+4+6) = 36
我們會發現整整少了50-36=14的Flow Time。
那麼要怎麼證明SPT出來的結果一定是最少Flow Time?
Process Time Pi < Pj
T(A) T(B)為前後Flow Time的總和 我們只看中間Pi Pj的部分:
假設 S1 是最佳解 
    T(A) + Pi + (Pi + Pj) + T(B)  
假設 S2 不是最佳解
    T(A) + Pj + (Pj + Pi) + T(B)
此時S1 S2的Flow Time差 S1 - S2 = Pi - Pj  < 0 ，由此可知必須將小的Pi放在前面。 

到這裡再重複一個觀念就是雖然不論用甚麼順序，總共的工作時間都是所有Process Time的總和。(因為只有一台機器 不管用甚麼順序 機器完成所有工作的時間都是固定的)
但是SPT要求的是最少的Flow Time，也就是任務出現後(上述假設任務同時出現)要盡可能早點完成。
比如說，今天有五個客人同時來點餐，雖然我們把五份餐點準備好的時間是固定的。此時Flow Time代表的卻是每一份單子被完成之前等待的時間，因此總Flow Time越短，也就代表客人等待的時間的加總越短。