蟻群最佳化演算法於多目標平行機台排程問題之研究

Ant Colony Optimization for Multi-Objective Parallel Machine Scheduling Problem

蕭裕民(Yu-Ming Hsiao)

指導教授 ： 梁韵嘉

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

摘要

製造系統中為了提升瓶頸工作站的效率以縮短製程時間，常把多台相同性質的機台擺放一起並同時運作，此即為平行機台的佈置方式。過往有關於平行機台排程的文獻，都是針對單一目標式求取其最佳解，顯然地已不符合日益複雜的生產環境，實際的生產環境中應該是多個目標列入衡量，而且各目標彼此之間存在相互衝突的現象，本研究同時考慮最大完工時間及總延遲時間兩個目標。近年來，蟻群最佳化演算法已成功應用在組合最佳化問題且越來越多學者開始採用此方法，由於平行機台排程問題屬於NP-hard問題，因此利用蟻群最佳化演算法進行求解。
本研究一共提出了三種多蟻群最佳化演算法架構，用以搜尋多目標平行機台排程問題的柏拉圖前緣，在多蟻群最佳化演算法中，分成三至五群蟻群進行求解，每群蟻群針對各自的目標式進行搜尋。不同架構的多蟻群最佳化演算法，其兩階段建構解的方式及費洛蒙更新方式均有所不同。利用國內某印刷電路板廠的實際生產數據作為測試例題，三種架構的多蟻群最佳演算法互相比較並和文獻上SPGA、MOGA、NSGA-II與SPEA-II四種演算法比較各自演算法的求解表現。實驗結果顯示架構一之多蟻群最佳化演算法 (ACO-I) 是多種演算法中，求解表現最好的方法。

關鍵字

蟻群最佳化演算法 ； 多目標 ； 平行機台 ； 最大完工時間 ； 總延遲時間

並列摘要

The arrangement of identical parallel machines is a common and practical approach to improve the efficiency of bottleneck workstations in a production system. In the literature, most of researches while scheduling parallel machines focused on the optimization of a single objective, but it obviously can no longer satisfy the demand of complex production systems nowadays. This study therefore seeks to deal with two conflicting objectives makespan and total tardiness simultaneously. The NP-hard property of the problem has made meta-heuristics be potential candidates for solving techniques. Recently, ant colony optimization (ACO) has shown its success in combinatorial optimization problems, and being a population-based search technique.
This study proposes three multiple ant colony optimization (MACO) algorithms to find the Pareto front for the multi-objective identical parallel machines scheduling problem (MOIPMSP). In the MACO algorithms, three or five ant colonies are adopted. Each ant colony explores he search space based on different objectives. The MACO algorithms have their own two-phase construction processes and pheromone updating rules. The performance of MACO is compared with each other and SPGA, MOGA, NSGA-II and SPEA-II from the literature. The test data is from a leading printed circuit board (PCB) factory in Taiwan. The computational results show that the MACO algorithm is a promising approach to solve the MOIPMSP.

並列關鍵字

Ant Colony Optimization, Multi-Objective, ； Parallel Machines Scheduling, Makespan ； Total Tardiness

參考文獻

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

李勝隆，2004，「基因演算法於印刷電路板鑽孔排程之應用」，元智大學，碩士論文。

陳柔君，2005，「蟻群演算法於等效平行機台排程問題之研究」，元智大學，碩士論文。

洪琦茹，2005，「蟻群演算法於單機多目標排程問題之應用」，元智大學，碩士論文。

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