[Math] Office Work - 從編排更表到Hungarian Algorithm

因為會處理歐美收市和亞洲收市，所以我這組人的繁忙時間是清早和晚上兩端，需要有輪班制，工作分早晚兩更，據英文堂所學這種工作時間有個形容詞是antisocial hour, 人手足夠時就可以讓同事返九點左右的正常時間。編更上如何令大家滿意，這問題幾似數學Operational Research / Graph Theory中的 Matching problem。大概最近FB見到恆隆同伯賴段片，數學應用的頭腦靈活過來，想到還是可以用典型的Hungarian Algorithm。這演算法所處理的情況是：假設有n個任務需要分派給n個人，每人要完成各個任務都有某個成本，問如何編配任務才能讓總成本最少。

例如成員 i 要處理任務 j 的成本是c_ij，這些成本可以寫成矩陣C表示。例如第一個人p1處理任務一task1要成本1, p1 處理 task2 要成本5, p1 處理 task3 要成本3；分派方法可以寫成矩陣A，這簡單例子的最佳分配可以直觀得知如下, 總成本為6。而Hungarian Algorithm 的步驟是這樣，大致有以下程序：（一）將所有數值減去該行最小的數，然後再將所有數值減去該列最小的數，今每行、列都有零存在。（二）[Trial and Error] 找出一個"Independent zero"的組合，用最少條線穿過所有零。（三）如果剛好存在於n條線上，該"Independent zero"組合就可以得出答案；如果只需少過n條線，修改矩陣重覆步驟二。

$$
C=\begin{bmatrix}
1 & 5 & 3 \\
4 & 2 & 8 \\
7 & 9 & 3 \end{bmatrix},
A=\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \end{bmatrix}
$$

現實問題係假設公司只有早中晚三更，6個組員中需要最少有3個返早，最少2個返夜。預早問了大家意願，亦都計及到從上而下的安排，能否有一個方法可以方便到編更者？

突然想到的是人和任務數量其實並非不同。
我們可以預備一個6*6的矩陣，行 p1 - p6 分別代表6個組員，列 a1 - a3, p1 - p2, n1 分別代表3個早更、2個夜更、1個彈性位。成本從兩個因素考慮。一是意願例如p1傾向返早，p5傾向返夜，p6想正常時間而傾向早，所以有如下數值(亦可以讓各人排更的傾向次序)。二是在管理安排上的需要：有需要返那更的1、不需要的0。意願和安排的比例是alpha:beta。
$$
Wills=\begin{bmatrix}
1 & 1 & 1 & 3 & 3 & 2 \\
1 & 1 & 1 & 3 & 3 & 2 \\
1 & 1 & 1 & 3 & 3 & 2 \\
1 & 1 & 1 & 3 & 3 & 2 \\
3 & 3 & 3 & 1 & 1 & 2 \\
2 & 2 & 2 & 3 & 3 & 1 \end{bmatrix},
Necessary=\begin{bmatrix}
1 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 \end{bmatrix}
$$
為了在排序時公平處理打和的時候，加入一個數字為0-1的隨機矩陣。 
$$
Random=\begin{bmatrix}
0.60 & 0.27 & 0.98 & 0.06 & 0.22 & 0.08 \\
0.85 & 0.65 & 0.88 & 0.59 & 0.74 & 0.81 \\
0.12 & 0.43 & 0.14 & 0.96 & 0.60 & 0.63 \\
0.68 & 0.98 & 0.06 & 0.31 & 0.65 & 0.21 \\
0.76 & 0.33 & 0.66 & 0.18 & 0.06 & 0.39 \\
0.14 & 0.84 & 0.43 & 0.94 & 0.80 & 0.51 \end{bmatrix}
$$
成本 = alpha*(意願) - beta*(需要) + (隨機), alpha=beta=1
$$
Cost=\begin{bmatrix}
0.60 & 0.27 & 0.98 & 3.06 & 3.22 & 2.08 \\
1.85 & 1.65 & 1.88 & 2.59 & 2.74 & 2.81 \\
1.12 & 1.43 & 1.14 & 3.96 & 3.60 & 2.63 \\
1.68 & 1.98 & 1.06 & 3.31 & 3.65 & 1.21 \\
3.76 & 3.33 & 3.66 & 1.18 & 1.06 & 2.39 \\
1.14 & 1.84 & 1.43 & 3.94 & 3.80 & 1.51 \end{bmatrix}
$$

下一步就是實作上，可以用R version3.2, "clue" package中的solve_LSAP:
solve_LSAP(x)
y <- solve_LSAP(x)
sum(x[chins(seq_along(y), y)])

網頁上也有現成的online solver, 例如hungarianalgorithm.com (本例子), 就有答案之餘還顯示出算法的過程，對想了解算法步驟的人十分好用，推薦一看。下圖這個是EasyCalculation.com上的版本。雖然這些要求逐個數字輸入，對n比較大時不方便，但足夠應付小規模的問題。

$$ Assign=\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} $$

然後，嘗試用Office Excel時，發覺可以更"簡單"地處理。因為Hungarian Algorithm 的問題亦是Integer Linear Programming 的特例 ，可以用內置的solver 解決，使用起來更方便得多。雖然，內置的一般算法如Simplex Method，複雜度不如Hungarian般只有O(n³)，代表當n增加時運算步驟更多，效能較慢，但在規模小的問題上用家應該感受不到什麼分別。

到此，可以解決另一個Holiday Support 的問題：2016年有14個公眾假期是在周一至周五，每日需要6個組員中的4個返工。年初時，如何在兼顧意願的情況下安排一份返工的初稿，再讓員工之後自行安排調更。
如果用意願矩陣的方法，這就只要修改Constraints中的：
每人最少要返 9 日，所以: Sum of Row >=9
每日最少要返 4 人 ，所以: Sum of Column >=4
然後可以再修改去兼顧特別要求，例如：我會想年初一至年初三，全部上班／全部放假，etc...