基因演算法於有限資源下不相關平行機台排程問題之應用

A Genetic Algorithm Approach for Unrelated Parallel-Machine Scheduling Problems with Constrained Resources

鄭志傑(Chih-Jye Tseng)

指導教授 ： 蔡啟揚

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

https://doi.org/10.6838/YZU.2006.00223

摘要

過去關於不相關平行機台研究的限制與假設條件，都還是將資源設定為無限的情況下，與業界中各機台可使用資源是有限的情況並非完全相同。而這類問題在學術上是熟知困難度極高的組合最佳化問題，除了少數特例外，此類問題皆屬於NP-hard問題，需要花費相當多的時間與資源才能求得最佳解，因此，本研究期望能夠在有限的資源與考量機台的整備時間限制下，建構一個以加權完工時間最小化的不相關平行機台排程模式。
本研究是使用在啟發式演算法中，具有多點平行搜尋與能避免落入最佳解的基因演算法，來求解此不相關平行機台之排程問題，並結合業界的實例資料建構不同項目的測試例題，以參數最佳化後執行所得之結果與其他排程方法及ILOG OPL限制規劃軟體所求之問題最佳解進行比較，在求解時間與求解品質上做一分析，以評估基因演算法於不相關平行機台排程問題之績效，期望能建構對於有限資源的不相關平行機台排程問題進行有效求解之模型，供業界或後續研究人員作為參考。

關鍵字

基因演算法 ； 不相關平行機台 ； 有限資源

並列摘要

The previous studies on unrelated parallel-machine scheduling problems usually assume that the necessary resources for processes are unconstrained. However, it does not conform to condition that the resources in scheduling problems are usually limited in practice. It is well known that most of the unrelated parallel-machine scheduling problems are NP-hard. It costs much time and a large number of resources to solve this kind of problems. Therefore, this research attempts to solve unrelated parallel-machine scheduling problems with sequence-dependent setup-time and constrained resources. The objective considered in this research is minimizing the total weighted completion time.
This research proposes a heuristic approach developed based on genetic algorithm for the problem. A numerical experiment with data collected from IC testing industry is conducted. Examples of different sizes are constructed to test the performance of the proposed algorithm. The results show that this algorithm solves the problem efficiently and effectively.

並列關鍵字

genetic algorithm ； unrelated parallel-machine ； constrained resources

參考文獻

6. 蕭陳鴻，「基因演算法於非等效平行機台排程之應用」，元智大學工業工程研究所，碩士論文 (2000)。

7. 葉麗芬，「雙目標非等效平行機台排程問題之探討」，元智大學工業工程與管理研究所，碩士論文 (2001)。

3. 吳思農，「模擬退火法於有限資源下不相關平行機台排程問題之應用」，元智大學工業工程與管理研究所，碩士論文 (2005)。

8. Allahverdi, A. and J. Mittenthal, “Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time,” Naval Research Logistics, 41, 677-682 (1994).

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