# 排程理論和演算法

## Notations

### Fundamentals

在本文中， $n$ 都代表了工作總數，而 $m$ 代表了可供生產的機器總數。在談到特定工作或機器時，通常使用符號 $j$ 來代指工作、符號 $i$ 來代指機器。
- Processing time：通常使用 $p_{ij}$ 代表工作 $j$ 在機器 $i$ 上所需的工作時長。如果只有一台機器或對於所有機器時長都相同時，則可以省略寫為 $p_j$ 。
- Release date：通常使用 $r_j$ 代表最早可以開始工作 $j$ 的時間，也可以理解為工作 $j$ 到達排程系統的時間。
- Due date：通常使用 $d_j$ 代表工作 $j$ 的交期。
- Weight：通常使用 $w_j$ 代表工作 $j$ 的權重、重要性。舉例來說， $w_j$ 可能為工作 $j$ 的倉儲成本或者工作 $j$ 的訂單價值。

### Scheduling Problems

接下來介紹各類排程問題，通常會使用三元組 $\alpha\,|\,\beta\,|\,\gamma$ 來表示問題的類型。
- $\alpha$ 代表了工作的環境
- $\beta$ 代表了工作的特徵或者限制條件
- $\gamma$ 代表了最佳化的目標函數(objective function)

常見的 $\alpha$ 有以下選擇：
- Single machine (1)：最基礎的情況，也就是只有一台機器 $(m = 1)$ 。
- Identical parallel machines $\left(Pm\right)$ ：有 $m$ 台相同的機器可以同時運行。
- Parallel machines $\left(Qm\right)$ ：有 $m$ 台機器可以同時運行，但是每台機器處理工作的效率不同。
- Flow shops $\left(Fm\right)$ ：有 $m$ 台機器排成一列，所有工作都必須按照機器1、機器2，機器3···的順序處理一遍。通常使用First In First Out (FIFO) 原則來處理等待下一台機器的工作佇列。
- Flexible flow shops $\left(FFc\right)$ ：與Flow shops相似，只不過將工作變為 $c$ 個階段，每個階段 $\ell$ 都有 $m_\ell$ 台相同的機器。換句話說，每個階段都從Flow shops的single machine變為parallel machines。所有工作都必須依序經過這 $c$ 個階段的處理。
- Job shops $\left(Jm\right)$ ：有 $m$ 台機器且每個工作都有自己的處理順序。比如說，工作1需要依序在機器1、機器3上運行，而工作2需要依序在機器2、機器4上運行，諸如此類。
- Flexible job shops $\left(FJc\right)$ ：與Job shops相似，只不過變為考慮 $c$ 個工作站，每個工作站都有Identical parallel machines。每個工作都有各自前往不同工作站的處理順序。

常見的 $\beta$ 有以下選擇：
- Release dates $(r_j)$ ：代表每個工作都有Release date $(r_j)$ 。如果這個符號沒出現，則所有工作都可以在一開始時就處理。
- Preemptions $(prmp)$：代表可以在任意時刻打斷工作處理過程，也就是說可以在任意時刻打斷原工作將其閒置並換上新的工作進行處理。被打斷的工作進度並未消失，如果重新指派其開始工作，則會恢復原進度繼續處理。如果這個符號沒出現，則工作一旦開始後皆不可被打斷。
- Precedence constraints $(prec)$：代表工作間可能存在前置要求。比如說，需要先完成工作1及工作2後才能開始工作3。如果這個符號沒出現，則所有工作都沒有前置要求。
- Sequence dependent setup times $(s_{ijk})$ ：代表機器 $i$ 接續不同工作時需要準備時間。 $s_{ijk}$ 代表了機器 $i$ 上工作 $j$ 結束後接續工作 $k$ 前所需的準備時間。
- Permutation $(prmu)$ ：代表在Flow shops中，遵循First In First Out (FIFO)原則。
- Recirculation $(rcrc)$ ：代表在Job shops或Flexible job shops中，需要於特定機器或工作站重複處理兩次以上。

給定排程後，以 $C_{ij}$ 代表工作 $j$ 在機器 $i$ 上完工的時間、 $C_{j}$ 代表工作 $j$ 完成的時間(也就是工作 $j$ 在最後一台需要經過處理的機器上的完工時間)。目標函數為各工作完成時間 $(C_j)$ 的函數。
- Makespan $(C_{\text{max}})$ ：所有工作都完成所需的時間，也就是 $\max(C_1,C_2,...,C_n)$ 。此目標函數通常代表了是否充分運用了所有機器。
- Total weighted flow time $(\sum w_jC_j)$ ：所有工作完成時間的加權和。前面我們提到權重可能代表工作的倉儲成本，因此Total weighted flow time可以代表特定排程的總倉儲成本。

目標函數也可能同時與各工作的Due date有關。
- Lateness of job $j$ 定義為

$$L_j = C_j - d_j$$

- Tardiness of job $j$ 定義為

$$T_j = \max(0,L_j) = \max(0,C_j - d_j)$$

- Unit Penalty of job $j$ 定義為

$$U_j = \begin{cases}\,1\,\text{if}\, C_j > d_j\\ \,0\text{ otherwise.}\end{cases}$$

這兩個定義之間的差別為Lateness可能為負值而Tardiness永遠大於等於零。與Due date有關的目標函數為：
- Maximum Lateness $(L_{\text{max}})$ ：所有工作的最大Lateness，也就是 $\max(L_1,L_2,...,L_n)$ 。
- Total weighted Tardiness $(\sum w_jT_j)$ ：所有Tardiness的加權和。
- Weighted number of tardy jobs $(\sum w_jU_j)$ ：Unit Penalty的加權和，代表了經過加權後遲交的工作數量。

### Examples
1. $1\,|\,r_j,prmp\,|\,\sum w_jC_j$ 代表了具有Release date且可中斷的Single machine environment，目標函數為Total weighted flow time。
1. $Pm\,|\,r_j,prec\,|\,\sum w_jT_j$ 代表了具有Release date及前置要求的Identical parallel machines environment，目標函數為Total weighted Tardiness。
1. $Jm\,||\,C_{\text{max}}$ 代表了沒有要求 $(\beta$ 被省略 $)$ 的Job Shop，目標函數為Makespan。
1. 在半導體生產環境，可以使用 $FJc\,|\,r_j,s_{ijk},rcrc\,|\,\sum w_jT_j$ 作為模型。

## Complexity Hierarchy

上述介紹的模型中，有些模型是其他模型的特例，比如single machine是parallel machines的特殊情形、 $\sum C_j$ 是 $\sum w_jC_j$ 的特殊情形。在這種時候通常會用下列符號表示

$$\alpha\mid\beta\mid\sum C_j\quad\leqslant\quad\alpha\mid\beta\mid\sum w_jC_j$$

對於兩個問題 $A,B$ ， $A\leqslant B$ 基本上代表，如果存在能有效解決問題 $B$ 的演算法，則也可以有效解決問題 $A$ 。因此求解 $A$ 並不會比求解 $B$ 更困難。
如果以箭頭形式來表現，其中 $A$ 指向 $B$ 代表 $A\leqslant B$ ，對於不同的機器環境我們有下列難度比較：


對於不同的目標函數，也有下列比較：


## Single Machine

首先考慮最基礎的情形：Single machine，並以目標函數來分類各種情形。在很多情況下，排程問題會是NP-hard(或strongly NP-hard)，此時想找到一個好的演算法變得十分困難。
- 注意到對於單機問題來說，Makespan總是不變的，也就是所有工作所需的時間之和 $\sum_{j=1}^n p_j$

### Total Weighted Flow Time

#### Case 1. $1\,||\,\sum w_jC_j$

>[!TIP]Algorithm
>按照Weighted Shortest Processing Time (WSPT)排程為最佳解。

意即按照 $w_j/p_j$ 的比值大小由大至小的來安排工作順序。這點不難理解，如果一份工作重要性很高且所需時間不長，那麼自然應該優先處理這份工作；相反的，如果一份工作重要性很低且所需時間很長，那麼自然應該先閒置這份工作。

#### Case 2. $1\,|\,prec\,|\,\sum w_jC_j$

這裡考慮簡單點的形式，假設前置要求都是長鏈形式如

$$1\rightarrow 2\rightarrow\cdots\rightarrow k$$$$k+1\rightarrow k+2\rightarrow\cdots\rightarrow n$$

對於長鏈

$$1\rightarrow 2\rightarrow\cdots\rightarrow k$$

它有一個重要特徵 $\rho$ -factor，定義為

$$\rho(1,2,...,k) = \displaystyle\max_{1\leqslant\ell\leqslant k}\left(\frac{\sum_{j=1}^\ell w_j}{\sum_{j=1}^\ell p_j}\right)$$

其中最大值成立時的 $\ell$ 被稱作支配這個 $\rho$ -factor的工作。

>[!TIP]Algorithm
>每當機器空閒時，從所有的長鏈中找出 $\rho$ -factor最大的，並按照鏈上的順序安排工作直到安排完支配這個 $\rho$ -factor的工作。重複進行上述步驟直到所有工作完成。

#### Example
考慮下列七個工作的排程，其中前置要求為

$$1\rightarrow 2\rightarrow 3\rightarrow 4$$$$5\rightarrow 6\rightarrow 7$$

| jobs | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| $w_j$ | 6 | 18 | 12 | 8 | 8 | 17 | 18 |
| $p_j$ | 3 | 6 | 6 | 5 | 4 | 8 | 10 |

1. 一開始，第一條鏈的支配工作為 job 2、 $\rho$ -factor為
$$(6+18)/(3+6) = 24/9$$
第二條鏈的支配工作為 job 6、 $\rho$ -factor為
$$(8+17)/(4+8) = 25/12$$
由於24/9 > 25/12，安排 job 1和 job 2進入排程。
1. job 1和 job 2完成後，第一條鏈的支配工作變為 job 3、 $\rho$ -factor為2。由於25/12 > 2，安排 job 5和 job 6進入排程。
1. job 5和 job 6完成後，第二條鏈的支配工作變為 job 7、 $\rho$ -factor為18/10。由於2 > 18/10，安排 job 3進入排程。
1. job 3完成後，第一條鏈的支配工作變為 job 4、 $\rho$ -factor為8/5。由於18/10 > 8/5，安排 job 7進入排程。
1. 最後，安排 job 4進入排程。

因此，根據上述演算法所得出的最佳排程為


#### Case 3. $1\,|\,r_j,prmp\,|\,\sum C_j$

假設 $p_j(t)$ 代表時間 $t$ 時工作 $j$ 所需的剩餘時間。
>[!TIP]Algorithm
>按照Shortest Remaining Processing Time (SRPT)進行排程為最佳解。

假設工作 $j$ 正在處理中，當有新工作 $k$ 在時間點 $r_k$ 被釋出時，比較 $p_j(r_k)$ 和 $p_k(r_k)$ 之間的大小。
- 若 $p_j(r_k)$ 較小，則繼續處理工作 $j$ 。
- 若是 $p_k(r_k)$ 較小，則打斷工作 $j$ 並處理工作 $k$ 。

按照類似的思路，當考慮 $1\,|\,r_j,prmp\,|\,\sum w_jC_j$ 時，自然的會想利用WSPT進行排程：
- 將上述方法更改為比較 $w_j/p_j(r_k)$ 和 $w_k/p_k(r_k)$ 之間的大小。

可惜的是，利用WSPT進行排程得到的結果並不一定是最佳解。實際上， $1\,|\,r_j,prmp\,|\,\sum w_jC_j$ 的排程問題為NP-hard。

### Maximum Lateness

#### Case 1. $1\,||\,L_{\text{max}}\,$

>[!TIP]Algorithm
>按照Earliest Due Date (EDD)進行排程為最佳解。

意即按照Due Date的大小由小至大來安排工作順序。不難理解，為了避免遲交過久，自然會優先處理交期較近的工作。

#### Case 2. $1\,|\,prec\,|\,L_{\text{max}}$

>[!TIP]Algorithm
>按照EDD進行排程為最佳解。

在有Precedence constraints的排程中，能夠排在最後的工作只有那些沒有後繼者的工作，我們把這樣子的工作的集合叫做 $\mathcal{J}$ 。
1. 從 $\mathcal{J}$ 中選出Due Date最大的，將其排入排程後面。
1. 蒐集沒有還沒被排程的後繼者的工作，並以此更新 $\mathcal{J}$ 。
1. 重複執行上述步驟直到排程結束。

#### Example

| jobs | 1 | 2 | 3 | 4 |
| -------- | -------- | -------- | -------- | -------- |
| $p_j$ | 2 | 3 | 5 | 7 |
| $d_j$ | 3 | 10 | 8 | 12 |

其中前置要求為

$$1\rightarrow 2$$$$3\rightarrow 4$$

演算法步驟如下：
1. 一開始， $\mathcal{J} = \{2,4\}$ 。由於12 > 10，因此將 job 4排在最後。
1. 更新 $\mathcal{J}$ 為 $\{2,3\}$ 。
1. 由於10 > 8，因此將 job 2排在倒數第二個位置。
1. 更新 $\mathcal{J}$ 為 $\{1,3\}$ 。
1. 由於8 > 3，因此將 job 3排在倒數第三個位置，job 1因此被排在第一個位置。

因此，根據上述演算法所得出的最佳排程為


#### Case 3. $1\,|\,r_j, prmp\,|\,L_{\text{max}}$

>[!TIP]Algorithm
>按照Preemptive EDD進行排程為最佳解。

#### Example

| jobs | 1 | 2 |
| -------- | -------- | -------- |
| $p_j$ | 3 | 3 |
| $d_j$ | 5 | 4 |
| $r_j$ | 0 | 1 |

1. 一開始執行 job 1。
1. 當時間為1時，job 2釋出。此時若繼續執行 job 1，job 2會遲交

$$(3+3) - 4 = 2$$

此時若打斷 job 1改成執行 job 2，job 1會遲交

$$(3+3)-5 = 1$$

1. 因此，當 job 2釋出，打斷 job 1改成執行 job 2，之後再重新執行 job 1。

#### Case 4. $1\,|\,r_j\,|\,L_{\text{max}}$

雖然 $1\,|\,r_j\,|\,L_{\text{max}}$ 是strongly NP-hard，但由於他在解決flow shop和job shop的排程時常常出現，因此我們還是得想辦法解決此問題。

>[!TIP]Algorithm
>利用Branch-and-Bound找出最佳解。

#### Branching Rule

在每一層中，假設 $\mathcal{J}$ 代表還沒被排程的工作、 $t$ 代表工作即將開始的時間點。那麼下一個被安排的工作 $j$ 應當滿足

$$r_j < \min_{k\in\mathcal{J}}\left(\max(t,r_k) + p_k\right)$$

不難看出，如果 $j$ 並不滿足上述式子，則可以先將最小化不等式右邊的工作塞入排程中，而不會延誤到工作 $j$ 。

#### Lower Bound

在每一層中，可以對還未排程的工作執行Preemptive EDD來得到下界。如果得出的排程恰好是nonpreemptive，那麼就可以排除大於這個下界的所有分支。

#### Example

考慮下列例子：

| jobs | 1 | 2 | 3 | 4 |
| -------- | -------- | -------- | -------- | -------- |
| $p_j$ | 4 | 2 | 6 | 5 |
| $d_j$ | 8 | 12 | 11 | 10 |
| $r_j$ | 0 | 1 | 3 | 5

- 在第一層中，有四個分支

$$(1,*,*,*),\,(2,*,*,*),\,(3,*,*,*),\,(4,*,*,*)$$

根據Branching Rule，可以輕鬆排除 $(3,*,*,*)$ 和 $(4,*,*,*)$ ：
- 如果先執行 job 2，那麼等到執行完後依然可以無縫銜接上 job 3。
- 如果先執行 job 1，那麼等到執行完後依然可以無縫銜接上 job 4。
- 根據Preemptive EDD：
- 分支 $(1,*,*,*)$ 執行結果為：在時間區間[0,4]執行 job 1，[4,5]執行 job 3，[5,10]執行 job 4，[10,15]執行 job 3，[15,17]執行 job 2。下界為 $L_{\text{max}} = 5$ 。
- 分支 $(2,*,*,*)$ 執行結果為：在時間區間[1,3]執行 job 2，[3,5]執行 job 1，[5,10]執行 job 4，[10,12]執行 job 1，[12,18]執行 job 3。下界為 $L_{\text{max}} = 7$ 。
- 在第二層中， $(1,*,*,*)$ 有三個分支 $(1,2,*,*),\,(1,3,*,*),\,(1,4,*,*)$ 。
- 根據Preemptive EDD：
- 分支 $(1,3,*,*)$ 執行結果為：在時間區間[0,4]執行 job 1，[4,10]執行 job 3，[10,15]執行 job 4，[15,17]執行 job 2。下界為 $L_{\text{max}} = 5$ ，與上一層的下界相同。此下界小於 $(2,*,*,*)$ 的下界7且排程為nonpreemptive，因此為最佳解。


#### Case 5. $1\,|\,r_j,prec\,|\,L_{\text{max}}$

此情形也可用Branch-and-Bound解決，甚至更加容易，因為precedence constraints可以幫助我們迅速排除許多分支。

### Number of Tardy Jobs

#### Case 1. $1\,||\,\sum U_j$

演算法的想法很簡單，將所有工作分為兩種類型：能在期限內完成的，和無法在期限內完成的。對於第一種類型的工作，使用EDD進行排程，而第二種類型的排程順序並不重要。

>[!TIP]Algorithm
>首先，重新編號工作使得 $d_j$ 變為由小到大排序，也就是 $d_1\leqslant d_2\leqslant\cdots\leqslant d_n$ 。
>1. 初始化 $\mathcal{S} = \emptyset,\,\mathcal{J} = \emptyset,\, k = 1$
>1. 將工作 $k$ 加入 $\mathcal{S}$
>1. 如果
$$\sum_{j\in \mathcal{S}}p_j\leqslant d_k$$
就前往下一步驟，否則就從 $\mathcal{S}$ 中去除所需工時最長的工作，並將其加入 $\mathcal{J}$ 。
>1. 若 $k = n$ ，則結束演算法，此時 $\mathcal{S}$ 就是那些能在期限內完成的工作， $\mathcal{J}$ 就是那些無法在期限內完成的工作。
若 $k < n$ ，更新 $k \leftarrow k + 1$，並回到第二步。

#### Example

考慮下列例子：

| jobs | 1 | 2 | 3 | 4 |
| -------- | -------- | -------- | -------- | -------- |
| $p_j$ | 7 | 8 | 4 | 6 |
| $d_j$ | 9 | 17 | 18 | 19 |

首先注意到 $d_j$ 已由小到大排序。演算法步驟如下：
:::spoiler 詳細步驟
1. 初始化 $\mathcal{S} = \emptyset,\,\mathcal{J} = \emptyset,\, k = 1$
1. 將工作 1 加入 $\mathcal{S}$ ，此時 $\mathcal{S} = [1]$
1. $p_1 = 7 < 9 = d_1$
1. 更新 $k = 2$
1. 將工作 2 加入 $\mathcal{S}$ ，此時 $\mathcal{S} = [1,2]$
1. $p_1 + p_2 = 7 + 8 = 15 < 17 = d_2$
1. 更新 $k = 3$
1. 將工作 3 加入 $\mathcal{S}$ ，此時 $\mathcal{S} = [1,2,3]$
1. $p_1 + p_2 + p_3 = 7 + 8 + 4 = 19 > 18 = d_2$ ，因此從 $\mathcal{S}$ 中去除工作2，並將其加入 $\mathcal{J}$ 。此時 $\mathcal{S} = [1,3],\,\mathcal{J} = [2]$
1. 更新 $k = 4$
1. 將工作 4 加入 $\mathcal{S}$ ，此時 $\mathcal{S} = [1,3,4]$
1. $p_1 + p_3 + p_4 = 7 + 4 + 6 = 17 < 19 = d_4$
1. 結束演算法。輸出 $\mathcal{S} = [1,3,4],\,\mathcal{J} = [2]$
:::

因此遲交工作數為1，且最佳排程為


### Total Weighted Tardiness

#### Case 1. $1\,||\,\sum w_jT_j$

如果權重皆相同，可以考慮Minimum Slack (MS)：
- 以 $\max(d_j-p_j-t, 0)$ 的大小由小到大安排工作。

注意到這個方法與之前不同，是與當前的時間有關的。因此，可能在開始時 $(t=0)\,j$ 比 $k$ 順位更高，但在中途轉變為具有相同的順位。
當權重不同時，可以結合WSPT和MS方法，例如Apparent Tardiness Cost (ATC)。

>[!TIP]Heuristic Algorithm
>ATC步驟如下：
>1. 令 $t$ 為機器空閒的時間點。對於還未被排程的工作，計算Ranking index：
$$I_j(t) = \frac{w_j}{p_j}\exp\left(-\frac{\max(d_j-p_j-t, 0)}{K\bar{p}}\right)$$
其中 $\bar{p}$ 為所剩工作的平均時長、$K$ 為參數。
>1. 將Ranking index最大的工作排入排程。
>1. 重複進行上述步驟直到排程完畢。

#### Case 2. $1\,|\,s_{jk}\,|\,\sum w_jT_j$

>[!TIP]Heuristic Algorithm
>與上面的方法相似，使用Apparent Tardiness Cost with Setups (ATCS)，步驟如下：
>1. 令 $t$ 為機器空閒的時間點。假設機器剛剛完成了工作 $j$ ，對於尚未完成的工作 $k$，計算Ranking index：
$$I_k(t,j) = \frac{w_k}{p_k}\exp\left(-\frac{\max(d_k-p_k-t, 0)}{K_1\bar{p}}\right)\exp\left(-\frac{s_{jk}}{K_2\bar{s}}\right)$$
其中 $\bar{p}$ 為所剩工作的平均時長、 $\bar{s}$ 為所剩工作的平均setup時長、 $K_1,K_2$ 為參數。
>1. 將Ranking index最大的工作排入排程。
>1. 重複進行上述步驟直到排程完畢。

## Parallel Machines

### Makespan

#### Case 1. $Pm\,||\,C_{\text{max}}$

由於明顯的

$$C_{\text{max}} \geqslant \frac{1}{m}\sum_{i=1}^n p_i$$

若要最小化makespan，重點就是將工作依照所需時間盡可能平均分配給各機台，使得每個機台的總處理時長相同。
由此想法，自然的會有下列演算法(LPT)：

>[!TIP]Heuristic Algorithm
>使用Longest Processing Time (LPT)，也就是說，將工作以時長大小排序，由大到小派發工作給目前空閒的機器。

雖然此方法並不見得能夠得到最佳解，但是可以證明

$$\frac{C_{\text{max}}(LPT)}{C_{\text{max}}(OPT)}\leqslant\frac{4}{3} - \frac{1}{3m}$$

其中 $C_{\text{max}}(LPT)$ 代表LPT的Makespan、 $C_{\text{max}}(OPT)$ 代表最佳解的Makespan。
因此，當 $m$ 很大時，LPT得出的結果大致上不會比最佳結果的4/3倍還糟糕。

#### Example

考慮 $m = 4$ 和

| jobs | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| $p_j$ | 7 | 7 | 6 | 6 | 5 | 5 | 4 | 4 | 4 |

||
| -------- |
|根據LPT所得的工作排程，Makespan為15|

||
| -------- |
|最佳工作排程，Makespan為12|

此時

$$\frac{C_{\text{max}}(LPT)}{C_{\text{max}}(OPT)} = \frac{15}{12} = \frac{4}{3} - \frac{1}{3\times 4}$$

#### Case 2. $Pm\,|\,r_j\,|\,C_{\text{max}}$

>[!TIP]Heuristic Algorithm
>使用Longest Processing Time (LPT)，可得結果
$$\frac{C_{\text{max}}(LPT)}{C_{\text{max}}(OPT)}\leqslant\frac{3}{2}$$

#### Case 3. $Pm\,|\,prec\,|\,C_{\text{max}}$

>[!TIP]Heuristic Algorithm
> Critical Path (CP) and Largest Number of Successors' Processing Times (LNSPT)
> 1. CP：對潛在候選工作沿著前置要求的長鏈計算長鏈中所有工作時數的總和，並指派總和最大的工作。
> 1. LNSPT：對潛在候選工作的所有後繼者計算工作時數的總和，並指派總和最大的工作。

#### Example

假設 $m = 2,\,n = 6$ ，且所有工作所需時數皆為1。前置要求為：


一開始可指派的工作有 1,4,6。

1. CP：
- 根據計算，$1\rightarrow 2\rightarrow 3$ 的長鏈上工作時數總和為最大(1+1+1 = 3)。首先指派1至機器1。之後指派4或6至機器2都可以。
- 根據CP原則，Makespan為3、排程為：


1. LNSPT：
- 根據計算，4,6的後繼者工作時數總和為最大(1+1 = 2)。首先指派4和6。
- 根據LNSPT原則，Makespan為4、排程為：


#### Case 4. $Pm\,|\,prmp\,|\,C_{\text{max}}$

可以將工作重新編號後使得 $p_1\geqslant p_2\geqslant\cdots\geqslant p_n$。

令 $C_{\text{max}}^* = \max\left(p_1,\frac{1}{m}\sum p_j\right)$ 。不難看出，我們有下界 $C_{\text{max}}\geqslant C_{\text{max}}^*$ 。

>[!TIP]Algorithm
> 1. 若將所有工作都分配到同一台機器上，Makespan即為所有工作時數的總和，因此
$$C_{\text{max}} = \sum_{j=1}^n p_j\leqslant mC_{\text{max}}^*$$
> 1. 把此單機排程依照時間分為 $m$ 個部分，也就是
$$[0, C_{\text{max}}^*],\, [C_{\text{max}}^*, 2C_{\text{max}}^*],\cdots,[(m-1)C_{\text{max}}^*, mC_{\text{max}}^*]$$
並將第一個區間的工作分配給機器1，第二個區間的工作分配給機器2，以此類推。
> 1. 如此一來，每個機台的完工時間都不大於 $C_{\text{max}}^*$ 。因此這個排程的Makespan滿足
$$C_{\text{max}}\leqslant C_{\text{max}}^*$$
但同時我們知道 $C_{\text{max}}\geqslant C_{\text{max}}^*$ ，因此等號成立且此排程為最佳排程。

### Total Weighted Flow Time

#### Case 1. $Pm\,||\,\sum C_j$

在之前單機的條件下，WSPT是最佳解。若權重全為1，在此情況下，實際上可以利用相似的推論證明Shortest Processing Time (SPT)是最佳解。
>[!TIP]Algorithm
>按照Shortest Processing Time (SPT)排程為最佳解。

#### Case 2. $Pm\,||\,\sum w_jC_j$

在一般情況下，WSPT並不見得會是最佳解。

#### Example

考慮 $m = 2,\,\varepsilon > 0$ ，和

| jobs | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- |
| $p_j$ | 1 | 1 | 3 |
| $w_j$ | $1+\varepsilon$ | $1+\varepsilon$ | 3 |

根據WSPT，先排入 job 1和 job 2。之後再排入 job 3。此時目標函數為

$$(1+\varepsilon)\times 1 + (1+\varepsilon)\times 1 + 3\times 4 = 12 + 2(1+\varepsilon)$$

而若是先排入 job 3和 job 1。之後再排入 job 2。此時目標函數為

$$3\times 3 + (1+\varepsilon)\times 1 + (1+\varepsilon)\times 2 = 9 + 3(1+\varepsilon)$$

由上可知，當 $\varepsilon$ 足夠小時，WSPT並非最佳解。

- 雖然WSPT並不見得能夠得到最佳解，但是可以證明

$$\frac{\sum w_jC_j(WSPT)}{\sum w_jC_j(OPT)} < \frac{1+\sqrt{2}}{2}$$

#### Case 3. $Qm\,||\,\sum C_j$

首先觀察到，如果工作 $j$ 被安排到機器 $i$ ，且工作 $j$ 之後還有 $k-1$ 個工作要在機器 $i$ 上運行，那麼工作 $j$ 對目標函數的貢獻為 $kp_{ij}$ (因為工作 $j$ 本身耗時 $p_{ij}$，而工作 $j$ 之後的 $k-1$ 個工作必須等待工作 $j$ 完工後才能開始)。
令

$$x_{ikj} = \begin{cases}1\quad\text{if job $j$ is scheduled as the $k$-th to last job on machine $i$,}\\ 0\quad\text{Otherwise.}\end{cases}$$

我們可以用整數規劃的形式來描述這個問題。

\begin{align}
&\min\sum_{i=1}^m\sum_{j=1}^n\sum_{k=1}^n kp_{ij}x_{ikj}\\
\text{subject to}\\
&\sum_{i=1}^m\sum_{k=1}^n x_{ikj} = 1, \,j = 1,2,...,n\\
&\sum_{j=1}^n x_{ikj} \leqslant 1,\,i = 1,2,...,m,\,k = 1,2,...,n\\
&x_{ikj}\in\{0,1\},\,i = 1,2,...,m,\,k = 1,2,...,n,\,j = 1,2,...,n
\end{align}

根據Network Flow相關理論，可以將上述整數規劃放寬為線性規劃 $(x_{ikj}\geqslant 0)$ 而不影響可行解。因此，並不需要真的去解這個整數規劃，而是利用Simplex Method等方法去解線性規劃，最佳解自然會滿足整數條件。

#### Case 4. $Pm\,|\,prmp\,|\,\sum C_j$

>[!TIP]Algorithm
>Nonpreemptive SPT排程仍為最佳解。

## Flow Shops

### Makespan

#### Case 1. $F2\,||\,C_{\text{max}}$

>[!TIP]Algorithm
>Johnson’s rule排程為最佳解。

對於工作 $j$ ，將其分為兩類：
1. 若 $p_{1j} < p_{2j}$ ，則 $j$ 為第一類。
1. 若 $p_{1j} > p_{2j}$ ，則 $j$ 為第二類。
1. 若 $p_{1j} = p_{2j}$ ，則 $j$ 為第一類或第二類都無所謂。

Johnson’s rule的步驟如下：
1. 將第一類中的工作依照所需時長由小到大排程。
1. 緊接在第一類後面將第二類中的工作依照所需時長由大到小排程。

#### Case 2. $Fm\,|\,prmu\,|\,C_{\text{max}}$

>[!TIP]Heuristic Algorithm
> 將工作 $j$ 的斜率定義為
$$s_j = -\sum_{i=1}^m\left(m - (2i-1)\right)p_{ij}$$
將斜率由大到小的安排工作。

從Johnson’s rule可看出，在第一台機器所需時長較短、在第二台機器所需時長較長的工作會被安排至流水線靠前的位置；而在第一台機器所需時長較長、在第二台機器所需時長較短的工作會被安排至流水線靠後的位置。

根據上面所給出的斜率定義，當工作在上游的機台所需時長較短、在下游的機台所需時長較長時，斜率較大；當工作在上游的機台所需時長較長、在下游的機台所需時長較短時，斜率較小。因此模仿Johnson’s rule將斜率較大者優先安排，斜率較小者延後安排。

實際上，存在多項式時間的近似演算法：
>[!TIP]Approximation Algorithm
> 存在多項式時間 $O(n^2m^2)$ 的演算法使得
>
> $$C_{\text{max}}(Approximation)\leqslant C_{\text{max}}^* + m(m-1)p_{\text{max}}$$
>
> 其中 $C_{\text{max}}^*$ 代表 $Fm\,||\,C_{\text{max}}$ 的最佳解、 $p_{\text{max}} = \max_{ij} p_{ij}$ 。

細節可參考[範例](#Coding-Example)及[[2]](#Reference)。

#### Case 3. $Fm\,|\,prmu,p_{ij} = p_j\,|\,C_{\text{max}}$

>[!TIP]Note
> 與單機時相似，Makespan為一固定常數而與排程無關
>
> $$C_{\text{max}} = \sum_{j=1}^np_j + (m-1)\max(p_1,...,p_n)$$

### Total Weighted Flow Time

#### Case 1. $Fm\,|\,prmu,p_{ij} = p_j\,|\,\sum C_j$

>[!TIP] Algorithm
> 適用於 $1\,||\,\sum C_j$ 的演算法同樣適用於 $Fm\,|\,prmu,p_{ij} = p_j\,|\,\sum C_j$

#### Case 2. $Fm\,|\,prmu,p_{ij} = p_j\,|\,\sum w_jC_j$

>[!TIP] Algorithm
> 按照Weighted Shortest Processing Time with Minimum Cost Insertion (WSPT-MCI)為最佳排程。
>1. 依照WSPT重新編號工作，也就是 $w_1/p_1\geqslant w_2/p_2\geqslant\cdots\geqslant w_n/p_n$
>1. 初始化 $\mathcal{S} = [1], \,k = 2$
>1. 將工作 $k$ 插入 $\mathcal{S}$ 中使得目標函數的增加量為最小，如果有不止一種選擇的話，將其插入位置最靠後的那個選擇。
>1. 更新 $k\leftarrow k + 1$
>1. 若 $k\leqslant n$ ，則回到第三步，否則結束演算法。

### Maximum Lateness

#### Case 1. $Fm\,|\,prmu,p_{ij} = p_j\,|\,L_{\text{max}}$

>[!TIP] Algorithm
> 適用於 $1\,||\, L_{\text{max}}$ 的演算法同樣適用於 $Fm\,|\,prmu,p_{ij} = p_j\,|\,L_{\text{max}}$

### Number of Tardy Jobs

#### Case 1. $Fm\,|\,prmu,p_{ij} = p_j\,|\,\sum U_j$

>[!TIP] Algorithm
> 適用於 $1\,||\,\sum U_j$ 的演算法同樣適用於 $Fm\,|\,prmu,p_{ij} = p_j\,|\,\sum U_j$

### Flow Shops with Reentry

考慮所有工作都必須重複處理 $N$ 個迴圈，也就是說，每當工作在最後一台機器處理完後，必須回到第一台機器重新開始處理，直到處理完 $N$ 圈為止。
假設工作 $j$ 在第 $\ell$ 圈時，在第 $i$ 台機器的處理時間只與 $j,\ell$ 有關且為

$$p_{ij\ell} = p_j + q_\ell,\,q_\ell\geqslant 0$$

在考慮重新進入迴圈的工作順序時，一個最自然的想法為：Loopwise Cyclic sequence (LC sequence)，代表維持原本工作的處理順序，依序執行各個迴圈。
- 在第 $\ell$ 圈進入第一台機器的工作順序和在第 $\ell - 1$ 圈離開最後一台機器的工作順序相同。

#### Case 1. $Fm\,|\,prmu,p_{ij\ell} = p_j\,|\,C_{\text{max}}$

這情形也就是對於 $\ell = 1,2,...,N$ ， $q_\ell = 0$ 。

>[!TIP]Note
> 任何 LC sequence 皆可以最小化 Makespan。

#### Case 2. $Fm\,|\,prmu,p_{ij\ell} = p_j + q_\ell\,|\,C_{\text{max}}$

>[!TIP] Algorithm
> 若 $q_\ell$ 為遞增，則按照LC-SPT為最佳解；若 $q_\ell$ 為遞減，則按照LC-LPT為最佳解。

### Flexible Flow Shops

假設工作 $j$ 在第 $\ell$ 個階段的所需時間為 $p_{\ell j}$ 。

#### Case 1. $FFc\,|\,prmu,p_{\ell j} = p_j\,|\,\sum C_j$

>[!TIP] Algorithm
> 如果每個階段的機器數量 $m_\ell$ 皆相同，則SPT排程為最佳解。

## Job Shops

### Makespan

#### Case 1. $J2\,||\,C_{\text{max}}$

在此情況下，可以將工作分為兩類：
1. 需要先在機器1上處理，之後再到機器2上處理。
1. 需要先在機器2上處理，之後再到機器1上處理。

對於第一類來說，可以看成是流水線順序依序為機器1、機器2的 $F2\,||\,C_{\text{max}}$ ；而對於第二類來說，可以看成是流水線順序依序為機器2、機器1的 $F2\,||\,C_{\text{max}}$ 。因此可以分別使用Johnson’s rule得到兩個最佳排程，並將其二者結合為最佳排程。

#### Case 1. $Jm\,||\,C_{\text{max}}$

為了方便描述，我們引入圖論中的術語並將此問題轉換為一張圖(Disjunctive graph)上的問題。
考慮以下 $N$ 個點的有向圖 $G$ ：
1. 圖 $G$ 的頂點包含所有必須處理的工作組的集合，形如 $(i,j)$ ，其中 $j$ 代表工作、 $i$ 代表處理的機器。除此之外，還有兩個dummy Node：Source和Sink分別代表起點和終點。
1. 圖 $G$ 的邊由兩種邊構成：
- Conjunctive edge：若工作 $j$ 必須先在機器 $i$ 處理完後才能在機器 $k$ 處理，則存在有向邊

$$(i,j)\longrightarrow (k,j)$$

- Disjunctive edge：若工作 $j,k$ 需在同一台機器 $i$ 上處理，則存在雙向邊

$$(i,j)\longleftrightarrow (i,k)$$

在選擇排程時，就與挑選兩個方向中的其中一個方向等價。必須注意，在排程時不能讓圖中出現迴圈否則會使排程變得不可行。
1. 圖 $G$ 的邊的距離由決定此條邊的工作之時長決定。舉例來說，由 $(i,j)$ 出發的有向邊的長度為 $p_{ij}$ 。另外，從起點出發的邊的距離皆為零。
1. Job shops的makespan即由圖中起點到終點的最長路徑距離來決定。

|  |
| -------- |
| Directed graph for job shop with makespan as objective. |

>[!TIP]Heuristic Algorithm
>Shifting Bottleneck演算法步驟如下：
>1. 令 $M$ 代表所有機器的集合、 $G$ 為去掉所有disjunctive edges的圖、 $C_{\text{max}}(G)$ 代表 $G$ 上從起點的終點的最長路徑。 初始化 $M_0 = \emptyset$ 。
>1. 對於所有 $i\in M\setminus M_0$ ，考慮單機問題 $1\,|\,r_j\,|\,L_{\text{max}}$ 。
> - $r_j$ 為 $G$ 中起點到 $(i,j)$ 的最長路徑長。
> - $d_j$ 為 $C_{\text{max}}(G)$ 減去 $G$ 中 $(i,j)$ 到終點的最長路徑長，再加上 $p_{ij}$ 。
> - 根據上述設定，最小化 $L_{\text{max}}$ 。假設 $L_{\text{max}}(i)$ 代表對應機器 $i$ 的最佳解。
>1. 找出bottleneck $k$ 滿足
>
> $$L_{\text{max}}(k) = \max_{i\in M\setminus M_0}L_{\text{max}}(i)$$
>
> 並根據上一步驟時求出的解，將 $k$ 上的工作進行排程。
>1. 按照 $k$ 的排程將對應的disjunctive edges加入 $G$ ，以及將 $k$ 加入$M_0$ 。
>1. 對於先前排程過的機器 $i\in M_0\setminus \{k\}$ ，必須考慮新加入的邊有沒有可能縮短 $i$ 的工作時數。因此，將 $i$ 所對應的disjunctive edges暫時去除，並按照與步驟2相同的方法計算出 $L_{\text{max}}(i)$ ，並將對應的disjunctive edges重新加入 $G$ 。
>1. 若 $M_0 = M$ 則結束演算法，否則回到步驟2。

#### Example 1.

考慮 $n=3,M=[1,2,3,4]$ 及

| jobs | machine sequence | processing times |
| -------- | -------- | -------- |
| 1 | $1\rightarrow 2\rightarrow 3$ | $p_{11}=10,\,p_{21}=8,\,p_{31}=4$ |
| 2 | $2\rightarrow 1\rightarrow 4\rightarrow 3$ | $p_{22}=8,\,p_{12}=3,\,p_{42}=5,\,p_{32}=6$|
| 3 | $1\rightarrow 2\rightarrow 4$ | $p_{13}=4,\,p_{23}=7,\,p_{43}=3$ |

|  |
| -------- |
| 初始圖 $G$ |

- Iteration 1：
1. 從圖中可看出，沿著上方第一條路徑或中間的第二條路徑都是最長路徑，因此

$$C_{\text{max}}(G) = 10+8+4=8+3+5+6=22$$

1. 接著對 $M\setminus M_0$ 考慮 $1\,|\,r_j\,|\,L_{\text{max}}$ 問題：
- 機器1：

| jobs | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- |
| $p_{1j}$ | 10 | 3 | 4 |
| $r_{1j}$ | 0 | 8 | 0 |
| $d_{1j}$ | 10 | 11 | 12 |

最佳排程為 $1\rightarrow 2\rightarrow 3$，$L_{\text{max}}(1) = 5$ 。
- 機器2：

| jobs | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- |
| $p_{2j}$ | 8 | 8 | 7 |
| $r_{2j}$ | 10 | 0 | 4 |
| $d_{2j}$ | 18 | 8 | 19 |

最佳排程為 $2\rightarrow 3\rightarrow 1$，$L_{\text{max}}(2) = 5$ 。
- 機器3：

| jobs | 1 | 2 |
| -------- | -------- | -------- |
| $p_{3j}$ | 4 | 6 |
| $r_{3j}$ | 18 | 16 |
| $d_{3j}$ | 22 | 22 |

最佳排程為 $2\rightarrow 1$，$L_{\text{max}}(3) = 4$ 。
- 機器4：

| jobs | 2 | 3 |
| -------- | -------- | -------- |
| $p_{4j}$ | 5 | 3 |
| $r_{4j}$ | 11 | 11 |
| $d_{4j}$ | 16 | 22 |

最佳排程為 $2\rightarrow 3$，$L_{\text{max}}(4) = 0$ 。
1. 從上述結果可知，機器1和機器2為bottleneck。任選兩者中其中一個，不妨假設選擇機器1為bottleneck。此時

$$M_0 = [1],\,C_{\text{max}}(G) = 22 + L_{\text{max}}(1) = 22 + 5 = 27$$

||
| -------- |
| 將機器1上的排程所對應的disjunctive edges加入 $G$ 後的圖 |
- Iteration 2：
1. 最長路徑為
$$S\rightarrow (1,1)\rightarrow (1,2)\rightarrow (1,3)\rightarrow (2,3)\rightarrow (4,3)\rightarrow T$$

1. 對 $M\setminus M_0$ 考慮 $1\,|\,r_j\,|\,L_{\text{max}}$ 問題：
- 機器2：

| jobs | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- |
| $p_{2j}$ | 8 | 8 | 7 |
| $r_{2j}$ | 10 | 0 | 17 |
| $d_{2j}$ | 23 | 10 | 24 |

最佳排程為 $2\rightarrow 1\rightarrow 3$，$L_{\text{max}}(2) = 1$ 。
- 機器3：

| jobs | 1 | 2 |
| -------- | -------- | -------- |
| $p_{3j}$ | 4 | 6 |
| $r_{3j}$ | 18 | 18 |
| $d_{3j}$ | 27 | 27 |

兩種排程皆為最佳排程， $L_{\text{max}}(3) = 1$ 。
- 機器4：

| jobs | 2 | 3 |
| -------- | -------- | -------- |
| $p_{4j}$ | 5 | 3 |
| $r_{4j}$ | 13 | 24 |
| $d_{4j}$ | 21 | 27 |

最佳排程為 $2\rightarrow 3$ ， $L_{\text{max}}(4) = 0$ 。
1. 從上述結果可知，機器2和機器3為bottleneck。任選兩者中其中一個，不妨假設選擇機器2為bottleneck。此時

$$M_0 = [1,2],\,C_{\text{max}}(G) = 27 + L_{\text{max}}(2) = 27 + 1 = 28$$

1. 將機器1所對應的disjunctive edges去除後重新計算，發現這並不會影響到makespan。
- Iteration 3：
1. 最長路徑為

$$S\rightarrow (1,1)\rightarrow (2,1)\rightarrow (2,3)\rightarrow (4,3)\rightarrow T$$

1. 對 $M\setminus M_0$ 考慮 $1\,|\,r_j\,|\,L_{\text{max}}$ 問題：
- 機器3：

| jobs | 1 | 2 |
| -------- | -------- | -------- |
| $p_{3j}$ | 4 | 6 |
| $r_{3j}$ | 18 | 18 |
| $d_{3j}$ | 28 | 28 |

兩種排程皆為最佳排程， $L_{\text{max}}(3) = 0$ 。
- 機器4：

| jobs | 2 | 3 |
| -------- | -------- | -------- |
| $p_{4j}$ | 5 | 3 |
| $r_{4j}$ | 13 | 24 |
| $d_{4j}$ | 22 | 28 |

最佳排程為 $2\rightarrow 3$，$L_{\text{max}}(4) = 0$ 。
1. 因為Maximum Lateness皆為零，因此機器3和4都不算是bottleneck。
- 由此得出最終排程的處理順序為機器1、機器2、機器3、機器4，Makespan為28。各機器的排程如下：
- 機器1： $1\rightarrow 2\rightarrow 3$
- 機器2： $2\rightarrow 1\rightarrow 3$
- 機器3： $1\rightarrow 2$
- 機器4： $2\rightarrow 3$

#### Example 2.

考慮 $n=4,\,M=[1,2,3]$ 及

| jobs | machine sequence | processing times |
| -------- | -------- | -------- |
| 1 | $1\rightarrow 2$ | $p_{11}=1,\,p_{21}=1$ |
| 2 | $2\rightarrow 1$ | $p_{22}=1,\,p_{12}=1$|
| 3 | $3$ | $p_{33} = 4$ |
| 4 | $3$ | $p_{34} = 4$ |

- Iteration 1：根據計算結果，首先安排機器3及加入邊 $(3,4)\rightarrow (3,3)$ 。
- Iteration 2：根據計算結果，安排機器1及加入邊 $(1,2)\rightarrow (1,1)$ 。
- Iteration 3：若根據計算結果，安排機器2及加入邊 $(2,1)\rightarrow (2,2)$ ，則圖 $G$ 中出現了迴圈。因此必須加上額外要求來避免此情況。在圖中可看到Iteration 2時存在長度為3的 $(2,2)$ 到 $(2,1)$ 的路徑

$$(2,2)\rightarrow (1,2)\rightarrow (1,1)\rightarrow (2,1)$$

因此，在Iteration 2完成後，我們加上以下條件：$(2,2)$ 必須先於 $(2,1)$ ，且 $(2,2)$ 完成後必須等待兩個單位的時間後才能開始 $(2,1)$ 。

|  |
| -------- |
| Iteration 2 和 Iteration 3時的圖 $G$ |
- 加上條件後，Iteration 3就能產出沒有迴圈的可行解。

### Total Weighted Tardiness

#### Case 1. $Jm\,||\,\sum w_jT_j$

之前考慮makespan時，由於只需要關注最後一個完成的工作，因此終點只有一個點。但是對於Total Weighted Tardiness，每個工作的完成時間點都對目標函數有影響，因此終點變為與工作數相同數量。

|  |
| -------- |
| Directed graph for job shop with total weighted tardiness as objective.|

Shifting Bottleneck演算法的步驟與之前相似，只不過每次需要考慮的單機問題不再是 $1\,|\,r_j\,|\,L_{\text{max}}$ 。

- 給定 $i,j,k$ 。假設現在要為機器 $i$ 排程，排入每個 $(i,j)$ 時皆有可能影響到目前已排程的機器中工作 $k$ 的完成時間 $C_k$ 。若要避免增加 $C_k$ ，則 $(i,j)$ 必須在某個給定的due date $d_{ij}^k$ 前完成。
- 如果圖中不存在 $(i,j)$ 到 $V_k$ 的道路，那麼 $(i,j)$ 甚麼時候完成皆不會影響到 $C_k$ ，因此 $d_{ij}^k = \infty$ ；如果圖中存在 $(i,j)$ 到 $V_k$ 的道路，令 $\mathcal{L}((i,j),k)$ 代表其中最長路徑的長度，此時

$$d_{ij}^k = \max(C_k, d_k) - \mathcal{L}((i,j),k) + p_{ij}$$

- 若是 $(i,j)$ 完成的時間 $C_{ij} > d_{ij}^k$ ，則目標函數會至少增加 $C_{ij} - d_{ij}^k$ 。
- 令 $T_{ij}^k = \max(C_{ij} - d_{ij}^k\,,\,0)$ 代表 $(i,j)$ 對於 $k$ 的tardiness。在考慮 $(i,j)$ 對其他工作的影響時，自然必須考慮所有工作。 $(i,j)$ 所貢獻的total weighted tardiness為：

$$h_{ij}(C_{ij}) = \sum_{k=1}^n w_kT_{ij}^k$$

同理，在考慮機器 $i$ 造成的total tardiness時，必須考慮所有可能的操作 $(i,j)$ 。因此考慮

$$h_i(C_i) = \sum_j h_{ij}(C_{ij})$$

並解決單機問題 $1\,||\,h_*(C_*)$ 。
- 為了解決單機問題 $1\,||\,h_*(C_*)$ ，可以使用ATC排程法：
1. 每當機器閒置時，例如時間 $t$ 時機器 $i$ 變為閒置。對於每個尚未排程的操作 $(i,j)$ 分別計算Ranking Index

$$I_{ij}(t) = \sum_{k=1}^n\frac{w_k}{p_{ij}}\exp\left(-\frac{\max(d_{ij}^k-p_{ij}+r_{ij}-t\,,\,0)}{K\bar{p}}\right)$$

其中 $\bar{p}$ 為尚未被排程之操作的平均處理時間取整數、 $K$ 為參數。
1. 將Ranking Index最高者排入機器 $i$ 排程。

- 選擇bottleneck時，計算前一個步驟所得的排程相對應的目標函數，並選擇其中最大的。將bottleneck上的工作排入排程。
- 與之前相同，可以考慮新加入的邊是否可以改善先前已排程機器的排程。
- 重複上述演算法直到排程完畢。

#### Example

| jobs | $w_j$ | $r_j$ | $d_j$ | machine sequence | processing times |
| -------- | -------- | -------- | -------- | -------- | -------- |
| 1 | 1 | 5 | 24 | $1\rightarrow 2\rightarrow 3$ | $p_{11} = 5,\, p_{21} = 10,\, p_{31} = 4$ |
| 2 | 2 | 0 | 18 | $3\rightarrow 1\rightarrow 2$ | $p_{32} = 4,\, p_{12} = 5,\, p_{22} = 6$ |
| 3 | 2 | 0 | 16 | $3\rightarrow 2\rightarrow 1$ | $p_{33} = 5,\, p_{23} = 3,\, p_{13} = 7$ |

||
| -------- |
| 初始圖 |

#### Iteration 1.

由上圖可知對於機器1、機器2、機器3：

\begin{align}
&d_{11}^1 = 24 - 19 + 5 = 10\\
&d_{12}^2 = 18 - 11 + 5 = 12\\
&d_{13}^3 = 16 - 7 + 7 = 16\\
\end{align}

| jobs | $p_{1j}$ | $r_{1j}$ | $d_{1j}^1,\,d_{1j}^2,\,d_{1j}^3$ |
| -------- | -------- | -------- | -------- |
| 1 | 5 | 5 | 10, $\infty$, $\infty$ |
| 2 | 5 | 4 | $\infty$, 12, $\infty$ |
| 3 | 7 | 8 | $\infty$, $\infty$, 16 |

\begin{align}
&d_{21}^1 = 24 - 14 + 10 = 20\\
&d_{22}^2 = 18 - 6 + 6 = 18\\
&d_{23}^3 = 16 - 10 + 3 = 9\\
\end{align}

| jobs | $p_{2j}$ | $r_{2j}$ | $d_{2j}^1,\,d_{2j}^2,\,d_{2j}^3$ |
| -------- | -------- | -------- | -------- |
| 1 | 10 | 10 | 20, $\infty$, $\infty$ |
| 2 | 6 | 9 | $\infty$, 18, $\infty$ |
| 3 | 3 | 5 | $\infty$, $\infty$, 9 |

\begin{align}
&d_{31}^1 = 24 - 4 + 4 = 24\\
&d_{32}^2 = 18 -15 + 4 = 7\\
&d_{33}^3 = 16 - 15 + 5 = 6\\
\end{align}

| jobs | $p_{3j}$ | $r_{3j}$ | $d_{3j}^1,\,d_{3j}^2,\,d_{3j}^3$ |
| -------- | -------- | -------- | -------- |
| 1 | 4 | 20 | 24, $\infty$, $\infty$ |
| 2 | 4 | 0 | $\infty$, 7, $\infty$ |
| 3 | 5 | 0 | $\infty$, $\infty$, 6 |

取 $K = 0.1$ 。對於機器1， $t = 4,\,\bar{p} = 5$ 。由此計算 $I_{11}(4),\,I_{12}(4),\,I_{13}(4)$ ，可知 $I_{11}(4)$ 值為最大，因此優先將 $(1,1)$ 排入排程。之後步驟也按照相同方式計算。

由此方法可得排程及目標函數值：

| machine | sequence | objective value |
| -------- | -------- | -------- |
| 1 | $(1,1)\rightarrow(1,2)\rightarrow(1,3)$ | 18 |
| 2 | $(2,3)\rightarrow(2,1)\rightarrow(2,2)$ | 16 |
| 3 | $(3,3)\rightarrow(3,2)\rightarrow(3,1)$ | 4 |

由於機器1排程的目標函數值最大，因此將 $(1,1)\rightarrow(1,2)\rightarrow(1,3)$ 排入排程。

| |
| -------- |
| After iteration 1 |

#### Iteration 2

由上圖可知對於機器2、機器3：

\begin{align}
&d_{21}^1 = 24 - 14 + 10 = 20\\
&d_{22}^2 = 21 - 6 + 6 = 21\\
&d_{23}^3 = 22 - 10 + 3 = 15\\
\end{align}

| jobs | $p_{2j}$ | $r_{2j}$ | $d_{2j}^1,\,d_{2j}^2,\,d_{2j}^3$ |
| -------- | -------- | -------- | -------- |
| 1 | 10 | 10 | 20, $\infty$, $\infty$ |
| 2 | 6 | 15 | $\infty$, 21, $\infty$ |
| 3 | 3 | 5 | $\infty$, $\infty$, 15 |

\begin{align}
&d_{31}^1 = 24 - 4 + 4 = 24\\
&d_{32}^2 = 21 - 15 + 4 = 10,\,d_{32}^3 = 22 - 16 + 4 = 10\\
&d_{33}^3 = 22 - 15 + 5 = 12\\
\end{align}

| jobs | $p_{3j}$ | $r_{3j}$ | $d_{3j}^1,\,d_{3j}^2,\,d_{3j}^3$ |
| -------- | -------- | -------- | -------- |
| 1 | 4 | 20 | 24, $\infty$, $\infty$ |
| 2 | 4 | 0 | $\infty$, 10, 10 |
| 3 | 5 | 0 | $\infty$, $\infty$, 12 |

計算Ranking index後可得

| machine | sequence | objective value |
| -------- | -------- | -------- |
| 2 | $(2,3)\rightarrow(2,1)\rightarrow(2,2)$ | 10 |
| 3 | $(3,2)\rightarrow(3,3)\rightarrow(3,1)$ | 0 |

由於機器2排程的目標函數值最大，因此將 $(2,3)\rightarrow(2,1)\rightarrow(2,2)$ 排入排程。

||
| -------- |
| After iteration 2 |

#### Iteration 3

由上圖可知對於機器3：

\begin{align}
&d_{31}^1 = 24 - 4 + 4 = 24\\
&d_{32}^2 = 26 - 15 + 4 = 15,\,d_{32}^3 = 22 - 16 + 4 = 10\\
&d_{33}^1 = 24 - 22 + 5 = 7,\,d_{33}^2 = 26 - 24 + 5 = 7,\,d_{33}^3 = 22 - 15 + 5 = 12\\
\end{align}

| jobs | $p_{3j}$ | $r_{3j}$ | $d_{3j}^1,\,d_{3j}^2,\,d_{3j}^3$ |
| -------- | -------- | -------- | -------- |
| 1 | 4 | 20 | 24, $\infty$, $\infty$ |
| 2 | 4 | 0 | $\infty$, 15, 10 |
| 3 | 5 | 0 | 7, 7, 12 |

根據計算後，將 $(3,3)\rightarrow(3,2)\rightarrow(3,1)$ 排入排程。

||
| -------- |
| After iteration 3 |

||
| -------- |
| Final schedule |

目標函數為

$$\sum_{j=1}^3 w_jT_j = 1\times (24-24) + 2\times (26-18) + 2\times (22-16) = 28$$

事實上，這並非是最佳解，最佳解為18。為了簡化問題，在上面步驟中選取好排程後並沒有對先前的機器進行重新排程。

### Flexible Job Shops

顯然Job Shops為Flexible Job Shops的特例，也就是每個工作站都只有一台機器。對於Flexible Job Shops，可以將Shifting Bottleneck heuristic稍作修改後適用。
- 此時每個工作站都能允許不只一個操作，只要工作站還有空閒的機器，安排新的操作時就無需等待前面的工作完成。因此在計算一條路徑之長度時，不能像之前那樣直接將路徑長度相加。而是要改為考慮parallel machines的makespan。
- 比如，假設中心1有兩台機器，則上述例子中的路徑 $(1,1)\rightarrow(1,2)\rightarrow(1,3)$ 之長度就相當於是這兩台機器上排程三個工作的makespan。

## Lot Scheduiling

### Single Machine

假設將整個工廠視為一個需要生產 $n$ 種產品的Single machine，其中：
- 產品 $j$ 每單位時間的產量為 $Q_j$
- 產品 $j$ 每單位時間的需求為 $D_j$
- 儲存一單位的產品 $j$ 所需的倉儲成本為 $h_j$ 每單位時間
- 生產產品 $j$ 前，需要setup cost $c_j$
- 當從生產產品 $j$ 切換至生產產品 $k$ 時，需要setup time $s_{jk}$

我們的目標為：在滿足需求的同時最小化生產成本。
為了簡化問題，考慮循環排程，例如生產的產品順序為

$$1\rightarrow 2\rightarrow 3\rightarrow\cdots\rightarrow n-1\rightarrow n\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow\cdots$$

在這種情況下，只需要決定cycle time(與就是從開始生產產品 $j$ 到下一次開始生產產品 $j$ 的間隔時間)就決定了整個排程。


假設cycle time為 $x$ ：
1. 為了滿足 $x$ 這段時間內的需求 $(D_jx)$ ，產品 $j$ 需要花費 $D_jx/Q_j$ 的時間來生產。
2. 在產品 $j$ 停止生產前，每單位時間倉儲量會增加 $Q_j - D_j$ ，因此在停止生產時的倉儲量為 $(Q_j-D_j)D_jx/Q_j$ 。而在停止生產後，每單位時間倉儲量會減少 $D_j$ 。
3. 假設開始生產前的倉儲量為零，產品 $j$ 在 $x$ 這段時間內的平均倉儲量為上圖中產品 $j$ 所構成三角形之高的一半，也就是 $\frac{1}{2}\frac{(Q_j-D_j)D_jx}{Q_j}$ 。
4. 在 $x$ 這段時間內生產產品 $j$ 每單位時間的平均成本為

$$\frac{c_j}{x} + \frac{h_j}{2}\frac{(Q_j-D_j)D_jx}{Q_j}$$

5. 完成一次生產循環每單位時間的平均成本為

$$\sum_{j=1}^n\left(\frac{c_j}{x} + \frac{h_j}{2}\frac{(Q_j-D_j)D_jx}{Q_j}\right)$$

為了最小化平均成本，令上式對 $x$ 微分後為零：

$$\sum_{j=1}^n\left(-\frac{c_j}{x^2} + \frac{h_j}{2}\frac{(Q_j-D_j)D_j}{Q_j}\right) = 0$$

可得

$$x = \sqrt{\left(\sum_{j=1}^n\frac{h_j(Q_j-D_j)D_j}{2Q_j}\right)^{-1}\sum_{j=1}^n c_j}$$

而idle time則為

$$x\left(1-\sum_{j=1}^n\frac{D_j}{Q_j}\right)$$

若 $s_{jk}$ 與 $j$ 無關，也就是 $s_{jk} = s_k$ 。則循環排程的順序並不受到setup time影響。
- 若 idle time 大於 $\sum_{j=1}^n s_j$ ，上述所求得的cycle time為循環排程中的最佳解。
- 若 idle time 小於 $\sum_{j=1}^n s_j$ ，則實際的cycle time必須比上面求得的還要大，最佳解為

$$x = \frac{\sum_{j=1}^n s_j}{1-\sum_{j=1}^n\frac{D_j}{Q_j}}$$

此時排程變為沒有 idle time。

## Metaheuristic

由於實際上面對的問題基本上都是屬於NP-hard，在工作數量大的情況下不太可能真的去找出最佳解。此時通常會退而求其次，使用Heuristic演算法找出一個還不錯的解。

由於問題的種類多又繁雜，如果要為每一種問題專門設計一個演算法就太花費時間和精力。因此，人們發展出可以套用在許多問題上的演算法稱為Metaheuristic。

此類演算法和之前所提出的Heuristic的差別為，之前的演算法都是一步一步建構出一個解；而Metaheuristic則不同，舉例來說，局部搜索是先由一個基本的可行解出發，透過此可行解附近的鄰居逐漸去「改善」這個解，最後得出一個局部最佳解。

設計局部搜索演算法通常有以下四項準則：

1. 如何表示一個排程
1. 如何定義鄰居(neighborhood)
1. 如何在鄰居中搜索
1. 如何決定是否應該接受搜索出的解

#### Discussion

1. 對於第一個問題，如果考慮的是nonpreemptive single machine，那麼可以使用 $1$ 到 $n$ 的數字之排列來表示一個排程。
- 比如說， $n = 4$ 時，2314代表了工作排程：

$$2\longrightarrow 3\longrightarrow 1\longrightarrow 4$$

如果考慮的是nonpreemptive job shop，那麼可以用 $m$ 個 $1$ 到 $n$ 的數字排列，其中每個數字排列代表對應機器上的工作排程。
1. 對於第二個問題，舉例來說，對於nonpreemptive single machine可以將鄰居定義為所有隨機交換目前排程中的兩個工作後可得的排程。

如果總共有 $n$ 個工作，那麼每個排程都共有 $C^n_2 = n(n-1)/2$ 個鄰居。
- 比如說， $n = 4$ 時，2314的鄰居有3214、1324、4312、2134、2413、2341。

對於nonpreemptive job shop及目標函數 $C_{\text{max}}$ ，我們知道會影響到目標函數的只有最長路徑。因此，可以將鄰居定義為所有隨機將最長路徑上兩個同機器，但不同工作的工作交換後可得的排程。

當然，也可以考慮更複雜的情況，交換時再往前一步看交換能否改進目標函數。如下圖，將 $(i,j),(i,k)$ 交換後可以注意到， $(i,k)$ 的開始時間受到 $(h,k)$ 的限制。因此，將 $(h,\ell),(h,k)$ 也交換來使工作 $k$ 更早完成。


1. 對於第三個問題，一個最簡單的方法就是從鄰居中隨機選擇一個。或者，也可以選擇所有鄰居中對目標函數改善最大的那個。
1. 第四個問題因設計而定，可以有一個決定性的過程來決定是否應該採納，也可以有一個基於機率的過程來決定。之所以要有這個步驟的原因是我們並不希望演算法永遠被困在局部最佳值。

### Simulated Annealing

假設 $f$ 代表目標函數。對於兩個排程 $S_k,S_c$ 定義機率函數

$$P(S_k, S_c) = \exp\left(\frac{f(S_k)-f(S_c)}{\beta_k}\right)$$

其中 $\beta_1\geqslant\beta_2\geqslant\beta_3\geqslant\cdots > 0$ 。

>[!TIP]Heuristic Algorithm
>Simulated Annealing 的步驟如下：
> 1. 初始化 $k = 1,\beta_1$ 及排程 $\mathcal{S}_1$ 。令 $\mathcal{S}_0 = \mathcal{S}_1$ 。
> 1. 從 $\mathcal{S}_k$ 的鄰居中選出 $\mathcal{S}_c$ 。
> - 若 $f(\mathcal{S}_0) < f(\mathcal{S}_c) < f(\mathcal{S}_k)$ ，令 $\mathcal{S}_{k+1}=\mathcal{S}_c$ 。
> - 若 $f(\mathcal{S}_c) < f(\mathcal{S}_0)$ ，令 $\mathcal{S}_{0}=\mathcal{S}_{k+1}=\mathcal{S}_{c}$ 。
> - 若 $f(\mathcal{S}_c) > f(\mathcal{S}_k)$ ，從零到一的數字中隨機生成一個數字 $U_k$ 。
> 1. 如果 $U_k\leqslant P(S_k, S_c)$ ，令 $\mathcal{S}_{k+1}=\mathcal{S}_c$ 。
> 1. 如果 $U_k > P(S_k, S_c)$ ，令 $\mathcal{S}_{k+1}=\mathcal{S}_k$ 。
> 1. 如果 $k > N$ ，終止演算法。否則更新 $\beta_{k+1},\,k\leftarrow k+1$ 並回到第二步。

上述演算法中：
- $\mathcal{S}_{0}$ 代表了到目前為止的最佳解。
- $\mathcal{S}_{k}$ 代表了第 $k$ 步時的排程。從 $\mathcal{S}_k$ 的鄰居中選出 $\mathcal{S}_c$ 。
1. 如果 $\mathcal{S}_c$ 的表現比 $\mathcal{S}_k$ 好，但是沒比目前的最佳解好，那就更新下一個目標為 $\mathcal{S}_c$ 。
1. 如果 $\mathcal{S}_c$ 的表現比目前的最佳解好，那就更新目前的最佳解及下一個目標為 $\mathcal{S}_c$ 。
1. 就算 $\mathcal{S}_c$ 的表現比 $\mathcal{S}_k$ 還差，還是有一定機率會更新下一個目標為 $\mathcal{S}_c$ 。因為我們並不希望演算法找到局部最佳解後就一直困在那裏。
- 通常來說，會選取 $\beta_k = a^k, 0 < a < 1$ 。
- 從式子

$$P(S_k, S_c) = \exp\left(\frac{f(S_k)-f(S_c)}{\beta_k}\right)$$

可看出，當 $f(\mathcal{S}_c) > f(\mathcal{S}_k)$ 時，如果 $\mathcal{S}_c$ 和 $\mathcal{S}_k$ 的表現差距越大，那麼機率函數就越小，因此更不可能更新為 $\mathcal{S}_c$ 。同樣的，如果 $\mathcal{S}_c$ 和 $\mathcal{S}_k$ 的表現差距越小，那麼機率函數就越大，因此更可能更新為 $\mathcal{S}_c$ 。
- 當 $f(\mathcal{S}_c) > f(\mathcal{S}_k)$ 時， $\beta_k$ 對機率函數的影響則為：
1. 當 $k$ 較小時， $\beta_k$ 較大，因此機率函數會較大。
1. 當 $k$ 較大時， $\beta_k$ 較小，因此機率函數會較小。

這意味著，在演算法前期更可能跳出當前的解，而後期更不可能跳出當前解。這與期望相吻合：我們自然會希望在一開始時演算法多搜索各種可能，而到後期時理想情況下已經找到了最佳解，因此便不再希望跳出最佳解了。

### Tabu-Search

Tabu-Search與Simulated Annealing類似，只不過決定的機制不再是機率性的。基本上Tabu-Search就是利用tabu-list記錄下最近走過的路，並禁止重複走已經走過的路，以此來避免困在局部最佳解。

>[!TIP]Heuristic Algorithm
>Tabu-Search 的步驟如下：
> 1. 初始化 $k = 1$ 及排程 $\mathcal{S}_1$ 。令 $\mathcal{S}_0 = \mathcal{S}_1$ 。
> 1. 從 $\mathcal{S}_k$ 的鄰居中選出 $\mathcal{S}_c$ 。
> - 若 $\mathcal{S}_k\rightarrow\mathcal{S}_c$ 不在tabu-list上，則將其加入tabu-list並令 $\mathcal{S}_{k+1} = \mathcal{S}_c$ 。若tabu-list超過給定的長度時，則將裡面存放最久的紀錄刪除。
> - 若 $\mathcal{S}_k\rightarrow\mathcal{S}_c$ 在tabu-list上，則令 $\mathcal{S}_{k+1} = \mathcal{S}_k$ 。
> - 若 $f(\mathcal{S}_c) < f(\mathcal{S}_0)$ ，更新 $\mathcal{S}_0 = \mathcal{S}_c$ 。
> 1. 如果 $k > N$ ，終止演算法。否則更新 $k\leftarrow k+1$ 並回到第二步。

### Genetic Algorithm

如同其名，Genetic Algorithm模仿的是基因的運行模式。每種排程方式被視為是族群中的個體，而個體之間又會透過基因產生他們的「後代」。在族群中，適應能力較好(也就是目標函數值較佳)的個體將會存活下來並把它的基因留存下去。如此一來，經過長期世代演進，理論上存活下來的都會是適應能力較好的個體。

要產生「後代」，一種常見的方式為 Linear Order Crossover (LOX)，步驟如下：
1. 隨機選取兩個個體作為父母。
1. 從第一位父母的基因中隨機選取一段子序列。
1. 將這段子序列複製到後代基因上的對應位置。
1. 從第二位父母的基因中將還未被選取的數字依序複製到後代基因上。

||
| -------- |
| Linear Order Crossover 的範例。|

在上述過程中，也可以考慮基因突變的可能性。舉例來說，每次產生後代時，有一定的機率會使後代基因的排序被打亂。

>[!Tip]Heuristic Algorithm
>Genetic Algorithm 的步驟如下：
>1. 假設族群的存活數量上限為 $\mathcal{E}$ 。初始化 $k=1$ 和排程 $\mathcal{S}_1,\mathcal{S}_2,\cdots,\mathcal{S}_\mathcal{E}$ 。
>1. 計算每個個體的適應度，根據適應度從族群中隨機挑出個體做為父母，並產生後代。上述過程中適應度越高的個體越可能被選為父母。
>1. 計算後代的適應度，從族群中選出適應度前 $\mathcal{E}$ 高的個體存活下來作為下一次的族群。
>1. 如果 $k > N$ ，終止演算法。否則更新 $k\leftarrow k+1$ 並回到第二步。

## Coding Example

實際情況中，面臨的問題可能為NP-Hard，因此不一定有好的演算法可以解決。此時一個萬用的做法為：利用Constraint Programming找出一個還不錯的可行解，之後再將其當作Metaheuristic演算法的初始條件進而找出更好的解。以下使用Google開發的OR-Tools和heuristic演算法解決排程問題：
1. Flow Shops $Fm\mid\mid C_{\text{max}}$
- https://github.com/jmmchang/Flow-Shops
2. Shifting Bottleneck Heuristic for Job-Shops
- https://github.com/jmmchang/ShiftingBottleneck
3. Flexible Job-Shops $FJc\mid r_j,s_{ijk}\mid \alpha C_{\text{max}} + (1-\alpha)\sum w_jT_j$
- https://github.com/jmmchang/Flexible-Job-Shops

## References
[1]. Michael L. Pinedo. 2022. *Scheduling : Theory, Algorithms, and Systems.* Springer.

[2]. Dorit S. Hochbaum. 1997. *Approximation Algorithms for NP-Hard Problems.* Intermational Thomson Publishıng.

[3]. Michael L. Pinedo. 2009. *Planning and Scheduling in Manufacturing and Services.* Springer.

[4]. David P. Williamson and David B. Shmoys. 2010. *The Design of Approximation Algorithms.* Cambridge University Press.

[5]. [Google OR-Tools](https://developers.google.com/optimization)