跳到主要內容

臺灣博碩士論文加值系統

(3.229.142.104) 您好!臺灣時間:2021/07/30 15:15
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:蔡曉政
研究生(外文):Siao-Jheng Cai
論文名稱:以邊界搜尋為基之基因演算法於設施佈置問題
論文名稱(外文):A Genetic Algorithm with Boundary Search for The Facility Layout Problem
指導教授:林志平林志平引用關係王明展王明展引用關係
指導教授(外文):Chih-Ping LinMing-Jaan Wang
口試委員:楊明峰
口試委員(外文):Ming-Feng Yang
口試日期:2012-06-20
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:工業工程與管理系碩士班
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:76
中文關鍵詞:邊界搜尋法連續型設施佈置問題基因演算法面積利用率
外文關鍵詞:Continuous facilities layoutBoundary search heuristicGenetic algorithmArea utilization
相關次數:
  • 被引用被引用:0
  • 點閱點閱:170
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
設施佈置是一種藉由指派或調整設施之間的相關位置,進而使系統以最佳的效率及最低的成本來進行生產。欲使系統中的所有的生產要素達到最有效的組合與分配,就必須仰賴良好的設施佈置方案,以高效率生產流程來降低的企業營運及土地購置成本。
在過去的研究中,趨近於二維平面轉為網路架構的連續型設施佈置問題於利用演算法計算時,需進行龐大的平行處理而使大規模設施佈置問題求解受限。然而邊界搜尋概念的出現則為大規模設施佈置問題帶來契機,邊界搜尋概念僅考量已配置部門之邊界作為配置可行性評估,將二維搜尋空間轉為一維搜尋空間,如此不僅大幅降低了計算程序的複雜性,相對於大規模的設施佈置問題也能求解出更有效的解決方案。
本研究除加入面積利用率之考量來架構其目標函式以解決連續型設施佈置問題之面積利用率過小的情況外,更透過邊界搜尋概念來界定出部門間配置的相關性進而產生出佈置方案特徵編碼來進行改良程序,並導入基因演算法之交配機制及突變機制來尋求較佳的佈置方案為主要核心研究。

Facilities layout is a professional technique to assign departments to the appropriate location, and to reach the minimal handling cost and land cost for a system. In addition, an appropriate layout could improve the productivity, increase the production efficiency and cost down the operation expenses of a system.
Many papers are published about continuous layout problem (CLP), CLP is to place the departments anywhere within a plant site without overlapping each others. CLP is base on two dimensions framework problem, however, to find the optimal layout cost of larger departments is too complexity and time-consuming. Boundary search heuristic (BSH) is a dimension schema for solving CLP, BSH could reduce the computing time and dealing with much more feasible for facilities layout problem. In order to eliminate redundant area and evaluate the layout cost of CLP, a factor of area utilization is considered in objective function of this research. Through BSH to define the correlation between the departments, and then generate the characteristics of layout design to encode. By Genetic Algorithms to achieve the improvement of BSH.

目錄
摘要 i
ABSTRACT ii
誌謝 iv
目錄 v
表目錄 vii
圖目錄 viii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與假設 3
1.4 研究流程 4
第二章 文獻探討 6
2.1 設施佈置問題 6
2.2 連續型長寬固定不相等面積部門之設施佈置問題 8
2.3 邊界搜尋技術 11
2.3.1 P/D之應用 12
2.3.2 TS/BSH及CBA間的差異 16
2.4 小結 23
第三章 模型建立與求解方法 24
3.1 模型建立 24
3.2 選擇及配置程序 26
3.2.1 可行解範圍定義 26
3.2.2 配置程序 28
3.3 改良程序 33
3.3.1 編碼 33
3.3.2 導入基因遺傳演算法之改良程序 35
第四章 實驗設計與結果分析 42
4.1 案例說明 42
4.2 參數設計 43
4.2.1 決定控制因子與水準數 43
4.2.2 田口直交表 44
4.2.3 田口試驗 45
4.3 案例驗證 48
4.3.1 案例1 - CBA (Imam and Mir, 1998) 48
4.3.2 標竿案例2 - L008-IM 49
4.3.3 標竿案例3 - L020-MI 53
4.3.4 標竿案例4 - L050 58
4.3.5 標竿案例5 – L100 63
4.4 案例分析總結 66
4.4.1 求解效率 66
4.4.2 面積利用率 67
4.4.3 小結 69
第五章 結論與建議 70
5.1 結論 70
5.2 研究貢獻 71
5.3 未來研究與建議 72
參考文獻 73

表目錄
表4.1 程式執行環境 42
表4.2 OHU-FLP之標竿案例 43
表4.3 控制因子與水準數 44
表4.4 L9直交表 45
表4.5 L9直交表轉換參數 45
表4.6 L008-IM之參數組合與S/N值 46
表4.7 因子水準之S/N回應值表 47
表4.8 GA/BSH初始解與CBA之結果比較表 49
表4.9 L008-IM之結果比較表 51
表4.10 L020-MI之結果比較表 55
表4.11 L050之結果比較表 60
表4.12 L100之結果比較表 64
表4.13 GA/BSH優於各演算法目標函數值之求解時間 67

圖目錄
圖1.1 間斷型及連續型佈置問題之配置方案 2
圖1.2 研究流程圖 5
圖2.1 Norman and Smith所提出的設施佈置方案完成圖 7
圖2.2 狹長形部門示意圖 8
圖2.3 Miao and Xu所提出之最佳佈置方案圖 10
圖2.4 Ohmori, Yoshimoto and Ogawa提出以PSO改良之設施佈置方案圖 11
圖2.5 Deb and Bhattacharyya所提出部門間非重疊示意圖 13
圖2.6 部門配置時P/D點後選位置示意圖 14
圖2.7 Deb and Bhattacharyyan所提出12種P/D點配置方案圖 15
圖2.8 Deb and Bhattacharyya求解12個部門之近似最佳佈置方案圖 15
圖2.9 四種CBA部門配置情形 18
圖2.10 CBA搜尋邊界之可行解範圍 20
圖2.11 CBA之映射邊界與目標函數值關係圖 20
圖2.12 BSH之已配置部門上下左右邊界示意圖 21
圖3.1 傳統邊界搜尋概念之配置順序圖 27
圖3.2 可行解範圍之差異 27
圖3.3 可行解範圍大小受限於已配置部門 28
圖3.4 以部門A為核心部門之邊界搜尋配置結果 29
圖3.5 與未配置部門之流量決定LEVEL內部門可行解配置順序示意圖 30
圖3.6 LEVEL 2配置完成圖 30
圖3.7 配置流程圖 32
圖3.8 CBA之搜尋邊界示意圖 33
圖3.9 本研究之分段邊界搜尋概念示意圖 34
圖3.10 配置完成所形成之初始解 34
圖3.11 初始配置方案之染色體示意圖 36
圖3.12 交配機制之基因選定示意圖 36
圖3.13 基因交換完成示意圖 37
圖3.14 交配機制完成示意圖 38
圖3.15 突變機制之基因選定示意圖 38
圖3.16 突變機制完成示意圖 39
圖3.17 改良程序流程圖 41
圖4.1 各因子水準S/N值回應圖 47
圖4.2 L008-IM最佳值收斂圖 50
圖4.3 BITOPT於L008-IM案例之最佳配置圖 52
圖4.4 L020-MI最佳值收斂圖 54
圖4.5 HOT於L020-MI案例之最佳配置圖 56
圖4.6 L050最佳值收斂圖 59
圖4.7 HOT於L050案例之最佳配置圖 61
圖4.8 L100最佳值收斂圖 64
圖4.9 VIP-PLANOPT 2010於L100案例之最佳配置圖 65
圖4.10 面積利用率比較圖 68
圖4.11 GA/BSH與VIP-PLANOPT 2010 及MA之減少成本關係圖 68

[1] R. R. Levary and S. Kalchik, “Facilities layout – A survey of solution procedures,” Computers and Industrial Engineering, vol. 9, no. 2, 1985, pp. 141-148.
[2] J. A. Tompkins, J. A. White, Y. A. Bozer, E. H. Frazelle, J. M. A. Tanchoco, and J. Trevino, Facilities Planning, Wiley, 1996.
[3] T. C. Koopmans, and M. Beckman, “Assignment Problems And The Location Of Economic Activities,” Econometrica, vol. 25, no. 1, 1957, pp. 53-76.
[4] Y. A. Bozer and R. D. Meller, “A new simulated annealing algorithm for the facility layout problem,” International Journal of Production Research, vol. 34, no. 6, 1996, pp. 1675-1692.
[5] J. S. Kochhar, B. T. Foster and S. S. Heragu, “HOPE: A genetic algorithm for the unequal area facility layout problem,” Computers and Operation Research, vol. 25, 1997, pp. 583-594.
[6] K. Y. Tam, “A Simulated Annealing Algorithm For Allocating Space To Manufacturing Cells,” International Journal Of Production Research, vol. 30, 1992, pp. 63-87.
[7] D. M. Tate and A. E. Smith, “Unequal Area Facility Layout Using Genetic Search,” Journal of IIE Transactions, vol.27, issue 4, 1995, pp. 465-472.
[8] M. H. Imam, and M. Mir, “Cluster Boundary Search Algorithm For Building-block Layout Optimization,” Advances In Engineering Software, vol. 29, no. 2, 1998, pp. 165-173.
[9] A. R. Jr. McKendall and A. Hakobyan, “Heuristics For The Dynamic Facility Layout Problem With Unequal-area Departments,” European Journal of Operational Research, vol. 201, issue 1, 2010, pp. 171-182.
[10] D. M. Simmons, “One-Dimensional Space Allocation : An Ordering Algorithm,” Operations Research, vol. 17, no. 5, 1969, pp. 812-826.
[11] S. S. Heragu and A. Kusiak, “Efficient Models For The Facility Layout Problem,” European Journal Of Operational Research, vol. 53, 1991, pp. 1-13.
[12] S. S. Heragu and A. S. Alfa, ”Experimental Analysis Of Simulated Annealing Based Algorithms For The Layout Problem,” European Journal of Operations Research, vol. 57, 1992, pp. 190-202.
[13] M. S. Bazaraa, “Computerized Layout Design : A Branch And Boud Approach,” AIIE Transactions, vol. 7, no.4, 1975, pp. 432-438.
[14] P. S. Welgama, P. R. Gibson and L. A. R. Al-Hakim, “Facilities Layout: A Knowledge-Based Approach for Converting A Dual Graph Into A Block Layout,” International Journal of Production Economics, vol. 33, 1994, pp. 17-30.
[15] B. A. Norman, A. E. Smith, and R. A. Arapoglu, “Integrated Facility Design Using An Evolutionary Approach With A Subordinate Network Algorithm,” PSN V Proceedings of the 5th International Conference On Parallel Problem Solving from Nature, Springer-Verlag London, UK, 1998, pp. 937-946.
[16] Y. K. Chen, S. W. Lin and S. Y. Chou, “An Efficient Two-staged Approach for Generating Block Layouts,” Computers & Operations Research, vol. 29, 2002, pp. 489-504.
[17] B. H. Ulutas, S. Kulturel-Konak, “An Artificial Immune System Based Algorithm to Solve Unequal Area Facility Layout Problem,” Expert System with Application, vol. 39, 2012, pp. 5384-5395.
[18] Z. Miao and K. L. Xu, “Research Of Multi-rows Facility Layout Based On Hybrid Algorithm,” Informaion Management, Innovation Management and Industrial Engineering International Conference, vol. 2, 2009, pp. 553-556.
[19] S. Ohmori, K. Yoshimoto, K. Ogawa, “Solving Facility Layout Problem Via Particle Swarm Optimization,” Computational Science And Optimization, Third International Joint Conference, vol. 1, 2010, pp. 409-413.
[20] P. S. Welgama and P. R. Gibson, “A Construction Algorithm for The Machine Layout Problem With Pick-up and Drop-off Points,” International Journal of Production Research, vol. 31, no. 11, 1993, pp. 2575-2590.
[21] R. D. Meller and K. Y. Gau, “The Facility Layout Problem: Recent and Emerging Trends and Perspectives,” Journal of Manufacturing Systems, vol. 15, no. 5, 1996, pp.351-366.
[22] R. Tavakkoli-Moghaddam, “Mathematical Programming Models for Solving Unequal-Sized Facilities Layout Problems – A Generic Search Method,” International Journal of Engineering, vol. 12, no. 4, 1999, pp. 233-245.
[23] R. Tavakkoli-Moghaddam, “A Continuous Plane Model to Machine Layout Problems Considering Pick-Up and Drop-Off Points: An Evolutionary Algorithm,” IJE Transactions B: Applications, vol. 16, no. 1, 2003, pp. 59-70.
[24] G. H. Hu, Y. P. Chen, Z. D. Zhou and H. C. Fang, “A Genetic Algorithm for The Inter-cell Layout and Material Handling System Design,” Int J Adv Manuf Technol, vol. 34, 2007, pp. 1153–1163.
[25] S. K. Deb and B. Bhattacharyya, “Solution Of Facility Layout Problems With Pickup/Drop-off Locations Using Random Search Techniques,” International Journal of Production Research, vol. 43, no. 22, 2005, pp. 4787-4812.
[26] J. G. Kim and Y. D. Kim, “Layout Planning for Facilities with Fixed Shapes and Input and Output Points,” International Journal of Production Research, vol. 38, issue 18, 2000, pp. 4635-4653.
[27] L. Chwif, M. R. P. Barretto and L. A. Moscato, “A Solution to The Facility Layout Problem Using Simulated Annealing,” Computers in Industry, vol. 36, 1998, pp. 125–132.
[28] M. Mir and M. H. Imam, “A hybrid Optimization Approach for Layout Design of Unequal-Area Facilities,” Computer & Industrial Engineering, vol. 39, 2001, pp. 49-63.
[29] M. H. Imam and M. Mir, “Nonlinear Programming Approach to Automated Topology Optimization,” Computer-Aided Design, vol. 21 no. 2, 1989, pp. 107-115.
[30] M. Mir and M. H. Imam, “Topology Optimization of Arbitrary-Size Block Using A Bivariate Formulation,” Computer-Aided Design, vol. 24, 1992, pp. 556-564.
[31] I. A. Tasadduq, M.H. Imam and A. R. Ahmad, “Layout Design Benchmark Problems,” Working Paper, 2011, pp. 1-22.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top