臺灣博碩士論文加值系統

本論文主要是在設計一個考量出入口與走道空間分佈的智慧型設施自動配置系統。所建立的系統除了安排各子設施的位置外，也將建議適當的設施出入口位置，及走道空間與分佈的情形，而系統評量的重點也將於最小化物料處理成本之外加上最少走道空間的需求。論文中首先嘗試推演一套結合最短路徑 (shortest path)、遺傳演算法 (Genetic Algorithm, GA)、及啟發式規則 (heuristic rules) 的混合式基因演算法 (Hybrid Genetic Algorithm, HGA)，以使在產生設施配置的同時系統也自動地建議相關的出入口位置與走道分佈狀況。
論文中使用電腦程式建構所推導的演算法以對含有走道分佈及設施出入口考量的設施配置進行建構及改善的模擬，以建議有效且經濟的空間配置及走道空間的需求。因此本系統將會相當具實用價值。

This thesis proposes an intelligent aisle construction system for automated facility layout problem with indoor and outdoor consideration. So the proposed system not only generates a layout but also suggests the space and distribution of aisles and indoors. The objective function is to minimize material handling cost and aisle space requirement. Therefore, the theory of shortest path, genetic algorithm (GA), and heuristic rules were combined to derive a hybrid genetic algorithm (HGA), which will efficiently suggest layouts with door and aisle structure.
A software system was implemented, based on the proposed algorithm, to simulate examples of layouts. The proposed software system also contains an interactive user interface to help the modification of the suggested layouts, including the locations of sub-facility, the number and locations of doors, and the space and distribution of aisles.
This proposed research derive an efficient algorithm and implement a software system, includes the design of interactive user interface, to simulate examples of facility layout problems with door and aisle structure. So, the proposed intelligent aisle construction system for automated facility layout will be very efficient and practicable.

致 謝 I
摘 要 II
Abstract III
目 錄 IV
表目錄 VI
圖目錄 VII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 1
1.3 研究流程 2
第二章 文獻回顧 4
2.1 設施規劃之探討 4
2.1.1 設施規劃的定義及發展歷史 4
2.1.2 設施規劃的分類 6
2.2 基因演算法 7
2.2.1 基因演算法之組成元素 7
2.2.2 基因演化流程 8
2.2.3 染色體交配機制 8
2.3 圖學理論與最短路徑演算法 11
2.4 啟發式搜尋法 12
2.5 國內外相關研究 12
第三章 問題定義 15
第四章 演算法推演與分析 19
4.1 資料表示法 24
4.1.1 遺傳演算法的字串 (string) 24
4.1.2 運算過程的資料 (Working Data) 24
4.1.3 配置結果的相關資料 (Output Data) 32
4.2 建構演算法 (Construction Algorithm) 32
4.2.1 Transfer function 字串轉換兩維設施配置演算法 33
4.2.2 Door function 出入口選擇演算法 34
4.2.3 Distance (Aisle) function 門對門距離與走道演算法 38
4.3 改善演算法 (Improvement Algorithm) 43
4.3.1 Representor 44
4.3.2 Creator 44
4.3.3 Stop criteria 44
4.3.4 Evaluator 44
4.3.5 Generator 45
第五章 模擬與討論 49
5.1 總物料處理成本的分析討論 61
5.2 走道長度的分析 64
5.3 計算時間的分析 66
5.4 綜合討論 68
第六章 結論與建議 69
6.1 結論 69
6.2 建議及未來進階研究 69
參考文獻 71

[1] J. Koopmans, M. Beckmann, Assignment problems and location of economic activities, Econometrica 25 1967, pp53—76.
[2] E. Buffa, G. Armour, Allocating facilities with CRAFT, Harvard Business Rev. 42 2 1964, pp136—159.
[3] Lee R, Moore JM. CORELAP-computerized relationship layout planning. The Journal of Industrial Engineering 1967;18:195±200.
[4] Seehof JM, Evans WO. Automated layout design program. The Journal of Industrial Engineering 1967;18:690±5.
[5] Tompkins JA, Reed Jr R. An applied model for the facilities design problem. International Journal of Production Research 1976;14:583±95.
[6] J. Grason, An approach to computerized space planning using graph theory, Proceedings of the Design Automation Workshop, June 28—30, Atlantis City, NJ, IEEE, New York, 1971, pp. 170—179
[7] R. Muther, Systematic Layout Planning, Cahners Books, Boston, 1973.
[8] Chan KC and Tansri H, A study of genetic crossover operation on the facility layout problem, Computers & Industrial Engineering, Vol. 26, No. 3, 1994, pp.537-550.
[9] K. L. Mak, Y. S. Wong and F. T. S. Chan, A genetic alroritjm for facility layout problems, Computer Intergrated Manufacturing Systems, Vol. 11, No. 1-2, pp.113-127, 1998
[10] C. Eastman, Automated space planning, Artificial Intelligence 4 1973 41—64.
[11] C. Pfefferkorn, The design problem solver: a system for designing equipment or furniture layouts, in: C. Eastman Ed. , Spatial Synthesis in Computer-Aided Building Design, Wiley, New York, 1975, pp. 98—146.
[12] U. Flemming, R. Coyne, S. Fenves, J. Garrett, R. Woodbury, SEED─software environment to support the early phases in building design, Proc. IKM94, Weimar, Germany, 1994, pp. 5—10.
[13] U. Flemming, C. Baykan, R. Coyne, Hierarchical generate- _ . and-test versus constraint-directed search, in: J. Gero Ed. ,Proceedings of the Artificial Intelligence in Design Confer-ence ’92, Kluwer, Dordrecht, 1992, pp. 817—838.
[14] Akin, B. Dave, S. Pithavadian, Heuristic generation of layouts HeGeL : based on a paradigm for problem structuring, Environ. Plan. B: Plan. Des. 19 1992 33—59.
[15] C. Baykan, Formulating spatial layout as a disjunctive constraint satisfaction problem, Doctoral Dissertation, Department of Architecture, Carnegie Mellon University, 1991.
[16] K.C. Chan and H. Tansri, "A study of Genetic Crossover Operations on the Facilities Layout Problem," Computers Ind. Engr. Vol. 26, No.3, p537,,p550, 1994.
[17] David M. Tate and Alice Smith, "Unequal Area Facility Layout by Genetic Search, "IIE Transactions 27, p465,,p472, 1995.
[18] 張建邦, "應用遺傳演算法於服務系統設施細部佈置問題之研究 - 以醫院為例," 元智大學，工業工程研究所，碩士論文, 1997。
[19] Yavuz A. Bozer, Russell D. Meller, and Steven J. Erlebacher, "An Improvement-type Layout Algorithm for Single and Multiple-floor Facilities," Management Science, Vol. 40, No. 7, p918,,p932, 1994.
[20] Chae-Bogk Kim, "Algorithms for Automated Three Dimensional Facility Layout Problems," PH.D. Diss., The University of Oklahoma, 1992.
[21] Kenichiro Matsuzake, Takashi Ironhara, & Kazuho Yoshimoto, "Heuristic Algorithm to Solve the Multi-Floor Layout Problem with the Consideration of Elevator Utilization," Computers & Industrial Engineering, 36, p487,,p502, 1999.
[22] J.L.Lin, B. Foote, S.Pulat, C.H. Chang, and J.Y.Cheung, "Solving the Failure-to-fit Problem for Plant Layout: By Changing Department Shapes and Sizes," EJOR 89, p135,,p146, 1996.
[23] Panagiotis Kouvelis, & Michael W. Kim, "Unidirectional Loop Network Layout Problem in Automated Manufacturing Systems," Operations Research, Vol. 40, No. 3, p533,,p550, 1992.
[24] Ali S. Kiran, Ali Tamer Unal, & Selcuk Karabati, "A location problem on unicyclic networks: Balanced case," European Journal of Operational Research 62, p194,,p202, 1992.
[25] S.J.Tretheway & B.L.Foote, "Automatic computation and drawing of facility layouts with logical aisle structures," Int. J. Prod. Res., Vol. 32, No. 7, p1545,,p1555, 1994.
[26] P.Banerjee & Y.Zhou, "Facilities layout design optimization with single loop material flow path configuration," Int. J. Prod. Res., Vol.33, No.1, p183,,p203, 1995.
[27] P.S.Welgama & P.R. Gibson, "A Hybrid Knowledge Based / Optimization System for Automated Selection of Materials Handling System," Computers Ind. Engng. Vol.28, No.2, p205,,p217, 1995.
[28] B.Benson & B.L.Foote, "DoorFAST: A constructive procedure to optimally layout a facility including aisles and door locations based on an aisle flow distance metric," Int. J. Prod. Res., Vol. 35, No. 7, p1825,,p1842, 1997.