子群體基因演算法於多目標排程之應用─以PCB鑽孔作業為例

在真實的印刷電路板鑽孔作業當中，排程的單一目標最佳化已無法滿足管理者的需求，管理者於決策時往往會考慮多個衡量指標，因此以往簡單的最佳化排程法則已漸漸淘汰而不被使用。大於兩台機台的排程問題是屬於NP-hard問題，因此本研究提出一個子群體基因演算法（SPGA）的啟發式方法，先以流程型排程問題來驗證SPGA的適用性，並以最小化總完工時間與最小化最大延遲時間當做排程績效衡量指標；接著再求解印刷電路板完全平行機台多目標排程問題，並以最小化總完工時間及最小化總延遲時間為排程目標，求解不同機台數、工件數組合題型之柏拉圖最佳解，使得結果在收斂性與擴散性能有不錯的表現。本研究所提出的方法SPGA將與MOGA、NSGA-II及SPEA-II等三個演化式演算法進行比較，並以可兼顧擴散性與收斂型的衡量指標來比較各演算法的優劣，從所有的測試題型結果可以發現，SPGA在求解排程問題的結果都相當不錯，也證實了能成為企業在求解排程問題上一個可用的工具。

關鍵字

印刷電路板、多目標排程問題、基因演算法、柏拉圖最佳解

並列摘要

In the real-world drilling operations of printed circuit board, the single objective optimization of scheduling problems has been no more satisfied by managers who always consider about conflicting objectives. Though many algorithms has been proposed for multi-objectives, no one can perform well in both convergence and diversity. Therefore, we propose a new algorithm called sub-population genetic algorithm (SPGA) in order to have better performance. We use it to solve two different types of scheduling problems. The first one is flow-shop scheduling, and it’s objective is to minimize the maximum completion time and maximum tardiness time. The other one is parallel machine scheduling problem, where objective is to minimize the maximum completion time and total tardiness time. Then we compare our SPGA with recently developed algorithms: MOGA, NSGA-II and SPEA-II, we use the value to measure the performance of different algorithms. The result of our experiments shows that our SPGA is better then any other algorithms, and it can perform well in both convergence and diversity.

並列關鍵字

Printed Circuit Board, Multi-Objectives Scheduling, Genetic Algorithm,Pareto Optimal Solutions

參考文獻

60. 湯璟聖，「動態彈性平行機群排程的探討」，中原大學，碩士論文，2003。

55. 林水耕，「應用混合式基因演算法求解流程型工廠之多目標排程問題」，元智大學，碩士論文，2001。

51. 王治元，「智慧型基因演算法於多目標排程之發展與應用─以PCB鑽孔作業為例」，元智大學，碩士論文，2004。

54. 阮永漢，「系統模擬與基因演算法於完全相同機台排程之應用」，碩士論文，元智大學，2002。

1. Brucker, P., Sceduling algorithms, Springer, Berin, 1998.

國際替代計量

子群體基因演算法於多目標排程之應用─以PCB鑽孔作業為例

主題瀏覽