(3.227.235.183) 您好!臺灣時間:2021/04/18 11:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:王明展
研究生(外文):Ming-Jaan Wang
論文名稱:基因演算法應用於設施佈置問題之研究
論文名稱(外文):A Study of Facility Layout Problem by Genetic Algorithm
指導教授:胡黃德胡黃德引用關係
指導教授(外文):Michael H. Hu
學位類別:博士
校院名稱:元智大學
系所名稱:工業工程與管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:85
中文關鍵詞:基因演算法空間填滿曲線物料流動因素成本形狀比率因素面積利用率因素總佈置成本
外文關鍵詞:Genetic AlgorithmSpace Filling CurveMaterial Flow Factor CostShape Ratio FactorArea Utilization FactorTotal Layout Cost
相關次數:
  • 被引用被引用:19
  • 點閱點閱:505
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:129
  • 收藏至我的研究室書目清單書目收藏:0
基因演算法應用於設施佈置問題之研究
學生:王明展 指導教授:胡黃德 博士
元智大學工業工程與管理研究所
摘 要
尋找最低的物料搬運成本,是設施佈置設計人員長久以來追求的目標。然而大部門數的設施佈置其最佳解的求算常是耗時不易得的,因此許多的啟發式演算法如:模擬退火(Simulated Annealing, SA)、塔布搜尋(Tabu Search, TA)、基因演算(Genetic Algorithm, GA)等方法被發展出來,以求得近似最佳解。本論文使用基因演算法及應用專家系統IF-THEN的規則發展一套空間填滿曲線(Space Filling Curve, SFC),來求間斷式設施佈置的最佳解。有關面積相等部門的佈置問題,其目標函數值的衡量是以物料流動因素成本(Material Flow Factor Cost, MFFC)為唯一考量。而有關面積不相等部門的佈置問題,其目標函數值的衡量是以總佈置成本 (Total Layout Cost, TLC)最小為考量,TLC為一多考量因素的目標函數,除了考慮物料流動因素成本外,更加入了形狀比率因素(Shape Ratio Factor, SRF)及面積利用率因素(Area Utilization Factor, AUF)。過去已發表的間斷式設施佈置文獻,少有針對部門的不規則形狀與廠房面積使用情形作一衡量與改善。本論文提出一套改善面積100%使用與調整部門不規則形狀成規則矩形形狀的方法。經由八個面積相等、五個面積不相等案例的實證結果得知,不論在面積相等部門或面積不相等部門的設施佈置問題上,本論文所發展方法均獲得較佳的成效。
關鍵字:基因演算法、空間填滿曲線、物料流動因素成本、形狀比率因素、面積利用率因素、總佈置成本
A Study of Facility Layout Problem by Genetic Algorithm
Student : Ming-Jaan Wang Advisor : Dr. Michael H. Hu
Institute of Industrial Engineering and Management
Yuan-Ze University
ABSTRACT
Minimal material handling cost (MHC) achievement is one of the critical objectives in facilities layout problems for layout designers. However, solving the larger departments of facilities layout problem accompanying with the optimal MHC is time-consuming or even infeasible. Therefore, many heuristic algorithms such as simulated annealing (SA), tabu search (TA), and genetic algorithm (GA) were developed to find out near-optimal solutions for MHC. This study used genetic algorithm and a rule-based expert system to implement and create space filling curve (SFC), for achieving the optimal solution of the discrete facility layout problem. Concerning the equal area department problems, the objective function is mainly according to the measurement of material flow factor cost (MFFC). However, the objective function for unequal area department problem in this study is a multiple criteria, involving MFFC, shape ratio factor (SRF), and area utilization factor (AUF) to reach minimal total layout cost (TLC). Then, a method of modified the irregular-shape departments to regular-shape ones and eliminate the redundant areas based on the principle of 100% area utilization is proposed. The experimental results show that the proposed approach is much more feasible for dealing with the facilities layout problems and better than existed results.
Keyword: Genetic Algorithm, Space Filling Curve, Material Flow Factor Cost, Shape Ratio Factor, Area Utilization Factor, Total Layout Cost
目 錄
中文摘要……………………………………………………………………………….i
英文摘要………………………………………………………………………………ii
誌謝…………………………………………………………………………………...iii
目錄…………………………………………………………………………………...iv
表目錄………………………………………………………………………………...vi
圖目錄………………………………………………………………………………..vii
第一章 緒論..………………………………………………………………………..1
1.1研究背景與動機……………………………………………………………….1
1.2研究目的……………………………………………………………………….4
1.3研究範圍與限制……………………………………………………………….5
1.4研究架構……………………………………………………………………….5
第二章 文獻回顧……………………………………………………………………7
2.1面積相等部門的設施佈置問題………………………………………………7
2.1.1數學模式…………………………………………………………….7
2.1.2最佳化方法………………………………………………………….8
2.1.3次佳解的啟發式演算方法………………………………………….9
2.1.4近似最佳解的啟發式演算方法……………………………………10
2.2面積不相等部門的設施佈置問題…………………………………………...11
2.2.1數學模式……………………………………..……………………..12
2.2.2求解的方法…………………………………………..……………..13
2.2.3近似最佳解的啟發式演算方法………………..…………………..16
2.3基因演算法…………………………………………………………………...17
2.4基因演算法應用於設施佈置問題的文獻探討……………………………...24
2.5其他設施佈置文獻的探討…………………………………………………...27
第三章 模式建立…………………………………………………..……………....30
3.1面積相等部門模式的建立…………………………………………………...30
3.2面積不相等部門模式的建立………………………………………………...31
第四章 求解程序.………………………………………………………………….37
4.1應用基因演算法於設施佈置問題……..……..……………………………...37
4.2空間填滿曲線………………………………………………………………...41
4.3 調整部門形狀與面積使用的程序…………………………………………..50
第五章 實例驗證與結果分析…………………………….……………………….55
5.1面積相等部門…………………………………………….…………………..55
5.2面積不相等部門………………………………………….…………………..60
5.2.1最佳化成本的分析與比較………………..…………………………61
5.2.2面積利用率與部門形狀的改善與調整..…….……………………...71
第六章 結論與未來展望………………………………..…………………………75
參考文獻.…………………………………………………….………………………77
附錄…………………………………………………….…………………………….82
案例問題資料
參考文獻
Abdinnour-Helm, S. and S. W. Hadley, “Tabu search based heuristics for multi-floor facility layout,” International Journal of Production Research, 38(2), pp. 365-383, 2000.
Alvarenga, A. G. D., F. J. Negreiros-Gomes and M. Mestria, “Metaheuristic methods for A class of the facility layout problem,” Journal of Intelligent Manufacturing, 11, pp. 421-430, 2000.
Apple, J. M., Plant Layout and Material Handling, John Wiley & Sons, Inc., New York, 1983.
Aromur, G. C. and E. S. Buffa “A heuristic algorithm and simulation approach to the relative location of facilities,” Management Science, 9(2), pp. 294-309, 1963.
Banerjee, P., B. Montreuil, and C. L. Moodie, “A modeling of interactive facilities layout designer reasoning using qualitative patterns,” International Journal of Production Research, 30(3), pp. 433-453, 1992.
Bargholdi, J. J. and L. K. Platzman, “An O(n log n) planar travelling salesman heuristic based on spacefilling curves,” Operational Research Letter, 1(4), pp. 121-125, 1982.
Bargholdi, J. J. and L. K. Platzman, “Design of efficient bin-numbering schemes for warehouses,” Material Flow, 4, pp. 247-254, 1988.
Bazaraa, M. S., “Computerized layout design: a branch and bound approach,” AIIE Transactions, 7(4), pp. 432-438, 1975.
Bazrgan-Lari, M. and H. Kaebernick, “An efficient hybrid method to solve equal and unequal-size faciliy layout problems,” International Journal of Industrial Engineering, 3(1), pp. 51-63, 1996.
Bazaraa, M. S. and O. Kirca, “A branch-and-bound-based heuristic for solving the QAP,” Naval Research Logistics Quarterly, 30, pp. 287-304, 1983.
Binaghi, E., “A fuzzy logic inference model for a rule-based system in medical diagnosis,” Expert System, 7(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, 40(7), pp. 918-932, 1994.
Buffa, E. S., G. C. Armour and T. E. Vollman, “Allocating facilities with CRAFT,” Harvard Business Review, 42, pp. 136-158, 1964.
Burkard, R. E. and T. Bonninger, “A heuristic for quadratic boolean program with applications to quadratic assignment problem,” European Journal of Operational Research, 13, pp. 374-386, 1983.
Burkard, R. E. and F. Rendl, “A thermodynamically motivated simulation procedure for combinational optimization problems,” European Journal of Operational Research, 17, pp. 169-174, 1984.
Burkard, R. E. and K. H. Stratman, “Numerical investigations on quadratic assignment problem,” Naval Research Logistics Quarterly, 25, pp. 129-144, 1978.
Chan, K. C. and H. Tansri, “A study of genetic crossover operations on the facilities layout problem,” Computers & Industrial Engineering, Vol. 26, No. 3, pp. 537-550, 1994.
Chiang, W. C. and P. kouvelis, “An improved tabu search heuristic for solving facility layout design problems,” International Journal of production Research, 34(9), pp. 2565-2585, 1996.
Chiang, Wen-Chyuan and Chichiang, “Intelligent local search strategies for solving facility layout problems with the quadratic assignment problems formulation,” European Journal of Operational Research, 106, pp. 457-488, 1998.
Chwif, L., R.P.B. Marcos and A.M. Lucas, “A solution to the facility layout problem using simulated annealing,” Computers in Industry, 36, pp. 125-132, 1998.
Cimikowski, Robert and E. Mooney, “Proximity-based adjacency determination for facility layout,” Computers and Industrial Engineering, 32(2), pp. 341-349, 1996.
Deisenroth, M. P. and J. M. Apple, “A computerized plant layout analysis and evaluation technique,” Technical paper, Annual AIIE Conference, Norcross, GA, 1972.
Donaghey, C. E. and V. F. Pier, “Solving the facility layout problem with BLOCPLAN,” Industrial Engineering Department, University of Houston, TX, 1990.
Francis, R. L., L. F. McGinnis and J. A. White, Facility Layout and Location: An Analytical Approach, Prentice-Hall, Inc., New Jersey, 1992.
Freeman, H., “Computer processing of line —drawing images,” Computing Surveys, 6, pp. 57-97, 1974.
Gen, M. and R. Cheng, “A survey of Penalty techniques in genetic algorithms,” IEEE, pp. 804-809, 1996.
Gero, J. S. and V. A. Kazakov, “Evolving design genes in space layout planning problems,” Artificial Intelligence in Engineering, No. 12, pp. 163-176, 1998.
Gero, J. S. and V. Kazakov, “Learning and reusing information in space layout planning problems using genetic engineering,” Artificial Intelligence in Engineering, 11(3), pp. 329-334, 1997.
Giffin, J. W., L. R. Foulds and K. C. Cameron, “Drawing a block plan from a relationship chart with graph theory and microcomputer,” Computers and Industrial Engineering, 10, pp. 109-116, 1986.
Gilkinson, J. C. L. C. Rabelo and B. O. Bush, “A real-world scheduling problem using Genetic algorithm,” Computers and Industrial Engineering, 29, pp. 177-181, 1995.
Glass, M., “The application of spacefilling curves to some VLSI design problems,” Unpublished manuscript, Fermi National Accelerator Laboratory, Batavia III, 1985.
Goldberg, D. E., Genetic Algorithms: in Search, Optimization and Machine Learning, Addison Wesley, 1989.
Gorey, M. R. and D. S. Johnson, computers and intractability: A guide to the theory of NP-completeness, New York: W.H. Freeman, 1979.
Hakim, L. Al. “On solving facility layout problems using genetic algorithms,” International Journal of Production Research, 38(11), pp. 2573-2582, 2000.
Hasaan, M. M. D., G. L. Hogg and D. R. Smith, “SHAPE: A construction algorithm for area placement evaluation,” International Journal of Production Research, 24(5), pp. 1283-1295, 1986.
Hassan, M. M. D. and G. L. Hogg, “On constructing a block layout by graph theory,” International Journal of Production Research, 29 (6), pp. 1263-1278, 1991.
Heragu, S. S. and A. Kusiak, “Machine layout: an optimization and knowledge-based approach,” International Journal of production Research, 28(4), pp. 615-635, 1990.
Heragu, S. S. and Alfa, “Experimental analysis of simulated annealing based algorithms for the layout problem,” European Journal of Operational Research, 57, pp. 190-202, 1992.
Hillier, F. S., “Quantitative tools for plant layout analysis,” Journal of Industrial Enginering, 14, pp. 33-40, 1963.
Hillier, F. S. and M. M. Connors, “Quadraitc assignment problem algorithms and the location of indivisible facilities,” Management Science, 13, pp. 42-57, 1966.
Holland, J. H., Adaption in natural and artificial system, The University of Michigan press, Ann Arbor, 1975.
Hosni, Y. A., G. E. Whitehouse and T. S. Atkins, “MICRO-CRAFT program documentation,” Institute of Industrial Engineers, Norcross, GA. 1984.
Hu, M. H., “Microcomputer aided facility layout via Graphics-MIFLAG II,” Proceedings of 1988 Annual CIIE Conference, pp. 615-640, 1988.
Islier, A. A. “A Genetic algorithm approach for multiple criteria facility layout design,” International Journal of Production Research, 36(6), pp. 1549-1569, 1998.
Jajodia, S., I. Minis, G. Harhalakis and J. M. Proth, “CLASS: Computerized layout solutions using simulated annealing,” International Journal of Production Research, 30 (1), pp. 95-108, 1992.
Kelly, J. P., M. Laguna and F. Glover, “A study of diversification strategies for the quadratic assignment problem,” Computers and Operations Research, 21(8), pp. 885-893, 1994.
Kirsch, U., Optimum Structural Design: Concepts, Methods, and Applications, McGraw-Hill, 1981.
Kochhar, J. S., B. T. Foster and S. S. Heragu, “HOPE: A genetic algorithm for the unequal area facility layout problem,” Computers and Operations Research, 25, pp. 583-594, 1997
Koopmans, T. C. and M. Beckman, “Assignment problems and the location of economic activities,” Econometrica, 25, pp. 53-76, 1957.
Kusiak, A. and S.S. Heragu, “The facility layout problem,” European Journal of Operational Research, 29, pp. 229-251, 1987.
Lacksonen, T. T. and E. E. Enscore, “Quadratic assignment algorithm for the dynamic layout problem,” International Journal of Production Research, 31(3), pp. 503-517, 1993.
Lawler, E. L. “The quadratic assignment problem,” Management Science, 9, pp. 586-599, 1963.
Lee, G.-C. and Y.-D. Kim, “Algorithms for adjusting shapes of departments in block layouts on the grid-base plane,” The International Journal of Management Science Omega, 28, pp. 111-122, 2000.
Lee, R. C. and J. M. Moore, “CORELAP-computerized relationship layout planning,” Journal of Industrial Engineering, 18, pp. 195-200, 1967.
Liggett, R. S. and W. J. Mitchell, “Optional space planning in practice,” Computer Aided Design, 13, pp. 277-288, 1981.
Mak, K. L., Y. S. Wong and F. T. S. Chan, “A genetic algorithm for facility layout problems,” Computer Integrated Manufacturing Systems, 11(1-2), pp. 113-127, 1998.
Meller, R. D. and Y. A. Bozer, “A new simulated annealing algorithm for the facility layout problem,” International Journal of Production Research, 34(6), pp. 1675-1692, 1996.
Meyers, F. E. and M. P. Stephens, Manufacturing Facilities Design and Material Handling, Prentice-Hall, Inc., New Jersey, 2000.
Michalewicz, M., Genetic Algorithm + Data structure = Evolution program. Springer-verlag, Berlin, 1992.
Montreuil, B., “A modeling framework for integrating layout design and flow network design,” Proceedings of the Material Handling Research Colloquium, Hebron, KY, pp. 43-58, 1990.
Nang, J. H., “A simple parallelizing scheme of genetic algorithm on distributed-memory multiprocessors,” Interational Journal of High speed Comupting, 6, pp. 451-474, 1994.
Nugent, C. E., T. E. Vollman, and J. Ruml, “An experimental comparison of techniques for the assignment of facilities to locations,” Operations Research, 16, pp. 150-173, 1968.
Raoot, A. D. and A. Rakshit, “An experimental comparison of systematic placement procedures for facility layout design,” International Journal of Production Research, 31(7), pp. 1735-1756, 1993.
Ravindra, K. A., B. O. James and A. Tiwari, “A greedy genetic algorithm for the quadratic assignment problem,” Computers & Operations Research, 27, pp. 917-934, 2000.
Rosenblatt, M. J., “The dynamics of plant layout,” Management Science, 32(1), pp. 76-86, 1986
Seehof, J. M. and W. O. Evans, “Automated layout design program,” Journal of Industrial Engineering, 18, pp. 690-695, 1967.
Seppannen, J. J. and J. M. Moore, “Facilities planning with graph theory,” Management Science, 17(4), pp. 242-253, 1970.
Suresh, G., V. V. Vinod and S. Sahu, “A genetic algorithm for facility layout,” International Journal of Production Research, 33(12), pp. 3411-3423, 1995.
Suresh, G. and S. Sahu, “Multiobjective facility layout using simulated annealing,” International Journal of Production Economics, 32, pp. 239-254, 1993.
Tam, K. Y. and D. K. Chan, “Solving facility layout problems with geometric constraints using parallel genetic algorithms: experimentation and findings,” International Journal of Production Research, 36(12), pp. 3253-3272, 1998.
Tam, K. Y. “A simulated annealing algorithm for allocating space to manufacturing cells,” International Journal of Production Research, 30(1), pp. 63-87, 1992.
Tam, K. Y., “Genetic algorithms, function optimization, and facility layout design,” European Journal of Operational Research, 63, pp. 322-346, 1992.
Tate, D. M. and A. E. Smith, “Unequal-area facility layout by genetic search,” IIE Transactions, 27, pp. 465-472, 1995.
Tate, D. M. and A. E. Smith, “A genetic approach to the quadratic assignment problem,” Computers Operation Research, 22(1), pp. 73-83, 1995.
Tavakkoli-Moghaddain, R. and E Shayan, “Facilities layout design by genetic algorithms,” Computers & Industrial Engineering, 35, pp. 527-530, 1998.
Tompkins, J. A. and R. Jr. Reed, “An applied model for the facilities design problem,” International Journal of Production Research, 14, pp. 583-595, 1976.
Tompkins, J. A., J. A. White, Y. A. Bozer, E. H. Frazelle, J. M. A. Tanchoco and J. Trevino, Facilities Planning, John Wiley & Sons, Inc., New York, 1996.
Urban, T. L. “Combining qualitative and quanitative analysis in facility layout, ” Production and Inventory Management, 30, pp. 73-77, 1989.
Wang, H. P. and R. A. Wysk, “An expert system for machining data selection,” Computer & Industrial Engineering, 10(2), pp. 99-107, 1985.
Wascher, G. and J. Merker, “A comparative evaluation of heuristics for the adjacehcy problem in facility layout planning,” International Journal of Production Research, 35 (2), pp. 447-466, 1997.
Whitley, D., T. Starkweather and D. shaner, The traveling salesman and sequence scheduling: quality solutions using genetic edge recombination, in Hand book of Genetic Algorithm, David, L., Van Nostrand Reinhold, New York, pp. 350-372, 1991.
Wilhelm, M. R., and T. L. Ward, “Solving quadratic assignment problem by simulated annealing,” IIE Transactions, 19, pp. 107-119, 1987.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔