模擬退火法於有限資源下不相關平行機台排程問題

A Simulated Annealing Algorithm for Unrelated Parallel-Machine Scheduling Problem with Constrained resources

吳思農(Si-Nong Wu)

指導教授 ： 蔡啟揚

元智大學/工程學院/工業工程與管理學系/碩士(2004年)

摘要

以往有關不相關平行機台的問題還是都著眼於資源是無限的情況下，但實業界的情況中各機台可使用的資源是有限的，這類問題在學術上是熟知困難度極高的組合最佳化問題，除了少數特例外，此類問題皆屬於NP-hard問題，因此本研究期望能夠在有限的資源與考量機台的整備時間限制下，建構一個在有限資源下的不相關平行機台排程之模式，績效衡量指標為總時程時間最小化，本研究嘗試使用模擬退火法能夠跳脫局部最佳解的機制，進而搜尋到全域最佳解的優點，來求解不相關平行機台之排程問題。
本研究探討模擬退火法的最佳參數組合，以小型、中型和大型測試例題，並結合實業界的實例驗證，於求解時間與求解品質上做一分析，並在資源有無的鬆緊度上做一探討，結果顯示無限的擴充資源，只會造成多餘的浪費，最後結果也顯示本研究所建構的排程指派演算法確實能對傳統的簡易派工法則上有一定的改善績效，且能有效的降低總時程時間，並對於有限資源下的不相關平行機台的排程問題建立一個排程指派演算法，結果也顯示此排程指派演算法在求解總時程時間上有良好的績效。

關鍵字

模擬退火法 ； 不相關平行機台 ； 總時程最小化

並列摘要

The study on unrelated parallel-machine scheduling problems has been assuming unconstrained resources. However, the resources in scheduling problems are usually limited in practice. It is well known that most of the unrelated parallel-machine scheduling problems alone are NP-hard. Therefore, utilizing its ability to escape local optimal points, the study applies simulated annealing method and attempts to develop an algorithm for unrelated parallel-machine scheduling problems. The objective considered in this study is to minimize the machines completing time.
In order to evaluate the performance of the proposed algorithm, numerical experiments are conducted and the algorithm is tested on three numerical examples of different sizes, as well as, practical cases. The results show that it performs well compared to simple dispatching rules.

並列關鍵字

Simulation annealing ； Unrelated parallel-machines ； Minimum makespan

參考文獻

1. Adenso-Diaz, B., “An SA/TS mixture algorithm for the scheduling tardiness Problem, “European journal of operational research, 88, 516-524, (1996).

2. Anagnostopoulos and Rabadi, G.., “A simulated annealing algorithm for the unrelated parallel machine scheduling problem”, Proceeding of the world automation congress, Orlando, Florida, June 9-13, (2002).

4. Bank, F., “Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties”, Mathematical and computer modeling 33, 363-383., (2001).

5. Ben-Daya, M. and Al-Fawzan, M., “ A simulated annealing approach for the one-machine mean tardiness scheduling problem, “ European Journal of operational Research 93, 61-67, (1996).

6. Ghedjati, F., “Genetic algorithms for the job-shop scheduling problem with parallel constraints: heuristic mixing method machines and precedence”, Computer & industrial engineering 37, 39-42, (1999).