二维不规则形优化排样技术研究
|
摘要
本文系统地研究了二维不规则多边形的自动优化排样问题及其方法。单一多边形优化排样是实际生产中最常见的问题之一，本文通过对冲压生产中的单一冲裁件在矩形板材上的排样问题研究，提出一种高效的二维整体优化自动排样算法。在单一多边形排样的研究基础上，本文研究了任意多边形对象在不规则板材上的优化排样问题。该多边形排样问题具有很高的计算复杂性，属于NP完全难题，本文在多边形的判交定位和自动排样方面提出有效的方法，并结合遗传模拟退火算法，给出多边形自动排样的有效算法。具体的实例分析表明，本文提出的理论和方法具有良好的排样效果和实用价值。
第一章首先介绍计算机辅助排样问题的相关知识，通过对其研究现状的分析讨论，引出本文的研究目标和工作重点。第一章最后简要介绍了本文的结构和章节组织。
第二章讨论单一冲裁件在固定长宽的矩形板材上的自动优化排样问题。通过对问题及排样参数的分析，提出整体优化的数学模型，并由此给出具体的自动优化排样算法。第二章的最后介绍了排样算法的一个应用，该计算机辅助自动排样系统的排样实例进一步证明了算法的实用性和良好的排样效果。
第三章介绍不规则异形件的排样问题。通过对常用的启发式算法以及多边形定位策略的分析介绍，引出了不规则异形件排样问题的瓶颈之一，那就是多边形的复杂形状容易引起高度的计算复杂性。针对这个问题，本文提出了一种多边形的几何表示方法，并由此提出一种高效的多边形判交与定位算法。算法极大地降低了几何复杂性对定位算法的影响，能够处理任意形状的多边形之间的排样定位，甚至允许多边形存在无效的区域。算法的不足是多边形的几何表示过程变得复杂了，为此，文中也给出了一种有效的算法，大大提高几何表示算法的效率。在第三章的研究基础上，第四章介绍了遗传模拟退火算法的基本思想，并将其与启发式定位算法相结合，提出实现不规则多边形自动优化排样的混合启发式算法。文中给出了具体的遗传模拟退火算法实现以及多边形的自动排样算法。
第五章对全文的研究内容进行了总结，论述了全文工作的创新点，并提出了今后研究工作的方向。
In the present manufacturing scenario, cutting of two-dimensional (2-D) shaped parts from 2-D sheets, with a minimum wastage of material, is an important task. The task of arranging the parts on the sheet is known as nesting. This paper studies the two-dimensional irregular auto-nesting problems, and also presents some effective methods to solve the problems.
What's the Computer Aided Nesting (CAN) problem? The paper discusses this problem and it's relative research works in chapter 1. The main research aim and our work are also introduced there.
In chapter 2, the paper proposes a model and algorithm for blank layout of single pattern in single rectangular sheet. This corresponding algorithm can work out the optimum layout automatically and efficiently.
The 2-D irregular nesting problem is discussed in chapter 3, which is known as the NP-hard problem in complexity. In this paper we designed a heuristic approach base on genetic simulated annealing algorithm, which will be introduced in chapter 4, can deal with the problem of packing multiple shaped parts in an irregular sheet without orientation limitation. At the same time, the algorithm also provided a new way to represent the sheet and part geometries, which can be irrespective of the complexity in the geometries. The proposed approach looked for the best sequence of the shaped parts and each part's optimum rotation by the genetic simulated annealing algorithm, and completed packing by the heuristic algorithm with the bottom-left-condition automatically. The algorithm is discussed in detail in this paper.
In chapter 4, we introduce the base ideas of Genetic Algorithms (GA) and Simulated Annealing (SA). Father on, a hybrid GA method is proposed to looked for the best sequence of the shaped parts and each part's optimum rotation. In combination with the heuristic location approach proposed in chapter 3, we present an approach for the packing of polygons base on genetic simulated annealing algorithm.
Chapter 5 summarizes all achievements of this dissertation, reviews innovation points and defects, and gives the further work in the future.
第一章首先介绍计算机辅助排样问题的相关知识，通过对其研究现状的分析讨论，引出本文的研究目标和工作重点。第一章最后简要介绍了本文的结构和章节组织。
第二章讨论单一冲裁件在固定长宽的矩形板材上的自动优化排样问题。通过对问题及排样参数的分析，提出整体优化的数学模型，并由此给出具体的自动优化排样算法。第二章的最后介绍了排样算法的一个应用，该计算机辅助自动排样系统的排样实例进一步证明了算法的实用性和良好的排样效果。
第三章介绍不规则异形件的排样问题。通过对常用的启发式算法以及多边形定位策略的分析介绍，引出了不规则异形件排样问题的瓶颈之一，那就是多边形的复杂形状容易引起高度的计算复杂性。针对这个问题，本文提出了一种多边形的几何表示方法，并由此提出一种高效的多边形判交与定位算法。算法极大地降低了几何复杂性对定位算法的影响，能够处理任意形状的多边形之间的排样定位，甚至允许多边形存在无效的区域。算法的不足是多边形的几何表示过程变得复杂了，为此，文中也给出了一种有效的算法，大大提高几何表示算法的效率。在第三章的研究基础上，第四章介绍了遗传模拟退火算法的基本思想，并将其与启发式定位算法相结合，提出实现不规则多边形自动优化排样的混合启发式算法。文中给出了具体的遗传模拟退火算法实现以及多边形的自动排样算法。
第五章对全文的研究内容进行了总结，论述了全文工作的创新点，并提出了今后研究工作的方向。
In the present manufacturing scenario, cutting of two-dimensional (2-D) shaped parts from 2-D sheets, with a minimum wastage of material, is an important task. The task of arranging the parts on the sheet is known as nesting. This paper studies the two-dimensional irregular auto-nesting problems, and also presents some effective methods to solve the problems.
What's the Computer Aided Nesting (CAN) problem? The paper discusses this problem and it's relative research works in chapter 1. The main research aim and our work are also introduced there.
In chapter 2, the paper proposes a model and algorithm for blank layout of single pattern in single rectangular sheet. This corresponding algorithm can work out the optimum layout automatically and efficiently.
The 2-D irregular nesting problem is discussed in chapter 3, which is known as the NP-hard problem in complexity. In this paper we designed a heuristic approach base on genetic simulated annealing algorithm, which will be introduced in chapter 4, can deal with the problem of packing multiple shaped parts in an irregular sheet without orientation limitation. At the same time, the algorithm also provided a new way to represent the sheet and part geometries, which can be irrespective of the complexity in the geometries. The proposed approach looked for the best sequence of the shaped parts and each part's optimum rotation by the genetic simulated annealing algorithm, and completed packing by the heuristic algorithm with the bottom-left-condition automatically. The algorithm is discussed in detail in this paper.
In chapter 4, we introduce the base ideas of Genetic Algorithms (GA) and Simulated Annealing (SA). Father on, a hybrid GA method is proposed to looked for the best sequence of the shaped parts and each part's optimum rotation. In combination with the heuristic location approach proposed in chapter 3, we present an approach for the packing of polygons base on genetic simulated annealing algorithm.
Chapter 5 summarizes all achievements of this dissertation, reviews innovation points and defects, and gives the further work in the future.
引文
[Ada69] M. Adamowicz, The optimum two-dimensional allocation of irregular, multiple-connected shapes with linear, logical and geometric constraints, Ph.D. Thesis, Department of Electrical Engineering, New York University, 1969.
[BCR80] R. Baker, E.G. Coffman, and R.L. Rivest. Orthogonal packings in two dimensions. SIAM Journal on Computing, 9(4):846-855, 1980.
[BDD01] J.A. Bennell, K.A.Dowsland, W.B. Dowsland. The irregular cutting-stock problem - a new procedure for deriving the no-fit polygon, Computers and Operations Research, 2001, 28:271-287.
[Bea85] J.E. Beasley, Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the Operational Research Society, 36(4): 297-306, 1985.
[CF94] H. Chen, N. S. Flann. Parallel Simulated Annealing and Genetic Algorithms: A Space of Hybrid Methods. In: Parallel Problem Solving from Nature 3, Springer-Verlag, 1994, 428-438.
[CGJ84] E.G. Coffman, M.R. Garey, and D.S. Johnson, Approximation algorithms for bin packing - an updated survey, Algorithm Design for Computer Systems Design, 49-106, Springer, Vienna, 1984.
[Cha83] B. Chazelle. The botton-left bin-packing heuristic: An efficient implementation. IEEE Transactions on Computers c32/8, 1983, 697-707.
[CJS90] E.G. Coffman, Jr., and P.W. Shot, Average-case analysis of cutting and packing in two dimensions, European Journal of Operational Research 44, 134-145, 1990.
[CMT79] N. Christofides, A. Mingozzi, and P. Toth, Loading problems, Combinatorial Optimization, 339-369, Wiley, New York, 1979.
[CR97] S.K. Cheng, K.P. Rao. Quick and precise clustering of arbitrarily shaped flat patterns based on stringy effect. Comput. & Ind. Engng., 1997, 33(3-4): 485-488.
[CR00] S.K.Cheng, K.P.Rao. Large-scale nesting of irregular patterns using compact neighborhood algorithm. Journal of Materials Processing Technology,2000,103:135-140.
[Dav91] L. Davis, Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, 1991.
[DB83] D. Dori, M. Ben-Bassat, Circumscribing a convex polygon by a polygon of fewer sides with minimal area addition, Comput. Vision Graphics Image Process. 1983, 24, 131-159.
[DD95] K.A. Dowsland, W.B. Dowsland. Solution approaches to irregular nesting problems. European Journal of Operational Research, 1995, Vol 84, pp 506-521.
[DKAG85] H. Dyckhoff, H.J. Kruse, D. Abel, and T. Gal, Trim-loss and related problems, OMEGA 13, 59-72, 1985.
[Dyc90] H. Dyckhoff, A typology of cutting and packing problems, European Journal of Operational Research 44, 145-160, 1990.
[EC71] S. Eilon, and N. Christofides, The loading problem, Management Science 17, 259-268, 1971.
[Far88] A.A. Farley, Mathematical programming models for cutting-stock problems in the clothing industry, Journal of the Operational Research Society, 39(1): 41-53, 1988.
[GG61] P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting stock problem — Part 1, European Journal of Operational Research 9, 724-746, 1961.
[Go176] B.L. Golden, Approaches to the cutting stock problem, AIIE Transactions 8, 265-274, 1976.
[Go189] D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA, 1989.
[Gre87] J. J. Grefenstette. Incorporating problem specific knowledge into genetic algorithms. In L. Davis, editor, Genetic Algorithms and Simulated Annealing, Pitman, 42～60. Morgan Kauflnann, 1987.
[Hin80] A.I. Hinxman, The trim-loss and assortment problem: a survey, European Journal of Operational Research and Development 16, 462-469, 1980.
[HN96] G.C. Han, S.J. Na, Two-stage approach for nesting in two-dimensional cutting problems using neural network and simulated annealing. Journal of Engineering Manufacture, 210(B6):509-19, 1996.
[Hol75] J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI, USA, 1975.
[IH95] H.S. Ismail, K.K.B. Hon. The nesting of two-dimensional shapes using genetic algorithms. Proc. Institution of Mechanical Engineers, J. of Engineering Manufacture, London, 1995, 209:115-124.
[Jak96] S. Jakobs. On genetic algorithms for the packing problems. European Journal of Operational Research 1996, 88: 165-181.
[JC98] S. Jain, H.G. Chang. Two-dimensional packing problems using genetic algorithms. Engineering with Computers, 1998, 14(3): 206-213.
[Jong75] A.D. Jong. An analysis of the behavior of a class of genetic adaptive systems. Doctoral dissertation, University of Michigan. Dissertation Abstract International, 36(10), 5140B. (University Microlms No 76-9381).
[KGV83] S. Kirkpatrick, D.C. Gelatt and M.P. Vechhi, "Opti- mization by simulated annealing," Science, vol. 220, pp.671-680, 1983.
[KV98] G.C. Krikpatricks, M. Veechi. Optimization by simulated annealing. Science, 1983, 220: 671～680.
[Liu98] Liu Jla-min. The research and application of the two-dimensional irregular nesting problem[Thesis]. Shenyang: Shenyang Polytechnic University, 1998(in Chinese).
[LW96] H. Lamousin, W.N. Waggenspack. Nesting of complex 2-D parts within irregular boundaries. Journal of Mechanical Design, 118(4): 615, 1996.
[LW97] H. Lamousin, W.N. Waggenspack. Nesting of two-dimensional irregular parts using a shape reasoning heuristic. Computer-Aided Design, Vol. 29, No. 3, pp 221-238, 1997.
[LZL97] Liu Hong, Zeng Guangzhou, Lin Zongkai. A system of optimizing nesting with analogical learning mechanism. Computers ind. Engng Vol. 32 No. 4, pp. 713-725, 1997.
[MT90] S. Martello, and P. Toth, Knapsack problems-algorithms and computer implementations, Wiley, New York, 1990.
[Nee84] A.Y.C. Nee, A heuristic algorithm for optimum layout of metal stamping blanks, Ann. CIRP 1984, 33,317-320.
[OD94] D. Orvosh and L. Davis, Using a Genetic Algorithm to Optimize Problems with Feasibility Constraints, Proceedings of the First IEEE Conference on Evolutionary Computation, 1994, 548-553.
[RA94] M.S. Reda, E.A. Abd, An interactive technique for the cutting stock problem with multiple rectangular sheets using genetic and heuristic algorithms, European Journal of Operational Research 78:304-317, 1994.
[RR99] B.A. Ramesh, B.N. Ramesh. Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms. International Journal of Production Research, Volume: 37 Number: 7 Page: 1625 - 1643.
[RR01] A. Ramesh Babu, N. Ramesh Babu. A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms. Computer-Aided Design, 2001, 33(12): 879-891.
[SM96] M. Shpitalni, V. Manevich, Optimal orthogonal subdivision of rectangular sheets, Trans. of ASME J. of Manufacturing Science and Engineering, Vol. 118, August 1996, pp. 281-288.
[VA87] P.J.M. Van Larrhoven, E.H.L. Aarts. Simulated Annealing: Theory and Application. Netherland: Kluwer Academic Publisher, Dordrecht, 1987.
[WB92] P.F. Whelan, B.G. Batchelor. Development of a vision system for the flexible packing of random shapes. Proc. S.P.I.E. conf. Machine Vision Applications, Architectures and Systems Integration, Boston, Mass., Nov. 1992, pp 223 - 232.
[Wen00] Wen Jun. Algorithm of arrangement based on case reasoning. Journal of Hubei Insfitute of Nationalities(Nat. Sci.), May 2000, Vol. 18 No. 2, pp. 63-66.
[YZH91] H.H. Yanasse, A.S.I. Zinober, R.G. Harris. Two-dimensional cutting stock with multiple stock sizes. Journal of the Operational Research Society 1991, 42(8): 673-683.
[曹炬93] 曹炬．冲裁件排样优化的一种模型和算法．中国机械工程，1993，4(5)：18-20．
[曹炬99] 曹炬．实用冲裁件优化排样系统的研究与开发．锻压机械，1999，34(1)：44-47．
[陈盛双01] 陈盛双，胡晓林，黄樟灿，吴方才．基于遗传算法的冲裁件对头双排算法．华中师范大学学报(自然科学版)，2001，35(2)：162-166．
[董长双98] 董长双，杨楚民，宾鸿赞．冲裁件二维排样优化．锻压技术，1998，23(4)：17-20．
[董长双99] 董长双，杨楚民，宾鸿赞．基于两参数的冲裁件二维排样优化．锻压技术，1999，24(6)：19-23．
[郭乃成88] 郭乃成，博铭旺，罗子键等．计算机辅助冲裁排样最优化．锻压技术，1988(1)，1988．
[龚时华99] 龚时华，汤漾平，段正澄．基于图形区域的同类零件自动优化排样算法实现．制造业自动化，1999，21(4)：18-20．
[黄有群95] 黄有群，刘嘉敏，朴致淳．剪床排料的计算机辅助设计．小型微型计算机系统，1995，16(7)：43-47．
[金晓淮98] 金晓淮，赵震，彭颖红．冲压毛坯排样CAD技术的研究．锻压技术，1998，23(4)：21-24．
[吉晓民96] 吉晓民，杨先海．冲裁件优化排样的最大截距法．西安理工大学学报，1996，12(2)：91-94．
[贾志欣01] 贾志欣，殷国富，罗阳等．矩形件排样的模拟退火算法求解．四川大学学报(工程科学版)，33(5)：35-38，2001．
[刘德全98] 刘德全，滕弘飞．矩形件排样问题的遗传算法求解．小型微型计算机系统，19(12)：19-25，1998．
[林好转94] 林好转．平行线分割一步平移法排样算法的研究．锻压技术，1994，19(5)：33-38．
[李新军92] 李新军，熊火轮，胡世光．点阵判交—一种计算机自动排样系统设计的新方法．锻压技术，1992，(5)：22-25．
[李英华99] 李英华，周兆英，熊沈蜀，刘长庚，杨延楣．机械工程师，1999，7．
[孙友松95] 孙友松，罗月参，优化排样的顶点算法．锻压技术，1995，20(4)：23-25．
[王德强97] 王德强，魏朋三．板材排样问题中的不规则多边形优化组合策略研究．中国图像图形学报，1997，2(7)：515-516．
[王华昌01] 王华昌，李志刚．冲裁件优化排样算法的研究．中国机械工 程，2001，12(2)：199-202．
[万战胜95] 冲压工艺及模具设计，中国铁道出版社，1995，北京．
[夏萼辉84] 夏萼辉，卞铭甲，李绍成．单双排冲裁件的最佳排样法．锻压机械，1984，19(2)：37-41．
[徐彦欣98] 徐彦欣．基于产生式规则的二维不规则零件的排料算法．小型微型计算机系统，1998，19(10)：48-52．
[余华刚87] 余华刚，肖样芷，肖景容．冲裁件排样的优化设计．华中工学院学报，1987，15(1)：5-10．
[周建华98] 周建华，赵建军，吴镝．不规则形状零件优化排样的关键技术．现代机械，1998，(2)：29-31．
[BCR80] R. Baker, E.G. Coffman, and R.L. Rivest. Orthogonal packings in two dimensions. SIAM Journal on Computing, 9(4):846-855, 1980.
[BDD01] J.A. Bennell, K.A.Dowsland, W.B. Dowsland. The irregular cutting-stock problem - a new procedure for deriving the no-fit polygon, Computers and Operations Research, 2001, 28:271-287.
[Bea85] J.E. Beasley, Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the Operational Research Society, 36(4): 297-306, 1985.
[CF94] H. Chen, N. S. Flann. Parallel Simulated Annealing and Genetic Algorithms: A Space of Hybrid Methods. In: Parallel Problem Solving from Nature 3, Springer-Verlag, 1994, 428-438.
[CGJ84] E.G. Coffman, M.R. Garey, and D.S. Johnson, Approximation algorithms for bin packing - an updated survey, Algorithm Design for Computer Systems Design, 49-106, Springer, Vienna, 1984.
[Cha83] B. Chazelle. The botton-left bin-packing heuristic: An efficient implementation. IEEE Transactions on Computers c32/8, 1983, 697-707.
[CJS90] E.G. Coffman, Jr., and P.W. Shot, Average-case analysis of cutting and packing in two dimensions, European Journal of Operational Research 44, 134-145, 1990.
[CMT79] N. Christofides, A. Mingozzi, and P. Toth, Loading problems, Combinatorial Optimization, 339-369, Wiley, New York, 1979.
[CR97] S.K. Cheng, K.P. Rao. Quick and precise clustering of arbitrarily shaped flat patterns based on stringy effect. Comput. & Ind. Engng., 1997, 33(3-4): 485-488.
[CR00] S.K.Cheng, K.P.Rao. Large-scale nesting of irregular patterns using compact neighborhood algorithm. Journal of Materials Processing Technology,2000,103:135-140.
[Dav91] L. Davis, Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, 1991.
[DB83] D. Dori, M. Ben-Bassat, Circumscribing a convex polygon by a polygon of fewer sides with minimal area addition, Comput. Vision Graphics Image Process. 1983, 24, 131-159.
[DD95] K.A. Dowsland, W.B. Dowsland. Solution approaches to irregular nesting problems. European Journal of Operational Research, 1995, Vol 84, pp 506-521.
[DKAG85] H. Dyckhoff, H.J. Kruse, D. Abel, and T. Gal, Trim-loss and related problems, OMEGA 13, 59-72, 1985.
[Dyc90] H. Dyckhoff, A typology of cutting and packing problems, European Journal of Operational Research 44, 145-160, 1990.
[EC71] S. Eilon, and N. Christofides, The loading problem, Management Science 17, 259-268, 1971.
[Far88] A.A. Farley, Mathematical programming models for cutting-stock problems in the clothing industry, Journal of the Operational Research Society, 39(1): 41-53, 1988.
[GG61] P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting stock problem — Part 1, European Journal of Operational Research 9, 724-746, 1961.
[Go176] B.L. Golden, Approaches to the cutting stock problem, AIIE Transactions 8, 265-274, 1976.
[Go189] D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA, 1989.
[Gre87] J. J. Grefenstette. Incorporating problem specific knowledge into genetic algorithms. In L. Davis, editor, Genetic Algorithms and Simulated Annealing, Pitman, 42～60. Morgan Kauflnann, 1987.
[Hin80] A.I. Hinxman, The trim-loss and assortment problem: a survey, European Journal of Operational Research and Development 16, 462-469, 1980.
[HN96] G.C. Han, S.J. Na, Two-stage approach for nesting in two-dimensional cutting problems using neural network and simulated annealing. Journal of Engineering Manufacture, 210(B6):509-19, 1996.
[Hol75] J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI, USA, 1975.
[IH95] H.S. Ismail, K.K.B. Hon. The nesting of two-dimensional shapes using genetic algorithms. Proc. Institution of Mechanical Engineers, J. of Engineering Manufacture, London, 1995, 209:115-124.
[Jak96] S. Jakobs. On genetic algorithms for the packing problems. European Journal of Operational Research 1996, 88: 165-181.
[JC98] S. Jain, H.G. Chang. Two-dimensional packing problems using genetic algorithms. Engineering with Computers, 1998, 14(3): 206-213.
[Jong75] A.D. Jong. An analysis of the behavior of a class of genetic adaptive systems. Doctoral dissertation, University of Michigan. Dissertation Abstract International, 36(10), 5140B. (University Microlms No 76-9381).
[KGV83] S. Kirkpatrick, D.C. Gelatt and M.P. Vechhi, "Opti- mization by simulated annealing," Science, vol. 220, pp.671-680, 1983.
[KV98] G.C. Krikpatricks, M. Veechi. Optimization by simulated annealing. Science, 1983, 220: 671～680.
[Liu98] Liu Jla-min. The research and application of the two-dimensional irregular nesting problem[Thesis]. Shenyang: Shenyang Polytechnic University, 1998(in Chinese).
[LW96] H. Lamousin, W.N. Waggenspack. Nesting of complex 2-D parts within irregular boundaries. Journal of Mechanical Design, 118(4): 615, 1996.
[LW97] H. Lamousin, W.N. Waggenspack. Nesting of two-dimensional irregular parts using a shape reasoning heuristic. Computer-Aided Design, Vol. 29, No. 3, pp 221-238, 1997.
[LZL97] Liu Hong, Zeng Guangzhou, Lin Zongkai. A system of optimizing nesting with analogical learning mechanism. Computers ind. Engng Vol. 32 No. 4, pp. 713-725, 1997.
[MT90] S. Martello, and P. Toth, Knapsack problems-algorithms and computer implementations, Wiley, New York, 1990.
[Nee84] A.Y.C. Nee, A heuristic algorithm for optimum layout of metal stamping blanks, Ann. CIRP 1984, 33,317-320.
[OD94] D. Orvosh and L. Davis, Using a Genetic Algorithm to Optimize Problems with Feasibility Constraints, Proceedings of the First IEEE Conference on Evolutionary Computation, 1994, 548-553.
[RA94] M.S. Reda, E.A. Abd, An interactive technique for the cutting stock problem with multiple rectangular sheets using genetic and heuristic algorithms, European Journal of Operational Research 78:304-317, 1994.
[RR99] B.A. Ramesh, B.N. Ramesh. Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms. International Journal of Production Research, Volume: 37 Number: 7 Page: 1625 - 1643.
[RR01] A. Ramesh Babu, N. Ramesh Babu. A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms. Computer-Aided Design, 2001, 33(12): 879-891.
[SM96] M. Shpitalni, V. Manevich, Optimal orthogonal subdivision of rectangular sheets, Trans. of ASME J. of Manufacturing Science and Engineering, Vol. 118, August 1996, pp. 281-288.
[VA87] P.J.M. Van Larrhoven, E.H.L. Aarts. Simulated Annealing: Theory and Application. Netherland: Kluwer Academic Publisher, Dordrecht, 1987.
[WB92] P.F. Whelan, B.G. Batchelor. Development of a vision system for the flexible packing of random shapes. Proc. S.P.I.E. conf. Machine Vision Applications, Architectures and Systems Integration, Boston, Mass., Nov. 1992, pp 223 - 232.
[Wen00] Wen Jun. Algorithm of arrangement based on case reasoning. Journal of Hubei Insfitute of Nationalities(Nat. Sci.), May 2000, Vol. 18 No. 2, pp. 63-66.
[YZH91] H.H. Yanasse, A.S.I. Zinober, R.G. Harris. Two-dimensional cutting stock with multiple stock sizes. Journal of the Operational Research Society 1991, 42(8): 673-683.
[曹炬93] 曹炬．冲裁件排样优化的一种模型和算法．中国机械工程，1993，4(5)：18-20．
[曹炬99] 曹炬．实用冲裁件优化排样系统的研究与开发．锻压机械，1999，34(1)：44-47．
[陈盛双01] 陈盛双，胡晓林，黄樟灿，吴方才．基于遗传算法的冲裁件对头双排算法．华中师范大学学报(自然科学版)，2001，35(2)：162-166．
[董长双98] 董长双，杨楚民，宾鸿赞．冲裁件二维排样优化．锻压技术，1998，23(4)：17-20．
[董长双99] 董长双，杨楚民，宾鸿赞．基于两参数的冲裁件二维排样优化．锻压技术，1999，24(6)：19-23．
[郭乃成88] 郭乃成，博铭旺，罗子键等．计算机辅助冲裁排样最优化．锻压技术，1988(1)，1988．
[龚时华99] 龚时华，汤漾平，段正澄．基于图形区域的同类零件自动优化排样算法实现．制造业自动化，1999，21(4)：18-20．
[黄有群95] 黄有群，刘嘉敏，朴致淳．剪床排料的计算机辅助设计．小型微型计算机系统，1995，16(7)：43-47．
[金晓淮98] 金晓淮，赵震，彭颖红．冲压毛坯排样CAD技术的研究．锻压技术，1998，23(4)：21-24．
[吉晓民96] 吉晓民，杨先海．冲裁件优化排样的最大截距法．西安理工大学学报，1996，12(2)：91-94．
[贾志欣01] 贾志欣，殷国富，罗阳等．矩形件排样的模拟退火算法求解．四川大学学报(工程科学版)，33(5)：35-38，2001．
[刘德全98] 刘德全，滕弘飞．矩形件排样问题的遗传算法求解．小型微型计算机系统，19(12)：19-25，1998．
[林好转94] 林好转．平行线分割一步平移法排样算法的研究．锻压技术，1994，19(5)：33-38．
[李新军92] 李新军，熊火轮，胡世光．点阵判交—一种计算机自动排样系统设计的新方法．锻压技术，1992，(5)：22-25．
[李英华99] 李英华，周兆英，熊沈蜀，刘长庚，杨延楣．机械工程师，1999，7．
[孙友松95] 孙友松，罗月参，优化排样的顶点算法．锻压技术，1995，20(4)：23-25．
[王德强97] 王德强，魏朋三．板材排样问题中的不规则多边形优化组合策略研究．中国图像图形学报，1997，2(7)：515-516．
[王华昌01] 王华昌，李志刚．冲裁件优化排样算法的研究．中国机械工 程，2001，12(2)：199-202．
[万战胜95] 冲压工艺及模具设计，中国铁道出版社，1995，北京．
[夏萼辉84] 夏萼辉，卞铭甲，李绍成．单双排冲裁件的最佳排样法．锻压机械，1984，19(2)：37-41．
[徐彦欣98] 徐彦欣．基于产生式规则的二维不规则零件的排料算法．小型微型计算机系统，1998，19(10)：48-52．
[余华刚87] 余华刚，肖样芷，肖景容．冲裁件排样的优化设计．华中工学院学报，1987，15(1)：5-10．
[周建华98] 周建华，赵建军，吴镝．不规则形状零件优化排样的关键技术．现代机械，1998，(2)：29-31．