蟻群演算法應用於多樓層設施規劃問題

Applying Ant Colony Optimization Algorithm to the Multiple-Floor Facilities Layout Problem

張俊隆(Chun-Lung Chang)

指導教授 ： 胡黃德

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

摘要

多樓層設施佈置問題是單樓層設施佈置問題的延伸，而其不同之處在於多樓層設施佈置問題有垂直搬運成本的考量，在目標函數值的考量上也因此變得更加複雜。設施規劃佈置問題為NP-Complete問題。本研究分別對單樓層同面積、單樓層不同面積、多樓層同面積與多樓層不同面積等四種設施佈置類型進行探討，其中多樓層設施佈置問題為本研究之主要探討重點。本研究針對多樓層設施佈置問題，建構蟻群演算法為例題測試之啟發式求解方法，以可接受的少許運算時間搜尋到穩健的目標函數值。本研究以Y方向掃描法為佈置空間的方法，將蟻群演算法對於多樓層設施佈置問題所搜尋到的設施佈置排序，以無先分層的動作而直接進行設施之佈置。本研究為將蟻群演算法應用於多樓層設施規劃問題，藉由田口實驗設計，配適蟻群演算法於多樓層設施佈置問題之最佳參數組合，對本研究測試例題進行結果分析與探討。測試結果顯示本研究之蟻群演算法所求得之目標函數值皆優於以往相關文獻研究方法之目標函數值。此外，本研究對改變佈置空間之面積形狀進行測試，測試結果顯示相同佈置面積但不同形狀之佈置空間求解，確實可以改善目標函數值。

關鍵字

多樓層設施佈置 ； 蟻群演算法 ； Y方向掃描法 ； 田口實驗設計

並列摘要

A multiple-floor facilities layout (MFFL) problem is an extension of a single-floor facilities layout (SFFL) problem. The difference between MFFL and SFFL is that the MFFL additionally requires considering vertical handling cost, implying that a MFFL problem is more difficult to solve than a SFFL problem. Moreover, a MFFL problem is an NP-complete problem. This research developed an efficient ant colony optimization (ACO) technique to slove the MFFL problems. The proposed ACO approach was used to solve a set of testing MFFL problems, including the same area in single-floor, different area in single-floor, the same area in multiple-floor and different area in multiple-floor. This research used Y-oscillatory sweep method to generate facilities layout without prior to assign appropriate facilities for each floor level, and employed Taguchi method to find the optimal combination of parameters of the proposed ACO technique. Numerical results showed that the ACO solutions obtained from testing problems were superior to the solutions published in the literature, and that the proposed ACO approach required less computation time. Also, the additional relaxation of the floor area constraint can have better solutions than those of the traditional fixed area.

並列關鍵字

Multiple-floor Facilities Layout ； Ant Colony Optimization ； Y-oscillatory Sweep Method ； Taguchi Method

參考文獻

廖峻谷，「以模擬退火求解多樓層設施規劃問題」，元智大學工業工程研究所，碩士論文，1994。

呂昌儒，「應用模糊理論求解多目標設施規劃問題」，元智大學工業工程研究所，碩士論文，1996。

劉錦湧，「應用基因演算法於設施佈置問題之研究」，元智大學工業工程研究所，碩士論文，1997。

古美玉，「應用模擬退火法於椎脊式設施規劃之研究一以半導體廠為例」，元智大學工業工程研究所，碩士論文，1999。

尤子玲，「以相鄰為評估基礎之設施佈置問題」，元智大學工業工程研究所，碩士論文，2002。