變動鄰域搜尋法於雙目標平行機台排程問題之研究

Variable Neighborhood Search for Bi-Objective Parallel Machine Scheduling Problem

田佳芸(Chia-Yun Tien)

指導教授 ： 梁韵嘉

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

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

摘要

在現實的印刷電路板（Printed Circuit Board；PCB）生產環境當中，平行機台為一普遍的生產佈置方式，其目的是為了提高整體的生產效率。有鑑於排程的單目標最佳化已逐漸無法滿足管理者的要求，管理者常會將多個目標作為績效衡量指標，並視為訂定決策時的考量項目，而且各個目標彼此之間存在著相互衝突的現象。由於多目標問題屬於NP-Hard問題，一般無法精確地定義出所謂的最佳解，而是必須透過柏拉圖前緣（Pareto Front）有關非支配解的搜尋，以提供決策者在面對多個相互衝突的目標時，有關求解問題之可行方案。因此，過去學者所提出的簡單排程法則已逐漸不敷使用，採行啟發式演算法遂成為一種趨勢。
本研究主要為利用一變動鄰域搜尋法（Variable Neighborhood Search；VNS）求解雙目標完全相同平行機台排程問題，目標為同時考量最大完工時間以及總延遲時間最小化。根據建構解方式以及演算架構的不同而分為四種不同的VNS方法，分別為：VNS-I、VNS-Ⅱ、VNS-III以及VNS-IV，透過國內某印刷電路板廠的實際生產數據作為測試例題，不僅比較了四種不同VNS之表現優劣，更與文獻中之SPGA、ACO-I、TWMGS以及SSA-SPGA方法進行比較，其結果顯示VNS求解績效表現良好。

關鍵字

變動鄰域搜尋法 ； 完全相同平行機台 ； 最大完工時間 ； 總延遲時間

並列摘要

Among all types of production environment, identical parallel machines are frequently used to increase the manufacturing capacity in Taiwan printed circuit board (PCB) industries. Additionally, multiple but conflicting objectives are usually considered when a manager plans the production scheduling. Compared to the single objective problem, the multiple-objective version no longer looks for an individual optimal solution; instead a Pareto front consisting of a set of non-dominated solutions will be established. The manager then can select one of the alternatives from the set. The identical parallel machine scheduling problem falls in the class of NP-Hard; therefore, metaheuristics have been commonly employed as the solving technique.This research aims at employing Variable Neighborhood Search（VNS）to solve the identical parallel machine scheduling problem with two conflicting objectives: makespan and total tardiness. According to the differences of the solution construction rules and the frameworks, our VNS can be divided into four categories: VNS-I, VNS-Ⅱ, VNS-Ⅲ, and VNS-IV. The performance of the proposed algorithm is tested on a set of real data collected from a leading PCB factory in Taiwan. The computational results show that our VNS algorithm outperforms four competing algorithms – SPGA, ACO-I, TWMGS, and SSA-SPGA in terms of solution quality and computational time.

並列關鍵字

Variable Neighborhood Search ； Identical Parallel Machine ； Makespan ； Total Tardiness

參考文獻

2. 李家智，2006，「順序性移動式精英政策之子群體基因演算法於多目標問題之應用」，元智大學，碩士論文。

6. 陳啟嘉，2006，「基因結構探勘於承接式子群體基因演算法求解多目標組合性問題」，元智大學，碩士論文。

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

7. 蕭裕民，2006，「蟻群最佳化演算法於多目標平行機台排程問題之研究」，元智大學，碩士論文。

5. 陳怡靜，2005，「變動鄰域搜尋法於串並聯系統複置配置問題之研究」，元智大學，碩士論文。