基于遗传退火算法板式家具大规模矩形件优化下料研究
|
摘要
优化下料,是一个在产品设计、制造和使用中如何节约原料、优化利用资源的问题。对优化下料问题的研究具有重要经济意义和社会效益。它在计算理论上非常复杂和困难,而在实际生产中却有着广泛的应用。随着智能优化算法理论和计算机技术的发展,为人们提供了用现代优化算法和计算机进行优化下料的可能性。本文研究的优化下料问题主要是板式家具生产中在矩形原料板上的大规模矩形件排样问题。
针对在板式家具中板材下料问题的具体特点,结合板式家具下料的工艺和约束条件,给出了在矩形原料板材上的矩形零件优化下料的定义、特点、性质并提出了在工艺条件以及规模约束下的大规模板式家具优化下料的数学模型。在对下料优化方案生成算法的研究中,提出了一种“生成即可行”的排样方法。根据板式家具下料“一刀切(Guillotine Cutting)”的工艺特性,设计了一种二叉树结构来表现排样方案的生成过程,保证了所有的方案在产生时即可行,使整个方案生成过程中的所有解都是可行解,因此避免了在寻优过程中再对编码进行可行性验证的操作。
提出了将现代智能优化算法:遗传算法(GA)、模拟退火算法(SA)和根据这两种算法的各自优势将其融合后的遗传退火算法(GASA)在大规模板式家具下料中的应用。并在应用过程中,对算法进行了改进。针对模拟退火算法冷却进度表和邻域范围难以确定,进入局部最优后难以跳出的问题,设计了温度可控的冷却进度表,提出了搜索进入局部最优的判定函数和升温函数,使搜索进入局部最优后能及时升温,并从局部最优中跳出,保证了解的最优性。设计了初始温度、邻域结构和随机接受函数,提高了求解速度;针对遗传算法在矩形件优化下料问题中应用的实际特点,提出一种全新的面向对象的遗传编码方式和基于“贯通原料”的基因变异方式,将变异后不可用基因数量降到了零,就适应度函数、初始群体的生成和遗传操作等关键问题提出了相应的设计方法;对两种算法进行了详细的对比分析和论证,从理论和实践的角度总结了两种算法各自优缺点,取模拟退火算法和遗传算法的各自长处,将它们有机地结合在一起,分别采用了本文提出的模拟退火算法中升温的控制和遗传算法中的编码和变异的方式,生成温控遗传-退火算法,混合算法搜索全局最优的能力大大提高;对三种算法从理论和实践的角度进行了对比分析,遗传-退火算法兼有遗传算法中种群、个体、交配、基因、遗传、变异等淘汰劣质解的操作,也有模拟退火算法中冷却进度表和接受概率等寻优控制技术,可以更好地实现大规模矩形件下料问题的快速求解。
研制了板式家具大规模矩形件优化下料系统,实验表明,该软件的优化效果高于国内同类研究成果,而且操作极其简便,节约原材料效果显著,实用性强。对同一组数据的求解,第三种遗传退火算法优化效率更高。
Cutting stock is concerned with how to saving material, optimize resources in product designing, manufacturing. The research on the problem has important economic meaning and social benefit. It is very complicated and difficult in computing theory, but it has got the extensive application in the actual manufacture. With the development of intelligent optimize algorithm theory and computer technology, it offers the possibility to people to solve the problem with modern optimal algorithm and computer. In this paper, the cutting stock problem was consistsed of packing rectangular items onto a rectangular raw material in the fibre furniture manufacture.Considered of the concrete characteristics of the cutting stock problem in the fibre furniture, it combined the craft and restraint condition in the fibre furniture, it gave the definition, characteristics and nature of cutting stock in rectangle parts on the rectangle raw material board, and had put forward the restrained of craft and items' scale modes of the fibre furniture, the mathematics model was given; On the research of cutting stock algorithm, the paper presented a method of "Be Feasible on Producing". According to the craft characteristic of "Guillotine cutting" in the fibre furniture manufacture, the paper adopted the binary tree structure to perform the process with layout pattern, ensureed that all schemes were feasible while producing. It made the whole solutions feasible while the cutting patterns were generated, so that it avoided carrying on feasible verification to encode in the course of searching optimal solution; The paper presented the application of modern intelligent optimizing algorithm: Genetic Algorithm (GA), Simulated Annealing (SA), and hybrid algorithm according to each advantages of Genetic Algorithm and Simulated Annealing (GASA) in the fibre furniture cutting phase, and in the course of applying, the paper improveed the algorithm; To the question of the difficulty in determining the proper cooling schedule and choosing a proper neighborhood in simulated annealing algorithm, and also the difficulty of escaping from the local optimal solution, the paper designed a temperature controlled cooling schedule, local optimum judging function and temperature raising function was given, it raised temperature in time after the search entered the local optimal solution, and it could make searching escape from the local optimal solution, ensured the final solution to be the optimal. It designed initial temperature, neighborhood structure and random acceptive function, the paper improved the speed of solving process; To the question of characteristic of Genetic Algorithm applied in the rectangular cutting stock problem, the paper presented a kind of Objective Oriented genetic coding method. It proposed the genetic mutation scheme on the basis of " Run-Through Material", unused gene quantity had been brought down to zero after making a variation, and it put forward corresponding definite method and key points, fitness function, initial formulation and genetic operation; The paper carried on detailed comparing and analysis to the two algorithms mentioned above, summarized the advantages and deficiencies in terms of the theory and the implementation of the two algorithms, fetched the advantages of Simulated Annealing algorithm and Genetic Algorithm, combined them together well, included the temperature controled of
Simulated Annealing algorithm and the coding method and the way of variation of Genetic Algorithm, that made the ability of searching for the optimum of the new hybrid algorithm: Genetic-Simulated Annealing algorithm to be improved greatly; The paper compared and analyzed the three kinds of algorithms in terms of theory and practice, Genetic-Simulated Annealing algorithm had not only such operation of individual, mating, gene, heredity, making a variation etc. in Genetic Algorithms, but also had Simulation Anneal algorithm's temperature controling, cooling schedule and technology of accepting probability etc. too, it could get the large scale rectangular cutting's best solution faster.The paper developed the fibre furniture manufacture's large scale rectangular cutting stock system, the experiment showed that the optimization result of the sysytem is higher than the domestic similar research results, and it was extremely simple and convenient to operate, it was remarkable to economize the raw materials, and it was practicability. To solve the same group data, the third method (Genetic-Simulated Annealing) is more efficiency.
针对在板式家具中板材下料问题的具体特点,结合板式家具下料的工艺和约束条件,给出了在矩形原料板材上的矩形零件优化下料的定义、特点、性质并提出了在工艺条件以及规模约束下的大规模板式家具优化下料的数学模型。在对下料优化方案生成算法的研究中,提出了一种“生成即可行”的排样方法。根据板式家具下料“一刀切(Guillotine Cutting)”的工艺特性,设计了一种二叉树结构来表现排样方案的生成过程,保证了所有的方案在产生时即可行,使整个方案生成过程中的所有解都是可行解,因此避免了在寻优过程中再对编码进行可行性验证的操作。
提出了将现代智能优化算法:遗传算法(GA)、模拟退火算法(SA)和根据这两种算法的各自优势将其融合后的遗传退火算法(GASA)在大规模板式家具下料中的应用。并在应用过程中,对算法进行了改进。针对模拟退火算法冷却进度表和邻域范围难以确定,进入局部最优后难以跳出的问题,设计了温度可控的冷却进度表,提出了搜索进入局部最优的判定函数和升温函数,使搜索进入局部最优后能及时升温,并从局部最优中跳出,保证了解的最优性。设计了初始温度、邻域结构和随机接受函数,提高了求解速度;针对遗传算法在矩形件优化下料问题中应用的实际特点,提出一种全新的面向对象的遗传编码方式和基于“贯通原料”的基因变异方式,将变异后不可用基因数量降到了零,就适应度函数、初始群体的生成和遗传操作等关键问题提出了相应的设计方法;对两种算法进行了详细的对比分析和论证,从理论和实践的角度总结了两种算法各自优缺点,取模拟退火算法和遗传算法的各自长处,将它们有机地结合在一起,分别采用了本文提出的模拟退火算法中升温的控制和遗传算法中的编码和变异的方式,生成温控遗传-退火算法,混合算法搜索全局最优的能力大大提高;对三种算法从理论和实践的角度进行了对比分析,遗传-退火算法兼有遗传算法中种群、个体、交配、基因、遗传、变异等淘汰劣质解的操作,也有模拟退火算法中冷却进度表和接受概率等寻优控制技术,可以更好地实现大规模矩形件下料问题的快速求解。
研制了板式家具大规模矩形件优化下料系统,实验表明,该软件的优化效果高于国内同类研究成果,而且操作极其简便,节约原材料效果显著,实用性强。对同一组数据的求解,第三种遗传退火算法优化效率更高。
Cutting stock is concerned with how to saving material, optimize resources in product designing, manufacturing. The research on the problem has important economic meaning and social benefit. It is very complicated and difficult in computing theory, but it has got the extensive application in the actual manufacture. With the development of intelligent optimize algorithm theory and computer technology, it offers the possibility to people to solve the problem with modern optimal algorithm and computer. In this paper, the cutting stock problem was consistsed of packing rectangular items onto a rectangular raw material in the fibre furniture manufacture.Considered of the concrete characteristics of the cutting stock problem in the fibre furniture, it combined the craft and restraint condition in the fibre furniture, it gave the definition, characteristics and nature of cutting stock in rectangle parts on the rectangle raw material board, and had put forward the restrained of craft and items' scale modes of the fibre furniture, the mathematics model was given; On the research of cutting stock algorithm, the paper presented a method of "Be Feasible on Producing". According to the craft characteristic of "Guillotine cutting" in the fibre furniture manufacture, the paper adopted the binary tree structure to perform the process with layout pattern, ensureed that all schemes were feasible while producing. It made the whole solutions feasible while the cutting patterns were generated, so that it avoided carrying on feasible verification to encode in the course of searching optimal solution; The paper presented the application of modern intelligent optimizing algorithm: Genetic Algorithm (GA), Simulated Annealing (SA), and hybrid algorithm according to each advantages of Genetic Algorithm and Simulated Annealing (GASA) in the fibre furniture cutting phase, and in the course of applying, the paper improveed the algorithm; To the question of the difficulty in determining the proper cooling schedule and choosing a proper neighborhood in simulated annealing algorithm, and also the difficulty of escaping from the local optimal solution, the paper designed a temperature controlled cooling schedule, local optimum judging function and temperature raising function was given, it raised temperature in time after the search entered the local optimal solution, and it could make searching escape from the local optimal solution, ensured the final solution to be the optimal. It designed initial temperature, neighborhood structure and random acceptive function, the paper improved the speed of solving process; To the question of characteristic of Genetic Algorithm applied in the rectangular cutting stock problem, the paper presented a kind of Objective Oriented genetic coding method. It proposed the genetic mutation scheme on the basis of " Run-Through Material", unused gene quantity had been brought down to zero after making a variation, and it put forward corresponding definite method and key points, fitness function, initial formulation and genetic operation; The paper carried on detailed comparing and analysis to the two algorithms mentioned above, summarized the advantages and deficiencies in terms of the theory and the implementation of the two algorithms, fetched the advantages of Simulated Annealing algorithm and Genetic Algorithm, combined them together well, included the temperature controled of
Simulated Annealing algorithm and the coding method and the way of variation of Genetic Algorithm, that made the ability of searching for the optimum of the new hybrid algorithm: Genetic-Simulated Annealing algorithm to be improved greatly; The paper compared and analyzed the three kinds of algorithms in terms of theory and practice, Genetic-Simulated Annealing algorithm had not only such operation of individual, mating, gene, heredity, making a variation etc. in Genetic Algorithms, but also had Simulation Anneal algorithm's temperature controling, cooling schedule and technology of accepting probability etc. too, it could get the large scale rectangular cutting's best solution faster.The paper developed the fibre furniture manufacture's large scale rectangular cutting stock system, the experiment showed that the optimization result of the sysytem is higher than the domestic similar research results, and it was extremely simple and convenient to operate, it was remarkable to economize the raw materials, and it was practicability. To solve the same group data, the third method (Genetic-Simulated Annealing) is more efficiency.
引文
[1] Cao Ju, Zhou ji. Design and realization of computer aided optimal layout for irregular shapes. The Fourth International Conference on CAD/CG, Wuhan, China, 1995, 10
[2] 李英华.二维几何形状优化排样系统2DunivNest.机械工程师,1999,(10):37-40
[3] 卢开澄.组合数学算法与分析.清华大学出版社,北京:1998
[4] Gilmore P.C. Gomory R.E., The theory and computation of Knapsack functions. Opns. Res., 1966, (14)1045-1047
[5] Gilmore P.C., Gomory R.E. A linear programming approach to the cutting stock problem-Part 11. Opns. Res., 1963, (11): 863-887
[6] Gilmore P.C., Gomory R.E. Multistage cutting stock problem of two and more dimensions. Opns Res., 1965, (13): 94-120
[7] Gilmore P.C., Gomory R.E. A linear programming approach to the cutting stock. Opns. Res.1961, (9): 849-859
[8] Wang P.Y. Two algorithms for constrained two-dimensional cutting stock problems. Operations Research, 1983,31: 573-586
[9] Beasley J.E. Bounds for Two-dimensional cutting. Journal of the operational Research Society, 1985, 36:71-74
[10] Beasley J. E. An exact two-dimensional non-guillotine cutting tree search produce. Opns. Soc., 1985,33:49-64
[11] Beasley J. E. Algorithms for unstrained two-dimensional guillotine cutting. Journal of Operational Research, 1985,36(4): 298-306
[12] Dagli C.H. A computer package for solving cutting stock problem. 7th International Conference Production Research, Windsor,Ontario,Canaca, 1983,11: 480-486
[13] Sriram M.and Kang S.M. A modified Hopfield network for two-dimensional module placement. Proceedings of IEEE International Symposium on circuits system,1990, 38(6): 1664-1667
[14] Dagli C.H. Knowledge-based system for cutting problems. European Journal of Operational Research, 1990,44:160-166
[15] Sweeney P.E. Cutting and Packing problems: a Categorized, application-Orientated research Bibliography. Journal of the operational Research Society, 1992, 43(7): 691-706
[16] Christofides N. and Whitlock, C. An algorithm for two-dimensional cutting problem. Operations Research, 1977,25:30-40
[17] Chauny F. A two-dimensional heuristic for two-dimensional cutting-stock problem. Journal of the operational Research Society, 1991,42:39-47
[18] Francois Vanderbeck. A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem. Management Science, 2001,47(6): 864-879
[19] Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems. Math Programming, 1999,86(9): 565-594
[20] Riehme J. The solution of two-stage guillotine stock problems having extremely varying demands. Eur. J. Oper. Res., 1996,91: 543-552
[21] Mhand Hifi. Exact algorithms for the guillotine strip cutting/packing problem. Computers Ops. Res., 1998,25(11): 925-940
[22] K.V.Viswanathan. A.Bagchi. An exact best-first search procedure for the constrained rectangular guillotine knap sack problem, Proceedings of the American Association for Articicial Intelligence, 1988: 145-149
[23] Liu Hong, Zeng Guangzhou and Lin Zongkai. A system of optimizing nesting with Analogical Learning Mechanism. Computers Ind. Engng. 1997,32(4): 713-725
[24] H.H.Yanasse, A.S.I.Zinober. Two-dimensional Cutting Stock with Multiple Stock Sizes, J.Opl,Res.Soc.,1991,42(8): 673-683
[25] T.W.Leung, C.HYung, Marvin D.Troutt. Application of Genetic Search and Simulated Annealing to the Two-dimensional Non-Guillotine Cutting Stock Problem, Computer & Industrial Engineering, 2001,40:201-214
[26] F.J.Vasko. A computational improvement to Wang's two-dimensional cutting stock algorithm, Computers and Industrial Engineering, 1989,16:109-115
[27] A.Y.C.Nee, K.W.Seow. Designing Algorithm for nesting Irregular Shapes with and without Boundary Constrains, Annals of the CIRP,1986,35(1): 39-43
[28] Dorit,S.H. and WolfgangMaass. Approximat ipmScje, esfprCpveromg and Packing Problem in Image Processing and V1SI, Journal of CM, 1985,32(1): 130-136
[29] Baker B.S., Coffinan, E.Gand Rivest,R.L. Orthogonal packing in two-dimensions. SIAM Journal of Computing. 1980,9: 846-855
[30] A.Albanoand, T.Orsini. A Tree Search Approach to the Partition and Knapsack Problem, The Computer Journal, 1980,23:256-261
[31] Dequan Liu, Hongfei Teng. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangle. European Journal of Operational Research, 1999,112: 413- 420
[32] Arenales M. To-staged and constrained two-dimensional guillotine cutting problem. Belgium the 16~(th) European conference on operational research, 1998,88-96
[33] A.Albano, Torsini. A heuristic solution of the rectanglar cutting stock problem. The Computer Journal, 1980,23(4): 338-343
[34] A.Albano, GSapuppo. Optimal Allocation of Two-dimensional Irregular Shapes Using Heuristic Search Methods. IEEE Trans. Syst., Man, and Cybernetics, 1980, SMC-10(5): 242- 248
[35] I.Coverdale, F.Wharton. An improved heuristic procedure for an on linear cutting stock problem. Mgmt.Sci. 1976,23:78-86
[36] F.Chauny, R.Loulou. A Two-phase Heuristic for the Two-dimensional Cutting-stock problem. J.OplRes.Soc, 1991,42(1): 39-47
[37] S.U.Foronda, H.F.Carino. A heuristic approach to the lumber allocation problem in hardwood dimension and furniture manufacturing, European Journal of Operational Research 54,1991, 151-162
[38] Cheok,B.T., Nee,Y.C. Algorithms for nesting of ship/off shore structural plates. Advances in Design Automation, 1991,32(2): 221-226
[39] Daza V.P., et al. Exact solutions for constrained two-dimensional cutting stock problems. European Journal of Operational Research,1995,84:633-644
[40] Morabito R.N.et al. An and-or graph approach to cutting stock problem. European Journal of Operational Research,1992,58:263-271
[41] Viswanathan K.V. et al. Best-first search methods for constrained two-dimensional cutting stock problems. Operations Research, 1993, 41 (4): 768-776.
[42] Arenales M.et al. An and-or graph approach to the solution of two-dimensional nonguillotine curing problems. European Journal of Operational Research, 1995,84:599-617
[43] Dyckhoff H., et al. Cutting and packing in production and distribution. Springer-Verlag, Berlin, 1992
[44] Dowsland K.A. et al. Packing problems. European Journal of Operational Research, 1992,56:177-190
[45] Han G.C. etal. Two-stage approach for nesting in two-dimensional cutting Problems using network and simulated annealing. Proceedings of the Institution of Mechanical Engineering, Part B, Journal of Engineering manufacture, 1996,210(B6): 509-519
[46] Han G.C. etal. A multi-stage solution for nesting in two-dimensional cutting problems using networks. Welding in the World, 1994,34(9): 409-410
[47] Dagli C.H. A simulated annealing approach for solving stock problem. Proceedings of IEEE International Conference on Systems, Man and Cybernetics, 1990,221-223
[48] Dagli C.H and Poshyannda P. New approaches to nesting rectangular patterns. Journal of intelligent manufacturing. 1997,(8): 177-190
[49] Theodoracators V.E., et al. The 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
[50] Andreas Bortfelt and Hermann Gehring, A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research, 2001,131: 143-161
[51] T.W Leung, Chi Kin Chan. Application of Mixed Simulated Annealing-Genetic Algorithm Heuristic for the Two-dimensional orthogonal packing problem, European Journal of Operational Research, 2003,145:530-542
[52] Victor Parada. Solution for the constrained Guillotine Cutting Problem by Simulated Annealing, Computers Ops Res, 1997,25(1): 37-47
[53] Saad M.A.Suliman. Pattern Generating Procedure for the Cutting Stock Problem. International Journal of Production Economics, 2001,(74): 293-301
[54] VanLaarhoven, P.J.M., Aarts, E.H.L. Simulated Annealing: Theory and Applications. D.Reidel Published, 1987
[55] Ellkis H. and Sartaj S. Fundamentals of Computer Algorithms. Computer Science Press, Inc, 1978
[56] Saad M.A.Suliman. Pattern Generating Procedure for the Cutting Stock Problem. International Journal of Production Economics, 2001, (74): 293-301
[57] Hongmei.Yu. A combined Genetic Algorithm/Simulated Annealing algorithm for Large Scale System Energy Integration, Computers & Chemical Engineering, 2000(24): 2023-2035
[58] B.G. Madsen. An Application of Traveling-Salesman Routines to Solve Pattern-Allocation Problems in the glass Industry. Journal of the operational Research Society, 1998, 39(3): 249-256
[59] 夏萼辉,卡铭甲,李绍成.单双排冲裁件的最佳排样法.计算机辅助设计.锻压机械,1984,(2):37-42
[60] 黄兆亭,苗永纯,张国良.微机辅助设计冲裁件最佳排样法.锻压机械,1985,(2):12-16
[61] 杨洪旗,储家佑.冲裁件的排样优化与动态排样寻优法.锻压机械,1987,(6):7-10
[62] 龚邦明,周汝忠.计算机优化排样.机械工业自动化,1989,(2):11-14
[63] 王少纯,王仲仁等.交互式微机辅助冲件排样法.锻压技术,1990,(5):23-26
[64] 曹炬,周济.冲裁件排样最优化的数学模型及算法.锻压技术,1993,18(6):21-24
[65] 张海渠,张树杰.冲压排料与板料裁切的最优化计算.机械设计与制造,1997,(5):18-20
[66] 董长双,杨楚民等.冲裁件二维排样优化.锻压技术,1998,(4):17-20
[67] 袁忠良.板材最优化套裁下料方法.锻压机械,1994,(6):31-34
[68] 袁忠良.最优化下料方法与程序.天津大学出版社,天津:1989
[69] 曹炬,周济.等矩形件排样优化的背包算法.中国机械工程,1994,5(2):11-12
[70] 曹炬,周济.矩形件排样优化的一种近似算法.计算机辅助设计与图形学学报,1995,7(3):190-195
[71] 曹炬.实用矩形件优化排样系统的研究与开发.锻压技术,1999,(5):19-23
[72] 曹炬,胡修彪.大规模矩形件优化排样的遗传算法.锻压机械,1999,(4):17-20
[73] 文贵华,丁月华.基于动态分割与合上的排样算法.1999,21(4):46-49
[74] 黄崇斌,胡吉全.板材优化下料矩形综合法.起重运输机械,1996,(6):28-30
[75] 黄有群,刘嘉敏.等剪床排样的计算机辅助设计.小型微型计算机系统,1998,16(7):43-47
[76] 张鸿宾.组合优化问题的启发式搜索.计算机科学,1998,(9):211-228
[77] 刘弘,曾广周等.具有类比学习机制的优化排样系统.计算机辅助设计与图形学学报,1997,9(5):436-441
[78] 文贵华等.一种改进的启发式布局方法.计算机工程与设计,2000,21(4):46-49
[79] 黄崇斌.二维板材优化下料快速搜索法.计算机辅助工程,2000,(1):43-47
[80] 刘德全,滕鸿飞.矩形件件排样问题的遗传算法求解.小型微型计算机系统,1988,(12):20-25
[81] 贾志欣,殷国富.矩形件排样的模拟退火算法求解.四川大学学报,2001,33(5):35-38
[82] 贾志欣等.基于碰撞算法的排样系统的研究与应用.模具工业,2002,(3):9-11
[83] 罗阳.机械制造车间生产作业多智能体规划原理与板材套料优化方法的研究.四川大学博士学位论文,2001,10-100
[84] 蔡正军,龚坚,刘飞.板材优化下料的数学模型研究.重庆大学学报(自然科学版),1996,190(2):82-88
[85] 龚坚,刘飞等.定长条材优化下料的实用算法研究.重庆大学学报(自然科学版),1997,20(1):92-96
[86] 曹军,岳琪,张怡卓.遗传神经网络在家具板材优化下料问题中的应用.森林工程,2003,19(1):36-38
[87] Hutmut Stadler. A one-dimensional cutting stock problem in the aluminium industry and its solution. European Journal of Operational Research, 1990,44:209-223
[88] Vasko.F.J. et al. A hierarchical approach for one-dimensional cutting stock problems in the steel industry that maximizes yield and minimizes overgrading. European Journal of Operational Research, 1999,114:72-82
[89] Heungsoon Felix Lee and E.C.Sewell. Thestrip-packing problem for a boat manufacturing firm. IIE Transactions, 1999,31:639-651
[90] 曹炬.实用冲裁件优化排样系统的研究与开发.锻压机械,1999,(1):44-47
[91] 张文江.家具制造厂板材综合下料问题的研究.林产工业,1999,26(4):14-17
[92] 吴承祯,洪伟.模拟退火法优化约束条件下造林规划设计的研究.自然资源学报,2001,5(10):75-80
[93] 金军.基于遗传算法的玻璃排版优化系统的设计与实现.四川大学硕士学位论文,2001,3-90
[94] Jun Cao, Yizhuo Zhang, Qi Yue. Solving the optimization allocating problem by the combination of genetic algorithms and artificial neural networks. Journal of Forestry Research, 2003, 14(1): 87-89
[95] 岳琪,孙丽萍,苏建民.家具优化下料模型研究.林业科技,2003,28(1):33-35
[96] 岳琪,宋文龙,孙杰.板式家具板材优化排料系统的研制与开发.林业机械与木工设备,2003,31(9):15-17
[97] Marco P.Tucci, Anote on global optimization in adaptive control, econometrics and macroeconomics, Journal of Economic Dynamics & control, 2002,26:1739-1764
[98] Eugene J.Zak, Modeling multistage cutting stock problems. European Journal of Operational Research, 2002,141: 313-327
[99] David J. et al. Programming Visual C++6.0技术内幕,希望电子出版社,北京:1999
[100] Harvey M. Deitel. C++大学教程.电子工业出版社,北京:2003
[101] 王凌.智能优化算法及其应用.清华大学出版社,北京:2001
[102] 康立山,谢云等.非数值并行算法.科学出版社,北京:2003
[103] 刑文训.现代优化计算方法.清华大学出版社,北京:2000
[2] 李英华.二维几何形状优化排样系统2DunivNest.机械工程师,1999,(10):37-40
[3] 卢开澄.组合数学算法与分析.清华大学出版社,北京:1998
[4] Gilmore P.C. Gomory R.E., The theory and computation of Knapsack functions. Opns. Res., 1966, (14)1045-1047
[5] Gilmore P.C., Gomory R.E. A linear programming approach to the cutting stock problem-Part 11. Opns. Res., 1963, (11): 863-887
[6] Gilmore P.C., Gomory R.E. Multistage cutting stock problem of two and more dimensions. Opns Res., 1965, (13): 94-120
[7] Gilmore P.C., Gomory R.E. A linear programming approach to the cutting stock. Opns. Res.1961, (9): 849-859
[8] Wang P.Y. Two algorithms for constrained two-dimensional cutting stock problems. Operations Research, 1983,31: 573-586
[9] Beasley J.E. Bounds for Two-dimensional cutting. Journal of the operational Research Society, 1985, 36:71-74
[10] Beasley J. E. An exact two-dimensional non-guillotine cutting tree search produce. Opns. Soc., 1985,33:49-64
[11] Beasley J. E. Algorithms for unstrained two-dimensional guillotine cutting. Journal of Operational Research, 1985,36(4): 298-306
[12] Dagli C.H. A computer package for solving cutting stock problem. 7th International Conference Production Research, Windsor,Ontario,Canaca, 1983,11: 480-486
[13] Sriram M.and Kang S.M. A modified Hopfield network for two-dimensional module placement. Proceedings of IEEE International Symposium on circuits system,1990, 38(6): 1664-1667
[14] Dagli C.H. Knowledge-based system for cutting problems. European Journal of Operational Research, 1990,44:160-166
[15] Sweeney P.E. Cutting and Packing problems: a Categorized, application-Orientated research Bibliography. Journal of the operational Research Society, 1992, 43(7): 691-706
[16] Christofides N. and Whitlock, C. An algorithm for two-dimensional cutting problem. Operations Research, 1977,25:30-40
[17] Chauny F. A two-dimensional heuristic for two-dimensional cutting-stock problem. Journal of the operational Research Society, 1991,42:39-47
[18] Francois Vanderbeck. A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem. Management Science, 2001,47(6): 864-879
[19] Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems. Math Programming, 1999,86(9): 565-594
[20] Riehme J. The solution of two-stage guillotine stock problems having extremely varying demands. Eur. J. Oper. Res., 1996,91: 543-552
[21] Mhand Hifi. Exact algorithms for the guillotine strip cutting/packing problem. Computers Ops. Res., 1998,25(11): 925-940
[22] K.V.Viswanathan. A.Bagchi. An exact best-first search procedure for the constrained rectangular guillotine knap sack problem, Proceedings of the American Association for Articicial Intelligence, 1988: 145-149
[23] Liu Hong, Zeng Guangzhou and Lin Zongkai. A system of optimizing nesting with Analogical Learning Mechanism. Computers Ind. Engng. 1997,32(4): 713-725
[24] H.H.Yanasse, A.S.I.Zinober. Two-dimensional Cutting Stock with Multiple Stock Sizes, J.Opl,Res.Soc.,1991,42(8): 673-683
[25] T.W.Leung, C.HYung, Marvin D.Troutt. Application of Genetic Search and Simulated Annealing to the Two-dimensional Non-Guillotine Cutting Stock Problem, Computer & Industrial Engineering, 2001,40:201-214
[26] F.J.Vasko. A computational improvement to Wang's two-dimensional cutting stock algorithm, Computers and Industrial Engineering, 1989,16:109-115
[27] A.Y.C.Nee, K.W.Seow. Designing Algorithm for nesting Irregular Shapes with and without Boundary Constrains, Annals of the CIRP,1986,35(1): 39-43
[28] Dorit,S.H. and WolfgangMaass. Approximat ipmScje, esfprCpveromg and Packing Problem in Image Processing and V1SI, Journal of CM, 1985,32(1): 130-136
[29] Baker B.S., Coffinan, E.Gand Rivest,R.L. Orthogonal packing in two-dimensions. SIAM Journal of Computing. 1980,9: 846-855
[30] A.Albanoand, T.Orsini. A Tree Search Approach to the Partition and Knapsack Problem, The Computer Journal, 1980,23:256-261
[31] Dequan Liu, Hongfei Teng. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangle. European Journal of Operational Research, 1999,112: 413- 420
[32] Arenales M. To-staged and constrained two-dimensional guillotine cutting problem. Belgium the 16~(th) European conference on operational research, 1998,88-96
[33] A.Albano, Torsini. A heuristic solution of the rectanglar cutting stock problem. The Computer Journal, 1980,23(4): 338-343
[34] A.Albano, GSapuppo. Optimal Allocation of Two-dimensional Irregular Shapes Using Heuristic Search Methods. IEEE Trans. Syst., Man, and Cybernetics, 1980, SMC-10(5): 242- 248
[35] I.Coverdale, F.Wharton. An improved heuristic procedure for an on linear cutting stock problem. Mgmt.Sci. 1976,23:78-86
[36] F.Chauny, R.Loulou. A Two-phase Heuristic for the Two-dimensional Cutting-stock problem. J.OplRes.Soc, 1991,42(1): 39-47
[37] S.U.Foronda, H.F.Carino. A heuristic approach to the lumber allocation problem in hardwood dimension and furniture manufacturing, European Journal of Operational Research 54,1991, 151-162
[38] Cheok,B.T., Nee,Y.C. Algorithms for nesting of ship/off shore structural plates. Advances in Design Automation, 1991,32(2): 221-226
[39] Daza V.P., et al. Exact solutions for constrained two-dimensional cutting stock problems. European Journal of Operational Research,1995,84:633-644
[40] Morabito R.N.et al. An and-or graph approach to cutting stock problem. European Journal of Operational Research,1992,58:263-271
[41] Viswanathan K.V. et al. Best-first search methods for constrained two-dimensional cutting stock problems. Operations Research, 1993, 41 (4): 768-776.
[42] Arenales M.et al. An and-or graph approach to the solution of two-dimensional nonguillotine curing problems. European Journal of Operational Research, 1995,84:599-617
[43] Dyckhoff H., et al. Cutting and packing in production and distribution. Springer-Verlag, Berlin, 1992
[44] Dowsland K.A. et al. Packing problems. European Journal of Operational Research, 1992,56:177-190
[45] Han G.C. etal. Two-stage approach for nesting in two-dimensional cutting Problems using network and simulated annealing. Proceedings of the Institution of Mechanical Engineering, Part B, Journal of Engineering manufacture, 1996,210(B6): 509-519
[46] Han G.C. etal. A multi-stage solution for nesting in two-dimensional cutting problems using networks. Welding in the World, 1994,34(9): 409-410
[47] Dagli C.H. A simulated annealing approach for solving stock problem. Proceedings of IEEE International Conference on Systems, Man and Cybernetics, 1990,221-223
[48] Dagli C.H and Poshyannda P. New approaches to nesting rectangular patterns. Journal of intelligent manufacturing. 1997,(8): 177-190
[49] Theodoracators V.E., et al. The 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
[50] Andreas Bortfelt and Hermann Gehring, A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research, 2001,131: 143-161
[51] T.W Leung, Chi Kin Chan. Application of Mixed Simulated Annealing-Genetic Algorithm Heuristic for the Two-dimensional orthogonal packing problem, European Journal of Operational Research, 2003,145:530-542
[52] Victor Parada. Solution for the constrained Guillotine Cutting Problem by Simulated Annealing, Computers Ops Res, 1997,25(1): 37-47
[53] Saad M.A.Suliman. Pattern Generating Procedure for the Cutting Stock Problem. International Journal of Production Economics, 2001,(74): 293-301
[54] VanLaarhoven, P.J.M., Aarts, E.H.L. Simulated Annealing: Theory and Applications. D.Reidel Published, 1987
[55] Ellkis H. and Sartaj S. Fundamentals of Computer Algorithms. Computer Science Press, Inc, 1978
[56] Saad M.A.Suliman. Pattern Generating Procedure for the Cutting Stock Problem. International Journal of Production Economics, 2001, (74): 293-301
[57] Hongmei.Yu. A combined Genetic Algorithm/Simulated Annealing algorithm for Large Scale System Energy Integration, Computers & Chemical Engineering, 2000(24): 2023-2035
[58] B.G. Madsen. An Application of Traveling-Salesman Routines to Solve Pattern-Allocation Problems in the glass Industry. Journal of the operational Research Society, 1998, 39(3): 249-256
[59] 夏萼辉,卡铭甲,李绍成.单双排冲裁件的最佳排样法.计算机辅助设计.锻压机械,1984,(2):37-42
[60] 黄兆亭,苗永纯,张国良.微机辅助设计冲裁件最佳排样法.锻压机械,1985,(2):12-16
[61] 杨洪旗,储家佑.冲裁件的排样优化与动态排样寻优法.锻压机械,1987,(6):7-10
[62] 龚邦明,周汝忠.计算机优化排样.机械工业自动化,1989,(2):11-14
[63] 王少纯,王仲仁等.交互式微机辅助冲件排样法.锻压技术,1990,(5):23-26
[64] 曹炬,周济.冲裁件排样最优化的数学模型及算法.锻压技术,1993,18(6):21-24
[65] 张海渠,张树杰.冲压排料与板料裁切的最优化计算.机械设计与制造,1997,(5):18-20
[66] 董长双,杨楚民等.冲裁件二维排样优化.锻压技术,1998,(4):17-20
[67] 袁忠良.板材最优化套裁下料方法.锻压机械,1994,(6):31-34
[68] 袁忠良.最优化下料方法与程序.天津大学出版社,天津:1989
[69] 曹炬,周济.等矩形件排样优化的背包算法.中国机械工程,1994,5(2):11-12
[70] 曹炬,周济.矩形件排样优化的一种近似算法.计算机辅助设计与图形学学报,1995,7(3):190-195
[71] 曹炬.实用矩形件优化排样系统的研究与开发.锻压技术,1999,(5):19-23
[72] 曹炬,胡修彪.大规模矩形件优化排样的遗传算法.锻压机械,1999,(4):17-20
[73] 文贵华,丁月华.基于动态分割与合上的排样算法.1999,21(4):46-49
[74] 黄崇斌,胡吉全.板材优化下料矩形综合法.起重运输机械,1996,(6):28-30
[75] 黄有群,刘嘉敏.等剪床排样的计算机辅助设计.小型微型计算机系统,1998,16(7):43-47
[76] 张鸿宾.组合优化问题的启发式搜索.计算机科学,1998,(9):211-228
[77] 刘弘,曾广周等.具有类比学习机制的优化排样系统.计算机辅助设计与图形学学报,1997,9(5):436-441
[78] 文贵华等.一种改进的启发式布局方法.计算机工程与设计,2000,21(4):46-49
[79] 黄崇斌.二维板材优化下料快速搜索法.计算机辅助工程,2000,(1):43-47
[80] 刘德全,滕鸿飞.矩形件件排样问题的遗传算法求解.小型微型计算机系统,1988,(12):20-25
[81] 贾志欣,殷国富.矩形件排样的模拟退火算法求解.四川大学学报,2001,33(5):35-38
[82] 贾志欣等.基于碰撞算法的排样系统的研究与应用.模具工业,2002,(3):9-11
[83] 罗阳.机械制造车间生产作业多智能体规划原理与板材套料优化方法的研究.四川大学博士学位论文,2001,10-100
[84] 蔡正军,龚坚,刘飞.板材优化下料的数学模型研究.重庆大学学报(自然科学版),1996,190(2):82-88
[85] 龚坚,刘飞等.定长条材优化下料的实用算法研究.重庆大学学报(自然科学版),1997,20(1):92-96
[86] 曹军,岳琪,张怡卓.遗传神经网络在家具板材优化下料问题中的应用.森林工程,2003,19(1):36-38
[87] Hutmut Stadler. A one-dimensional cutting stock problem in the aluminium industry and its solution. European Journal of Operational Research, 1990,44:209-223
[88] Vasko.F.J. et al. A hierarchical approach for one-dimensional cutting stock problems in the steel industry that maximizes yield and minimizes overgrading. European Journal of Operational Research, 1999,114:72-82
[89] Heungsoon Felix Lee and E.C.Sewell. Thestrip-packing problem for a boat manufacturing firm. IIE Transactions, 1999,31:639-651
[90] 曹炬.实用冲裁件优化排样系统的研究与开发.锻压机械,1999,(1):44-47
[91] 张文江.家具制造厂板材综合下料问题的研究.林产工业,1999,26(4):14-17
[92] 吴承祯,洪伟.模拟退火法优化约束条件下造林规划设计的研究.自然资源学报,2001,5(10):75-80
[93] 金军.基于遗传算法的玻璃排版优化系统的设计与实现.四川大学硕士学位论文,2001,3-90
[94] Jun Cao, Yizhuo Zhang, Qi Yue. Solving the optimization allocating problem by the combination of genetic algorithms and artificial neural networks. Journal of Forestry Research, 2003, 14(1): 87-89
[95] 岳琪,孙丽萍,苏建民.家具优化下料模型研究.林业科技,2003,28(1):33-35
[96] 岳琪,宋文龙,孙杰.板式家具板材优化排料系统的研制与开发.林业机械与木工设备,2003,31(9):15-17
[97] Marco P.Tucci, Anote on global optimization in adaptive control, econometrics and macroeconomics, Journal of Economic Dynamics & control, 2002,26:1739-1764
[98] Eugene J.Zak, Modeling multistage cutting stock problems. European Journal of Operational Research, 2002,141: 313-327
[99] David J. et al. Programming Visual C++6.0技术内幕,希望电子出版社,北京:1999
[100] Harvey M. Deitel. C++大学教程.电子工业出版社,北京:2003
[101] 王凌.智能优化算法及其应用.清华大学出版社,北京:2001
[102] 康立山,谢云等.非数值并行算法.科学出版社,北京:2003
[103] 刑文训.现代优化计算方法.清华大学出版社,北京:2000