人員排班問題啟發式解法之應用

Abstract

服務事業所面臨的顧客需求，隨著時間的改變而變化很大，並且其所 提供的服務具及時性而不能儲存，因此使得人力的配置成為一個複雜的問 題。 人員排班問題在學術上已被證明為NP-Complete問題[7]，無法在 合理的運算時間內求得最佳解，因此為了能簡單迅速地找到一近似解，一 般皆採用啟發式解法。 本研究組合文獻中已有之方法，以Morris & Showalter之MS演算法[20]求得一起始可行解，再以 Easton & Rossin之 EAS演算2法[12]產生相同成本解，最後加上Henderson & Berry之LPI演算 法[16]及本研究發展之EXCHANGE演算法進行解的改善，成為一個組合的啟 發式解法MEX。在研究中，首先以小規模的例題測試，測試例題為一天之 內的排班，模式中包含了520個變數及28個限制式，55個測試例題以組合 啟發式解法求解，皆得到最佳解。最後，以臺灣電信北區管理局『104』 東區查號臺的接線生排班為應用實例，排班長度為一個星期，模式中包含 了43680個變數及196個限制式。然而受到求解工具的限制，我們作了一些 簡化的假設，建立六個模式，其中最大的模式包含10920個變數，最小的 模式則包含 2856個變數。然後在兩種不同的需求情況下進行求解。求解 結果誤差的衡量是與LP目標函數值比較的百分誤差。情況一中的求解結果 誤差介於 1.64％∼4.1％ ，而情況二則介於0.82％∼4.23％。綜合兩個 情況的結果看來，誤差皆在 5％以內，由此顯示我們的求解效率相當不錯 。