以柴比雪夫分群法建構子群體權重向量求解多目標問題

Sub-population Genetic Algorithm II for Multi-objective Parallel Machine Scheduling Problems

徐麟(Lin Hsu)

指導教授 ： 張百棧

元智大學/資訊學院/資訊管理學系/碩士(2011年)

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

摘要

近年來，排程的單一目標最佳化已無法滿足管理者的需求，管理者於決策時往往會考慮多個衡量指標，因此以往簡單的最佳化排程法則已漸漸淘汰而不被使用。而排程問題隸屬於NP-hard問題，因此以傳統最佳化方法求解相當費時，故本研究提出一個子群體基因演算法(SPGA-II)的啟發式演算方法，其主要方法是利用柴比雪夫分割方法將搜尋空間分割成數個子群體空間並給予權重向量，在不同的權重向量空間中搜尋最佳解；並以流程型排程問題來驗證SGPA-II的適用性，多目標求解法就是在各目標之間進行取捨(tradeoff)，本研究二個目標式分別為最小化總完工時間與最小化最大延遲時間，求解相同機台數、不同工件數組合題型之柏拉圖最佳解，研究結果顯示SPGA-II兼顧收斂性與擴散性。本研究所提出的方法SPGA-II將與SPGA、MOGA、NSGA-II、SPEA-II等四種演算式演算法進行比較，並與衡量指標D1R來比較各演算法的優劣，從所有的測試題型結果可以發現，SPGA-II在求解排程問題的結果都相當不錯。

關鍵字

多目標排程問題 ； 柴比雪夫分割方法 ； 流程型排程問題 ； 柏拉圖最佳解

並列摘要

In recent years, industrial manufacturing usually faces the tradeoff of multi-objective decision problems. Many researchers have become more aware of the efficiency of heuristics for solving multi-objective problems. In this paper, we improve the previous SPGA approach and present a Sub-population Genetic Algorithm II (SPGA-II). SPGA-II takes advantage of the Tchebycheff Decomposition and effective Pareto Fronts and Reference Points generated during the evolutionary process to enhance the performance of the proposed approach. Our experimental results show that SPGA-II is able to improve the performance of SPGA in solving Parallel Machine Scheduling Problems.

並列關鍵字

Multi-objective Problems ； Tchebycheff Decomposition ； Parallel Flow-shop Scheduling ； Pareto front.

參考文獻

56.林昆霖，「子群體基因演算法於多目標排程之應用-以PCB鑽孔作業為例」，元智大學，碩士論文，2005。

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

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

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

1.Zhang, Q., Li, H., “MOEA/D: A Multiobjective Evolutionary Algorithm Base on Decomposition,” IEEE Transactions on Evolutionary Computation, 11 (6), pp. 712-731, 2007.