典型制造企业待发区布局算法研究
|
摘要
布局问题在许多行业是一个重要的生产环节,如果应用快速有效的布局问题的解决方法,则可以大大地降低生产成本,提高生产效率。
本文首先给出了一系列布局问题的理论基础,对布局问题的启发式算法的定义及其算法规则进行了简要介绍。然后对贪心算法和拟人算法这两种布局的启发式算法从问题的提出,基本概念的简介,布局策略的研究,到最终算法进行了详细的描述。最后对已有的启发式算法进行了相应改进,并依据改进算法对某典型制造企业的缓存区的待发功能区为例进行合理布局,将改进后的布局与原有布局进行比较,可见,布局状况有显著改善,改进布局可达到令人满意的效果。
Layout problems stem from modern production and daily life in many areas and they perform all kinds of forms. They are widely used in the mechanical engineering, aerospace, robot motion planning, pattern recognition, transportation, large-scale integrated circuit design, publishing and printing, clothing, leather, shipbuilding, city planning and architectural design, and many other industries. People have studied more deeply on the layout problems. In many areas we have also made some progress, but the study of the overall layout is relatively weak. Layout problem in many industries is an important part of the production , it can greatly reduce production costs, improve production efficiency in the manufacturing enterprise if we have the quick and efficient layout solution to the problem. This paper studies storage travel area, introduces the theory of distribution in detail, gives a detailed description and analysis on the layout algorithm.
Layout problems are complex combinatorial optimization problems and NP-complete problems. It is very difficult to find the exact global optimal solution in a certain period of time. This paper uses the heuristic algorithm, the focus of analysis is to combine the greedy algorithm and the people algorithm, study and improvement it. Then applies it on solving the problem of distribution, establishes the model to solve the layout problem, gives effective algorithm and feasible programmes. The use of heuristic methods, algorithms and programming techniques makes it to be true that design two-dimensional layout of a buffer zone, and Analysis parameters of the example.
The main contents are as follows:
First, in the introduction part we introduce the significance and the application of the layout problem, the research results in the theory of the domestic and international distribution , the practical application status of the layout problem solving method , and put forward the issue content of this paper.
Then focuses on the theoretical foundation on solving the layout problem and describes the layout problems heuristic algorithm.Expound the characteristic of solving the layout problem and the principles we should give an attention when we solve the problem. Recapitulate briefly all aspects about the layout problems related: layout problems bound and layout model.Put forward the concept of feasible domain, space sequencing rules and positioning rules of layout objects.
Introduces typical rectangular layout methods and carried out a detailed analysis on the greedy algorithm and the people algorithm of the layout problem. We has proposed the problem, introduced the basic concepts , studied the distribution strategy, and gave the final algorithm description. These two algorithms to solve different objectives layout problems were provided their own effective means. The layout algorithm minimizes the various possible location, accesses time and reduce complexity of the algorithm. If a combination of appropriate intelligent algorithm improve the initial distribution, there is hope to put the layout algorithm in the ultimate practice.
Followed gives the empirical analysis and introduces various functional areas of the travel area. Travel has been selected as the main study area and is the example of its layout analysis. The Travel district and layout objects status are given. According to heuristic algorithm of the travel areas layout and the existing layout status, with the improved greedy algorithm and the impersonate algorithm, make a reasonable layout. And comparing the improved layout with the original layout, we get the corresponding conclusions .
Finally, we gave the summary of the full text, obtained some useful conclusions, and gave a number of ideas on further research.
本文首先给出了一系列布局问题的理论基础,对布局问题的启发式算法的定义及其算法规则进行了简要介绍。然后对贪心算法和拟人算法这两种布局的启发式算法从问题的提出,基本概念的简介,布局策略的研究,到最终算法进行了详细的描述。最后对已有的启发式算法进行了相应改进,并依据改进算法对某典型制造企业的缓存区的待发功能区为例进行合理布局,将改进后的布局与原有布局进行比较,可见,布局状况有显著改善,改进布局可达到令人满意的效果。
Layout problems stem from modern production and daily life in many areas and they perform all kinds of forms. They are widely used in the mechanical engineering, aerospace, robot motion planning, pattern recognition, transportation, large-scale integrated circuit design, publishing and printing, clothing, leather, shipbuilding, city planning and architectural design, and many other industries. People have studied more deeply on the layout problems. In many areas we have also made some progress, but the study of the overall layout is relatively weak. Layout problem in many industries is an important part of the production , it can greatly reduce production costs, improve production efficiency in the manufacturing enterprise if we have the quick and efficient layout solution to the problem. This paper studies storage travel area, introduces the theory of distribution in detail, gives a detailed description and analysis on the layout algorithm.
Layout problems are complex combinatorial optimization problems and NP-complete problems. It is very difficult to find the exact global optimal solution in a certain period of time. This paper uses the heuristic algorithm, the focus of analysis is to combine the greedy algorithm and the people algorithm, study and improvement it. Then applies it on solving the problem of distribution, establishes the model to solve the layout problem, gives effective algorithm and feasible programmes. The use of heuristic methods, algorithms and programming techniques makes it to be true that design two-dimensional layout of a buffer zone, and Analysis parameters of the example.
The main contents are as follows:
First, in the introduction part we introduce the significance and the application of the layout problem, the research results in the theory of the domestic and international distribution , the practical application status of the layout problem solving method , and put forward the issue content of this paper.
Then focuses on the theoretical foundation on solving the layout problem and describes the layout problems heuristic algorithm.Expound the characteristic of solving the layout problem and the principles we should give an attention when we solve the problem. Recapitulate briefly all aspects about the layout problems related: layout problems bound and layout model.Put forward the concept of feasible domain, space sequencing rules and positioning rules of layout objects.
Introduces typical rectangular layout methods and carried out a detailed analysis on the greedy algorithm and the people algorithm of the layout problem. We has proposed the problem, introduced the basic concepts , studied the distribution strategy, and gave the final algorithm description. These two algorithms to solve different objectives layout problems were provided their own effective means. The layout algorithm minimizes the various possible location, accesses time and reduce complexity of the algorithm. If a combination of appropriate intelligent algorithm improve the initial distribution, there is hope to put the layout algorithm in the ultimate practice.
Followed gives the empirical analysis and introduces various functional areas of the travel area. Travel has been selected as the main study area and is the example of its layout analysis. The Travel district and layout objects status are given. According to heuristic algorithm of the travel areas layout and the existing layout status, with the improved greedy algorithm and the impersonate algorithm, make a reasonable layout. And comparing the improved layout with the original layout, we get the corresponding conclusions .
Finally, we gave the summary of the full text, obtained some useful conclusions, and gave a number of ideas on further research.
引文
[1]Dowsland KA,Dowsland WB.Packing Problems[J].European Journal of Operational Research,1992,56(1):2-14.
[2]Dyelth off HA Ty Polo of cutting and Packing Problems[J].European Journal of Operational Research,1990,44(2):145-159.
[3]Kenndy MP,ChuaLo.Unifying the tankand Hopfield linear Programming eireuit and the eanonieal nonlinear Programming eireuitofchuaandlin[J].IEEE Transaction son Cireuitsand Systems,1987,33(1)-34(2):210-214.
[4]Agrawal PK.Minimizing trim loss in cutting rectangular blanks of a single size from a rectanglar sheet using orthogonal guillotine cuts[J],European Journal of Operational Research,1993,64:410-422.
[5]E.G.Cofman,Jo.and P.W.Shoe.Average-case analysis of cutting and packing in two dimensions[J].European Journal of Operational Research,1990,44(1):134-144.
[6]Farley AA.Selection of stock plate characteristics and cutting style for two dimensional cutting stock situations[J].European Journal of Operational Research,1990,44(1):239-246.
[7]Farley AA.The cutting stock problem in the canvas industry[J].European Journal of Operational Research,1990,44:247-255.
[8]Healy P,Moll R.A local optimization-based solution to the rectangle layout problem[J].Journal of Operational Research Society,1996,47:523-537.
[9]Oliveira J F,Ferreira J S.An improved version of Wang's algorithm for two-dimensional cutting problems[J].European Journal of Operational Research,1990,5(1):2.
[10]喻宏波.布局模装系统的研究[D].天津大学硕士学位论文,2000.
[11]赵素芬.几何布局问题及其应用(一)[J].呼和浩特科技,1993(2),19-21.
[12]Harald Dyckhoff.A typology of cutting and packing problems[J].European Journal of Operational Research,1990,44:145-159.
[13]王金敏,王玉新,查建中.布局问题约束的分类及表达[J].计算机辅助设 计与图形学学报,2002,12(5):173-17.
[14]Gary M R,Johnson D S.Computer and Intractability:A Guide to the Theory of NP-Completeness[D].Freeman,New YORK,1979.
[15]Paul E S,Elizabeth RP.Cutting and Packing Problem:A Categorized Application-Orientated Research Bibliography[J].Journal of Operational Research Society,1992,43(7):691-706.
[16]王爱虎.并行布局求解理论与方法的研究[D].天津大学博士学位论文,1997.
[17]Valerio de,Carvalho J M,et al.An LP-based approach to a two-stage cutting stock problem[J].European Journal of Operational Research,1995,84:580-58.
[18]Geing Hetal.A computer-based heuristic for packing pooled shipment containers[J].European Journal of Operational Research,1990,44:277-288.
[19]Bischoff EE,Marriott M D.A comparative evaluation of heuristics for container loading[J].European Journal of Operational Research,1990,44:267-276.
[20]Coffman E G,Shoe P W.Average-case analysis of cutting and packing in two dimensions[J].European Journal of Operational Research,1990,44:134-144.
[21]Hassler R W,Talbot F B.Load planning for shipments of low density products[J].European Journal of Operational Research,1990,44:289-299.
[22]Albano A.A method to improve two-dimensional layout[J].Computer Aided Design,1980,10(5):242-248.
[23]N.Christofides,C.Whitlock.two-dimensional cutting problems[J].An algorithm for Oper.Res.25(1977)30-44.
[24]Beasley J E.Algorithms for unconstrained two-dimensional guillotine cutting[J].Journal of the Operational Research Society 1985;36:297-306.
[25]王爱虎.并行布局求解理论与方法的研究[D].天津大学博士学位论文,1997.
[26]周俊健.一类线性规划问题的最优解饱和布局的性质[JJ.系统工程,1992,10(2).
[27]戴佐.智能布局系统设计理论与方法的研究[D].天津大学博士学位论文,1995.
[28]詹叔浩,黄文奇.一类几何布局问题的计算机辅助设计[J].应用数学学报,1983,6(1):34-46.
[29]Teng Hongfei etal.Layout Optimization for the Objects Located within a Rotating Vesselk a Three-Dimensional Packing Problem with Behavioral Constraints[J].Computer & Operations Research,2001,28(6):521-535.
[30]吴慧中等.一种立体空间布局模型及布局算法[J].计算机学报,1994,17(11):835-841.
[31]FENG Enmin,WANG Xilu,WANG Xiumei et al.Algorithm of Globle Optimization for Solving Layout Problems[J].European Journal of Operational Research,1999,114(2):430-436.
[32]李智等.基于遗传算法的港口布局优化[J].武汉理工大学学报,2001,25(4):456-458.
[33]王金敏,马丰宁,陈东祥等.一种基于约束的布局求解算法[J].计算机辅助设计与图形学学报,1998,10(2):156-160.
[34]陆一平,周济,钟毅芳.平面约束圆集布局的膨胀算法[J].华中理工大学学报.1998,26(10):45-47.
[35]张博.BBL布局结构及算法研究[D].电子科技大学硕士学位论文,2007.
[36]杨维嘉.布局问题求解方法与策略的研究[D].天津大学硕士学位论文,2005.
[37]唐泽盛,周嘉玉,李新友.计算机图形学基础[M],北京:清华大学出版社,1994
[38]Yu-Liang,Wuetal-An elective quasi-human based heuristic for solving the rectangle packing problem[J].European Journal of Operational Research,2002,141:341-358.
[39]李越.集装箱装载配置优化算法研究[D].上海交通大学硕士学位论文.
[40]VL.R.富尔兹.组合优化[M].上海:上海翻译出版公司,1988.
[41]Zanakis S H,Evans J R and Vazacopoulos AA.Heuristic methods and applications:A categorized survey[J].Europ.J.Opl.Res,1989,43:88-110.
[42]Sinclair M.Comparison of the performance of modern heuristics for combinatorial optimization on real data[J].Computers and Operational Research,1993,20(7):687-695.
[43]王爱虎,查建中.一种基于二又树结构表达的矩形物体布局的启发式方法[J].软件学报,1996,6.
[44]邹海明,余祥宣.计算机算法基础(第一版)[J].武汉,华中理工大学出版社, 1985,71-72.
[45]M.R.加里,D.S.约翰逊.计算机和难解性-NP完全理论指导[M].北京,科学出版社,1987.
[46]黄文奇,刘建.集成电路模块布局问题的一种有效算法[J].计算机工程与应用,2003,39(15):102-103.
[47]黄文奇,工瑞民.求解单位等边三角形Packing问题得占角算法[J].鄂州大学学报,2000,7(2).
[48]呈吕凤.C++语言基础教程[M].北京:清华大学出版社,1999,3.
[49]钱能.C++程序设计教程[M].北京:清华大学出版社,1999,4.
[50]何大勇、查建中等.智能布局集成求解策略研究[M].武汉:人民交通出版社,1999,10.
[51]陈端兵,黄文奇.求解矩形packing问题的贪心算法[J].计算机工程,2007,33(4).
[52]黄文奇,陈端兵.一种求解矩形块布局问题的拟物拟人算法[J].计算机科学,2005,32(11).
[2]Dyelth off HA Ty Polo of cutting and Packing Problems[J].European Journal of Operational Research,1990,44(2):145-159.
[3]Kenndy MP,ChuaLo.Unifying the tankand Hopfield linear Programming eireuit and the eanonieal nonlinear Programming eireuitofchuaandlin[J].IEEE Transaction son Cireuitsand Systems,1987,33(1)-34(2):210-214.
[4]Agrawal PK.Minimizing trim loss in cutting rectangular blanks of a single size from a rectanglar sheet using orthogonal guillotine cuts[J],European Journal of Operational Research,1993,64:410-422.
[5]E.G.Cofman,Jo.and P.W.Shoe.Average-case analysis of cutting and packing in two dimensions[J].European Journal of Operational Research,1990,44(1):134-144.
[6]Farley AA.Selection of stock plate characteristics and cutting style for two dimensional cutting stock situations[J].European Journal of Operational Research,1990,44(1):239-246.
[7]Farley AA.The cutting stock problem in the canvas industry[J].European Journal of Operational Research,1990,44:247-255.
[8]Healy P,Moll R.A local optimization-based solution to the rectangle layout problem[J].Journal of Operational Research Society,1996,47:523-537.
[9]Oliveira J F,Ferreira J S.An improved version of Wang's algorithm for two-dimensional cutting problems[J].European Journal of Operational Research,1990,5(1):2.
[10]喻宏波.布局模装系统的研究[D].天津大学硕士学位论文,2000.
[11]赵素芬.几何布局问题及其应用(一)[J].呼和浩特科技,1993(2),19-21.
[12]Harald Dyckhoff.A typology of cutting and packing problems[J].European Journal of Operational Research,1990,44:145-159.
[13]王金敏,王玉新,查建中.布局问题约束的分类及表达[J].计算机辅助设 计与图形学学报,2002,12(5):173-17.
[14]Gary M R,Johnson D S.Computer and Intractability:A Guide to the Theory of NP-Completeness[D].Freeman,New YORK,1979.
[15]Paul E S,Elizabeth RP.Cutting and Packing Problem:A Categorized Application-Orientated Research Bibliography[J].Journal of Operational Research Society,1992,43(7):691-706.
[16]王爱虎.并行布局求解理论与方法的研究[D].天津大学博士学位论文,1997.
[17]Valerio de,Carvalho J M,et al.An LP-based approach to a two-stage cutting stock problem[J].European Journal of Operational Research,1995,84:580-58.
[18]Geing Hetal.A computer-based heuristic for packing pooled shipment containers[J].European Journal of Operational Research,1990,44:277-288.
[19]Bischoff EE,Marriott M D.A comparative evaluation of heuristics for container loading[J].European Journal of Operational Research,1990,44:267-276.
[20]Coffman E G,Shoe P W.Average-case analysis of cutting and packing in two dimensions[J].European Journal of Operational Research,1990,44:134-144.
[21]Hassler R W,Talbot F B.Load planning for shipments of low density products[J].European Journal of Operational Research,1990,44:289-299.
[22]Albano A.A method to improve two-dimensional layout[J].Computer Aided Design,1980,10(5):242-248.
[23]N.Christofides,C.Whitlock.two-dimensional cutting problems[J].An algorithm for Oper.Res.25(1977)30-44.
[24]Beasley J E.Algorithms for unconstrained two-dimensional guillotine cutting[J].Journal of the Operational Research Society 1985;36:297-306.
[25]王爱虎.并行布局求解理论与方法的研究[D].天津大学博士学位论文,1997.
[26]周俊健.一类线性规划问题的最优解饱和布局的性质[JJ.系统工程,1992,10(2).
[27]戴佐.智能布局系统设计理论与方法的研究[D].天津大学博士学位论文,1995.
[28]詹叔浩,黄文奇.一类几何布局问题的计算机辅助设计[J].应用数学学报,1983,6(1):34-46.
[29]Teng Hongfei etal.Layout Optimization for the Objects Located within a Rotating Vesselk a Three-Dimensional Packing Problem with Behavioral Constraints[J].Computer & Operations Research,2001,28(6):521-535.
[30]吴慧中等.一种立体空间布局模型及布局算法[J].计算机学报,1994,17(11):835-841.
[31]FENG Enmin,WANG Xilu,WANG Xiumei et al.Algorithm of Globle Optimization for Solving Layout Problems[J].European Journal of Operational Research,1999,114(2):430-436.
[32]李智等.基于遗传算法的港口布局优化[J].武汉理工大学学报,2001,25(4):456-458.
[33]王金敏,马丰宁,陈东祥等.一种基于约束的布局求解算法[J].计算机辅助设计与图形学学报,1998,10(2):156-160.
[34]陆一平,周济,钟毅芳.平面约束圆集布局的膨胀算法[J].华中理工大学学报.1998,26(10):45-47.
[35]张博.BBL布局结构及算法研究[D].电子科技大学硕士学位论文,2007.
[36]杨维嘉.布局问题求解方法与策略的研究[D].天津大学硕士学位论文,2005.
[37]唐泽盛,周嘉玉,李新友.计算机图形学基础[M],北京:清华大学出版社,1994
[38]Yu-Liang,Wuetal-An elective quasi-human based heuristic for solving the rectangle packing problem[J].European Journal of Operational Research,2002,141:341-358.
[39]李越.集装箱装载配置优化算法研究[D].上海交通大学硕士学位论文.
[40]VL.R.富尔兹.组合优化[M].上海:上海翻译出版公司,1988.
[41]Zanakis S H,Evans J R and Vazacopoulos AA.Heuristic methods and applications:A categorized survey[J].Europ.J.Opl.Res,1989,43:88-110.
[42]Sinclair M.Comparison of the performance of modern heuristics for combinatorial optimization on real data[J].Computers and Operational Research,1993,20(7):687-695.
[43]王爱虎,查建中.一种基于二又树结构表达的矩形物体布局的启发式方法[J].软件学报,1996,6.
[44]邹海明,余祥宣.计算机算法基础(第一版)[J].武汉,华中理工大学出版社, 1985,71-72.
[45]M.R.加里,D.S.约翰逊.计算机和难解性-NP完全理论指导[M].北京,科学出版社,1987.
[46]黄文奇,刘建.集成电路模块布局问题的一种有效算法[J].计算机工程与应用,2003,39(15):102-103.
[47]黄文奇,工瑞民.求解单位等边三角形Packing问题得占角算法[J].鄂州大学学报,2000,7(2).
[48]呈吕凤.C++语言基础教程[M].北京:清华大学出版社,1999,3.
[49]钱能.C++程序设计教程[M].北京:清华大学出版社,1999,4.
[50]何大勇、查建中等.智能布局集成求解策略研究[M].武汉:人民交通出版社,1999,10.
[51]陈端兵,黄文奇.求解矩形packing问题的贪心算法[J].计算机工程,2007,33(4).
[52]黄文奇,陈端兵.一种求解矩形块布局问题的拟物拟人算法[J].计算机科学,2005,32(11).