應用基因演算法於工件可分段處理下不相關平行機台問題之研究

A Genetic Algorithm Approach for Unrelated Parallel-Machine Scheduling Problems with Dividable Jobs

范雅喬(Ya-Chiao Fan)

指導教授 ： 蔡啟揚

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

摘要

平行機台一直是近年來在排程問題中一個重要的研究領域之一，但平行機台的排程問題在學術上是屬於困難度極高的組合最佳化問題，除了少數特例外，此類問題均屬於NP-hard問題，需要花費相當多的時間及資源才能求得最佳解，因此本研究期望能在具有順序相依整備時間，工作是有不同到達時間且加工方式是可視為可分段處理的前提條件下，去建構出一個以總絕對延誤時間最小化的不相關平行機台排程模式。
而本研究是嘗試使用具有平行搜尋與能避免落入局部最佳解的基因演算法來求解此不相關平行機台之排程問題，並結合某偏光板廠中的PSA製程之實際案例資料去對在部份分段作業模式下的不同分段比重進行效益比較，期能提供業界或後續研究人員作為參考。

關鍵字

基因演算法 ； 不相關平行機台 ； 排程 ； 順序相依 ； 分段處理

並列摘要

Parallel-machine scheduling has been one of the important research fields of scheduling problems in recent years. It is a difficult combinatorial optimization problem. Except for few cases, this kind of problems belongs to NP-hard problems which require considerable time and resources to find optimal solutions. This research considers parallel-machine scheduling problems where jobs can be divided into stages and do not require continuous process. An unrelated parallel-machine scheduling model with dividable jobs, sequence-dependence setup times, and non-zero arrival times, is constructed and the objective is to minimize total absolute lateness.
This research applies Genetic Algorithm Approach on the considered scheduling problem. The Genetic Algorithm has parallel searching functions and capability to avoid partial optimal solution. Numerical experiment containing various test problems with real case data of the PSA process from a Polarizer manufacturing factory is conducted to evaluate the performance of the proposed algorithm. It is the aim of this research that the results can be of valuable to industries and follow-up research.

並列關鍵字

genetic algorithm ； unrelated parallel-machine ； scheduling ； sequence dependent ； dividable jobs

參考文獻

32. 王苡宸，2008，「資源限制下比例式非等效平行機台排程問題之研究」，元智大學工業工程與管理研究所，碩士論文。

42. 張毓仁，2001，「多階段不等效平行機之排程研究」，中原大學工業工程研究所，碩士論文。

44. 陳建隆，2008，「基因演算法於多目標TFT-LCD模組廠排程問題之研究」

51. 熊詩敏，2007，「結合優勢性質與基因遺傳演算法於具有整備時間之單機與非等效平行機台之研究」，元智大學工業工程與管理研究所，碩士論文。

53. 鄭志傑，2006，「基因演算法於有限資源下不相關平行機台排程問題之應用」，元智大學工業工程與管理研究所，碩士論文。