基于图像的不规则零件排样算法研究
|
摘要
金属板材是船舶制造中消耗的主要原材料之一。船舶制造中一个关键环节是如何设计板料的切割和利用方案。船体建造板材套料系统能够提高生产效率和资源使用率，保证船舶制造的智能化、数字化。
排样问题的目标是在给定的几何图形上不重叠地叠放更多的几何图形，使材料利用率最高。这是一类NP-hard问题，而且大规模规则件排样和不规则件排样问题随着问题规模的增大，计算复杂度更是爆炸性增长。如何缩短排样时间同时提高板料利用率，是该问题研究的重点和难点。本文从排样的数据结构、优化理论、算法分析以及协同计算等方面进行了深入的研究，提出了一系列解决方案和算法并开发了一个排样实验系统对算法进行了验证和分析。研究成果和创新点可概括如下：
1.对排样问题提出了一套基于图像处理的数据表示和评价方法
对于排样问题的研究，目前学者们绝大部分是采用基于图形的方法。但其实基于图像的方法有独特的优势，论文对这方面进行了探索。论文提出了一种基于图像颜色数据分析的重叠检测、出界检测和评价方法，并通过为图像建立“角边链”（描述零件像素坐标和相交等信息）和“信息板”（描述板材像素已被哪个零件占据）数据结构并依据这些数据绘图，使得在试排图像中基于边就可以实现分析评价，使基于图像的二维排样问题复杂度由面积级降至线性级。
2.提出了动态邻域及并行模拟退火的算法
基于图像的方法的一个缺点是精度不足，为了增加精度，可以扩大图像的尺寸，但这会引起计算的复杂度和排样时间的飞速增加。为了解决这个矛盾，论文对二维排样模拟退火算法的邻域机制和接受新解的机制进行了改进，提出一套动态邻域及并行模拟退火算法，从而解决了“离散”类方法中的精度与时间的矛盾，并使得用模拟退火求解二维排样问题的速度得到了极大提高。
3.提出一种基于“开放边集”的解码方法。
“开放边集”是一种对后续零件入排有指导意义的轮廓或孔洞边段的有序集合。基于开放边集，论文提出一种用百分比和入排角度组成的编码方法，该方法可以表示所有可能的入排位置。基于这种百分比编码，可以实现快速搜索入排方案，从而实现构造解码。基于开放边集的解码方法不同于传统的BL、BLF、最低水平线、剩余矩形等方法，也不用计算临界多边形（NFP），排样无需进行矩形化预处理和零件靠接后处理，无论矩形件还是不规则件都适合，是一种新的入排解码思路。
论文继续提出基于该解码算法与遗传算法结合的混合排样算法，并进一步提出一些加速排样的新技术，如配角初排、开边挑选、分布式方案。这些算法使得排样的板材利用率比前人有所提高，多个实验算例打破了已有报道的最高利用率。
4.对余料管理进行了研究，并提出了一个基于余料的套排规划算法
合理利用余料是提高板材利用率的一个好思路。论文研究了板材排样完成后余料图像的提取、余料的分解以及余料自动再参排的方法，并实现了套排规划与排样优化的同一化，一方面使得板材选件更加自动化，另一方面使得多次排样后板材利用率进一步提高。
5.根据以上核心算法，编写了排样程序系统。实验证明，该排样系统效果良好。
Metal sheet is a kind of the main material in ship building. A key problem in shipbuilding is how to design the cutting layout and let the utilization of the sheet be maximal.Nesting system for ship building can increase the production efficiency and the utilization ofresource, and it can ensure the shipbuilding intelligent and digital.
The goal of the nesting problem is to place geometric figures in another given geometricfigure as more as posible, so that getting the maximum material utilization. This is a kind ofNP-hard problem. Furthermore, as to the large-scale or irregular nesting problem, thecomputation complexity will grow explosively when the problem scale increase. How toshorten the nesting time while increasing the utilization? It is the key point and difficulty inresearch. This paper studies the nesting problem deeply in data structure, optimization theory,algorithm, collaborative computing. A series of solutions and algorithms are brought forward.A testing nest system was developed and verified the algorithms. The achievments andinovations are listed as follow:
(1) Put forward a set of data structures and evaluation methods based image processing
At present, most research of nesting problem is base on graphics. However, methodbased on image has special advantage. This paper explores in this area. This paper putforwards a method for overlap detection, out of bounds testing and evaluation. Throughcreating the data structures of “Vertex-Edge Chain”(describing part pixel coordinates andintersection information) and “Information Board”(recording which parts have occupiedwhich sheet pixels) and drawing according these data, analysis and evaluation can beachieved, so that the complexity of two-dimensional nesting problem based on imagedecreases to linear level from area level.
(2)Brings forword the algorithm of dynamic neighborhood and parellel simulatedannealing
A shortcoming of the method based on image is that the precision not enough. Expandthe image dimension can increase precision, but computing complexity will grow at very fastspeed. In order to resolve this conflict, this paper improves the neighborhood mechanism andof new solution accepting mechanism, and brings forward an algorithm of dynamicneighborhood scale and parallel simulated annealing. This algorithm resolved the conflict, sothat the speed of nesting increases greatly when using simulated annealing.
(3) Put forward a decode method based on “open edge set”.
Based on the “open edge set”, a encoding method which described with percentage andplacing angle is brought forward. This encoding method can represent all the possible places.Based of this percent encoding, we can search for good place quickly. This decoding methodis different from the traditional methods such as BL, BLF, Lowest Horizontal Line, remainingrectangle, and needn’t NFP. Rectangle pretreatment and collision post processing are notneeded either. It is a new idea for nest decoding.
This paper continues to raise a mixed algorithm combined with the decoding method andgenetic algorithm. And further Some technologies that speed up nesting were discussed, suchangle match, open edge selecting and distributed method. These algorithms allow the nestingutilization be better. The utilization of some testing example exceed existing reports.
(4) discussed the remnant management, and put forward a nesting plan method thatbased on remnant.
This paper discussed the extraction, decomposition of remnants and the method ofattending nesting again automatically. Nesting plan and nesting optimization were realizeduniformly. On the one hand, it makes sheet selecting be more automatic. On the other hand, itmakes the sheet utilization be further promoted.
(5) According to the above core algorithm, a nesting system has been developed.Experiments have proved that the system has good performance.
排样问题的目标是在给定的几何图形上不重叠地叠放更多的几何图形，使材料利用率最高。这是一类NP-hard问题，而且大规模规则件排样和不规则件排样问题随着问题规模的增大，计算复杂度更是爆炸性增长。如何缩短排样时间同时提高板料利用率，是该问题研究的重点和难点。本文从排样的数据结构、优化理论、算法分析以及协同计算等方面进行了深入的研究，提出了一系列解决方案和算法并开发了一个排样实验系统对算法进行了验证和分析。研究成果和创新点可概括如下：
1.对排样问题提出了一套基于图像处理的数据表示和评价方法
对于排样问题的研究，目前学者们绝大部分是采用基于图形的方法。但其实基于图像的方法有独特的优势，论文对这方面进行了探索。论文提出了一种基于图像颜色数据分析的重叠检测、出界检测和评价方法，并通过为图像建立“角边链”（描述零件像素坐标和相交等信息）和“信息板”（描述板材像素已被哪个零件占据）数据结构并依据这些数据绘图，使得在试排图像中基于边就可以实现分析评价，使基于图像的二维排样问题复杂度由面积级降至线性级。
2.提出了动态邻域及并行模拟退火的算法
基于图像的方法的一个缺点是精度不足，为了增加精度，可以扩大图像的尺寸，但这会引起计算的复杂度和排样时间的飞速增加。为了解决这个矛盾，论文对二维排样模拟退火算法的邻域机制和接受新解的机制进行了改进，提出一套动态邻域及并行模拟退火算法，从而解决了“离散”类方法中的精度与时间的矛盾，并使得用模拟退火求解二维排样问题的速度得到了极大提高。
3.提出一种基于“开放边集”的解码方法。
“开放边集”是一种对后续零件入排有指导意义的轮廓或孔洞边段的有序集合。基于开放边集，论文提出一种用百分比和入排角度组成的编码方法，该方法可以表示所有可能的入排位置。基于这种百分比编码，可以实现快速搜索入排方案，从而实现构造解码。基于开放边集的解码方法不同于传统的BL、BLF、最低水平线、剩余矩形等方法，也不用计算临界多边形（NFP），排样无需进行矩形化预处理和零件靠接后处理，无论矩形件还是不规则件都适合，是一种新的入排解码思路。
论文继续提出基于该解码算法与遗传算法结合的混合排样算法，并进一步提出一些加速排样的新技术，如配角初排、开边挑选、分布式方案。这些算法使得排样的板材利用率比前人有所提高，多个实验算例打破了已有报道的最高利用率。
4.对余料管理进行了研究，并提出了一个基于余料的套排规划算法
合理利用余料是提高板材利用率的一个好思路。论文研究了板材排样完成后余料图像的提取、余料的分解以及余料自动再参排的方法，并实现了套排规划与排样优化的同一化，一方面使得板材选件更加自动化，另一方面使得多次排样后板材利用率进一步提高。
5.根据以上核心算法，编写了排样程序系统。实验证明，该排样系统效果良好。
Metal sheet is a kind of the main material in ship building. A key problem in shipbuilding is how to design the cutting layout and let the utilization of the sheet be maximal.Nesting system for ship building can increase the production efficiency and the utilization ofresource, and it can ensure the shipbuilding intelligent and digital.
The goal of the nesting problem is to place geometric figures in another given geometricfigure as more as posible, so that getting the maximum material utilization. This is a kind ofNP-hard problem. Furthermore, as to the large-scale or irregular nesting problem, thecomputation complexity will grow explosively when the problem scale increase. How toshorten the nesting time while increasing the utilization? It is the key point and difficulty inresearch. This paper studies the nesting problem deeply in data structure, optimization theory,algorithm, collaborative computing. A series of solutions and algorithms are brought forward.A testing nest system was developed and verified the algorithms. The achievments andinovations are listed as follow:
(1) Put forward a set of data structures and evaluation methods based image processing
At present, most research of nesting problem is base on graphics. However, methodbased on image has special advantage. This paper explores in this area. This paper putforwards a method for overlap detection, out of bounds testing and evaluation. Throughcreating the data structures of “Vertex-Edge Chain”(describing part pixel coordinates andintersection information) and “Information Board”(recording which parts have occupiedwhich sheet pixels) and drawing according these data, analysis and evaluation can beachieved, so that the complexity of two-dimensional nesting problem based on imagedecreases to linear level from area level.
(2)Brings forword the algorithm of dynamic neighborhood and parellel simulatedannealing
A shortcoming of the method based on image is that the precision not enough. Expandthe image dimension can increase precision, but computing complexity will grow at very fastspeed. In order to resolve this conflict, this paper improves the neighborhood mechanism andof new solution accepting mechanism, and brings forward an algorithm of dynamicneighborhood scale and parallel simulated annealing. This algorithm resolved the conflict, sothat the speed of nesting increases greatly when using simulated annealing.
(3) Put forward a decode method based on “open edge set”.
Based on the “open edge set”, a encoding method which described with percentage andplacing angle is brought forward. This encoding method can represent all the possible places.Based of this percent encoding, we can search for good place quickly. This decoding methodis different from the traditional methods such as BL, BLF, Lowest Horizontal Line, remainingrectangle, and needn’t NFP. Rectangle pretreatment and collision post processing are notneeded either. It is a new idea for nest decoding.
This paper continues to raise a mixed algorithm combined with the decoding method andgenetic algorithm. And further Some technologies that speed up nesting were discussed, suchangle match, open edge selecting and distributed method. These algorithms allow the nestingutilization be better. The utilization of some testing example exceed existing reports.
(4) discussed the remnant management, and put forward a nesting plan method thatbased on remnant.
This paper discussed the extraction, decomposition of remnants and the method ofattending nesting again automatically. Nesting plan and nesting optimization were realizeduniformly. On the one hand, it makes sheet selecting be more automatic. On the other hand, itmakes the sheet utilization be further promoted.
(5) According to the above core algorithm, a nesting system has been developed.Experiments have proved that the system has good performance.
引文
[1] Garey M R, Johnson D S．Computer and Interactability：AGuide to the Theory ofNP-Completeness[M]．San Francisco: W H Freeman and Company.1979.
[2]王洪涛,廖敏.基于网络的钣金件展开排样系统设计[J].机械设计与制造,2011,5:36-38.
[3]程晖,唐明浩.遗传模拟退火算法在服装排料中的研究[J].微型机与应用,2012,1:
[4]张玉萍,张春丽,蒋寿伟.皮料优化排样的有效方法[J].软件学报,2005,16(2):316-323.
[5]崔耀东.采用计算机提高玻璃下料利用率的方法[J].建筑技术,1994,9:
[6]崔耀东.计算机排样技术及其应用[M]．北京：机械工业出版社，2004.1.
[7]贾志欣.排样问题的研究现状与趋势.计算机辅助设计与图形学学报[J],2004,16(7):890-897.
[8]周石林.一维下料问题的研究[D].南京航空航天大学硕士学位论文.2000.
[9] Wei Liangliang, YeJiawei. Contrast of one-dimensional CuttingAlgorithm[C]. The5thWorld Multiconference on Systemics, Cybernetics and Inofmratics Orlando, USA,2001.
[10]白瑞斌.临界多边形法在二维不规则零件排样中的研究与实现[D].西北工业大学硕士学位论文.2002.
[11] L.V. Kantorovich. Mathematical methods of organizing and planning production (AnEnglish translation on a Russian paper published in1939)[J]. Management Science.1960(6):363-422.
[12] Gilmore. P. C. and Gomory. R. E. A Linear programming approach to the cutting stockproblem. Operations Research[J].1961,9(5):849-859.
[13] Gilmore. P. C. and Gomory. R. E. A Linear programming approach to the cutting stockproblem–partⅡ. Operations Research[J].1963,11(5):863-888.
[14] Gilmore.P.C.and R.E. Gomory. Multistage cutting stock problems of two and moredimensions. Operations Research[J].1965,13(1):94-120.
[15] Gilmore.P. C.and R.E. Gomory. The theory and computation of knapsack functions.Operation Research[J].1966,14(5):849-859.
[16] Sweeney P E, Parternoster E R. Cutting and packing problems:Acategorized,application-orientated research bibliography[J]. Journal of Operational Research Society.1992,43(7):691-706.
[17]Alberto Caprara, Hans Kellerer, Ulrich Pferschy, et al.Approximation algorithm forknapsack problems with cardinality constraints[J]. European Journal of OperationalResearch,2000,123(2):333-345.
[18] Petra Schwerin, Gerhard Wascher. The Bin-packing problem: Aproblem generator andsome numerical experiments with FFD packing and MTP[J]. International Transactionsin Operational Research,1997,4(5/6):377-389.
[19] Zhang G H, Cai X Q, Wong C K. Linear time-approximation algorithms for binpacking[J]. Operations Research Letter,2000,26(5):217-222.
[20] Miro Gradisar，Gortan Resinovic，Miroljub Kljajic．Ahybrid approach for optimizationof one-dimensional cutting[J]．European Journal ofOperational Research，1999，119(3)：719-728.
[21] Vasko F J，Newhart D D，Kenneth L，et a1．Ahierarchical approach for one—dimensional cutting stock problems in the steel industry that maximizes yield andminimizes overgrading[J]．European Journal of Operational Research，1999，114(1)：72-82.
[22] Toth Paolo．Optimization engineering techniques for exact solution of NP-hardcombinatorial optimization problems[J]．European Journal of Operational Research，2000，125(2)，222-238.
[23]Chiotti O J，Montagna J M．Aglobal approach for the provision of bar pieces in ametallurgic firm[J]．Mathematical and Computer Modelling，1998，28(9)：73-89.
[24]Oliver Hohhaus．On the best number of different standard lengths to stock forone．dimensional assortment problems[J]. International Journal of ProductionEconomics。2003，83(3)：233-246.
[25] Belov G，Scheithauer G．Acutting plane algorithm for the one-dimensional cutting stockproblem with multiple stock lengths[J]．European Journal of Operational Research，2002，141(2)：274-294.
[26] Schilling，Gordian; Georgiadis，Miehael C..An algorithm for the determinationof optimalcutting patterns. Computers and Operations Research,2002,29(8):1041-1058
[27] Zak，Eugene J.. Modeling multistage cutting stock problems. European Journal ofOperational Research,2002,141(2):313-327.
[28] Liu Hong，Zeng Guangzhou，Lin Zongkai．Asystemof optimizing nesting withanalogical learning mechanism[J]．Computers&Industrial Engineering，1997，32(4)：713-725.
[29] Heungsoon F L，Sewell E C．The strip-packing problem for a boat manufacturingfirm[J]．1iE Transactions，1999，31(7)：639-65l.
[30] Dagli C H．Tatoglu MY．An approach to two dimensional cutting stockproblems[J]．International Journal of Production Research，1987，25(2)：175～190.
[31] Fayard，Didier;Zissimo Poulos，Vassilis，An approximation algorithm for solvingunconstrained two-dimensional knapsack problems[J]. European Journal of OperationalResearch,1995,84(3):618-632.
[32] Dell’Amico，Mauro; Martello，Silvano; Vigo，Daniele.Alower bound for thenon-oriented two-dimensional bin packing problem[J]. DiscreteApplied Mathematics,2002,118(1-2):13-24.
[33] Dagli C．Cutting stock problem：Combined use of heuristics and optimizationmethods[A]．In：Proceedings of the9th International Conference on ProductionResearch，1987．843-849.
[34] Dagli CH．Knowledge—based systems for cutting stock problems[J]．European Journalof Operational Research，1990，44(2):160-166.
[35] Schollmeyer M，Lin J Q，Krishnamurthy K，et a1．Hybrid expert systemand operationsresearch for solving nesting problems[A]．In：Proceedings of the World Congress onExpert System．New York：Pergamon Press，1991:1223-l23l.
[36]Loris Faina.An application of simulated annealing to the cutting stock problem[J]. Eur Jof Oper Res,1999,114:542-556.
[37]贾志欣,殷国富,罗阳等.矩形件排样的模拟退火算法求解[J].四川大学学报(工程科学版),2001,33(5):35-38.
[38]Stefan Jakobs. On genetic algorithms for the packing of polygons[J]. Eur J of Oper Res,1996,88:165-181.
[39]曹炬,胡修彪.大规模矩形件优化排样的遗传算法[J].锻压机械.1999,4:17-20.
[40]宋连超,朱建良,张彤.矩形件排样优化贪婪算法及系统开发[J].哈尔滨理工大学学报,2007,1:29-31.
[41]李方娟,陈玉全,李金宇等.冲裁件优化排样算法研究[J].哈尔滨理工大学学报,2007,6:100-103.
[42] Levine J, Ducatelle F.Ant colony optimization and local search for bin packing andcutting stock problems[J]. Journal of the Operational Research Society,2004,55:705-716.
[43]宋佩华,蒋联源,欧启忠.基于离散粒子群算法求解矩形件排样问题[J].计算机应用与软件.2008,25(1):238-240.
[44] Hopper E，Turton B．Agenetic algorithm for a2D industrial packing problem[J].Computers&Industrial Engineering，1999，37(1/2)：375～378
[45] Leung T W，Yung C H，Marvin D．Troutt．Application of genetic search and simulatedannealing to the two-dimensional non-guillotine cutting stock problem[J]．Computers&Industrial Engineering，2001，40(3)：201～204
[46] B S Baker，E G Coffman，R LRivest．on}l0ganal packing in two dimensions[J]．SIAMJournal on Computing，1980，9(4)：846—855
[47]刘德全、腾弘飞．矩形件排样问题的遗传算法求解[J]．小型微型计算机系统，1998,19(12):20-25
[48] Liu D.Q., Teng H.F..An improved BL-algorithm for genetic algorithm of the orthogonalpacking of rectangles[J]. European Journal of Operational Research,1999,112(2):413-420
[49] Chazelle B..The bottomn-left bin-packing heuristic: an efficient implementation[J].IEEETransactions on Computers,1983,C-32(8):697–70
[50]贾志欣、殷国富、罗阳．二维不规则零件排样问题的遗传算法求解[J]．计算机辅助设计及图形学学报.2002,14(5):467-470
[51]李满江、孟祥旭．矩形件和任意多边形排样问题的算法及应用[J]．贵州工业大学学报(自然科学版),2002,31(4):126-130
[52]梁利东、叶家玮等．船体板材排样优化算法研究设计与智能系统的设计[D]．华南理工大学，2009年博士论文
[53] T.W.Leung,C.H.Yung,Marvin D.Troutt.Application of genetic search and simulatedannealing to the two-dimensional non-guillotine cutting stock problem[J]. Computers&Industiral Engineering.2001,40:201-204
[54] Chen M., Huang W.Q.. A two-level search algorithm for2Drectangular packing problem[J]. Computers&Industrial Engineering,2007,53(1):123-136
[55] Binkley K.J., Hagiwara M..Applying self-adaptive evolutionary algorithmsto two-dimensional packing problems using a four corners' heuristic[J]. EuropeanJournal of Operational Research,2007,183(3):1230-1248
[56] Wang Huaiqing, Huang Wenqi, Zhang Quan, et al.An ImprovedAlgorithm for thePacking of Unequal Circles Within a Larger Containing Circle[J]. European Journal ofOperational Research,2002,141(2):440-453.
[57] Huang Wenqi, Li Yu, Li Chumin, et al. New Heuristic for Packing Unequal Circles into aCircular Container[J]. Computers&Operations Research,2006,33(8):2125-2142.
[58]Akeb H, Hifi M, M’Hallah R.ABeam SearchAlgorithm for the Circular PackingProblem[J]. Computers&Operations Research,2009,36(5):1513-1528.
[59]赵政宝、楚纪正，尚颖.用于求解二维圆形排样问题的自适应混合算法[J].计算机工程.2012,38(8):260-267
[60]曹新明、蒋瑞斌.不规则零件最小包络矩形的求解研究[J].科技通报,2007,1(23):102-105.
[61]杨传华、吴锦文、李殿国等.基于二维不规则图形的实用排样算法研究.组合机床与自动化加工技术.2010,3:88-90
[62]贾志欣，殷国富，罗阳等.异型件排样系统的研究与开发.计算机工程.2002,28(12).218-220
[63] GomesAM，Oliveira JF．A2-exchange heuristic for nesting problems．European Journalof Operational Research，2002，141(2)：359-370
[64] GomesAM，Oliveira JF．Solving irregular strip packing problems by hybridisingsimulated annealing and linear programming．European Journal ofOperationalResearch，2006，17l(3)：811-829．
[65] Liu HY，He YJ．Algorithm for2-D irregular—shaped nesting problem based on the NFPalgorithm and lowest-gravity—center principle．Journal of Zhejiang University--ScienceA，2006，7(4)：570—576．
[66] Bennell J A，Downsland KA，Dowsland W B．The irregular cutting-stock problem-a newprocedure for deriving the no．fit polygon[J]．Computer&Operations Research，2001(28)：271-287．
[66]刘嘉敏，佟德刚，黄有群.临界多边形生成算法的改进[J]．沈阳工业大学学报.2005,27(5):567-570.
[67] Dowsland K.A., Vaid S., Dowsland W.B..An algorithm for polygon placement using abottom-left strategy[J]. European Journal of Operational Research,2002,141(2):371-381.
[68]刘胡瑶、何援军.基于重心NFP的二维不规则形状排样算法[J].中国机械工程.2007,18(6).723-731.
[69] Oliveira J.F., GomesA.M., Ferreira J.S.. TOPOS–Anew constructive algorithm fornesting problems[J]. OR Spectrum,2000,22(2):263-28
[70]陈勇唐敏童若锋等.基于遗传模拟退火算法的不规则多边形排样[J].计算机辅助设计与图形学学报.2003,15(5):598-609
[71] BabuAR, Babu NR．Ageneric approach for nesting of2-Dparts in2-Dsheets usinggenetic and heuristic algorithms．Computer-Aided Design,2001,33:879-891．
[72] BouganisA, Shanahan M．Avision-based intelligent system for packing2-D irregularshapes．IEEE Trans．onAutomation Science and Engineering,2007,4(3):382-394．
[73] Zhang YP, Zhang CL, Jiang SW．An effective approach for leather nesting．Journal ofSoftware,2005,16(2)：316-323
[74] Heckmann R, Lengauer T．Asimulated annealing approach to the nesting problem in thetextile manufacturing industry．Annals of Operations Research,1995,57:103-133．
[75]杨彩、顾海明、史俊友等.不规则件最优排放布局的实现[J].青岛科技大学学报.2005,26(2):146-157
[76]林好转.平行线分割一步平移法排样算法的研究[J].锻压技术,1994,19(5):33-35
[77]吉晓民，杨先海.冲裁件优化排样的最大截距法[J].西安理工大学学报,1996,12(2):91-94
[78] Nye T.J.. Stamping strip layout for optimal raw material utilization[J]. Journal ofManufacturing Systems,2000,19(4):239-248
[79] Mulero R., Layton B.. Two-dimensional Minkowski sum optimization of gangedstamping blank layouts for use on pre-cut sheet metal for convex and concave parts[J].Journal of Manufacturing Systems,2007,26(1):44-52
[80]梅颖、叶家玮等．船体建造板材套料系统中排样优化算法与碰靠技术研究[D]．华南理工大学，2010年博士论文
[81]岳琪曹军.改进的模拟退火算法在板式家具工业优化下料问题中的应用[J].计算机应用研究.2005,22(10):226-228
[82]史俊友,苏传生,翟红岩.不规则零件优化排样的神经网络混合优化算法[J].工程设计学报.2009,16(4):271-275
[83]李敬花、樊付见、王昊等.遗传模拟退火融合算法求解工程二维排样问题[J].计算机集成制造系统.2011,17(9):1962-1967
[84] Aarts E H L, Van Laarhoven P J M. SimulatedAnnealing, Theory and Application[M].Dordrecht: D Reidel Publishing Company.1987.
[85] Hopper E，Turton B.An empirical investigation of meta-heuristic and heuristicalgorithms for a2D packing problem[J]. European Journal of Operational Research.2001,128(1):34-57.
[86]陈仕军、曹炬.矩形件优化排样的一种启发式算法[J].计算机工程与应用.2010,46(12).230-232
[87] Loris Faina.An application of simulated annealing to the cutting stock problem[J]. Eur Jof Oper Res,1999,114:542-556.
[88] S. Jakobs. On genetic algorithms for the packing of polygons[J]. Eurpean Journal ofOperational Research.1996(88):165-181
[89]隗平平、刘斌.基于并行遗传算法的矩形件排样优化[J].组合机床与自动化加工技术.2011,3:78-82
[90]梁利东、叶家玮.基于遗传算法的不规则件优化排样研究[J].计算机工程与应用.2009,45(2):223-228
[91] Levine J, Ducatelle F.Ant colony optimization and local search for bin packing andcutting stock problems[J]. Journal of the Operational Research Society,2004,55:705-716.
[92]冯琳、史俊友.基于蚁群算法的矩形件优化排样问题[J].青岛科技大学学报(自然科学版).2011,32(1):90-94
[93]梁利东、钟相强.粒子群算法在不规则件排样优化中的应用[J].中国机械工程.2010,21(17):2050-2052
[94]黄兆龙.用启发算法和神经网络法解决二维不规则零件排样问题[J].微计算机信息.2004,20(7):118-119
[95]谢青.遗传模拟退火混合算法在钣金自动排样中的研究[J].机械.2010,37(5):18-21.
[96]李方娟、陈玉全、安爱民等.冲裁件智能排样系统的研究[J].制造技术与机床.2008,6:113-115.
[97]陈江义、宋雪枫、张明伟.融合蚁群算法和遗传算法的矩形件排样问题研究[J].郑州大学学报(理学版).2011,43(2):79-82
[98]宋亚男、邓飞其、叶家玮.基于改进免疫遗传算法的不规则图形排样[J].计算机工程.2005,31(9):170-172
[99]李明、黄平捷、周泽魁.基于小生境遗传算法的矩形件优化排样[J].湖南大学学报(自然科学版).2009,36(1):46-49.
[100] Udy J L, et a1．Computation of interferences between three-dimensional objects and theoptimal packing problem[J]．Advance in Engineering Software,1988,10(1)：8-14
[101] Kim J J, Gossard D C．Reasoning on the location of components for assemblypacking[J]．Journal of Mechanical Design,1991,118(4)：402-407
[102] Bischoff E E, Janetz F, Ratcliff M S W．Loading pallets with non-identicalitems[J]．European Journal of Operational Research,1995,84(3)：681-692
[103] Andreas Bortfeldt, Herrnann Gehring．Ahybrid genetic algorithm for the containerloading problem[J]．EuropeanJournal ofOperational Research,2001,131(1)：143-161
[104] Morabito R,Arenales M．AnAND／OR-graph approach to the container loadingproblem[J]．International Transactions of Operational Research,1994,1(1)：59-73
[105]张德富、魏丽军、陈青山等.三维装箱问题的组合启发式算法[J]．软件学报.2007,18(9):2083-2089
[106]张德富、彭煜、朱文兴等.求解三维装箱问题的混合模拟退火算法[J]．计算机学报.2009,11:2147-2156
[107]卜雷、袁新江、蒲云.基于遗传算法的集装箱单箱三维装载优化问题[J]．中国铁道科学.2004,25(4):108-111
[108]许光泞、俞金寿.改进遗传算法求解三维集装箱装载问题[J]．华东理工大学学报（自然科学版）.2007,33(3):425-428
[109]陶献伟,王华昌,李志刚.矩形件优化排样模拟退火算法求解[J].锻压技术.2003,3期:24-27.
[110] Hifi M, Paschos V T, Zissimopoulos V.Asimulated annealing approach for the circularcutting problem[J]. European Journal of Operational Research,2004,159:430-448.
[111]李明,宋成芳,周泽魁.一种二维不规则零件优化排样算法[J].四川大学学报：工程科学版.2005,37(4):134-138.
[112]王桂宾,周来水,邓冬梅.基于模拟退火算法的矩形件排样[J].中国制造业信息化.2006,8:65-67.
[113] Metropolis N., RosenbluthA. W., Rosenbluth M.N. et al. Equation of state Calculationby Fast Computing Machines[J]. Journal of Chemical Physics.1953,21(6):1087-1092.
[114] Kirpatrick S., Gelatt Jr. C. D., Vecchi M. P. Optimization by SimulatedAnnealing[J].Science.1983,220(13):671-680.
[115]王凌.智能优化算法及其应用[M].北京:清华大学出版社.2001.
[116]MarzcUo S，MonaciM，Vigo D．An Exact App Roach to the Strip-packingProblem[J].Infonm Journal On Computing,2003,(5):310-319．
[117]王菲,罗意平,杨岳.定序列矩形件优化排样新算法[J].工程图学学报,2005,26(4):47-50.
[118]杨传华,吴锦文,李亚芹等.定序列矩形件优化排样的二维搜索算法[J].佳木斯大学学报（自然科学版），2010，28(3):354-356,359.
[119]Andrea Lodi etc．Two-dimemional Packing Problems：Asurvey[J]．Eur. J. of Oper.Res．2002,141:241-252．
[120]BortfeldtA.Agenetic algori thm for the two-dimensional strip packing problem withrectangular pieces[J]. Eu ropean Journal of Operational Research,2006,172(3):814-837.
[121]龚志辉,黄星梅.二维矩形件优化排样算法的改进研究[J].湖南大学学报(自然科学版),2003,30(3):47-49.
[122]唐坚刚,刘丛,张丽红.基于改进遗传算法的不规则图形排样[J].计算机工程,2010,36(3):185-187.
[123]陈锦昌. C语言计算机绘图教程[M].广州：华南理工大学出版社，1998.9.
[124]关治、陆金甫，数值分析基础[M]，高等教育出版社，1998.5.
[125]Egeblad J，Nielsen B K，OdgaardA.Fast neighborhood seareh for two-andthree-dimensional nesting problems[J]. European Journal of Operational Research.2007,183(3):1249-1266.
[126]Hopper E.. Two-dimensional packing utilising evolutionary algorithem and othermeta-heuristic methods[D]. Cardiff, UK:University of Wales,2000
[127]Burke E., Hellier R., Kendall G., et al..ANew Bottom-Left-Fill HeuristicAlgorithm forthe Two-Dimensional Irregular Packing Problem[J]. Operations Research,2006,54(3):587-601.
[128]Fujita K.,Akagji S., Kirokawa N.. Hybrid approach for optimal nesting using a geneticalgorithm and a local minimization algorithm[J].Advances in DesignAutomation;American Society of Mechanical Engineers, Design Engineering Division (Publication)DE,1993,65pt1:477-484.
[129]Holland J. H.Adaptation in Natural andArtificial System[M].AnnArbor, MI: TheUniversity of Michigan Press.1975.
[130] Stephen C H Leung, Yangbin Lin, Defu Zhang. Extended local search algorithm basedon nonlinear programming for two-dimensional irregular strip packing problem[J].Computers&Operations Research,2012,39(3):678-686.
[131]Del Valle,Aline M, De Queiroz etc.. Heuristics for two-dimensional knapsack andcutting stock problems with items of irregular shape[J]. Expert Systems withApplications,2012,39(16):12589-12598.
[132]Kannan D.An Introduction to Stochastic[M]. Elsevier North Holland Inc.1979.
[133]何春雄.应用随机过程[M].广州:华南理工大学出版社.2008.
[2]王洪涛,廖敏.基于网络的钣金件展开排样系统设计[J].机械设计与制造,2011,5:36-38.
[3]程晖,唐明浩.遗传模拟退火算法在服装排料中的研究[J].微型机与应用,2012,1:
[4]张玉萍,张春丽,蒋寿伟.皮料优化排样的有效方法[J].软件学报,2005,16(2):316-323.
[5]崔耀东.采用计算机提高玻璃下料利用率的方法[J].建筑技术,1994,9:
[6]崔耀东.计算机排样技术及其应用[M]．北京：机械工业出版社，2004.1.
[7]贾志欣.排样问题的研究现状与趋势.计算机辅助设计与图形学学报[J],2004,16(7):890-897.
[8]周石林.一维下料问题的研究[D].南京航空航天大学硕士学位论文.2000.
[9] Wei Liangliang, YeJiawei. Contrast of one-dimensional CuttingAlgorithm[C]. The5thWorld Multiconference on Systemics, Cybernetics and Inofmratics Orlando, USA,2001.
[10]白瑞斌.临界多边形法在二维不规则零件排样中的研究与实现[D].西北工业大学硕士学位论文.2002.
[11] L.V. Kantorovich. Mathematical methods of organizing and planning production (AnEnglish translation on a Russian paper published in1939)[J]. Management Science.1960(6):363-422.
[12] Gilmore. P. C. and Gomory. R. E. A Linear programming approach to the cutting stockproblem. Operations Research[J].1961,9(5):849-859.
[13] Gilmore. P. C. and Gomory. R. E. A Linear programming approach to the cutting stockproblem–partⅡ. Operations Research[J].1963,11(5):863-888.
[14] Gilmore.P.C.and R.E. Gomory. Multistage cutting stock problems of two and moredimensions. Operations Research[J].1965,13(1):94-120.
[15] Gilmore.P. C.and R.E. Gomory. The theory and computation of knapsack functions.Operation Research[J].1966,14(5):849-859.
[16] Sweeney P E, Parternoster E R. Cutting and packing problems:Acategorized,application-orientated research bibliography[J]. Journal of Operational Research Society.1992,43(7):691-706.
[17]Alberto Caprara, Hans Kellerer, Ulrich Pferschy, et al.Approximation algorithm forknapsack problems with cardinality constraints[J]. European Journal of OperationalResearch,2000,123(2):333-345.
[18] Petra Schwerin, Gerhard Wascher. The Bin-packing problem: Aproblem generator andsome numerical experiments with FFD packing and MTP[J]. International Transactionsin Operational Research,1997,4(5/6):377-389.
[19] Zhang G H, Cai X Q, Wong C K. Linear time-approximation algorithms for binpacking[J]. Operations Research Letter,2000,26(5):217-222.
[20] Miro Gradisar，Gortan Resinovic，Miroljub Kljajic．Ahybrid approach for optimizationof one-dimensional cutting[J]．European Journal ofOperational Research，1999，119(3)：719-728.
[21] Vasko F J，Newhart D D，Kenneth L，et a1．Ahierarchical approach for one—dimensional cutting stock problems in the steel industry that maximizes yield andminimizes overgrading[J]．European Journal of Operational Research，1999，114(1)：72-82.
[22] Toth Paolo．Optimization engineering techniques for exact solution of NP-hardcombinatorial optimization problems[J]．European Journal of Operational Research，2000，125(2)，222-238.
[23]Chiotti O J，Montagna J M．Aglobal approach for the provision of bar pieces in ametallurgic firm[J]．Mathematical and Computer Modelling，1998，28(9)：73-89.
[24]Oliver Hohhaus．On the best number of different standard lengths to stock forone．dimensional assortment problems[J]. International Journal of ProductionEconomics。2003，83(3)：233-246.
[25] Belov G，Scheithauer G．Acutting plane algorithm for the one-dimensional cutting stockproblem with multiple stock lengths[J]．European Journal of Operational Research，2002，141(2)：274-294.
[26] Schilling，Gordian; Georgiadis，Miehael C..An algorithm for the determinationof optimalcutting patterns. Computers and Operations Research,2002,29(8):1041-1058
[27] Zak，Eugene J.. Modeling multistage cutting stock problems. European Journal ofOperational Research,2002,141(2):313-327.
[28] Liu Hong，Zeng Guangzhou，Lin Zongkai．Asystemof optimizing nesting withanalogical learning mechanism[J]．Computers&Industrial Engineering，1997，32(4)：713-725.
[29] Heungsoon F L，Sewell E C．The strip-packing problem for a boat manufacturingfirm[J]．1iE Transactions，1999，31(7)：639-65l.
[30] Dagli C H．Tatoglu MY．An approach to two dimensional cutting stockproblems[J]．International Journal of Production Research，1987，25(2)：175～190.
[31] Fayard，Didier;Zissimo Poulos，Vassilis，An approximation algorithm for solvingunconstrained two-dimensional knapsack problems[J]. European Journal of OperationalResearch,1995,84(3):618-632.
[32] Dell’Amico，Mauro; Martello，Silvano; Vigo，Daniele.Alower bound for thenon-oriented two-dimensional bin packing problem[J]. DiscreteApplied Mathematics,2002,118(1-2):13-24.
[33] Dagli C．Cutting stock problem：Combined use of heuristics and optimizationmethods[A]．In：Proceedings of the9th International Conference on ProductionResearch，1987．843-849.
[34] Dagli CH．Knowledge—based systems for cutting stock problems[J]．European Journalof Operational Research，1990，44(2):160-166.
[35] Schollmeyer M，Lin J Q，Krishnamurthy K，et a1．Hybrid expert systemand operationsresearch for solving nesting problems[A]．In：Proceedings of the World Congress onExpert System．New York：Pergamon Press，1991:1223-l23l.
[36]Loris Faina.An application of simulated annealing to the cutting stock problem[J]. Eur Jof Oper Res,1999,114:542-556.
[37]贾志欣,殷国富,罗阳等.矩形件排样的模拟退火算法求解[J].四川大学学报(工程科学版),2001,33(5):35-38.
[38]Stefan Jakobs. On genetic algorithms for the packing of polygons[J]. Eur J of Oper Res,1996,88:165-181.
[39]曹炬,胡修彪.大规模矩形件优化排样的遗传算法[J].锻压机械.1999,4:17-20.
[40]宋连超,朱建良,张彤.矩形件排样优化贪婪算法及系统开发[J].哈尔滨理工大学学报,2007,1:29-31.
[41]李方娟,陈玉全,李金宇等.冲裁件优化排样算法研究[J].哈尔滨理工大学学报,2007,6:100-103.
[42] Levine J, Ducatelle F.Ant colony optimization and local search for bin packing andcutting stock problems[J]. Journal of the Operational Research Society,2004,55:705-716.
[43]宋佩华,蒋联源,欧启忠.基于离散粒子群算法求解矩形件排样问题[J].计算机应用与软件.2008,25(1):238-240.
[44] Hopper E，Turton B．Agenetic algorithm for a2D industrial packing problem[J].Computers&Industrial Engineering，1999，37(1/2)：375～378
[45] Leung T W，Yung C H，Marvin D．Troutt．Application of genetic search and simulatedannealing to the two-dimensional non-guillotine cutting stock problem[J]．Computers&Industrial Engineering，2001，40(3)：201～204
[46] B S Baker，E G Coffman，R LRivest．on}l0ganal packing in two dimensions[J]．SIAMJournal on Computing，1980，9(4)：846—855
[47]刘德全、腾弘飞．矩形件排样问题的遗传算法求解[J]．小型微型计算机系统，1998,19(12):20-25
[48] Liu D.Q., Teng H.F..An improved BL-algorithm for genetic algorithm of the orthogonalpacking of rectangles[J]. European Journal of Operational Research,1999,112(2):413-420
[49] Chazelle B..The bottomn-left bin-packing heuristic: an efficient implementation[J].IEEETransactions on Computers,1983,C-32(8):697–70
[50]贾志欣、殷国富、罗阳．二维不规则零件排样问题的遗传算法求解[J]．计算机辅助设计及图形学学报.2002,14(5):467-470
[51]李满江、孟祥旭．矩形件和任意多边形排样问题的算法及应用[J]．贵州工业大学学报(自然科学版),2002,31(4):126-130
[52]梁利东、叶家玮等．船体板材排样优化算法研究设计与智能系统的设计[D]．华南理工大学，2009年博士论文
[53] T.W.Leung,C.H.Yung,Marvin D.Troutt.Application of genetic search and simulatedannealing to the two-dimensional non-guillotine cutting stock problem[J]. Computers&Industiral Engineering.2001,40:201-204
[54] Chen M., Huang W.Q.. A two-level search algorithm for2Drectangular packing problem[J]. Computers&Industrial Engineering,2007,53(1):123-136
[55] Binkley K.J., Hagiwara M..Applying self-adaptive evolutionary algorithmsto two-dimensional packing problems using a four corners' heuristic[J]. EuropeanJournal of Operational Research,2007,183(3):1230-1248
[56] Wang Huaiqing, Huang Wenqi, Zhang Quan, et al.An ImprovedAlgorithm for thePacking of Unequal Circles Within a Larger Containing Circle[J]. European Journal ofOperational Research,2002,141(2):440-453.
[57] Huang Wenqi, Li Yu, Li Chumin, et al. New Heuristic for Packing Unequal Circles into aCircular Container[J]. Computers&Operations Research,2006,33(8):2125-2142.
[58]Akeb H, Hifi M, M’Hallah R.ABeam SearchAlgorithm for the Circular PackingProblem[J]. Computers&Operations Research,2009,36(5):1513-1528.
[59]赵政宝、楚纪正，尚颖.用于求解二维圆形排样问题的自适应混合算法[J].计算机工程.2012,38(8):260-267
[60]曹新明、蒋瑞斌.不规则零件最小包络矩形的求解研究[J].科技通报,2007,1(23):102-105.
[61]杨传华、吴锦文、李殿国等.基于二维不规则图形的实用排样算法研究.组合机床与自动化加工技术.2010,3:88-90
[62]贾志欣，殷国富，罗阳等.异型件排样系统的研究与开发.计算机工程.2002,28(12).218-220
[63] GomesAM，Oliveira JF．A2-exchange heuristic for nesting problems．European Journalof Operational Research，2002，141(2)：359-370
[64] GomesAM，Oliveira JF．Solving irregular strip packing problems by hybridisingsimulated annealing and linear programming．European Journal ofOperationalResearch，2006，17l(3)：811-829．
[65] Liu HY，He YJ．Algorithm for2-D irregular—shaped nesting problem based on the NFPalgorithm and lowest-gravity—center principle．Journal of Zhejiang University--ScienceA，2006，7(4)：570—576．
[66] Bennell J A，Downsland KA，Dowsland W B．The irregular cutting-stock problem-a newprocedure for deriving the no．fit polygon[J]．Computer&Operations Research，2001(28)：271-287．
[66]刘嘉敏，佟德刚，黄有群.临界多边形生成算法的改进[J]．沈阳工业大学学报.2005,27(5):567-570.
[67] Dowsland K.A., Vaid S., Dowsland W.B..An algorithm for polygon placement using abottom-left strategy[J]. European Journal of Operational Research,2002,141(2):371-381.
[68]刘胡瑶、何援军.基于重心NFP的二维不规则形状排样算法[J].中国机械工程.2007,18(6).723-731.
[69] Oliveira J.F., GomesA.M., Ferreira J.S.. TOPOS–Anew constructive algorithm fornesting problems[J]. OR Spectrum,2000,22(2):263-28
[70]陈勇唐敏童若锋等.基于遗传模拟退火算法的不规则多边形排样[J].计算机辅助设计与图形学学报.2003,15(5):598-609
[71] BabuAR, Babu NR．Ageneric approach for nesting of2-Dparts in2-Dsheets usinggenetic and heuristic algorithms．Computer-Aided Design,2001,33:879-891．
[72] BouganisA, Shanahan M．Avision-based intelligent system for packing2-D irregularshapes．IEEE Trans．onAutomation Science and Engineering,2007,4(3):382-394．
[73] Zhang YP, Zhang CL, Jiang SW．An effective approach for leather nesting．Journal ofSoftware,2005,16(2)：316-323
[74] Heckmann R, Lengauer T．Asimulated annealing approach to the nesting problem in thetextile manufacturing industry．Annals of Operations Research,1995,57:103-133．
[75]杨彩、顾海明、史俊友等.不规则件最优排放布局的实现[J].青岛科技大学学报.2005,26(2):146-157
[76]林好转.平行线分割一步平移法排样算法的研究[J].锻压技术,1994,19(5):33-35
[77]吉晓民，杨先海.冲裁件优化排样的最大截距法[J].西安理工大学学报,1996,12(2):91-94
[78] Nye T.J.. Stamping strip layout for optimal raw material utilization[J]. Journal ofManufacturing Systems,2000,19(4):239-248
[79] Mulero R., Layton B.. Two-dimensional Minkowski sum optimization of gangedstamping blank layouts for use on pre-cut sheet metal for convex and concave parts[J].Journal of Manufacturing Systems,2007,26(1):44-52
[80]梅颖、叶家玮等．船体建造板材套料系统中排样优化算法与碰靠技术研究[D]．华南理工大学，2010年博士论文
[81]岳琪曹军.改进的模拟退火算法在板式家具工业优化下料问题中的应用[J].计算机应用研究.2005,22(10):226-228
[82]史俊友,苏传生,翟红岩.不规则零件优化排样的神经网络混合优化算法[J].工程设计学报.2009,16(4):271-275
[83]李敬花、樊付见、王昊等.遗传模拟退火融合算法求解工程二维排样问题[J].计算机集成制造系统.2011,17(9):1962-1967
[84] Aarts E H L, Van Laarhoven P J M. SimulatedAnnealing, Theory and Application[M].Dordrecht: D Reidel Publishing Company.1987.
[85] Hopper E，Turton B.An empirical investigation of meta-heuristic and heuristicalgorithms for a2D packing problem[J]. European Journal of Operational Research.2001,128(1):34-57.
[86]陈仕军、曹炬.矩形件优化排样的一种启发式算法[J].计算机工程与应用.2010,46(12).230-232
[87] Loris Faina.An application of simulated annealing to the cutting stock problem[J]. Eur Jof Oper Res,1999,114:542-556.
[88] S. Jakobs. On genetic algorithms for the packing of polygons[J]. Eurpean Journal ofOperational Research.1996(88):165-181
[89]隗平平、刘斌.基于并行遗传算法的矩形件排样优化[J].组合机床与自动化加工技术.2011,3:78-82
[90]梁利东、叶家玮.基于遗传算法的不规则件优化排样研究[J].计算机工程与应用.2009,45(2):223-228
[91] Levine J, Ducatelle F.Ant colony optimization and local search for bin packing andcutting stock problems[J]. Journal of the Operational Research Society,2004,55:705-716.
[92]冯琳、史俊友.基于蚁群算法的矩形件优化排样问题[J].青岛科技大学学报(自然科学版).2011,32(1):90-94
[93]梁利东、钟相强.粒子群算法在不规则件排样优化中的应用[J].中国机械工程.2010,21(17):2050-2052
[94]黄兆龙.用启发算法和神经网络法解决二维不规则零件排样问题[J].微计算机信息.2004,20(7):118-119
[95]谢青.遗传模拟退火混合算法在钣金自动排样中的研究[J].机械.2010,37(5):18-21.
[96]李方娟、陈玉全、安爱民等.冲裁件智能排样系统的研究[J].制造技术与机床.2008,6:113-115.
[97]陈江义、宋雪枫、张明伟.融合蚁群算法和遗传算法的矩形件排样问题研究[J].郑州大学学报(理学版).2011,43(2):79-82
[98]宋亚男、邓飞其、叶家玮.基于改进免疫遗传算法的不规则图形排样[J].计算机工程.2005,31(9):170-172
[99]李明、黄平捷、周泽魁.基于小生境遗传算法的矩形件优化排样[J].湖南大学学报(自然科学版).2009,36(1):46-49.
[100] Udy J L, et a1．Computation of interferences between three-dimensional objects and theoptimal packing problem[J]．Advance in Engineering Software,1988,10(1)：8-14
[101] Kim J J, Gossard D C．Reasoning on the location of components for assemblypacking[J]．Journal of Mechanical Design,1991,118(4)：402-407
[102] Bischoff E E, Janetz F, Ratcliff M S W．Loading pallets with non-identicalitems[J]．European Journal of Operational Research,1995,84(3)：681-692
[103] Andreas Bortfeldt, Herrnann Gehring．Ahybrid genetic algorithm for the containerloading problem[J]．EuropeanJournal ofOperational Research,2001,131(1)：143-161
[104] Morabito R,Arenales M．AnAND／OR-graph approach to the container loadingproblem[J]．International Transactions of Operational Research,1994,1(1)：59-73
[105]张德富、魏丽军、陈青山等.三维装箱问题的组合启发式算法[J]．软件学报.2007,18(9):2083-2089
[106]张德富、彭煜、朱文兴等.求解三维装箱问题的混合模拟退火算法[J]．计算机学报.2009,11:2147-2156
[107]卜雷、袁新江、蒲云.基于遗传算法的集装箱单箱三维装载优化问题[J]．中国铁道科学.2004,25(4):108-111
[108]许光泞、俞金寿.改进遗传算法求解三维集装箱装载问题[J]．华东理工大学学报（自然科学版）.2007,33(3):425-428
[109]陶献伟,王华昌,李志刚.矩形件优化排样模拟退火算法求解[J].锻压技术.2003,3期:24-27.
[110] Hifi M, Paschos V T, Zissimopoulos V.Asimulated annealing approach for the circularcutting problem[J]. European Journal of Operational Research,2004,159:430-448.
[111]李明,宋成芳,周泽魁.一种二维不规则零件优化排样算法[J].四川大学学报：工程科学版.2005,37(4):134-138.
[112]王桂宾,周来水,邓冬梅.基于模拟退火算法的矩形件排样[J].中国制造业信息化.2006,8:65-67.
[113] Metropolis N., RosenbluthA. W., Rosenbluth M.N. et al. Equation of state Calculationby Fast Computing Machines[J]. Journal of Chemical Physics.1953,21(6):1087-1092.
[114] Kirpatrick S., Gelatt Jr. C. D., Vecchi M. P. Optimization by SimulatedAnnealing[J].Science.1983,220(13):671-680.
[115]王凌.智能优化算法及其应用[M].北京:清华大学出版社.2001.
[116]MarzcUo S，MonaciM，Vigo D．An Exact App Roach to the Strip-packingProblem[J].Infonm Journal On Computing,2003,(5):310-319．
[117]王菲,罗意平,杨岳.定序列矩形件优化排样新算法[J].工程图学学报,2005,26(4):47-50.
[118]杨传华,吴锦文,李亚芹等.定序列矩形件优化排样的二维搜索算法[J].佳木斯大学学报（自然科学版），2010，28(3):354-356,359.
[119]Andrea Lodi etc．Two-dimemional Packing Problems：Asurvey[J]．Eur. J. of Oper.Res．2002,141:241-252．
[120]BortfeldtA.Agenetic algori thm for the two-dimensional strip packing problem withrectangular pieces[J]. Eu ropean Journal of Operational Research,2006,172(3):814-837.
[121]龚志辉,黄星梅.二维矩形件优化排样算法的改进研究[J].湖南大学学报(自然科学版),2003,30(3):47-49.
[122]唐坚刚,刘丛,张丽红.基于改进遗传算法的不规则图形排样[J].计算机工程,2010,36(3):185-187.
[123]陈锦昌. C语言计算机绘图教程[M].广州：华南理工大学出版社，1998.9.
[124]关治、陆金甫，数值分析基础[M]，高等教育出版社，1998.5.
[125]Egeblad J，Nielsen B K，OdgaardA.Fast neighborhood seareh for two-andthree-dimensional nesting problems[J]. European Journal of Operational Research.2007,183(3):1249-1266.
[126]Hopper E.. Two-dimensional packing utilising evolutionary algorithem and othermeta-heuristic methods[D]. Cardiff, UK:University of Wales,2000
[127]Burke E., Hellier R., Kendall G., et al..ANew Bottom-Left-Fill HeuristicAlgorithm forthe Two-Dimensional Irregular Packing Problem[J]. Operations Research,2006,54(3):587-601.
[128]Fujita K.,Akagji S., Kirokawa N.. Hybrid approach for optimal nesting using a geneticalgorithm and a local minimization algorithm[J].Advances in DesignAutomation;American Society of Mechanical Engineers, Design Engineering Division (Publication)DE,1993,65pt1:477-484.
[129]Holland J. H.Adaptation in Natural andArtificial System[M].AnnArbor, MI: TheUniversity of Michigan Press.1975.
[130] Stephen C H Leung, Yangbin Lin, Defu Zhang. Extended local search algorithm basedon nonlinear programming for two-dimensional irregular strip packing problem[J].Computers&Operations Research,2012,39(3):678-686.
[131]Del Valle,Aline M, De Queiroz etc.. Heuristics for two-dimensional knapsack andcutting stock problems with items of irregular shape[J]. Expert Systems withApplications,2012,39(16):12589-12598.
[132]Kannan D.An Introduction to Stochastic[M]. Elsevier North Holland Inc.1979.
[133]何春雄.应用随机过程[M].广州:华南理工大学出版社.2008.