复合材料铺层排样技术研究与开发
|
摘要
复合材料因其比强度高、比模量大、材料的刚度和强度可设计等一系列优点,在航空航天领域得到广泛应用,但高昂的价格成了复合材料应用的最大壁垒。国外的研究和应用成果表明数字化技术是降低复合材料构件制造成本、提高构件性能的有效途径。目前国内主要还以手工设计和手工制造为主、自动化程度不高,不仅浪费人力、物力,而且产品质量难以保证,因此有必要对复合材料数字化技术进行研究。优化排样是复合材料构件数字化生产过程中的重要环节。
本文在研究各种排样算法的基础上,提出了新的矩形件排样算法、优化算法以及不规则样片的排样算法,并与复合材料铺层排样的特点相结合开发了复合材料铺层排样软件。主要研究内容和创新点如下:
矩形件排样不仅适用于矩形样片的排放,也是不规则样片排样的基础。本文在建立矩形件排样数学模型的基础上,介绍了各种常见的定序列矩形件排样算法并分析其特点,提出了一种新的启发式排样算法——最低轮廓线搜索算法。该算法满足“最下最左”条件,克服了其他排样算法对某些排样图不能给出排列的缺点,实验结果表明该算法排样效果好于最低水平线算法和最下最左(BL)算法。利用该算法实现了大量不同规格图纸的集中出图,省时省力,节约纸张20~50%。
矩形件排样问题具有图形运算和组合优化两方面的特性,单纯的排样算法只能解决图形运算问题,样片的排放顺序对排样结果同样重要。针对较小规模(一般少于100个图形)的矩形件排样问题,本文提出了模拟退火与最低轮廓线搜索算法相结合的综合优化算法。对于十多个图形的排样,该算法可短时间内求得最优解;对于近百个图形的排样,在排样效果相当的情况下,该算法比其他基于模拟退火的综合优化算法效率提高百倍以上。针对大规模矩形件排样问题,本文提出了蚁群算法与最低轮廓线搜索算法相结合的综合优化算法,该算法比模拟退火与最低轮廓线算法相结合的综合优化算法效率提高十倍以上。
不规则图形排样是所有排样研究中的热点和难点。本文将不规则样片简化成多边形进行排样,提出了两种不同的解决方法:一是基于矩形的排样方法,二是直接对多边形进行排样。基于矩形求解不规则样片排样时,将图形运算、矩形件排样算法及交互调整相结合,提出了基于矩形的多边形综合排样算法。通过各种优化组合策略,对单一样片和多种样片进行组合求其最小包络矩形,从而将不规则形状样片排样转化为矩形件排样进行求解。直接排放多边形时,重点研究两个多边形的临界多边形(NFP)的求解。首先对基于倾斜图法的NFP求解法进行了改进和优化,完善了凹、凸两多边形NFP的求解,然后提出了适用于任意两多边形NFP求解的边界绕行法,该方法比基于倾斜图的求解方法适用范围广,计算简单、效率高。
根据复合材料构件数字化生产的主要过程,分析总结了复合材料铺层排样的特点,并将优化排样算法与复合材料铺层排样的特点相结合,设计开发了复合材料构件铺层排样软件系统。
Composite was widely used in aerospace because of its high strength, modulus, designable rigidity and strength. But high price has becoming an obstacle for its use. The overseas investigation shown that digital manufacture technology is effective for cost saving. However, composite parts are mainly made by hand domestically, it is very slow and quality is not able to be assured. So research on composites digital technology is very urgent. Optimized packing is a key process of composites digital manufacture, and it belongs to NP complete problem.
Based on the study of various packing algorithms, the author proposed a new rectangular packing algorithm, a hybrid heuristic optimizing algorithm and a new irregular packing problem, and combined these algorithms with composites plies packing specialties to develop a composites packing software. The main achievements and creative ideas are given below.
The rectangular packing problem not only deals with packing of 2D rectangular parts but also plays an important role in solving irregular packing problem. In order to solve the problem of rectangular parts optimal layout with dynamic constraints, a on-line packing algorithm for order-given parts is proposed——Lowest Outline Searching Algorithm based on its mathematical model. It satisfies the requirement of BL (bottom left) condition and overcome the shortcomings of other algorithm for some patterns. What’s more, according to the test compariation with other algorithm such as BL and Lowest herizatinal Line Algorithm, it shown that the algorithm is very effective. And this algorithm is used for many drawings packing and mass printing, which is helpful to save time and paper.
Rectangular packing problem mainly consist two fields, which is geometry caculation and compound optimization. Single packing method is only for geometry calculation, but packing order is also very important to optimized layout. In this paper a hybrid optimization algorithm of simullated annealing and Lowest Outline Searching Algorithm was proposed to solve small scale rectangular packing problem and the ways to improve its efficiency was studied. It can get best layout for more than ten rectangles, while for about one hundard rectangles, it is more than 100 times faster than other Simullated annealing based optimization algorithm with almost same material usage.Also ant colony based optimization algorithm was put forward to solve large scale packing problem. The ant colony was used to search a good packing order while Lowest Outline Searching Algorithm is used get the pattern for the ordered parts. Many experiments results show that ant colony based optimization is much faster than simulated annealing based hybrid optimization alrightm; it is very suitable for large scale rectangular packing problem.
The irregular packing problem is among the most difficult class of packing problem and has been studied for many years. This paper concentrate on solving the problem from two aspects,that is the method based on graphics calculation and the rectangular packing based on method. For the rectangular based one, graphics calculation, rectangular packing and interactive adjust technologies are combined together to get the enclosed rectangular of irregular parts and packing them. For graphics calculation method, the no-fit polygon algorithm was studied for calculating the relative position for two polygons to save the un-used margin. The existing method based on slope graph is mended and a new boundary slide algorithm was proposed to calculate NFP. The new one is suitable for any two polygons and it is easier than what have been used.
Based on the main procedure of composites digital manufacture, the specialty of composite ply packing is analyzed and summed up. According to composites ply packing property and based on the study of theory and algorithms mentioned above,the author designed and developed a software for packing composite layers, which can be integrated with the composite digital manufacture system.
本文在研究各种排样算法的基础上,提出了新的矩形件排样算法、优化算法以及不规则样片的排样算法,并与复合材料铺层排样的特点相结合开发了复合材料铺层排样软件。主要研究内容和创新点如下:
矩形件排样不仅适用于矩形样片的排放,也是不规则样片排样的基础。本文在建立矩形件排样数学模型的基础上,介绍了各种常见的定序列矩形件排样算法并分析其特点,提出了一种新的启发式排样算法——最低轮廓线搜索算法。该算法满足“最下最左”条件,克服了其他排样算法对某些排样图不能给出排列的缺点,实验结果表明该算法排样效果好于最低水平线算法和最下最左(BL)算法。利用该算法实现了大量不同规格图纸的集中出图,省时省力,节约纸张20~50%。
矩形件排样问题具有图形运算和组合优化两方面的特性,单纯的排样算法只能解决图形运算问题,样片的排放顺序对排样结果同样重要。针对较小规模(一般少于100个图形)的矩形件排样问题,本文提出了模拟退火与最低轮廓线搜索算法相结合的综合优化算法。对于十多个图形的排样,该算法可短时间内求得最优解;对于近百个图形的排样,在排样效果相当的情况下,该算法比其他基于模拟退火的综合优化算法效率提高百倍以上。针对大规模矩形件排样问题,本文提出了蚁群算法与最低轮廓线搜索算法相结合的综合优化算法,该算法比模拟退火与最低轮廓线算法相结合的综合优化算法效率提高十倍以上。
不规则图形排样是所有排样研究中的热点和难点。本文将不规则样片简化成多边形进行排样,提出了两种不同的解决方法:一是基于矩形的排样方法,二是直接对多边形进行排样。基于矩形求解不规则样片排样时,将图形运算、矩形件排样算法及交互调整相结合,提出了基于矩形的多边形综合排样算法。通过各种优化组合策略,对单一样片和多种样片进行组合求其最小包络矩形,从而将不规则形状样片排样转化为矩形件排样进行求解。直接排放多边形时,重点研究两个多边形的临界多边形(NFP)的求解。首先对基于倾斜图法的NFP求解法进行了改进和优化,完善了凹、凸两多边形NFP的求解,然后提出了适用于任意两多边形NFP求解的边界绕行法,该方法比基于倾斜图的求解方法适用范围广,计算简单、效率高。
根据复合材料构件数字化生产的主要过程,分析总结了复合材料铺层排样的特点,并将优化排样算法与复合材料铺层排样的特点相结合,设计开发了复合材料构件铺层排样软件系统。
Composite was widely used in aerospace because of its high strength, modulus, designable rigidity and strength. But high price has becoming an obstacle for its use. The overseas investigation shown that digital manufacture technology is effective for cost saving. However, composite parts are mainly made by hand domestically, it is very slow and quality is not able to be assured. So research on composites digital technology is very urgent. Optimized packing is a key process of composites digital manufacture, and it belongs to NP complete problem.
Based on the study of various packing algorithms, the author proposed a new rectangular packing algorithm, a hybrid heuristic optimizing algorithm and a new irregular packing problem, and combined these algorithms with composites plies packing specialties to develop a composites packing software. The main achievements and creative ideas are given below.
The rectangular packing problem not only deals with packing of 2D rectangular parts but also plays an important role in solving irregular packing problem. In order to solve the problem of rectangular parts optimal layout with dynamic constraints, a on-line packing algorithm for order-given parts is proposed——Lowest Outline Searching Algorithm based on its mathematical model. It satisfies the requirement of BL (bottom left) condition and overcome the shortcomings of other algorithm for some patterns. What’s more, according to the test compariation with other algorithm such as BL and Lowest herizatinal Line Algorithm, it shown that the algorithm is very effective. And this algorithm is used for many drawings packing and mass printing, which is helpful to save time and paper.
Rectangular packing problem mainly consist two fields, which is geometry caculation and compound optimization. Single packing method is only for geometry calculation, but packing order is also very important to optimized layout. In this paper a hybrid optimization algorithm of simullated annealing and Lowest Outline Searching Algorithm was proposed to solve small scale rectangular packing problem and the ways to improve its efficiency was studied. It can get best layout for more than ten rectangles, while for about one hundard rectangles, it is more than 100 times faster than other Simullated annealing based optimization algorithm with almost same material usage.Also ant colony based optimization algorithm was put forward to solve large scale packing problem. The ant colony was used to search a good packing order while Lowest Outline Searching Algorithm is used get the pattern for the ordered parts. Many experiments results show that ant colony based optimization is much faster than simulated annealing based hybrid optimization alrightm; it is very suitable for large scale rectangular packing problem.
The irregular packing problem is among the most difficult class of packing problem and has been studied for many years. This paper concentrate on solving the problem from two aspects,that is the method based on graphics calculation and the rectangular packing based on method. For the rectangular based one, graphics calculation, rectangular packing and interactive adjust technologies are combined together to get the enclosed rectangular of irregular parts and packing them. For graphics calculation method, the no-fit polygon algorithm was studied for calculating the relative position for two polygons to save the un-used margin. The existing method based on slope graph is mended and a new boundary slide algorithm was proposed to calculate NFP. The new one is suitable for any two polygons and it is easier than what have been used.
Based on the main procedure of composites digital manufacture, the specialty of composite ply packing is analyzed and summed up. According to composites ply packing property and based on the study of theory and algorithms mentioned above,the author designed and developed a software for packing composite layers, which can be integrated with the composite digital manufacture system.
引文
[1]曹桂荣,杨雨生,林道盛,一种高效的计算机辅助毛坯排样优化方法——复合形法,锻压技术,1998,23(5):23-26
[2] Julia A. Bennell, Jose F. Oliveira, The geometry of nesting problems: A tutorial,European Journal of Operational Research, 2007, (184):397-415
[3] A. Miguel Gomes, Jose F. Oliveira, Solving Irregular Strip Packing problems by hybridizing simulated annealing and linear programming, European Journal of Operational Research, 2006, (171):811-829
[4] J. S, On genetic algorithms for the packing of polygons, European Journal of Operational Research, 1996, (88):165-181
[5] H. E, T.B.C. H., An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research 2001, (128): 34-57
[6]中国航空研究院,复合材料结构设计手册,北京:航空工业出版社,2001:89-91
[7]崔耀东,计算机排样技术及其应用,北京:机械工业出版社,2004
[8] J. Coffman, E.G.Gray, M.R.Johnson, Approximation algorithms for bin packing——an updated survey, in algorithm Design for Computer System Design, Ausiello, Q,Lucertini, M. and Serafini, Springer-Verlag. New York, 1984: 49-106
[9]贾志欣,面向发电设备制造的下料优化排样原理与关键技术,博士学位论文,成都:四川大学,2002
[10]蒋勇,二维不规则零件优化排样系统,硕士学位论文,上海:同济大学,2002
[11] H. E, T.B.C. H., A Review of the Application of Meta-Heuristic Algorithms to 2D Strip Packing Problems, Artificial Intelligence Review, 2001, (16): 257-300
[12] Andrea Lodi, Silvano Martello, Daniele Vigo, Heuristic algorithms for the three-dimensional bin packing problem, European Journal of Operational Research, 2002, (141): 410-420
[13]霍军周,李广强,滕弘飞,用并行遗传/Powell/蚁群混合算法求解卫星舱布局问题,大连理工大学学报,2006,46(5):679-684
[14] P.E Sweeney, E.R.Parternoster., Cutting and packing problems: a categorized application-orientated research bibliography, Journal of Operational Research Society, 1992, 43(7): 691-706
[15] G. Wascher, An LP-based approach to cutting stock problems with multiple objects, European Journal of Operational Research, 1990, (44): 175-184
[16] Roberto Baldacci, Marco A. Boschetti, A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem, European Journal of Operational Research, 2007, (183): 1136-1149
[17] C. Goulimis, Optimal solutions for the cutting stock problem, European Journal of Operational Research 1990, (44): 197-208
[18] G. Zhang, X. Cai, C.K. Wong, Linear time-approximation algorithms for bin packing, Operations Resarch 2000, (26): 217-222
[19] P. Schwerin, G. Wascher, The Bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP, lnt. Trans. Opt. Res., 1997, 4(36): 377-389
[20] Mauro Dell'Amicoa, Silvano Martellob, Daniele Vigo, A lower bound for the non-oriented two-dimensional bin packing problem, Discrete Applied Mathematics, 2002, (118): 13-24
[21] M. Gradisar, G. Resinovic, M. Kljajic, A hybrid approach for optimization of one-dimensional cutting, European Journal or Operational Research, 1999, (119): 719-728
[22] Toth, Optimization engineering techniques for exact solution of NP-hard combinatorial optimization problems, European Journal of Operational Research, 2000, (125): 222-238
[23] A. Lodi, Two-dimensional packing problems: A survey, European Journal of Operational Research, 2002, (141): 241-252
[24] E.G. Birgina, J.M. Martínezb, F.H. Nishiharaa, Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization, Computers & Operations Research, 2006 (33):3535-3548
[25] Heungsoon, Felix Lee, The strip-packing problem for a boat manufacturing firm, IIE Transactions, 1999, (31): 639-651
[26] Mao Chen, Wenqi Huang, A two-level search algorithm for 2D rectangular packing problem, Computers & Industrial Engineering, 2007, (53): 123–136
[27] Eleni Hadjiconstantinou, Manuel Iori,A hybrid genetic algorithm for the two-dimensional single large object placement problem,European Journal of Operational Research 2007,(183): 1150-1166
[28] P. P, D.C. H, Genetic neuro-nester, Journal of Intelligent Manufacturing, 2004, (15): 201-218
[29] L. Faina, Application of simulated annealing to cutting stock problem, European Journal of Operational Research 1999, (68): 389-399
[30] K.A. Dowsland, Some experiments with simulated annealing techniques for packing problems, European Journal of Operational Research 1993 (68): 389-399
[31] Alvarez-Valdes, F. Parreno, J.M. Tamarit, A tabu search algorithm for a two-dimensional non-guillotine cutting problem, European Journal of Operational Research 2007, (183): 1167-1182
[32] P. Poshyanonda, C.H. Dagli, Genetic neuro-nester, Journal of Intelligent Manufacturing, 2004, (15): 201-218
[33] H.M. J, F. H, A multistage solution to the template-layout problem, IEEE Transactions on System, Science and Cybernetics, 1970, (SSC-6): 141-151
[34] M. Adamowicz, A. Albano, Nesting two-dimensional shapes in rectangular modules, Computer-Aided Design, 1976, (8): 27-33
[35] A. Albano, G. Sapuppo, Optional allocation of two-dimensional irregular shapes using heuristic search methods, IEEE Transactions on Systems, r11an and Cybernetics, 1980, (9): 302-310
[36] H.S. Ismail, K.K.B. Hon, Nesting of two-dimensional shapes using genetic algorithms,Proceedings of the Institution of Mechanical Engineers, 1995, 209(B): 115-124
[37] V.M.M. Marques, C.F.G. Bispo, J.J.S. Sentieiro, A system for the compaction of two-dimensional irregular shapes based on simulated annealing, In Proceedings of IECON 1991: 1911-1916
[38] Roberts.S.A., Application of heuristic technique to the cutting stock problem for work tops, Journal of Operational Research Society, 1984, (35): 369-377
[39] B. Cheok, Y. Nee, Algorithms for nesting and ship loff shore structure al plates, Advances in Design Automation, 1991, 32(2): 221-226
[40] Liu Hong, Z. Guangzhou, L. Zongkai, A System of optimizing Nesting with Analogical Learning Mechanism, Computers Industry, 1997, 32(4 ): 713-725
[41] Q. W., S. J.L., A nesting algorithm for irregular parts and factors affecting trim losses, international Journal of Production Research, 1987, 25 (33): 81-397
[42] D. K.A., Dowsland W. , Heuristic approaches to irregular cutting problems, Working paper EBMS/13 Eruopean Business Management School, UK: 1993
[43] H. L, W. N, Practice&experience nesting of two-dimentional irregular parts using a shape reasoning heuristic, Computer Aided Design, 1997, 29(3): 221-238
[44] S. Jain, G.H. Chang, Two dimensional packing problems using genetic algorithms, Engineering with Computers 1998, (14): 206-213
[45] G.C. Han, S.J. Na, Two-stage approach for nesting in two-dimensional cutting problems using neural network and simulated annealing, Proceedings of the Institute of Mechanical Engineers, Part B, Journal of Engineering Manufacture 1996, 210(B6): 509-519
[46] B.H.Gwee, M.H.Lim, Polyominoes tiling by a genetic algorithm, Computational Optimization and Applications, 1996, (6): 273-291
[47] E.K. Burke, R.S.R. Hellier, G. Kendall, G. Whitwell, Complete and robust no-fit polygon generation for the irregular stock cutting problem, European Journal of Operational Research, 2007, (179): 27-49
[48] M. Teresa Cost, A. Miguel Gomes, Jose'F. Oliveira, Heuristic approaches to large-scale periodic packing of irregular shapes on a rectangular sheet, European Journal of Operational Research, 2007, in press
[49] K. Ratanapan, C.H. Dagli, An object-based evolutionary algorithm for solving irregular nesting problems, In Proceedings for Artificial Neural Networks in Engineering Conference, ASME Press, New York, 1997: 383-388
[50] K. Ratanapan, C.H. Dagli, An object-based evolutionary algorithm: the nesting solution, In Proceedings of the International Conference on Evolutionary Computation, IEEE, Piscataway, USA, 1998: 581-586
[51] Hamish T. Dean,Yiliu Tu, John F. Raffensperger, An improved method for calculating the no-fit polygon, Computers & Operations Research, 2006, (33): 1521-1539
[52] H.G. Andreas Bortfeldt, A hybrid genetic algorithm for the container loading problem. European Journal of Operations Research, 2001, (131):143-161
[53] U.J. L, Computation of interferences between three-dimensional objects and the optimalpacking problem. Advance in Engineering Software, 1988, 10 (1):8-14
[54] K.J. J., G.D. C., Reasoning on the location of components for assembly packing. Journal of Mechanical Design, 1991,118 (4): 402-407
[55] G. H., A computer-based heuristic for packing pooled shipment containers. European Journal of Operational Research, 1990, 44: 277-288
[56] R. Morabito, A. M., An AND/OR-graph approach to the container loading problem, International Transactions of Operational Research, 1994, 1 ( I ): 59-73
[57] L. Faina., A global optimization algorithm for the three-dimensional packing problem, European Journal of Operational Research, 2000, 126:340-354
[58]贾志欣,排样问题的研究现状与趋势,计算机辅助设计与图形学学报,2004,16(7):890-897
[59]贾志欣,殷国富,罗阳,二维不规则零件排样问题的遗传算法求解,计算机辅助设计与图形学学报,2002,12 (5):467-470
[60]贾志欣,殷国富,罗阳等,矩形件排样的模拟退火算法求解,四川大学学报(工程科学版),2001,33(5):35-38
[61]贾志欣,殷国富,李红林,基于碰撞算法的排样系统的研究与应用,模具工业,2002,(3):9-12
[62]贾志欣,排样问题的研究现状与趋势,计算机辅助设计与图形学学报,2004,16(7): 890-897
[63]贾志欣,殷国富,罗阳等,异形件排样系统的研究与开发,计算机工程,2002,(12): 218-220
[64]曹炬,二维异形切割件优化排样的拟合算法,中国机械工程,2000,11(4):438-441
[65]曹炬,周济,余俊,矩形件排样优化的背包算法,中国机械工程,1994,5(2):11-12
[66]曹炬,周济,余俊,矩形件排样优化的一种近似算法,计算机辅助设计与图形学学报1995,7(3):190-195
[67]陈学松,曹矩,方仍存,一种求解矩形件排样问题的启发式算法,锻压技术,2004,(5): 26-28
[68]方仍存,曹矩,陈学松等,矩形件排样优化的丁字尺法,锻压技术,2004,(3):24-26
[69]饶运清,段正澄,计算机辅助排样系统的研制,计算机辅助设计与图形学学报,1994,6(1):72-74
[70]刘德全,藤弘飞,矩形件排样问题的遗传算法求解,小型微型计算机系统,1998,19(12): 20-25
[71]腾弘飞,张宝,刘俊等,航天器布局方案设计,大连理大学学报,2003,43(1):86-92
[72]霍军周,李广强,滕弘飞,人机结合蚁群/遗传算法及其在卫星舱布局设计中的应用,机械工程学报,2005,41(3):112-116
[73]曾威,史彦军,滕弘飞,卫星仓布局CAD系统:Pro/E二次开发若干关键技术,计算机辅助设计与图形学学报,2005,17(11):2575-2579
[74]滕弘飞,孙治国,刘德全等,复杂布局问题:航天器舱布局方案设计,大连理工大学学报,2001,41(5):581-588
[75]钱志勤,滕弘飞,复杂布局设计问题的算法,中国机械工程,2001,13(8):72-75
[76]钱志勤,滕弘飞,孙治国,人机交互的遗传算法及其在约束布局优化中的应用.计算机学报,2001,24( 5):553-559
[77]刘胡瑶,何援军,基于轨迹计算的临界多边形求解算法,计算机辅助设计与图形学学报,2006,18(8): 1123-1129
[78]袁国华,赵震,彭颖红,级进模工步排样中的组合优化问题研究,机械科学与技术,200019(6):947-949
[79]李明,张光新,周泽魁,基于改进遗传算法的二维不规则零件优化排样,湖南大学学报(自然科学版),2006,33(2): 48-50
[80]洪灵,王耘,一种不规则零件排样的快速解码算法,2005,17(11):2465-2470
[81]王亮申,苏铁明,杨鑫华,基于顶点的冲裁零件排样系统,机械科学与技术,2002,21(2): 334-336
[82]曹炬,张雄,冲裁件排样优化的一种模型和算法,中国机械工程,1993,4(5): 18-20
[83]孙友松,罗月参,冲裁件优化排样的顶点算法,锻压技术,1995,(4): 23-25
[84]陆文,高鸣燕,计算机辅助任意多边形排料,航空学报,1989(4):212-215
[85]徐彦欣,基于产生式规则的二维不规则零件的排料算法,小型微型计算机系统,1998,19(10):48-52
[86]刘嘉敏,张胜男,黄有群,计算机辅助设计与图形学学报,二维不规则形状自动排料算法的研究与实现,2000,12(7):488-491
[87]佟德刚,二维不规则形状排料算法研究与实现,硕士学位论文,沈阳:沈阳工业大学,2005
[88]陈勇,唐敏,童若锋等,基于遗传模拟退火算法的不规则多边形排样,计算机辅助设计与图形学学报,2003,15(5): 598-606
[89]张丽萍,张春丽,蒋寿伟,皮料优化排样的有效方法,软件学报,2005,16(2): 316-323
[90]刘嘉敏,伶德刚,黄有群,临界多边形生成算法的改进,沈阳工业大学学报,2005,27(5):567-570
[91] Teng hong fei, Ge Wen-hai, Layout optimization for the dishes installed on a rotating table. Sci in China: Series A, 1994, 37(10):1212-1218
[92] W.X.-l. Feng En-min, Wang Xiu-mei, etal., Algorithm of global optimization for solving lay-out problems. Euro J Oper Res, 1999, 114(2):430-436
[93]赵渠森,先进复合材料手册,北京:机械工业出版社,2003:1132-1140
[94] Hhttp://www-306.ibm.com/software/applications/plm/catiav4/prods/covH
[95] Hhttp://www.caeda.com.cn/materials/paper/ESAComp_Design.pdfH
[96] Hhttp://www.vistagy.comH
[97] T.W. Leung, C.H. Yung, and M.D. Troutt, Application of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem, Computers & lndustrial Engineering, 2001, 40: 201-204
[98] L.D. Q, T.h. fei, An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles,European Journal of Operational Research,1999,112: 413-420
[99] Fujita.K, Akagji.S, Kirokawa.N, Hybrid approach for optimal nesting using a genetic algorithm and a local minimisation algorithm, In Proceedings of the 19th Annual ASMEDesign Automation Conference 1: Albuquerque,NM,USA, 1993: 477-484
[100] T. Kampke, Simulated annealing: use of a new tool in bin-packing. Annals of Operations Research, 1988, (16): 327-332
[101] L. Faina, Application of simulated annealing to the cutting stock problem European Journal of Operational Research 1999, 114: 542-556
[102] P. Jain, P. Fenyes, R. Richter, Optimal blank nesting using simulated annealing, Journal of Mechanical Design -Transactions of the ASME, 1988, 114: 160-165
[103] V.E. Theodoracatos, J.L. Grimsley, Optimal packing of arbitrarily-shaped polygons using simulated annealing and polynomial-time cooling schedules, Computer Methods in Applied Mechanics and Engineering, 1995, 125: 53-70
[104] E. Burke, G. Kendall, Applying Simulated Annealing and the No Fit Polygon to the Nesting Problem, In Proceedings of the World Manufacturing Congress, 1999: 27-30
[105] J. Blazewicz, P. Hawryluk, R. Walkowiak, Using a tabu search approach for solving the two-dimensional irregular cutting problem, Annals of Operations Research, 1993, 41: 313-327
[106] B. E, K. G, Comparison of meta-heuristic algorithms for clustering rectangles, In: Proceedings of the 24th International Conference on Computers and Industrial Engineering, Uxbridge, UK: 1998
[107]施法中,计算机辅助几何设计与非均匀有理B样条,北京:高等教育出版社,2001
[108] Z. Defu, Kang Yan, D. Ansheng, A new heuristic recursive algorithm for the strip rectangular packing problem, Computers & Operations Research, 2006, 33(8): 2209-2217
[109] M. Dorigo, Optimization Learning and Natural Algorithms,Ph.D.Thesis (in Italian), Politecnico di Milano, Italy, 1992
[110] Alberto Colorni, Marco Dorigo, Vittorio Maniezzo, An investigation of some properties of an "Ant algorithm",In proceedings of the parallel problem solving from nature conference, brussels, belgium, 1992: 509-520
[111] Edmund Burke and Graham Kendall, Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem, Proceedings of the 12th Australiaelligence: Advanced Topics in Artificial Intelligence, 1999: 453-464
[112]黄红兵,蚂蚁算法在矩形件优化排样中的应用,机械工程师,2006,(2):98-100
[113] Wen Peng, Ruofeng Tong, Min Tang, Jinxiang Dong, A Parallel Algorithm of PoIygons Packing Based on Ant Colony The 9th International Conference on Computer Supported Cooperative Work in Design Proceedings,2005: 846-851
[114]邢文训,谢金星,现代优化计算方法,北京:清华大学出版社,1999: 1-293
[115]孔宪蔗,蔡洪学,简单多边形凸包的双动线检测算法,计算机学报,1994,17(8): 596-600
[116]董兴辉,计算机辅助排料系统的研究,现代电力,1997,14(1): 64-69
[117] V. J., Milenkovic, K. Daniels, Translational polygon containment and minimal enclosure using mathematical programming, International Transactions in Operational Research, 1999, 6(5): 525-554
[118] D.K. A, S. V, D. WB, An algorithm for polygon placement using a bottom-left strategy, European Journal of Operational Research 2002, 141: 371-381
[119] J.A. Bennell, K.A. Dowsland, W.B. Dowsland, The irregular cutting-stock problem - a new procedure for deriving the no-fit polygon, Computers & Operation Research, 2001, 28(3): 271-281
[120]曲吉林,确定任意简单多边形平移时碰撞部位的扫描算法,计算机学报,2000,23(7): 692-698
[121]邓冬梅,周来水,安鲁陵,复合材料铺层的排样研究,兵器材料科学与工程,2007, 30(6):17-21
[2] Julia A. Bennell, Jose F. Oliveira, The geometry of nesting problems: A tutorial,European Journal of Operational Research, 2007, (184):397-415
[3] A. Miguel Gomes, Jose F. Oliveira, Solving Irregular Strip Packing problems by hybridizing simulated annealing and linear programming, European Journal of Operational Research, 2006, (171):811-829
[4] J. S, On genetic algorithms for the packing of polygons, European Journal of Operational Research, 1996, (88):165-181
[5] H. E, T.B.C. H., An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research 2001, (128): 34-57
[6]中国航空研究院,复合材料结构设计手册,北京:航空工业出版社,2001:89-91
[7]崔耀东,计算机排样技术及其应用,北京:机械工业出版社,2004
[8] J. Coffman, E.G.Gray, M.R.Johnson, Approximation algorithms for bin packing——an updated survey, in algorithm Design for Computer System Design, Ausiello, Q,Lucertini, M. and Serafini, Springer-Verlag. New York, 1984: 49-106
[9]贾志欣,面向发电设备制造的下料优化排样原理与关键技术,博士学位论文,成都:四川大学,2002
[10]蒋勇,二维不规则零件优化排样系统,硕士学位论文,上海:同济大学,2002
[11] H. E, T.B.C. H., A Review of the Application of Meta-Heuristic Algorithms to 2D Strip Packing Problems, Artificial Intelligence Review, 2001, (16): 257-300
[12] Andrea Lodi, Silvano Martello, Daniele Vigo, Heuristic algorithms for the three-dimensional bin packing problem, European Journal of Operational Research, 2002, (141): 410-420
[13]霍军周,李广强,滕弘飞,用并行遗传/Powell/蚁群混合算法求解卫星舱布局问题,大连理工大学学报,2006,46(5):679-684
[14] P.E Sweeney, E.R.Parternoster., Cutting and packing problems: a categorized application-orientated research bibliography, Journal of Operational Research Society, 1992, 43(7): 691-706
[15] G. Wascher, An LP-based approach to cutting stock problems with multiple objects, European Journal of Operational Research, 1990, (44): 175-184
[16] Roberto Baldacci, Marco A. Boschetti, A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem, European Journal of Operational Research, 2007, (183): 1136-1149
[17] C. Goulimis, Optimal solutions for the cutting stock problem, European Journal of Operational Research 1990, (44): 197-208
[18] G. Zhang, X. Cai, C.K. Wong, Linear time-approximation algorithms for bin packing, Operations Resarch 2000, (26): 217-222
[19] P. Schwerin, G. Wascher, The Bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP, lnt. Trans. Opt. Res., 1997, 4(36): 377-389
[20] Mauro Dell'Amicoa, Silvano Martellob, Daniele Vigo, A lower bound for the non-oriented two-dimensional bin packing problem, Discrete Applied Mathematics, 2002, (118): 13-24
[21] M. Gradisar, G. Resinovic, M. Kljajic, A hybrid approach for optimization of one-dimensional cutting, European Journal or Operational Research, 1999, (119): 719-728
[22] Toth, Optimization engineering techniques for exact solution of NP-hard combinatorial optimization problems, European Journal of Operational Research, 2000, (125): 222-238
[23] A. Lodi, Two-dimensional packing problems: A survey, European Journal of Operational Research, 2002, (141): 241-252
[24] E.G. Birgina, J.M. Martínezb, F.H. Nishiharaa, Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization, Computers & Operations Research, 2006 (33):3535-3548
[25] Heungsoon, Felix Lee, The strip-packing problem for a boat manufacturing firm, IIE Transactions, 1999, (31): 639-651
[26] Mao Chen, Wenqi Huang, A two-level search algorithm for 2D rectangular packing problem, Computers & Industrial Engineering, 2007, (53): 123–136
[27] Eleni Hadjiconstantinou, Manuel Iori,A hybrid genetic algorithm for the two-dimensional single large object placement problem,European Journal of Operational Research 2007,(183): 1150-1166
[28] P. P, D.C. H, Genetic neuro-nester, Journal of Intelligent Manufacturing, 2004, (15): 201-218
[29] L. Faina, Application of simulated annealing to cutting stock problem, European Journal of Operational Research 1999, (68): 389-399
[30] K.A. Dowsland, Some experiments with simulated annealing techniques for packing problems, European Journal of Operational Research 1993 (68): 389-399
[31] Alvarez-Valdes, F. Parreno, J.M. Tamarit, A tabu search algorithm for a two-dimensional non-guillotine cutting problem, European Journal of Operational Research 2007, (183): 1167-1182
[32] P. Poshyanonda, C.H. Dagli, Genetic neuro-nester, Journal of Intelligent Manufacturing, 2004, (15): 201-218
[33] H.M. J, F. H, A multistage solution to the template-layout problem, IEEE Transactions on System, Science and Cybernetics, 1970, (SSC-6): 141-151
[34] M. Adamowicz, A. Albano, Nesting two-dimensional shapes in rectangular modules, Computer-Aided Design, 1976, (8): 27-33
[35] A. Albano, G. Sapuppo, Optional allocation of two-dimensional irregular shapes using heuristic search methods, IEEE Transactions on Systems, r11an and Cybernetics, 1980, (9): 302-310
[36] H.S. Ismail, K.K.B. Hon, Nesting of two-dimensional shapes using genetic algorithms,Proceedings of the Institution of Mechanical Engineers, 1995, 209(B): 115-124
[37] V.M.M. Marques, C.F.G. Bispo, J.J.S. Sentieiro, A system for the compaction of two-dimensional irregular shapes based on simulated annealing, In Proceedings of IECON 1991: 1911-1916
[38] Roberts.S.A., Application of heuristic technique to the cutting stock problem for work tops, Journal of Operational Research Society, 1984, (35): 369-377
[39] B. Cheok, Y. Nee, Algorithms for nesting and ship loff shore structure al plates, Advances in Design Automation, 1991, 32(2): 221-226
[40] Liu Hong, Z. Guangzhou, L. Zongkai, A System of optimizing Nesting with Analogical Learning Mechanism, Computers Industry, 1997, 32(4 ): 713-725
[41] Q. W., S. J.L., A nesting algorithm for irregular parts and factors affecting trim losses, international Journal of Production Research, 1987, 25 (33): 81-397
[42] D. K.A., Dowsland W. , Heuristic approaches to irregular cutting problems, Working paper EBMS/13 Eruopean Business Management School, UK: 1993
[43] H. L, W. N, Practice&experience nesting of two-dimentional irregular parts using a shape reasoning heuristic, Computer Aided Design, 1997, 29(3): 221-238
[44] S. Jain, G.H. Chang, Two dimensional packing problems using genetic algorithms, Engineering with Computers 1998, (14): 206-213
[45] G.C. Han, S.J. Na, Two-stage approach for nesting in two-dimensional cutting problems using neural network and simulated annealing, Proceedings of the Institute of Mechanical Engineers, Part B, Journal of Engineering Manufacture 1996, 210(B6): 509-519
[46] B.H.Gwee, M.H.Lim, Polyominoes tiling by a genetic algorithm, Computational Optimization and Applications, 1996, (6): 273-291
[47] E.K. Burke, R.S.R. Hellier, G. Kendall, G. Whitwell, Complete and robust no-fit polygon generation for the irregular stock cutting problem, European Journal of Operational Research, 2007, (179): 27-49
[48] M. Teresa Cost, A. Miguel Gomes, Jose'F. Oliveira, Heuristic approaches to large-scale periodic packing of irregular shapes on a rectangular sheet, European Journal of Operational Research, 2007, in press
[49] K. Ratanapan, C.H. Dagli, An object-based evolutionary algorithm for solving irregular nesting problems, In Proceedings for Artificial Neural Networks in Engineering Conference, ASME Press, New York, 1997: 383-388
[50] K. Ratanapan, C.H. Dagli, An object-based evolutionary algorithm: the nesting solution, In Proceedings of the International Conference on Evolutionary Computation, IEEE, Piscataway, USA, 1998: 581-586
[51] Hamish T. Dean,Yiliu Tu, John F. Raffensperger, An improved method for calculating the no-fit polygon, Computers & Operations Research, 2006, (33): 1521-1539
[52] H.G. Andreas Bortfeldt, A hybrid genetic algorithm for the container loading problem. European Journal of Operations Research, 2001, (131):143-161
[53] U.J. L, Computation of interferences between three-dimensional objects and the optimalpacking problem. Advance in Engineering Software, 1988, 10 (1):8-14
[54] K.J. J., G.D. C., Reasoning on the location of components for assembly packing. Journal of Mechanical Design, 1991,118 (4): 402-407
[55] G. H., A computer-based heuristic for packing pooled shipment containers. European Journal of Operational Research, 1990, 44: 277-288
[56] R. Morabito, A. M., An AND/OR-graph approach to the container loading problem, International Transactions of Operational Research, 1994, 1 ( I ): 59-73
[57] L. Faina., A global optimization algorithm for the three-dimensional packing problem, European Journal of Operational Research, 2000, 126:340-354
[58]贾志欣,排样问题的研究现状与趋势,计算机辅助设计与图形学学报,2004,16(7):890-897
[59]贾志欣,殷国富,罗阳,二维不规则零件排样问题的遗传算法求解,计算机辅助设计与图形学学报,2002,12 (5):467-470
[60]贾志欣,殷国富,罗阳等,矩形件排样的模拟退火算法求解,四川大学学报(工程科学版),2001,33(5):35-38
[61]贾志欣,殷国富,李红林,基于碰撞算法的排样系统的研究与应用,模具工业,2002,(3):9-12
[62]贾志欣,排样问题的研究现状与趋势,计算机辅助设计与图形学学报,2004,16(7): 890-897
[63]贾志欣,殷国富,罗阳等,异形件排样系统的研究与开发,计算机工程,2002,(12): 218-220
[64]曹炬,二维异形切割件优化排样的拟合算法,中国机械工程,2000,11(4):438-441
[65]曹炬,周济,余俊,矩形件排样优化的背包算法,中国机械工程,1994,5(2):11-12
[66]曹炬,周济,余俊,矩形件排样优化的一种近似算法,计算机辅助设计与图形学学报1995,7(3):190-195
[67]陈学松,曹矩,方仍存,一种求解矩形件排样问题的启发式算法,锻压技术,2004,(5): 26-28
[68]方仍存,曹矩,陈学松等,矩形件排样优化的丁字尺法,锻压技术,2004,(3):24-26
[69]饶运清,段正澄,计算机辅助排样系统的研制,计算机辅助设计与图形学学报,1994,6(1):72-74
[70]刘德全,藤弘飞,矩形件排样问题的遗传算法求解,小型微型计算机系统,1998,19(12): 20-25
[71]腾弘飞,张宝,刘俊等,航天器布局方案设计,大连理大学学报,2003,43(1):86-92
[72]霍军周,李广强,滕弘飞,人机结合蚁群/遗传算法及其在卫星舱布局设计中的应用,机械工程学报,2005,41(3):112-116
[73]曾威,史彦军,滕弘飞,卫星仓布局CAD系统:Pro/E二次开发若干关键技术,计算机辅助设计与图形学学报,2005,17(11):2575-2579
[74]滕弘飞,孙治国,刘德全等,复杂布局问题:航天器舱布局方案设计,大连理工大学学报,2001,41(5):581-588
[75]钱志勤,滕弘飞,复杂布局设计问题的算法,中国机械工程,2001,13(8):72-75
[76]钱志勤,滕弘飞,孙治国,人机交互的遗传算法及其在约束布局优化中的应用.计算机学报,2001,24( 5):553-559
[77]刘胡瑶,何援军,基于轨迹计算的临界多边形求解算法,计算机辅助设计与图形学学报,2006,18(8): 1123-1129
[78]袁国华,赵震,彭颖红,级进模工步排样中的组合优化问题研究,机械科学与技术,200019(6):947-949
[79]李明,张光新,周泽魁,基于改进遗传算法的二维不规则零件优化排样,湖南大学学报(自然科学版),2006,33(2): 48-50
[80]洪灵,王耘,一种不规则零件排样的快速解码算法,2005,17(11):2465-2470
[81]王亮申,苏铁明,杨鑫华,基于顶点的冲裁零件排样系统,机械科学与技术,2002,21(2): 334-336
[82]曹炬,张雄,冲裁件排样优化的一种模型和算法,中国机械工程,1993,4(5): 18-20
[83]孙友松,罗月参,冲裁件优化排样的顶点算法,锻压技术,1995,(4): 23-25
[84]陆文,高鸣燕,计算机辅助任意多边形排料,航空学报,1989(4):212-215
[85]徐彦欣,基于产生式规则的二维不规则零件的排料算法,小型微型计算机系统,1998,19(10):48-52
[86]刘嘉敏,张胜男,黄有群,计算机辅助设计与图形学学报,二维不规则形状自动排料算法的研究与实现,2000,12(7):488-491
[87]佟德刚,二维不规则形状排料算法研究与实现,硕士学位论文,沈阳:沈阳工业大学,2005
[88]陈勇,唐敏,童若锋等,基于遗传模拟退火算法的不规则多边形排样,计算机辅助设计与图形学学报,2003,15(5): 598-606
[89]张丽萍,张春丽,蒋寿伟,皮料优化排样的有效方法,软件学报,2005,16(2): 316-323
[90]刘嘉敏,伶德刚,黄有群,临界多边形生成算法的改进,沈阳工业大学学报,2005,27(5):567-570
[91] Teng hong fei, Ge Wen-hai, Layout optimization for the dishes installed on a rotating table. Sci in China: Series A, 1994, 37(10):1212-1218
[92] W.X.-l. Feng En-min, Wang Xiu-mei, etal., Algorithm of global optimization for solving lay-out problems. Euro J Oper Res, 1999, 114(2):430-436
[93]赵渠森,先进复合材料手册,北京:机械工业出版社,2003:1132-1140
[94] Hhttp://www-306.ibm.com/software/applications/plm/catiav4/prods/covH
[95] Hhttp://www.caeda.com.cn/materials/paper/ESAComp_Design.pdfH
[96] Hhttp://www.vistagy.comH
[97] T.W. Leung, C.H. Yung, and M.D. Troutt, Application of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem, Computers & lndustrial Engineering, 2001, 40: 201-204
[98] L.D. Q, T.h. fei, An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles,European Journal of Operational Research,1999,112: 413-420
[99] Fujita.K, Akagji.S, Kirokawa.N, Hybrid approach for optimal nesting using a genetic algorithm and a local minimisation algorithm, In Proceedings of the 19th Annual ASMEDesign Automation Conference 1: Albuquerque,NM,USA, 1993: 477-484
[100] T. Kampke, Simulated annealing: use of a new tool in bin-packing. Annals of Operations Research, 1988, (16): 327-332
[101] L. Faina, Application of simulated annealing to the cutting stock problem European Journal of Operational Research 1999, 114: 542-556
[102] P. Jain, P. Fenyes, R. Richter, Optimal blank nesting using simulated annealing, Journal of Mechanical Design -Transactions of the ASME, 1988, 114: 160-165
[103] V.E. Theodoracatos, J.L. Grimsley, Optimal packing of arbitrarily-shaped polygons using simulated annealing and polynomial-time cooling schedules, Computer Methods in Applied Mechanics and Engineering, 1995, 125: 53-70
[104] E. Burke, G. Kendall, Applying Simulated Annealing and the No Fit Polygon to the Nesting Problem, In Proceedings of the World Manufacturing Congress, 1999: 27-30
[105] J. Blazewicz, P. Hawryluk, R. Walkowiak, Using a tabu search approach for solving the two-dimensional irregular cutting problem, Annals of Operations Research, 1993, 41: 313-327
[106] B. E, K. G, Comparison of meta-heuristic algorithms for clustering rectangles, In: Proceedings of the 24th International Conference on Computers and Industrial Engineering, Uxbridge, UK: 1998
[107]施法中,计算机辅助几何设计与非均匀有理B样条,北京:高等教育出版社,2001
[108] Z. Defu, Kang Yan, D. Ansheng, A new heuristic recursive algorithm for the strip rectangular packing problem, Computers & Operations Research, 2006, 33(8): 2209-2217
[109] M. Dorigo, Optimization Learning and Natural Algorithms,Ph.D.Thesis (in Italian), Politecnico di Milano, Italy, 1992
[110] Alberto Colorni, Marco Dorigo, Vittorio Maniezzo, An investigation of some properties of an "Ant algorithm",In proceedings of the parallel problem solving from nature conference, brussels, belgium, 1992: 509-520
[111] Edmund Burke and Graham Kendall, Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem, Proceedings of the 12th Australiaelligence: Advanced Topics in Artificial Intelligence, 1999: 453-464
[112]黄红兵,蚂蚁算法在矩形件优化排样中的应用,机械工程师,2006,(2):98-100
[113] Wen Peng, Ruofeng Tong, Min Tang, Jinxiang Dong, A Parallel Algorithm of PoIygons Packing Based on Ant Colony The 9th International Conference on Computer Supported Cooperative Work in Design Proceedings,2005: 846-851
[114]邢文训,谢金星,现代优化计算方法,北京:清华大学出版社,1999: 1-293
[115]孔宪蔗,蔡洪学,简单多边形凸包的双动线检测算法,计算机学报,1994,17(8): 596-600
[116]董兴辉,计算机辅助排料系统的研究,现代电力,1997,14(1): 64-69
[117] V. J., Milenkovic, K. Daniels, Translational polygon containment and minimal enclosure using mathematical programming, International Transactions in Operational Research, 1999, 6(5): 525-554
[118] D.K. A, S. V, D. WB, An algorithm for polygon placement using a bottom-left strategy, European Journal of Operational Research 2002, 141: 371-381
[119] J.A. Bennell, K.A. Dowsland, W.B. Dowsland, The irregular cutting-stock problem - a new procedure for deriving the no-fit polygon, Computers & Operation Research, 2001, 28(3): 271-281
[120]曲吉林,确定任意简单多边形平移时碰撞部位的扫描算法,计算机学报,2000,23(7): 692-698
[121]邓冬梅,周来水,安鲁陵,复合材料铺层的排样研究,兵器材料科学与工程,2007, 30(6):17-21