摘要
全球竞争日益激烈,我国经济增长方式从粗放型向集约型转变,产品生命周期愈来愈短,市场需求变化越来越快。这也就要求企业车间的设备布局能根据生产计划的变化而变化,从而增加制造系统的柔性,降低生产成本,提高效益,所以对车间的多阶段动态设备布局问题进行研究显得异常重要。本文通过分析动态环境下的车间设备布局问题,建立以成本为总目标函数的数学模型,并运用不同的算法求解该模型,得到适用于不同情况的求解方法。本文的主要工作如下:
1.阐述课题研究的背景和意义,分析国内外研究现状,概述动态设备布局的理论基础。
2.分析动态环境下的车间设备布局问题,研究其成本构成,特别是在重布局过程中所应考虑的成本因素,建立以成本为总目标函数的数学模型,总成本包括:物料搬运成本、区域利用成本和重布局成本。其中,重布局成本包括设备的拆装成本和关闭成本。
3.介绍遗传算法、模拟退火算法、Dijkstra算法和双向扫视算法,将它们以不同形式综合运用以求解该模型,得到三种不同的求解方法:基于工艺路线问题的求解、基于最短路问题的求解和基于SA算法的求解,它们有各自的适用于情况。
4.在实际案例中分别应用基于最短路问题的求解方法和基于SA算法的求解方法,并将实验结果进行比较,验证其优缺点及适用条件。
5.总结本文的主要成果,并展望后续的研究工作和未来的研究方向。
With the increasing global competition, our country’s economic growth mode changes from extensive to intensive, product life-cycle becomes shorter and shorter, and market demand change becomes faster and faster. It demands that the facility layout of workshop can be changed for the production planning, which can increase the flexibility of manufacturing system, decrease production cost and improve efficiency. Therefore, it’s very important to research the multi-stage dynamic facility layout problem.
This thesis establishes the mathematical model of cost objective function through analyzing the facility layout problem of workshop in dynamic environment and gets different solution methods for different situations. Main contents of the thesis are as following:
Firstly, explain the background and significance of the research, review the development and current research status both domestic and abroad, and summarize the theoretical basis of FLP.
Secondly, research the cost structure of DFLP, especially the factors of relocation process, then establish the mathematical model of cost objective function, including material handling cost, area-utilization cost and relocation cost, where relocation cost includes dismounting and assembling cost and shut-down cost.
Thirdly, introduce GA, SA, Dijkstra, and Double Sweep Algorithm, then use them comprehensively to solve the established model and get three different methods used in different situations, respectively based processing route, based shortest path and based SA.
Fourthly, take the based shortest path method and based SA method into practice and analyze the case, then prove the advantages, disadvantages and suitable conditions by comparing the experiment results.
Finally, conclude the main results and suggest the directions of future research.
引文
[1]伊俊敏.物流工程[M].北京:电子工业出版社, 2006.04.
[2] Chwif L, Pereira Barretto M R, Moscato L A. A solution to the facility layout problem using simulated annealing [J]. Computers in Industry, 1998, 36, 125-132.
[3]刘丽文.生产与运作管理[M].北京:清华大学出版社, 1998.
[4] Louis C, Yaya S K. Computational aspects of the facility layout design problem [J]. Nonlinear Analysis, 2001, 7, 5599-5610.
[5]理查德·缪瑟.系统布置设计[M].机械工业出版社, 1988.
[6] Koopmans T C, Beckman M. Assignment problems and the location of economic activities [J]. Econometrica, 1957, 25: 53-76.
[7] Liao T W. Design of Line Type Cellular Manufacturing Systems for Minimum Operating and Total Material Handling Costs [J]. International Journal of Production Research, 1993, 32(2): 387-397.
[8] Heragu S S, Kusiak A. Efficient models for the facility layout problem [J]. European Journal of Operational Research, 1991, 53(1): 1-13.
[9]林立千.设施规划与物流中心设计[M].北京:清华大学出版社, 2003.8.
[10] Tate D, A Smith. Unequal-area facility layout by genetic search [J]. IIE Transactions, 1995, 27: 465-472.
[11] Cohoon J, S Hegde, N Martin, Distributed genetic algorithms for the floor plan design problem [J]. IEEE Transactions, l991, 10: 483-491.
[12] Tam K. Genetic algorithms, function optimization, facility layout design [J]. European Journal of Operational Research, 1992, 63: 322-346.
[13] Mitsuo Gen, Kenichi Ida. Multirow Machine Layout Problem in Fuzzy Environment Using Genetic Algorithms [J]. Computers and Engineering, 1995, (29): 519-523.
[14] Kyu-Yeul Leea, Myung-ⅡRohb. An Improved Genetic Algorithm for Mu1ti-floor Facility Layout Prob1ems Having Inner Structure Walls and Passages [J]. Computers & Operations Research, 2005, (32): 879-899.
[15] Jajodia S, Minis I, Harhalakis. et. al. CLASS: Computerized Solution using simulated annealing [J]. International Journal of Production Research, 1992, 30(1): 95-108.
[16] Heragu S S, Alfa A S. Experimental Analysis of Simulated Annealing Based Algorithms for the Layout Problem [J]. European Journal of Operational Research, 1992, 57(2): 190-223.
[17] Lari M B. Layout designs in cellular manufacturing [J]. European Journal of Operational Research, 1999, 112(3): 258-272.
[18]王俊峰. M台设备单行布置问题的一种新解法[J].安徽工学院学报, 1995, 14(3): 82-87.
[19]经小川,古钟壁,王祯学.遗传算法存布局设计中的应用研究[J].四川大学学报(自然科学版), 2001, 38(3): 370-373.
[20]刘正刚,姚冠新.设施布置设计的回顾、现状与展望[J].江苏理工大学学报(社会科学版)2001, (1): 74-78.
[21]姚冠新,刘正刚.设施布置问题的非线性目标规划模型及其遗传算法[J].江苏理工大学学报(社会科学版), 2001, 6(2): 57-61.
[22]查建中,唐晓君,陆一平.布局及布置设计问题求解自动化的理论与方法综述[J].计算机辅助设计与图形学学报, 2002, 8: 705-711.
[23]李广强,霍军周,膝弘飞.并行混合遗传算法及其在布局设计中的应用[J].计算机工程, 2003, 29(17): 6-8.
[24]于瑞峰,王永县,朱友芹.基于人因学的工作地设施布局的优化设计研究[J].系统工程理论与实践, 2004, (3): 40-45.
[25]于瑞峰,王永县.手工装配作业单元的布局优化设计研究[J].工业工程与管理, 2004, (2): 36-39.
[26] Hignett S, McAtamney L. Rapid Entire Body Assessment (REBA) [J]. Applied Ergonomics, 2000, 31: 201-205.
[27]吴永忠,吴永明,袁红亮.家族保护遗传算法解决设备布局问题的研究[J].计算机工程, 2005, 3l(6): 186-188.
[28]叶慕静,周根贵.基于遗传算法的系统布置设计及初步应用[J].工业工程, 2005, 8(3): 97-101.
[29]康立山,谢云,尤矢勇等.非数值并行算法(第一册)——模拟退火算法[M].北京:科学出版社, 2003.
[30]谢云.解布局问题的模拟退火算法[J].荆州师专学报, 1993, 42(302): 26-31.
[31]李红军.模拟退火遗传算法的性能评价[J].湖南城市学院学报, 2003, 24(3): 128-135.
[32]熊范伦,邓超.退火遗传算法及其应用[J].生物数学学报, 2000, 15(2): 150-154.
[33]龙兵,安伟光,姜兴渭.基于遗传模拟退火算法的结构可靠性分析[J].哈尔滨工程大学学报, 2005, 26(6):35-41.
[34]刘怀亮,刘淼.一种混合遗传模拟退火算法及应用[J].广东大学学报(自然科学版), 2005, 4(2): 18-24.
[35]王东奇,冯俊.基于遗传模拟退火算法的可重构单元布局的研究[J].组合机床与自动化加工技术, 2006(2): 34-42.
[36]柏甫荣,秦永法.基于智能优化算法的设备布局设计[J].组合机床与自动化加工技术, 2004(6): 50-55.
[37]张刚,殷国富,邓克文等.改进的实数编码遗传算法在产品布局设计中的应用[J].计算机集成制造系统, 2005(10): 1451-1455.
[38] Reimert R P H, Gambrell C C. Minimizing material handling with a flexible plant layout [J]. International Journal of Production Research. 1966, 5: 23-28.
[39] Palekar U S, Batta R, Bosch R M, Elhence S. Modeling Uncertainties in Plant Layout Problems [J]. European Journal of Operational Research. 1992, 63: 347-359.
[40] J Balakrishnan, C H Cheng. Genetic Search and the Dynamic Layout Problem [J]. Computers & Operations Research, 2000, 27(6): 587-593.
[41]李波,邱枫.基于单亲遗传算法的动态设备布局仿真研究[J].智能系统学报, 2007, 2(1): 74-79.
[42] A Baykasoglu, N N Z Gindy. A Simulated Annealing Algorithm for Dynamic Layout Problem [J]. Computers & Operations Research, 2001, 28(14): 1403-1426.
[43] T L Urban. A Heuristic for the Dynamic Facility Layout Problem [J]. IIE Transactions, 1993, 25(4): 57-63.
[44] T Yang, B A Peters. Flexible Machine Layout Design for Dynamic and Uncertain Production Environments [J]. European Journal of Operational Research, 1998, 108(1): 49-64.
[45]曹振新,朱云龙,宋崎.制造系统的设备布局方法[J].辽宁工程技术大学学报, 2005, 24(3): 413-416.
[46] J Balakrishnan, C H Cheng, D G Conway et al. A Hybrid Genetic Algorithm for the Dynamic Plant Layout Problem [J]. International Journal of Production Economics, 2003, 86(2): 107-120.
[47] M Braglia, S Zanoni, L Zavanella. Layout Design in Dynamic Environments: Strategies and Quantitative Indices [J]. International Journal of Production Research, 2003, 41(5): 995-1016.
[48] P Kouvelis, A Kurawarwala, G J Gutierrez. Algorithms for Robust Single and Multiple Period Layout Planning for Manufacturing Systems [J]. European Journal of Operations Research, 1992, 63(2): 287-303.
[49] G. Meng, S. S. Heragu, H. Zijm. Reconfigurable Layout Problem [J]. International Journal of Production Research, 2004, 42(22): 4709-4729.
[50] A. Baykasoglu, T. Dereli, I. Sabuncu. An Ant Colony Algorithm for Solving Budget Constrained and Unconstrained Dynamic Facility Layout Problems [J]. International Journal of Management Science, 2006, 34(4): 385-396.
[51] T. Dunker, G. Radons, E. Westkamper. Combining Evolutionary Computation and Dynamic Programming for Solving a Dynamic Facility Layout Problem [J]. European Journal of Operational Research, 2005, 165(1): 55-69.
[52]刘飞,董明,侯文皓等.设施布局多重指标优化[J].上海交通大学学报, 2007(4): 664-668.
[53]宋凯雷,陈峰,董明等.基于CRAFT的多阶段柔性设备布局优化算法[J].工业工程与管理, 2008(2): 74-79.
[54] Ming Dong, Chang Wu, Forest Hou. Shortest path based simulated annealing algorithm for dynamic facility layout problem under dynamic business environment [J]. Expert Systems with Applications, 2009: 11221-11232.
[55] Hicks P E, Cowan T E. CRAFT-M for Layout Rearrangement [J]. Industrial Engineering. 1976, 5: 30-35.
[56] M J Rosenbaltt. The Dynamics of Plant Layout [J]. Management Science, 1986, 32(1): 76-86.
[57] Lacksonen T A. Static and Dynamic Layout Problem with Varying Areas [J]. Journal of Operations Research. 1994, 45: 59-69.
[58] Heragu S, S Kusiak. A machine layout problem in flexible manufacturing systems [J]. Operations Research, 1988, 36(2): 258-268.
[59] Meller R D, Narayanan V, Vance P H. Optimal facility layout design [J]. Operations Research Letters, 1999, 23: 117-127.
[60] Afentakis P, Millen R A, Solomon M M, Dynamic Layout Strategies for Flexible Manufacturing Systems [J]. International Journal of Production Research, 1990, 28(2): 311-323.
[61] Conway D G, Venkataraman M A. Genetic search and the dynamic facility layout problem [J]. Computer and Operations Research, 1994, 21: 955-960.
[62] Balakrishnan J, Jacobs R F, Venkataramanan M A. Solutions for the constrained dynamic facility layout problem [J]. European Journal of Operational Research 1992, 57: 280-286.
[63] Kochhar J S, Heragu S S. Facility Layout Design in a Changing Environment [J]. International Journal of Production Research, 1999, 37(11): 2429-2446.
[64] S K Peer, Dinesh K Sharma. Human-computer interaction design with multi-goal facilities layout model [J]. Computers and Mathematics with Applications, 2008, (56): 2164-2174.
[65] Wang T Y, Wu K B, Liu Y W. A simulated annealing algorithm for facility layout problems under variable demand in Cellular Manufacturing Systems [J]. Computers in Industry, 2001, 46: 181-188.
[66]楼洪梁,杨将新,林亚福等.基于图论的可重构制造系统重构策略[J].机械工程学报, 2006, 42(3): 22-29.
[67] Sahni S, Gonzalez T. P-complete approximation problem [J]. Journal of Association for Computer Machiniary. 1976, 23(3): 555-565.
[68]刘德忠,费仁元,吴国蔚.制造工程组织学[M].科学出版社, 2005: 433-446.
[69]王伟.发动机车间布局设计优化及应用[D].北京工业大学. 2006: 16-20.
[70]齐二石.物流工程[M].北京:中国科学技术出版社, 2004: 85-96.
[71] M. J. Rosenblatt. The Dynamics of Plant Layout [J]. Management Science, 1986, 32(1): 76-86.
[72]锁小红.基于制造系统功能的设施布局设计研究[D].山东大学. 2008.
[73]张礼镇.工业工程[M].科学出版社, 1995: 36-49.
[74] R. D. Meller, V. Narayanan, P. H. Vance. Optimal Facility Layout Design [J]. Operations Research Letters, 1998, 23(3-5): 117-127.
[75] Alan R McKendall Jr., Jin Shang, Saravanan Kuppusamy. Simulated annealing heuristics for the dynamic facility layout problem [J]. Computers & Operations Research 2006, 2431-2444.
[76] Holland J. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Pr., 1975.
[77] Yunfeng M, Yang C, Zhang M. Genetic algorithm for time-satisfaction based set covering location problem[C]. IEEE Proceedings on Communications, Circuits and Systems, 2005(5): 104l-1042.
[78]刘缵武.应用图论[M].国防科技大学出版社, 2006.
[79] Michalewicz Z. Genetic Algorithms + Data Struction = Evolution Program. Springer, 1992.
[80]杜端甫.运筹图论[M].北京:北京航空航天大学出版社, 1990.
[81]刑文训.现代优化计算方法[M].北京:清华大学出版社, 2000.
[82]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社, 2002.
[83]李敏强,寇纪淞,林丹等.遗传算法的基本理论与应用[M].北京:科学出版社, 2002.