多樓層設施佈置問題是單樓層設施佈置問題的延伸，而其不同之處在於多樓層設施佈置問題有垂直搬運成本的考量，在目標函數值的考量上也因此變得更加複雜。設施規劃佈置問題為NP-Complete問題。本研究分別對單樓層同面積、單樓層不同面積、多樓層同面積與多樓層不同面積等四種設施佈置類型進行探討，其中多樓層設施佈置問題為本研究之主要探討重點。本研究針對多樓層設施佈置問題，建構蟻群演算法為例題測試之啟發式求解方法，以可接受的少許運算時間搜尋到穩健的目標函數值。本研究以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.

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii

第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究範圍與假設 3
1.4 研究流程 4
第二章 文獻探討 6
2.1 啟發式演算法 6
2.2 多樓層設施佈置 9
2.3 空間填滿曲線 (Space Filling Curve, SFC) 12
2.4 蟻群演算法 17
2.4.1 人工蟻群 18
2.4.2 蟻群演算法之虛擬碼 20
2.4.3 蟻群演算法之參數設定 22
2.4.4 蟻群演算法應用之領域 22
2.5 蟻群演算法相關文獻 23
2.5.1 螞蟻系統 (Ant System, AS) 24
2.5.2 評等為基螞蟻系統 (Rank-Based Version of Ant System, ASrank) 25
2.5.3 快速螞蟻系統 (Fast Ant System, FAS) 27
2.5.4 蟻群系統 (Ant Colony System, ACS) 28
2.5.5 極大-極小螞蟻系統 (Max-Min Ant System, MMAS) 30
2.5.6 隨機樹狀搜尋 (Approximate Nondeterministic Tree-Search, ANTS) 31
第三章 模式建立 33
3.1 目標模式建立 33
3.2 重心與距離之計算方式 34
3.2.1 重心之計算方式 35
3.2.2 距離之計算方式 35
3.3 設施擺放方式 41
3.3.1 單樓層設施佈置 41
3.3.2 多樓層設施佈置 41
3.4系統程式撰寫流程說明 42
3.4.1 蟻群演算法應用至QAP方法說明 43
3.4.2 機率轉移規則 43
3.4.3 費洛蒙更新規則 44
3.4.4 程式撰寫步驟說明 44
3.5 系統程式介面說明 47
第四章 案例驗證與結果分析 51
4.1 測試驗證環境 51
4.2 驗證例題 51
4.3 蟻群演算法之田口參數實驗設計 52
4.3.1 田口實驗設計簡介 53
4.3.2 田口實驗設計可控制因子之設定 54
4.3.3 例題參數之田口實驗設計 55
4.4 例題測試與結果分析 64
4.4.1 單樓層同面積設施佈置例題之比較分析 64
4.4.2 單樓層不同面積設施佈置例題之比較分析 70
4.4.3 多樓層同面積設施佈置例題之比較分析 74
4.4.4 多樓層不同面積設施佈置例題之比較分析 80
第五章 結論與建議 88
5.1 結論 88
5.2 建議與未來研究方向 89

參考文獻 90
附錄一 單樓層同面積例題流量表 97
附錄二 單樓層同面積例題初始排序與成本 102
附錄三 單樓層同面積例題最佳設施排序與成本 104
附錄四 單樓層不同面積例題流量表 106
附錄五 多樓層同面積例題流量表 109
附錄六 多樓層同面積例題初始排序與成本 112
附錄七 多樓層不同面積例題流量表 114

廖峻谷，「以模擬退火求解多樓層設施規劃問題」，元智大學工業工程研究所，碩士論文，1994。
呂昌儒，「應用模糊理論求解多目標設施規劃問題」，元智大學工業工程研究所，碩士論文，1996。
劉錦湧，「應用基因演算法於設施佈置問題之研究」，元智大學工業工程研究所，碩士論文，1997。
古美玉，「應用模擬退火法於椎脊式設施規劃之研究一以半導體廠為例」，元智大學工業工程研究所，碩士論文，1999。
鄒少雄，「使用雙向天車下晶圓廠設施佈置之研究」，中原大學工業工程研究所，碩士論文，1999。
簡文璋，「探討質化與量化因子在晶圓廠設施佈置之研究」，中原大學工業工程研究所，碩士論文，2000。
沙永傑，「設施佈置問題的文獻探討與分析」，Journal of the Chinese Institute of Industrial Engineers, Vol. 18, No. 1, pp. 55-73, 2001。
徐益興，「利用門檻接受法求解考慮電梯配置之多樓層設施規劃問題之研究」，中華大學工業工程研究所，碩士論文，2001。
尤子玲，「以相鄰為評估基礎之設施佈置問題」，元智大學工業工程研究所，碩士論文，2002。
王明展，「基因演算法應用於設施佈置問題之研究」，元智大學工業工程研究所，博士論文，2003。
郭獻隆，「多樓層倉儲系統中專用儲位與垂直搬運設備之佈置設計」，成功大學工業管理研究所，碩士論文，2003。
姜淑真，「多樓層設施佈置研究-以懸吊式物料搬運系統探討」，雲林科技大學工業工程研究所，碩士論文，2003。
陳譽升，「應用蟻群演算法於半導體晶圓廠之設施規劃問題」，元智大學工業工程研究所，碩士論文，2005。
陳怡妏，「應用蟻群尋優法探討以緊密度為評估基礎之設施佈置問題」，元智大學工業工程研究所，碩士論文，2005。
Armour, G. C., and E. S. Buffa, “A Heuristic Algorithm and Simulation Approach to Relative Location of Facilities,” Management Science, Vol. 9, No. 2, pp. 294-309, 1963.
Ball, M. O., B. K. Kaku and A. Vakhutinsky, “Network-based Formulations of the Quadratic Assignment Problem,” European Journal of Operational Research, Vol. 104, No. 1, pp. 241-249, 1998.
Banerjee, P., “A Manufacturing Layout Reasoning Architecture Based on Automated Integration of Linear Objective Optimization and Non-Linear Qualitative Analysis,” Ph. D. Thesis, Purdue University, West Lafayette, Indian. 1990.
Banerjee, P. and Zhou Y., “Facilities Layout Design Optimization with Single Loop Material Flow Path Configuration,” International Journal of Production Research, Vol. 33, No. 1, pp. 183-203, 1995.
Binaghi, E., “A Fuzzy Logic Inference Model for a Rule-based System in Medical Diagnosis,” Expert System, Vol. 7, No. 3, pp. 134-141, 1990.
Bozer, Y. A., R. D. Meller, and S. J. Erlebacher, “An Improvement-Type Layout Algorithm for Single and Multiple-Floor Facilities,” Management Science, Vol. 40, No. 7, pp. 918-932, 1994.
Bozer, Y. A. and R. D. Meller, “A New Simulated Annealing Algorithm for the Facility Layout Problem,” International Journal of Production Research, Vol. 34, No. 6, pp. 1675-1692, 1996.
Bozer, Y. A. and R. D. Meller, “Alternative Approaches to Slove the Multi-Floor Facility Layout Problem,” Journal of Manufacturing Systems, Vol. 16, No. 3, pp. 192, 1997.
Bullnheimer, B., R. F. Hartl, and C. Stauss, “A New Rank Based Version of the Ant System-A Computational Study,” Technical Report POM-03/97, Institute of Management Science, University of Vienna, Austria, 1999.
Donaghey, C. E., and V. F. Pire, “Solving the Facility Layout Problem with BOLCPLAN,” Industrial Engineering Department, University of Houston, TX, 1990.
Dorigo, M., Maniezzo, V., and Colorni, A., “Positive Feedback as a Search Stratey,” Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, IT, 1991.
Dorigo, M., “Optimization, Learning and Natural Algorithms,” Ph. D. Thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992.

Dorigo, M., “Ant System: Optimization by a Colony of Cooperatimg Agents,” IEEE Transaction on Systems, Vol. 26, No.1, pp. 29-41, 1996.
Dorigo, M. and L. M. Gambardella, “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66, 1997.
Dorigo M., Di Caro, G. and Gambardella. L. M., “Ant Algorithms for Discrete Optimization,” Artificial Life, Vol. 5, No. 2, pp. 137-172, 1999.
Francis, R. L., L. F. McGinnis, Jr., and J. A. White, “Facility Layout and Location: An Analytical Approach,” 2nd, ed., Prentice Hall, 1992.
Gambardella, L. M., Taillard, E. D. and Agazi, G., “MACS-VRTW: An Multiple Ant Colony System for Vehicle Routing Problem with Time Windows,” In D. Corne, M. Dorigi, and F. Glover editor, New Ideas in Optimization, McGraw-Hill, London, UK, pp. 63-76, 1999.
Goldberg, D. E., “Genetic Algorithms: in Search, Optimization and Machine Learning,” Addison Wesley, 1963.
Hassan, M. M. D., G.L. Hogg and D. R. Smith, “SHAPE: A Construction Algorithm for Area Placement Evaluation,” International Journal of Production Research, Vol. 24, No. 5, pp. 1283-1295, 1986.
Helm, S. A. and S. W. Hadley, “Tabu Search Based Heuristics for Multi-floor Facility Layout,” International Journal of Production Research, Vol. 38, No. 2, pp. 365-383, 2000.
Hillier, F. S., “Quantitative Tools for Plant Layout Analysis,” Journal of Industrial Engineering, Vol. 14, No. 1, pp. 33-40, 1963.
Hillier, F. S. and M. M. Conners, “Quadratic Assignment Problem Algorithms and the Locations of Indivisible Facilities,” Management Science, Vol. 13, No. 1, pp. 42-57, 1966.
Hu, M. H., “Microcomputer Aided Facility Layout Via Graphics-MIFLAG II,” Proceedings of 1988 Annual CIIE Conference, pp. 615-640, 1988.
Iman, M. H., and M. Mir, “Automated Layout of Facilities of Unequal Areas,” Computers & Industrial Engineering, Vol. 24, No. 3, pp. 355-366, 1993.
Irvine, S. A. and I. R. Melchert, “A New Approach to the Block Layout Problem,” International Journal of Production Research, Vol. 35, No. 8, pp. 2359-2376, 1997.
Jajodia, S., I. Minis, G. Harhalakis and J. M. Proth, “CLASS: Computerized Layout Solutions Using Simulated Annealing,” International Journal of Production Reasearch, Vol. 30, No. 1, pp. 95-108, 1992.
Johnson, R. A. and D. W. Wichern, “Applied Multivariate Statictical Analysis,” Prentice Hall, 1982.
Johnson, R. V., “Spacecraft for Multi-floor Layout Planning,” Management Science, Vol. 28, No. 4, pp. 407-417, April, 1982.
Kaku, B. K., G. L. Thompson and I. Baybars, “A Heuristic Method for The Multi-story Layout Problem,” European Journal of Operational Research, Vol. 37, No. 3, pp. 384-397, 1988.
Kaku, B. K., G. L. Thompson and T. E. Morton, “A Hybrid Heuristic for the Facilities Layout Problem,” Computers & Operations Research, Vol. 18, No. 93, pp. 241-253, 1991.
Kerr, R., “Knowledge-Based Manufacturing Management,” Addison Wesley Publishing Co. Inc., Sydney, 1991.
Kusiak, A. and S. S. Heragu, “The Facility Layout Problem,” European Journal of Operational Research, Vol. 29, No. 3, pp. 229-251, 1987.
Lee, K. Y., M. I. Roh and H. S. Jeong, “An Improved Genetic Algorithm for Multi-floor Facility Layout Problems Having Inner Structure Walls and Passages,” Computers & Operations Research, Vol. 32, No. 4, pp. 879-899, 2005.
Lee, R. C., and J. M. Moore, “CORELAP-Computerized Relationship Layout Planning,” Journal of Industrial Engineering, Vol. 18, pp. 195-200, 1967.
Lee, S. G., T. C. Chung, and T. U. Jung, “An Effective Dynamic Weighted Rule for Ant Colony System Optimization,” Proceedings of the Congress on Evolutionary Computation, Vol. 2, pp. 1393-1397, 2001.
Liggett, R. S. and W. J. Mitchell, “Optimal space planning in practice,” reprinted from Computer Aided-Design, pp. 91-102, September, 1981.
Liggett, R. S. and W. J. Mitchell, “Interactive Graphic Floor Plan Layout Method,” Journal of Computer Aided-Design, Vol. 13, No. 5, pp. 277-288, September, 1981.
Ligget R. S., “Automated Facilities Layout:Past, Present and Future,” Automation in Construction, Vol. 9, No. 2, pp. 197-215, 2000.
Maniezzo, V., “Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem,” Technical Report CSR 98-1, C.L. in Scienze dell’Informazione, Universita di Bologna, Sede di Cesena, Italy, 1998.
Maniezzo, V., and A. Colorni, “The Ant System Applied to the Quadratic Assignment Problem,” IEEE Transactions on Knowledge Data Engineering, Vol. 11, No. 5, pp. 769-778, 1999.
Matsuzaki, K., T. Irohara and K. Yoshimoto, “Heuristic Algorithm to Solve the Multi-floor Layout Problem with the Consideration of Elevator Utilization,” Computers & Industrial Engineering, Vol. 36, No. 2, pp. 487-502, April, 1999.
Merz, P. and M. Middendorf, “A Comparison of Memetic Algorithms, Tabu Search, and Ant Colonies for the Quadratic Assignment Problem,” Proceedings of the Congress on Evolutionary Computation, pp.2063-2070, 1999.
Muther, R., “Systematic Layout Planning,” Industrial Institute, Boston, 1961.
Nugent, E. and T. E. Vollmann “An Experiment Comparison of Technique for the Assignment of Facility to Locations,” Operations Research, Vol. 16, No. 1, pp.150-173, 1968.
Patsiatzis, D. I. and Lazaros G. Papageorgiou, “Optimal Multi-floor Process Plant Layout,” Computers & Chemical Engineering, Vol. 26, No. 4-5, pp. 575-583, 2002.
Pesch, E., F. Glover, T. Bartsch, F. Salewski and I. Osman, “Efficient Facility Layout Planning Maximally Planar Graph Model,” International Journal of Operations and Production Management, Vol. 37, No. 2, pp. 263-283, 1999.
Raoot, A. D. and A. Rakshit, “An Experimental Comparison of Systematic Placement Procedures for Facility Layout Design,” International Journal of Production Research, Vol. 31, No. 7, pp. 1735-1756, 1993.
Raoot, A. D. and A. Rakshit, “A ‘FUZZY’ Heuristic for the Quardratic Assignment Formulation to the Facility Layout Problem,” International Journal of Production Research, Vol. 32, No. 3, pp. 563-581, 1994.
Sahni, S. and T. Gonzalez, “P-Complete Approximation Problem,” Journal of Associated Computing Machinery, Vol. 23, No. 3, pp. 555-565, 1976.
Scriabin, M. and R. C. Vergin, “A Cluster-Analytic Approach to Facility Layout,” Management Science, Vol. 31, No. 1, pp. 33-49, 1985.
Seehof, J. M. and W. O. Evans, “Automated Layout Design Program,” Journal of Industrial Engineering, Vol. 18, pp. 690-695, 1967.
Sharpe, R., ans B. S. Marksjo, “Solution of the Facilities Layout Problem Simulated Annealing,” Computers in Environment and Urban System, Vol. 11, No. 4, pp. 147-154, 1986.
Shyu, S. J., B. M. T. Lin and P. Y. Yin, “Application of Ant Colony Optimization for No-wait Flowshop Scheduling Problem to Minimize the Total Complete Time,” Computers & Industrial Engineering, Vol. 47, No. 2-3, pp.181-193, 2004.
Stutzle, T., “An Ant Approach to the Flow Shop Problem,” Technical Report AIDA-97-07, FG Intellektik, FB informatik, TH Darmstadt, September, 1997.
Stutzle, T. and H. Hoos, “The MAX-MIN Ant System and Local Search for The Traveling Salesman Problem,” Proceeding of IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference, pp. 309-314, 1997.
Stutzle, T. and H. Hoos, “Improvement on the Ant System: Introducing the MAX-MIN Ant System,” In R.F. Albrecht G.D. Smith, N.C. Steele, editors, Artificial Neural Networks and Genetic Algorithms, pp. 245-249, Springer Verlag, New York, 1998.
Stutzle, T. and H. Hoos, “MAX-MIN Ant System,” Future Generation Computer System, Vol. 16, No. 8, pp. 889-914, 2000.
Taillard, E. D. and L. M. Gambardella, ”Adaptive Memories for the Quadratic Assignment Problem,” Technical Report IDSIA-87-97, Lugano,1997.
Talbi, E-G., O. Roux, C. Fonlupt, D. Robillard, “Parallel Ant Colonies for the quadratic assignment problem,” Future Generation Computer Systems, Vol.17, No. 4, pp. 441-449, 2001.
Tam, K. Y., “A Simulated Algorithm for Allocating Space to Manufacturing Cells,” International Journal of Production Research, Vol. 30, No. 1, pp. 63-87, 1992.

T''kindt, V., N. Monmarché, F. Tercinet and D. Laügt, “An Ant Colony Optimization Algorithm to Solve a 2-machine Bicriteria Flowshop Scheduling Problem,” European Journal of Operational Research, Vol. 142, No. 2, pp. 250-257, 2002.
Tompkins, J. A., J. A. White, Y. A. Bozer, E. H. Frazelle, J. M. A. Tanchoco and J. Trevino, “Facilities Planning,” Wiley and Son, New York, 1996.
Wang, H. P. and R. A. Wysk, “An Expert System for Machining Data Selection,” Computer & Industrial Engineering, Vol. 10, No. 2, pp. 99-107, 1985.
Ying-Chin Ho and Colin L. Moodie, “A Hybrid Approach for Concurrent Layout Design of Cells and Their Flow Paths in a Tree Configuration,” International Journal of Production Research, Vol. 38, No. 4, pp. 895-928, 2000.