基于Memetic算法的套料与切割优化方法研究
|
摘要
当前，绿色制造和节能减排已经成为制造业的重点发展方向之一。二维排样技术作为一种减少能耗和提高材料利用率的关键技术，一直是学术界和工业界的重要研究领域，并且在机械制造、船舶装备、服装剪裁等过程中得到广泛应用。其中，套料与切割方法是提高复杂零件或部件加工效率和板材利用率的关键。本文研究了矩形件套料、异形件套料和切割路径规划等优化方法，主要研究工作体现在：
研究套料与切割问题的理论基础与求解框架。描述套料与切割问题概念，分析这两类问题性质，给出数学模型，并设计基于Memetic算法的求解思路和框架。
研究矩形件套料算法。针对矩形件有直角排放规律的特点，提出一种最左下占角动作(BLCO)放置策略；基于改进个体之间的交叉运算，构造一种改进的优先运算交叉算子IPOX。利用Memetic算法中全局随机搜索和局部集中搜索混合的思想，提出一种基于遗传算法和模拟退火算法的HGASA混合算法。
研究异形件套料算法。针对异形件形状的多样性和旋转角度的任意性，研究基于临界多边形(NFP)的几何计算方法和基于旋转矩阵的零件旋转角度变化，并提出基于左下角方法的异形件定位策略。在强化禁忌搜索的集中搜索机制基础上，提出基于遗传算法和禁忌搜索算法的HGATS混合算法。
研究切割路径优化方法。在切割起点选取的优化过程中，通过轮廓特征点分析，提取离原点最近的特征点作为初始切割起点，采用爬山算法寻找周边邻域的较优解；在切割顺序排序的优化过程中，将其转化为TSP问题，并引入蚁群算法求解。在此基础上提出混合蚁群算法和爬山算法的HACHC算法求解这两个问题。
基于提出的HGASA、HGATS、HACHC三种混合智能算法，开发拥有自主知识产权的SmartNest系统。结合典型的工业实例，提出解决方案总体架构图、软件系统架构图和主要功能模块，规范套料和切割的流程图，并在系统中实现了三种新混合算法的功能。通过与三款国际知名排样软件的比较，本文的研究成果在钢板消耗长度、材料利用率等方面均取得满意结果。
Nowadays，green manufacturing and energy-saving technology has become one of thekey issues of the manufacturing industry. As a key technology to reduce energyconsumption and improve materials utilization, two-dimensional cutting and packingtechnology has been becoming the important research focus in academia and industry, andwidely used in the processing of machinery manufacturing, ship equipment and tailoring.Research on the method of two dimensional cutting and packing is the key to improve theprocessing efficiency of complex parts and the utilization of plate. In this thesis, theoptimization methods, namely rectangular packing, irregular packing and cutting pathplanning are studied from a systematic viewpoint. The main researches are organized asfollows.
The theoretical basis and solving framework of cutting and packing problem are studied,followed by the description of the concept of cutting and packing problem, Themathematical models of the two problems are established, and the optimization methodand the framework of general solution based on Memetic algorithm is discussed.
Algorithms in rectangular packing problem are studied. For the characteristics at rightangles to the emission of the rectangular pieces, a placement policy of bottom left corneroccupying (BLCO) is developed. An improved priority operation crossover operator IPOXis constructed based on improved crossover operation between individuals. By using themixed ideas of global random search and local focus search from Memetic algorithm, thehybrid algorithm HGASA based on genetic algorithm and simulated annealing algorithmis proposed.
Algorithms in irregular packing problem are studied. For the diversity of the shape andthe arbitrary nature of the rotation angle of the shaped pieces, the geometric calculationmethods based on the no fit polygon (NFP) are studied, followed by the changes ofrotation angle based on the rotation matrix. The positioning strategy of shaped piecesbased on the bottom left fit is proposed, and the focus search mechanism of tabu search is strengthened. Then the hybrid algorithm HGATS based on genetic algorithm and tabusearch algorithm is proposed.
Optimization methods in cutting path planning are studied. In the optimization processof selecting cutting starting point, the contour feature point is analyzed to extract the initialcutting starting point from the recent feature points to the origin, in which the hillclimbing algorithm is used to find the better solution of the surrounding neighbors. In theoptimization process of sorting cutting order, as it as the TSP problem, the ant colonyalgorithm is used to solve this problem. Then the hybrid algorithm HACHC based on antcolony algorithm and hill climbing algorithm for the two problems is proposed.
SmartNest software with independent intellectual property rights is developed based onthree kinds of hybrid intelligent algorithm, namely HGASA, HGATS and HACHC.Combined with the typical enterprise production instance, the general solutions framework,software system framework, main function module and flow chart of automatic cuttingand packing are presented, and the functions of three new hybirid algorithms are alsoachieved in this software. Compared with the three types of international famous nestingsoftware, the satisfactory result from SmartNest in the steel plate length and materialutilization is achieved.
研究套料与切割问题的理论基础与求解框架。描述套料与切割问题概念，分析这两类问题性质，给出数学模型，并设计基于Memetic算法的求解思路和框架。
研究矩形件套料算法。针对矩形件有直角排放规律的特点，提出一种最左下占角动作(BLCO)放置策略；基于改进个体之间的交叉运算，构造一种改进的优先运算交叉算子IPOX。利用Memetic算法中全局随机搜索和局部集中搜索混合的思想，提出一种基于遗传算法和模拟退火算法的HGASA混合算法。
研究异形件套料算法。针对异形件形状的多样性和旋转角度的任意性，研究基于临界多边形(NFP)的几何计算方法和基于旋转矩阵的零件旋转角度变化，并提出基于左下角方法的异形件定位策略。在强化禁忌搜索的集中搜索机制基础上，提出基于遗传算法和禁忌搜索算法的HGATS混合算法。
研究切割路径优化方法。在切割起点选取的优化过程中，通过轮廓特征点分析，提取离原点最近的特征点作为初始切割起点，采用爬山算法寻找周边邻域的较优解；在切割顺序排序的优化过程中，将其转化为TSP问题，并引入蚁群算法求解。在此基础上提出混合蚁群算法和爬山算法的HACHC算法求解这两个问题。
基于提出的HGASA、HGATS、HACHC三种混合智能算法，开发拥有自主知识产权的SmartNest系统。结合典型的工业实例，提出解决方案总体架构图、软件系统架构图和主要功能模块，规范套料和切割的流程图，并在系统中实现了三种新混合算法的功能。通过与三款国际知名排样软件的比较，本文的研究成果在钢板消耗长度、材料利用率等方面均取得满意结果。
Nowadays，green manufacturing and energy-saving technology has become one of thekey issues of the manufacturing industry. As a key technology to reduce energyconsumption and improve materials utilization, two-dimensional cutting and packingtechnology has been becoming the important research focus in academia and industry, andwidely used in the processing of machinery manufacturing, ship equipment and tailoring.Research on the method of two dimensional cutting and packing is the key to improve theprocessing efficiency of complex parts and the utilization of plate. In this thesis, theoptimization methods, namely rectangular packing, irregular packing and cutting pathplanning are studied from a systematic viewpoint. The main researches are organized asfollows.
The theoretical basis and solving framework of cutting and packing problem are studied,followed by the description of the concept of cutting and packing problem, Themathematical models of the two problems are established, and the optimization methodand the framework of general solution based on Memetic algorithm is discussed.
Algorithms in rectangular packing problem are studied. For the characteristics at rightangles to the emission of the rectangular pieces, a placement policy of bottom left corneroccupying (BLCO) is developed. An improved priority operation crossover operator IPOXis constructed based on improved crossover operation between individuals. By using themixed ideas of global random search and local focus search from Memetic algorithm, thehybrid algorithm HGASA based on genetic algorithm and simulated annealing algorithmis proposed.
Algorithms in irregular packing problem are studied. For the diversity of the shape andthe arbitrary nature of the rotation angle of the shaped pieces, the geometric calculationmethods based on the no fit polygon (NFP) are studied, followed by the changes ofrotation angle based on the rotation matrix. The positioning strategy of shaped piecesbased on the bottom left fit is proposed, and the focus search mechanism of tabu search is strengthened. Then the hybrid algorithm HGATS based on genetic algorithm and tabusearch algorithm is proposed.
Optimization methods in cutting path planning are studied. In the optimization processof selecting cutting starting point, the contour feature point is analyzed to extract the initialcutting starting point from the recent feature points to the origin, in which the hillclimbing algorithm is used to find the better solution of the surrounding neighbors. In theoptimization process of sorting cutting order, as it as the TSP problem, the ant colonyalgorithm is used to solve this problem. Then the hybrid algorithm HACHC based on antcolony algorithm and hill climbing algorithm for the two problems is proposed.
SmartNest software with independent intellectual property rights is developed based onthree kinds of hybrid intelligent algorithm, namely HGASA, HGATS and HACHC.Combined with the typical enterprise production instance, the general solutions framework,software system framework, main function module and flow chart of automatic cuttingand packing are presented, and the functions of three new hybirid algorithms are alsoachieved in this software. Compared with the three types of international famous nestingsoftware, the satisfactory result from SmartNest in the steel plate length and materialutilization is achieved.
引文
[1]刘飞,祁国宁,宁汝新,邵新宇,曹华军.先进制造系统及管理运作.国家自然科学基金委员会学科发展战略研究报告：《机械与制造科学》第15章.北京:科学出版社,2006.
[2] Chryssolouris G. Manufacturing Systems: Theory and Practice. New York,Springer-Verlag,1992.
[3] Tridech S., Cheng K. Low carbon manufacturing: characterization, theoreticalmodels and implementation, The6th International Conference on ManufacturingResearch Brunel University, UK,2008.
[4] IMC26. Energy Efficient&Low Carbon Manufacturing, Sept.2009, Dublin http://internationalmanufacturingconference.com/Location.php.
[5] Wa¨scher G., Hausner H., Schumann H. An improved typology of cutting andpacking problems. European Journal of Operational Research,2007,183:1109-1130.
[6] Lodi A., Martello S., Monaci M. Two-dimensional Packing problems: a Survey.European Journal of Operational Research,2002,141:241-252.
[7] Babu R.A., Babu R.N. Effective nesting of rectangular parts in multiple rectangularsheets using genetic and heuristic algorithms. International Journal of ProductionResearch,1999,37:1625-1643.
[8] Lesh N., Marks J., Mahon A., Mitzenmacher M. Exhaustive approaches to2Drectangular perfect packings. Information Processing Letters,2004,90:7-14.
[9] Martello S., Monaci M., Vigo D. An exact approach to the strip-packing problem.INFORMS Journal of Computing,2003,15:310-319.
[10] Baker B.S., Coffman E.G., Rivest R.L. Orthogonal packings in two dimensions.SIAM Journal on Computing,1980,9:846-855.
[11] Chazelle B. The bottom left bin packing heuristic: an efficient implementation.IEEE Transactions on Computers,1983,32:697-707.
[12] Hopper E., Turton B.C.H. An empirical investigation of meta-heuristic andheuristic algorithms for a2D packing problem. European Journal of OperationalResearch,2001,128:34-57.
[13] Lesh N., Marks J., Mahon M.A., Mitzenmacher M. New heuristic and interactiveapproaches to2D rectangular strip packing. ACM Journal of ExperimentalAlgorithm,2005,10:1-18.
[14] Lesh N., Mitzenmacher M. Bubble search: a simple heuristic for improvingpriority-based greedy algorithms. Information Processing Letters,2006,97:161-169.
[15] Burke E., Kendall G., Whitwell G. A new placement heuristic for the orthogonalstock-cutting problem. Operations Research,2004,52:655-671.
[16] Coffmann J.E., Garey D., Tarjan R. Performance bounds for level orientedtwo-dimensional packing algorithms. SIAM Journal on Computing,1980,9:808-826.
[17] Mumford-Valenzuela C., Vick J., Wang P.Y. Heuristics for Large Strip PackingProblems with Guillotine Patterns: An Empirical Study. Kluwer AcademicPublishers, Dordrecht,2003,501-522.
[18] Bortfeldt A., Gehring H. New large benchmarks for the two-dimensionalstrip-packing problem with rectangular pieces. In: IEEE Proceedings of the ThirtyNinth Hawaii International Conference on Systems Sciences,2006,30-35.
[19] Zhang D., Kang Y., Deng A. A new heuristic recursive algorithm for the striprectangular packing problem. Computers and Operations Research,2006,33:2209-2217.
[20] Neveu B., Trombettoni G., Araya I. Incremental move for strip-packing.Proceedings of ICTAI, Greece,2007.
[21] Soke A., Bingul Z. Hybrid genetic algorithm and simulated annealing fortwo-dimensional non-guillotine rectangular packing problems. EngineeringApplications of Artificial Intelligence,2006,19:557-567.
[22] Bortfeldt A. A genetic algorithm for the two-dimensional strip packing problemwith rectangular pieces. European Journal of Operational Research,2006,172:814-837.
[23] Burke E., Kendall G., Whitwell G. Meta-heuristic enhancements of the best-fitheuristic for the orthogonal stock-cutting problem. Technical Report, University ofNottingham, NOTTCS-TR-2006-3,2006.
[24] Alvarez-Valdes R., Parreno F., Tamarit J.M. Reactive GRASP for the strip-packingproblem. Computers&Operations Research,2008,35:1065-1083.
[25] Riff M.C., Bonnaire X., Neveu B. A revision of recent approaches fortwo-dimensional strip-packing problems. Engineering Applications of ArtificialIntelligence,2009,22:823-827.
[26]张德富,陈竞驰,刘永凯,陈火旺.用于二维不规则排样的离散临界多边形模型.软件学报,2009,20:1511-1520.
[27] Bennell J.A., Oliveira J.F. The geometry of nesting problems-A tutorial. EuropeanJournal of Operational Research,2008,184:397-415.
[28] Babu A.R., Babu N.R. A generic approach for nesting of2-D parts in2-D sheetsusing genetic and heuristic algorithms. Computer-Aided Design,2001,33:879-891.
[29] Ferreira J.C., Alves J.C., Albuquerque C., Oliveira J.F., Ferreira J.S., Matos J.S. AFlexible Custom Computing Machine for Nesting Problems, In: Proceedings ofXIII DCIS, Madrid, Spain,1998.
[30] Konopasek M. Mathematical treatments of some apparel marking and cuttingproblems. U.S. Department of Commerce Report99-26-90857-10,1981.
[31] Art J.R.C. An approach to the two-dimensional irregular cutting stock problem.IBM Cambridge Scientific Centre, Technical Report,1966,36-Y08.
[32] Mahadevan A. Optimization in computer aided pattern packing. Ph.D. Thesis,North Carolina State University,1984.
[33] Ghosh P.K. An algebra of polygons through the notion of negative shapes. CVGIP:Image Understanding,1991,54:119-144.
[34] Whitwell G. Novel Heuristic and Meta-heuristic Approaches to Cutting andPacking. PhD. thesis, University of Nottingham, UK,2005.
[35] Bennell J.A., Song X. A comprehensive and robust procedure for obtaining theno-fit polygon using Minkowski sums. Computers and Operations Research,2008,35:267-281.
[36] Stoyan Y.G., Terno J., Scheithauer G., Gil N., Romanova T. Phi-functions forprimary2D-objects. Studia Informatica Universalis,2001,2:1-32.
[37] Stoyan Y., Scheithauer G., Gil N., Romanova T. Φ-functions for complex2D-objects.4OR: Quarterly Journal of the Belgian, French and Italian OperationsResearch Societies,2004,2:69-84.
[38] Berg M.D., Kreveld M.V., Overmars M., Schwarzkopf O. Computational geometry:algorithms and applications (Second Edition), published by Springer-Verlag BerlinHeidelberg, New York,2005.
[39]周培德.计算几何：算法设计与分析(第三版).清华大学大学出版社,北京,2008.
[40] Gomes A.M., Oliveira J.F. A2-exchange heuristic for nesting problems. EuropeanJournal of Operational Research,2002,141:359-370.
[41] Li Z., Milenkovic V. Compaction and separation algorithms for non-convexpolygons and their applications. European Journal of Operational Research,1995,84:539-561.
[42] Milenkovic V.J., Daniels K. Translational polygon containment and minimalenclosure using mathematical programming. International Transactions inOperational Research,1999,6:525-554.
[43] Bennell J.A., Dowsland K.A. Hybridizing tabu search with optimization techniquesfor irregular stock cutting. Management Science,2001,47:1160-1172.
[44] Pirlot M. General local search methods. European Journal of Operational Research,1996,92:493-511.
[45] Gomes A.M., Oliveira J.F. Solving irregular strip packing problems by hybridizingSA and LP. European Journal of Operational Research,2006,171:811-822.
[46] Lenstra J.K., Rinnooy A.H.G. Some simple applications of the traveling salesmanproblem. Operational Research Quarterly,1975,26:717-733.
[47] Manber U., lsrani S. Pierce point minimization and optimal torch pathdetermination in flame cutting. Journal of Manufacturing Systems,1984,3:81-89.
[48] Cenrny V. Thermo dynamical approach to the traveling salesman problem: anefficient simulation algorithm. Journal of Optimization Theory and Applications,1985,45:41-51.
[49] Hopfield J.J., Tank D.W. Neural computation of decisions in optimizationproblems. Biological Cvhernetics,1985,52:141-152.
[50] Garey M., Johnson R. A guide to the theory of NP-completeness. Computers andIntractability: W.H. Freeman,1979:1-7.
[51] Lin S., Kernighan B.W. An effective heuristic algorithm for traveling problem.Operation Research,1973,21:498-500.
[52] Gomaez A., Gonzalez R. A Particle swarm-based meta-heuristic to solve thetraveling salesman problem. Proceedings of the2006International Conference onArtificial Intelligence,2006,698-702.
[53] Rutenbar R.A. Simulated annealing algorithms: an overview. IEEE Circuits andDevices Magazine,1989,19-26.
[54] Hrkpatrick S., Gelatt C.D. Vecchi M.P. Optimization by simulated annealing.Science,1983,220:671-680.
[55] Bland J.A. Dawson G.E. Tabu Search and Design Optimization. Computer AidedDesign,1991,23:195-201.
[56] Han G, Na S. A study on torch path planning in laser cutting process, part2:cutting path optimization using simulated annealing. Journal of ManufacturingProcess.1999,1:62-70.
[57]徐路宁,王霄.激光切割板材的工艺处理.应用激光,22:533-538.
[58] Rykalin N. Laser machining and welding. Pergamon Press,1987,35:326-332.
[59]王家金,激光加工技术.计量出版社,1992:186-197.
[60] Granamuthu D. Application of laser in materials processing, ASM, Metals Park,1979,129:41-46.
[61]朱企业.激光精密加工.机械工业出版社,1994:199-278.
[62] Castelino K., Souza R.D., Wright P.K. Tool-path optimization for minimizingairtime during machining. Journal of Manufacturing Systems,2002,22:173-180.
[63]刘会霞,王霄,蔡兰.钣金件数控激光切割割嘴路径的优化.计算机辅助设计与图形学学报,2004,5:660-665.
[64]刘会霞,王霄,周明,蔡兰.共边排样件激光切割路径的规划.中国激光,2004,10:1269-1274.
[65] Dorigo M., Maniezzo V., Colorni A. The ant system optimization by a colony ofcooperating agents. IEEE Transactions on Systems, Man and Cybernetics, Part B,1996,26:1-13.
[66] Gambardella L.M., Dorigo, M. Solving symmetric and asymmetric TSPs by antcolonies. In: Proceedings of the IEEE International Conference on EvolutionaryComputation, Nagoya: IEEE Press,1996,622-627.
[67] Liang K.H., Yao X. A new evolutionary approach to cutting stock problems withand without contiguity. Computers&Operations Research,2002,29:1641-1659.
[68]冯爱新,殷苏民,周建忠,张永康,戴峰泽,谢华锟.少无废料激光板材切割技术.应用激光,2005,5:87-89.
[69]高伟增,张宝剑,陈付贵,朱家义.基于遗传算法的切割路径优化.西南交通大学学报,2005,8:457-461.
[70]李建涛,黄星梅,钟志华.二维矩形件切割的路径优化.机械设计与制造,2005,4:86-87.
[71]俞武嘉,傅建中,陈子辰.基于遗传算法的刀具路径优化排布方法.浙江大学学报,2006,12:2117-2121.
[72]王书文,黄星梅,李建涛.二维矩形件组块优化切割的研究与实现.苏州大学学报,2007,12:49-52.
[73]李泳,张宝峰.复杂轮廓激光切割路径优化算法的研究.天津理工大学学报,2007,6:76-79.
[74] Oysu C., Bingul Z. Application of heuristic and hybrid-GASA algorithms totool-path optimization problem for minimizing airtime during machining.Engineering Applications of Artificial Intelligence,2009,22:389-396.
[75]李妮妮，陈章位，陈世泽.基于局部搜索和遗传算法的激光切割路径优化.计算机工程与应用,2010,46:234-239.
[76]康立山,谢云,尤矢勇,罗祖华.非数值并行算法(第一册),第一版.科学出版社,北京,1994.
[77]冯玉蓉.模拟退火算法的研究及其应用.昆明理工大学硕士论文,2005.
[78]顾小丰,孙世新,卢光辉.计算复杂性.机械工业出版社,北京,2005.
[79]龙哲.船体零件自动排料及优化问题的研究.上海交通大学硕士论文,2008.
[80]姚恩瑜,何勇,陈仕平.数学规划与组合优化.浙江大学出版社,杭州,2001.
[81]高永超.智能优化算法的性能及搜索空间研究.山东大学博士论文,2007.
[82] Moscato P., Norman M.G. A Memetic approach for the travelling salesmanproblem implementation of a computational ecology for combinatorialoptimization on message passing systems. In proceedings of the internationalconference on parallel computing and transport applications,1992.
[83]刘漫丹.文化基因算法研究进展.自动化技术与应用,2007,11:1-5.
[84] Radcliffe N.J., Surry P.D. Formal Memetic algorithms. Evolutionary Computing,1994.
[85]陈志敏.基于文化基因算法的拓扑优化方法研究.华中科技大学博士论文,2010,15-18.
[86] Peng Z., Zhi Z., Chen G.L, Yao X. A novel memetic algorithm with randommulti-local-search: A case study of TSP. Proceedings of the2004Congress onEvolutionary Computation,2004:1-6.
[87] Franca P.M., Moscato P. New Memetic algorithm for the asymmetric travelingsalesman problem. Journal of Heuristics,2004,10:483–506.
[88] Franca P.M., Mendes A., Moscato P. A Memetic algorithm for the total tardinesssingle machine scheduling problem. European Journal of Operational Research,2000.
[89] Yeh W. C. A Memetic algorithm for the n/2flowshop scheduling problem.International Journal of Advanced Manufactory Technology,2002,20:464-473.
[90] Hara T.O., Bull L. A Memetic accuracy-based neural learning classifier system.Evolutionary Computation, the2005IEEE Congress,2005,3:2040–2045.
[91] Wong K.W., Ong Y.S., Eren H. Hybrid fuzzy modelling using Memetic algorithmfor hydrocyclone control. Proceedings of the third international conference onmachine learning and cybernetics,2004.
[92] Yeh W.C. An efficient memetic algorithm for the multi-stage supply chain networkproblem. International Journal of Advanced Manufactory Technology,2005.
[93] Aydemir M.E., Giinel T., Kargin S. SAR image processing by a Memetic algorithm.RAST,2005:684-687.
[94]李智放.无功优化进化计算的局部搜索策略及多目标处理方法.华中科技大学博士学位论文,2010,26-27.
[95] Kobayashi, S. Foundations of genetic algorithms and its applications,Communications of ORSJ,1993,45:256-261.
[96] Rechenberg, I. Evolution strategie: Optimieriung technischer Systeme nachPrinzipien der biologischen Evolution, Frommann-Holzboog, Stuttgart, Germany,1973.
[97] Davidor Y. Epistasis variance: A viewpoint on GA-hardness. In Foundations ofGenetic Algorithms, G. Rawlins, Ed. Morgan Kaufmann,1991,23-35.
[98] Radcliffe N., Surry P. Fitness variance of formae and performance prediction. InProceedings of the3rd Workshop on Foundations of Genetic Algorithms, SanFrancisco,1994,51-72.
[99] Wu F.J. A framework for Memetic algorithms. Master thesis, University ofAuckland,2001,10-12.
[100] Cotta C., Muruzabal J. Towards a more efficient evolutionary induction of bayesiannetworks. In Parallel Problem Solving From Nature VII, J. Merelo et al., Eds., vol.2439of Lecture Notes in Computer Science. Springer-Verlag, Paris,2002.
[101] Moscato, P. An introduction to population approaches for optimization andhierarchical objective functions: the role of tabu search. Annals of OperationsResearch,1993,41:85-121.
[102] Cotta C., Troya J. Information processing in transmitting recombination. AppliedIntelligence,2003,16:945-948.
[103] Hansen P., Mladenovic N. Variable neighborhood search: principles andapplications. European Journal of Operational Research,2001,130:449-467.
[104]王赞.基于染色体自交叉Memetic算法的教学调度问题研究.天津大学博士学位论文,2009,33-34.
[105] Hochbaum D.S., Wolfgang M. Approximation schemes for covering and packingproblems in image processing and VLSI. Journal Associated Computer Machine,1985,32:130-136.
[106] Leung J., Tam T., Wong C.S., Young G., Chin F. Packing squares into square.Journal Parallel Distributed Compute,1990,10:271-275.
[107] Dowsland K.A., Dowsland W.B. Packing problems. European Journal ofOperational Research,1992,56:2-14.
[108] Jakobs S. On genetic algorithms for the packing of polygons. European Journal ofOperational Research,1996,88:165-181.
[109] Lai K.K., Chan W.M. An evolutionary algorithm for the rectangular cutting stockproblem. International Journal of Industrial Engineering,1997,4:130-139.
[110] Leung T.W., Chan C.K., Troutt M. Comparison of meta-heuristics for the twodimensional orthogonal packing problem. Working Paper, Department of AppliedMathematics, The Hong Kong Ploytechnic University, Hong Kong,2000.
[111] Leung T.W., Chan C.K., Troutt M.D. Application of a mixed simulated annealinggenetic algorithm heuristic for the two-dimensional orthogonal packing problem.European Journal of Operational Research,2003,145:530-542.
[112] Ortmann F.G., Ntene N., Vuuren J.H.V. New and improved level heuristic for therectangular strip packing and variable-sized bin packing problems. EuropeanJournal of Operational Research,2010,203:306-315.
[113] Baker B.S., Coffman J.E.G., Rivest R.L. Orthogonal packing in two dimensions.SIAM Journal on Computing,1980,9:846-855.
[114] Huang W., Chen D. A new heuristic algorithm for the rectangle packing. ComputerOperation Research,2007,34:3270-3280.
[115] Holland J.H. Adaptation in natural and artificial systems. Cambridge, MA: MITPress,1975.
[116]葛培明.改进的遗传算法及其在工程优化中的应用.西南交通大学博士论文,2006,45-49.
[117]张文修,梁怡.遗传算法的数学基础(第2版).西安交通大学出版社,西安,2006:150-154.
[118]石岩.基于遗传模拟退火算法的二维不规则多边形排样问题.西北工业大学硕士论文,2007,21-23.
[119] Davis L. Adapting operator probabilities in genetic algorithms. In Proceedings ofthe Third International Conference on Genetic Algorithms(ICGA3)，Schaffer, J.D.(ed.), San Mateo, CA: Morgan Kaufmann Publishers,1989:61-69.
[120] Lobo F.G., Goldberg D.E. Decision making in a hybrid genetic algorithm.Proceedings of the1997IEEE Conference on Evolutionary Computation，NewYork: IEEE Press,1997:121-125.
[121] Metroplis N., Rosenbluth A., Rosenbluth M. Equation of state calculations by fastcomputing machines. Journal of Cherimal Physics,1953,21:1087-1092.
[122] Kirkpatrick S., Gelatt J.C.D., Vecchi M.P. Optimization by simulated annealing.Science,1983,220:671-680.
[123]陈勇,唐敏,童若锋,董金祥.基于遗传模拟退火算法的不规则多边形排样.计算机辅助设计与图形学学报,2003,15:598-603.
[124]闫红超.基于遗传模拟退火算法的PCB贴装工艺优化研究.西安电子科技大学硕士论文,2006,31-32.
[125] Wang L., Zheng D.Z. An effective hybrid optimization strategy for job shopscheduling problems. Computer Operation Research,2001,28:585-596.
[126] Kobayashi S., Ono I., Yamamura M. An efficient genetic algorithm for job shopscheduling problems. In Proceedings of the6th International Conference onGenetic Algorithms,1995:506-511.
[127] Zhang C.Y., Rao Y.Q., Li P.G. An effective hybrid genetic algorithm for the jobshop scheduling problem. International Journal of Advanced ManufactoryTechnology,2008,39:965-974.
[128] Albano A., Sapuppo G. Optimal allocation of two-dimensional irregular shapesusing heuristic search methods. IEEE Transactions on Systems, Man CyberneticsSMC-10,1980,242-248.
[129] Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solvingthe two-dimensional irregular cutting problem. Annals of Operations Research,1993,41:313-325.
[130] Marques V.M.M., Bispo C.F.G., Sentieiro J.J.S. A system for the compaction oftwo-dimensional irregular shapes based on simulated annealing. Proceeding1991International Conference Industrial Electronics, Control andInstrumentation-IECON’91, Kobe, Japan,1991,3:1911-1916.
[131] Fujita K., Akagi S., Hirokawa N. Hybrid approach for optimal nesting using agenetic algorithm and a local minimization algorithm. Proceeding1993ASMEDesign Automation Conference,1993,65:477-484.
[132] Oliveira J.F., Ferreira J.S. Algorithms for nesting problems. Rene V. V. Vidal, ed.Applied Simulated Annealing, Lecture Notes in Economics and MathematicalSystems. Springer-Verlag, Berlin, Germany,1993:255-273.
[133] Dighe R., Jakiela M.J. Solving pattern nesting problems with genetic algorithmsemploying task decomposition and contact detection. Evolutionary Compute,1996,3:239-266.
[134] Jakobs S. On genetic algorithms for the packing of polygons. European Journal ofOperational Research,1996,88:165-181.
[135] Bounsaythip C., Maouche S. Irregular shape nesting and placing with evolutionaryapproach. Proceeding IEEE International Conference Systems, Man Cybernetics,1997,4:3425-3430.
[136] Oliveira J.F., Gomes A.M., Ferreira J.S. A new constructive algorithm for nestingproblems. OR Spektrum,2000,22:263-284.
[137] Hopper E., Turton B.C.H. An empirical investigation of metaheuristic and heuristicalgorithms for a2D packing problem. European Journal of Operational Research,2001,128:34-57.
[138] Gomes A.M., Oliveira J.F. A2-exchange heuristic for nesting problems. EuropeanJournal of Operational Research,2002,141:359-370.
[139] Burke E., Hellier R., Kendall G., Whitwell G. A new bottom-left-fill heuristicalgorithm for the two dimensional irregular packing problem. Operations Research,2006,54:587-601.
[140] Lee W.C., Ma H., Cheng B.W. A heuristic for nesting problems of irregular shapes.Computer Aided Design,2008,40:625-633.
[141]何援军.计算机图形学算法与实践.长沙:湖南科技出版社，1992.
[142]朱雅音,王化文,万丰,于雷.确定两个任意简单多边形交、并、差的算法.计算机研究与发展.2003,40:576-583.
[143]刘胡瑶.基于临界多边形的二维排样算法研究.上海交通大学博士论文，2007,44-65.
[144] Feito F.R., Torres J.C., Urena A. Orientation, simplicity, and inclusion test forplanar polygons. Computers&Graphics,1995,19:595-600.
[145] Bennell J.A., Dowsland K.A., Dowsland W.B. The irregular cutting-stock problem-a new procedure for deriving the no-fit polygon. Computers and OperationsResearch,2001,28:271-287.
[146] Milenkovic V., Daniels K., Li Z. Placement and compaction of non-convexpolygons for clothing manufacture. In: Proceedings of the4th CanadianConference on Computational Geometry, St. John's, Newfoundland,1993:236-243.
[147] Ghosh P. K. A unified computational framework for Minkowski operations.Computers and Graphics,1993,17:357-378.
[148] Glover F. Heuristics for integer programming using surrogate constraints. DecisionScience,1977,8:156-166.
[149] Reeves C. Genetic algorithms and neighborhood search. In Gogarty,1993,128:115-130.
[150]吕玉龙，沈青松，石铁流，王翼飞.基于禁忌搜索和遗传算法的智能化双聚类方法.应用科学学报,2009,27:282-287.
[151]贺一.禁忌搜索及其并行化研究.西南大学博士论文,2006,41-44.
[152]张超勇.基于自然启发式算法的作业车间调度问题理论与应用研究.华中科技大学博士论文,2006,65-69.
[153]段敬民,常跃军,李赞祥,崔建明.基于退火算法的物流配送网的求优研究.中国工程科学,2012,7:109-112.
[154] David F R.,石教英译．计算机图形学的算法基础．北京:机械工业出版社,2002:131-147.
[155]王树禾.图论及其算法．合肥:中国科学技术大学出版社,1990:9-19.
[156]舒贤林,徐志才.图论基础及其应用.北京:北京邮电学院出版社,1988:12-22.
[157]戴一奇,胡冠章.图论与代数结构.北京:清华大学出版社,1995,6:32-56.
[158] Dorigo M. Caro G.D., Gambardella L.M. Ant algorithms for discrete optimization.Artificial Life,1999,5:137-172.
[159]楚瑞.基于蚁群算法的无人机航路规划.西北工业大学硕士论文,2006,24-25.
[160]汪定伟,王俊伟,王洪峰,张瑞友,郭哲.智能优化方法.北京:高等教育出版社,2007,171-173.
[161]蔡力钢,饶运清,郭军,吕文林.面向集中下料的钣金排样编程系统.华中理工大学学报,1999,27:66-68.
[162]罗阳.机械制造车间生产作业多智能体规划原理与板材套料优化方法的研究.四川大学博士论文,2001,72-74.
[163]饶运清,高伟增,李培根.面向CIMS的板类零件下料工艺系统.制造业自动化,2002,24:5-8.
[164]饶运清,郭军,宋志刚,蔡力钢.集成钣金优化排料系统.制造技术与机床,1999,4:35-37.
[165]蔡力钢,饶运清,郭军,宋志刚.板类零件数控加工CAD/CAPP/CAM系统.机械设计与制造,1999,6:11-13.
[2] Chryssolouris G. Manufacturing Systems: Theory and Practice. New York,Springer-Verlag,1992.
[3] Tridech S., Cheng K. Low carbon manufacturing: characterization, theoreticalmodels and implementation, The6th International Conference on ManufacturingResearch Brunel University, UK,2008.
[4] IMC26. Energy Efficient&Low Carbon Manufacturing, Sept.2009, Dublin http://internationalmanufacturingconference.com/Location.php.
[5] Wa¨scher G., Hausner H., Schumann H. An improved typology of cutting andpacking problems. European Journal of Operational Research,2007,183:1109-1130.
[6] Lodi A., Martello S., Monaci M. Two-dimensional Packing problems: a Survey.European Journal of Operational Research,2002,141:241-252.
[7] Babu R.A., Babu R.N. Effective nesting of rectangular parts in multiple rectangularsheets using genetic and heuristic algorithms. International Journal of ProductionResearch,1999,37:1625-1643.
[8] Lesh N., Marks J., Mahon A., Mitzenmacher M. Exhaustive approaches to2Drectangular perfect packings. Information Processing Letters,2004,90:7-14.
[9] Martello S., Monaci M., Vigo D. An exact approach to the strip-packing problem.INFORMS Journal of Computing,2003,15:310-319.
[10] Baker B.S., Coffman E.G., Rivest R.L. Orthogonal packings in two dimensions.SIAM Journal on Computing,1980,9:846-855.
[11] Chazelle B. The bottom left bin packing heuristic: an efficient implementation.IEEE Transactions on Computers,1983,32:697-707.
[12] Hopper E., Turton B.C.H. An empirical investigation of meta-heuristic andheuristic algorithms for a2D packing problem. European Journal of OperationalResearch,2001,128:34-57.
[13] Lesh N., Marks J., Mahon M.A., Mitzenmacher M. New heuristic and interactiveapproaches to2D rectangular strip packing. ACM Journal of ExperimentalAlgorithm,2005,10:1-18.
[14] Lesh N., Mitzenmacher M. Bubble search: a simple heuristic for improvingpriority-based greedy algorithms. Information Processing Letters,2006,97:161-169.
[15] Burke E., Kendall G., Whitwell G. A new placement heuristic for the orthogonalstock-cutting problem. Operations Research,2004,52:655-671.
[16] Coffmann J.E., Garey D., Tarjan R. Performance bounds for level orientedtwo-dimensional packing algorithms. SIAM Journal on Computing,1980,9:808-826.
[17] Mumford-Valenzuela C., Vick J., Wang P.Y. Heuristics for Large Strip PackingProblems with Guillotine Patterns: An Empirical Study. Kluwer AcademicPublishers, Dordrecht,2003,501-522.
[18] Bortfeldt A., Gehring H. New large benchmarks for the two-dimensionalstrip-packing problem with rectangular pieces. In: IEEE Proceedings of the ThirtyNinth Hawaii International Conference on Systems Sciences,2006,30-35.
[19] Zhang D., Kang Y., Deng A. A new heuristic recursive algorithm for the striprectangular packing problem. Computers and Operations Research,2006,33:2209-2217.
[20] Neveu B., Trombettoni G., Araya I. Incremental move for strip-packing.Proceedings of ICTAI, Greece,2007.
[21] Soke A., Bingul Z. Hybrid genetic algorithm and simulated annealing fortwo-dimensional non-guillotine rectangular packing problems. EngineeringApplications of Artificial Intelligence,2006,19:557-567.
[22] Bortfeldt A. A genetic algorithm for the two-dimensional strip packing problemwith rectangular pieces. European Journal of Operational Research,2006,172:814-837.
[23] Burke E., Kendall G., Whitwell G. Meta-heuristic enhancements of the best-fitheuristic for the orthogonal stock-cutting problem. Technical Report, University ofNottingham, NOTTCS-TR-2006-3,2006.
[24] Alvarez-Valdes R., Parreno F., Tamarit J.M. Reactive GRASP for the strip-packingproblem. Computers&Operations Research,2008,35:1065-1083.
[25] Riff M.C., Bonnaire X., Neveu B. A revision of recent approaches fortwo-dimensional strip-packing problems. Engineering Applications of ArtificialIntelligence,2009,22:823-827.
[26]张德富,陈竞驰,刘永凯,陈火旺.用于二维不规则排样的离散临界多边形模型.软件学报,2009,20:1511-1520.
[27] Bennell J.A., Oliveira J.F. The geometry of nesting problems-A tutorial. EuropeanJournal of Operational Research,2008,184:397-415.
[28] Babu A.R., Babu N.R. A generic approach for nesting of2-D parts in2-D sheetsusing genetic and heuristic algorithms. Computer-Aided Design,2001,33:879-891.
[29] Ferreira J.C., Alves J.C., Albuquerque C., Oliveira J.F., Ferreira J.S., Matos J.S. AFlexible Custom Computing Machine for Nesting Problems, In: Proceedings ofXIII DCIS, Madrid, Spain,1998.
[30] Konopasek M. Mathematical treatments of some apparel marking and cuttingproblems. U.S. Department of Commerce Report99-26-90857-10,1981.
[31] Art J.R.C. An approach to the two-dimensional irregular cutting stock problem.IBM Cambridge Scientific Centre, Technical Report,1966,36-Y08.
[32] Mahadevan A. Optimization in computer aided pattern packing. Ph.D. Thesis,North Carolina State University,1984.
[33] Ghosh P.K. An algebra of polygons through the notion of negative shapes. CVGIP:Image Understanding,1991,54:119-144.
[34] Whitwell G. Novel Heuristic and Meta-heuristic Approaches to Cutting andPacking. PhD. thesis, University of Nottingham, UK,2005.
[35] Bennell J.A., Song X. A comprehensive and robust procedure for obtaining theno-fit polygon using Minkowski sums. Computers and Operations Research,2008,35:267-281.
[36] Stoyan Y.G., Terno J., Scheithauer G., Gil N., Romanova T. Phi-functions forprimary2D-objects. Studia Informatica Universalis,2001,2:1-32.
[37] Stoyan Y., Scheithauer G., Gil N., Romanova T. Φ-functions for complex2D-objects.4OR: Quarterly Journal of the Belgian, French and Italian OperationsResearch Societies,2004,2:69-84.
[38] Berg M.D., Kreveld M.V., Overmars M., Schwarzkopf O. Computational geometry:algorithms and applications (Second Edition), published by Springer-Verlag BerlinHeidelberg, New York,2005.
[39]周培德.计算几何：算法设计与分析(第三版).清华大学大学出版社,北京,2008.
[40] Gomes A.M., Oliveira J.F. A2-exchange heuristic for nesting problems. EuropeanJournal of Operational Research,2002,141:359-370.
[41] Li Z., Milenkovic V. Compaction and separation algorithms for non-convexpolygons and their applications. European Journal of Operational Research,1995,84:539-561.
[42] Milenkovic V.J., Daniels K. Translational polygon containment and minimalenclosure using mathematical programming. International Transactions inOperational Research,1999,6:525-554.
[43] Bennell J.A., Dowsland K.A. Hybridizing tabu search with optimization techniquesfor irregular stock cutting. Management Science,2001,47:1160-1172.
[44] Pirlot M. General local search methods. European Journal of Operational Research,1996,92:493-511.
[45] Gomes A.M., Oliveira J.F. Solving irregular strip packing problems by hybridizingSA and LP. European Journal of Operational Research,2006,171:811-822.
[46] Lenstra J.K., Rinnooy A.H.G. Some simple applications of the traveling salesmanproblem. Operational Research Quarterly,1975,26:717-733.
[47] Manber U., lsrani S. Pierce point minimization and optimal torch pathdetermination in flame cutting. Journal of Manufacturing Systems,1984,3:81-89.
[48] Cenrny V. Thermo dynamical approach to the traveling salesman problem: anefficient simulation algorithm. Journal of Optimization Theory and Applications,1985,45:41-51.
[49] Hopfield J.J., Tank D.W. Neural computation of decisions in optimizationproblems. Biological Cvhernetics,1985,52:141-152.
[50] Garey M., Johnson R. A guide to the theory of NP-completeness. Computers andIntractability: W.H. Freeman,1979:1-7.
[51] Lin S., Kernighan B.W. An effective heuristic algorithm for traveling problem.Operation Research,1973,21:498-500.
[52] Gomaez A., Gonzalez R. A Particle swarm-based meta-heuristic to solve thetraveling salesman problem. Proceedings of the2006International Conference onArtificial Intelligence,2006,698-702.
[53] Rutenbar R.A. Simulated annealing algorithms: an overview. IEEE Circuits andDevices Magazine,1989,19-26.
[54] Hrkpatrick S., Gelatt C.D. Vecchi M.P. Optimization by simulated annealing.Science,1983,220:671-680.
[55] Bland J.A. Dawson G.E. Tabu Search and Design Optimization. Computer AidedDesign,1991,23:195-201.
[56] Han G, Na S. A study on torch path planning in laser cutting process, part2:cutting path optimization using simulated annealing. Journal of ManufacturingProcess.1999,1:62-70.
[57]徐路宁,王霄.激光切割板材的工艺处理.应用激光,22:533-538.
[58] Rykalin N. Laser machining and welding. Pergamon Press,1987,35:326-332.
[59]王家金,激光加工技术.计量出版社,1992:186-197.
[60] Granamuthu D. Application of laser in materials processing, ASM, Metals Park,1979,129:41-46.
[61]朱企业.激光精密加工.机械工业出版社,1994:199-278.
[62] Castelino K., Souza R.D., Wright P.K. Tool-path optimization for minimizingairtime during machining. Journal of Manufacturing Systems,2002,22:173-180.
[63]刘会霞,王霄,蔡兰.钣金件数控激光切割割嘴路径的优化.计算机辅助设计与图形学学报,2004,5:660-665.
[64]刘会霞,王霄,周明,蔡兰.共边排样件激光切割路径的规划.中国激光,2004,10:1269-1274.
[65] Dorigo M., Maniezzo V., Colorni A. The ant system optimization by a colony ofcooperating agents. IEEE Transactions on Systems, Man and Cybernetics, Part B,1996,26:1-13.
[66] Gambardella L.M., Dorigo, M. Solving symmetric and asymmetric TSPs by antcolonies. In: Proceedings of the IEEE International Conference on EvolutionaryComputation, Nagoya: IEEE Press,1996,622-627.
[67] Liang K.H., Yao X. A new evolutionary approach to cutting stock problems withand without contiguity. Computers&Operations Research,2002,29:1641-1659.
[68]冯爱新,殷苏民,周建忠,张永康,戴峰泽,谢华锟.少无废料激光板材切割技术.应用激光,2005,5:87-89.
[69]高伟增,张宝剑,陈付贵,朱家义.基于遗传算法的切割路径优化.西南交通大学学报,2005,8:457-461.
[70]李建涛,黄星梅,钟志华.二维矩形件切割的路径优化.机械设计与制造,2005,4:86-87.
[71]俞武嘉,傅建中,陈子辰.基于遗传算法的刀具路径优化排布方法.浙江大学学报,2006,12:2117-2121.
[72]王书文,黄星梅,李建涛.二维矩形件组块优化切割的研究与实现.苏州大学学报,2007,12:49-52.
[73]李泳,张宝峰.复杂轮廓激光切割路径优化算法的研究.天津理工大学学报,2007,6:76-79.
[74] Oysu C., Bingul Z. Application of heuristic and hybrid-GASA algorithms totool-path optimization problem for minimizing airtime during machining.Engineering Applications of Artificial Intelligence,2009,22:389-396.
[75]李妮妮，陈章位，陈世泽.基于局部搜索和遗传算法的激光切割路径优化.计算机工程与应用,2010,46:234-239.
[76]康立山,谢云,尤矢勇,罗祖华.非数值并行算法(第一册),第一版.科学出版社,北京,1994.
[77]冯玉蓉.模拟退火算法的研究及其应用.昆明理工大学硕士论文,2005.
[78]顾小丰,孙世新,卢光辉.计算复杂性.机械工业出版社,北京,2005.
[79]龙哲.船体零件自动排料及优化问题的研究.上海交通大学硕士论文,2008.
[80]姚恩瑜,何勇,陈仕平.数学规划与组合优化.浙江大学出版社,杭州,2001.
[81]高永超.智能优化算法的性能及搜索空间研究.山东大学博士论文,2007.
[82] Moscato P., Norman M.G. A Memetic approach for the travelling salesmanproblem implementation of a computational ecology for combinatorialoptimization on message passing systems. In proceedings of the internationalconference on parallel computing and transport applications,1992.
[83]刘漫丹.文化基因算法研究进展.自动化技术与应用,2007,11:1-5.
[84] Radcliffe N.J., Surry P.D. Formal Memetic algorithms. Evolutionary Computing,1994.
[85]陈志敏.基于文化基因算法的拓扑优化方法研究.华中科技大学博士论文,2010,15-18.
[86] Peng Z., Zhi Z., Chen G.L, Yao X. A novel memetic algorithm with randommulti-local-search: A case study of TSP. Proceedings of the2004Congress onEvolutionary Computation,2004:1-6.
[87] Franca P.M., Moscato P. New Memetic algorithm for the asymmetric travelingsalesman problem. Journal of Heuristics,2004,10:483–506.
[88] Franca P.M., Mendes A., Moscato P. A Memetic algorithm for the total tardinesssingle machine scheduling problem. European Journal of Operational Research,2000.
[89] Yeh W. C. A Memetic algorithm for the n/2flowshop scheduling problem.International Journal of Advanced Manufactory Technology,2002,20:464-473.
[90] Hara T.O., Bull L. A Memetic accuracy-based neural learning classifier system.Evolutionary Computation, the2005IEEE Congress,2005,3:2040–2045.
[91] Wong K.W., Ong Y.S., Eren H. Hybrid fuzzy modelling using Memetic algorithmfor hydrocyclone control. Proceedings of the third international conference onmachine learning and cybernetics,2004.
[92] Yeh W.C. An efficient memetic algorithm for the multi-stage supply chain networkproblem. International Journal of Advanced Manufactory Technology,2005.
[93] Aydemir M.E., Giinel T., Kargin S. SAR image processing by a Memetic algorithm.RAST,2005:684-687.
[94]李智放.无功优化进化计算的局部搜索策略及多目标处理方法.华中科技大学博士学位论文,2010,26-27.
[95] Kobayashi, S. Foundations of genetic algorithms and its applications,Communications of ORSJ,1993,45:256-261.
[96] Rechenberg, I. Evolution strategie: Optimieriung technischer Systeme nachPrinzipien der biologischen Evolution, Frommann-Holzboog, Stuttgart, Germany,1973.
[97] Davidor Y. Epistasis variance: A viewpoint on GA-hardness. In Foundations ofGenetic Algorithms, G. Rawlins, Ed. Morgan Kaufmann,1991,23-35.
[98] Radcliffe N., Surry P. Fitness variance of formae and performance prediction. InProceedings of the3rd Workshop on Foundations of Genetic Algorithms, SanFrancisco,1994,51-72.
[99] Wu F.J. A framework for Memetic algorithms. Master thesis, University ofAuckland,2001,10-12.
[100] Cotta C., Muruzabal J. Towards a more efficient evolutionary induction of bayesiannetworks. In Parallel Problem Solving From Nature VII, J. Merelo et al., Eds., vol.2439of Lecture Notes in Computer Science. Springer-Verlag, Paris,2002.
[101] Moscato, P. An introduction to population approaches for optimization andhierarchical objective functions: the role of tabu search. Annals of OperationsResearch,1993,41:85-121.
[102] Cotta C., Troya J. Information processing in transmitting recombination. AppliedIntelligence,2003,16:945-948.
[103] Hansen P., Mladenovic N. Variable neighborhood search: principles andapplications. European Journal of Operational Research,2001,130:449-467.
[104]王赞.基于染色体自交叉Memetic算法的教学调度问题研究.天津大学博士学位论文,2009,33-34.
[105] Hochbaum D.S., Wolfgang M. Approximation schemes for covering and packingproblems in image processing and VLSI. Journal Associated Computer Machine,1985,32:130-136.
[106] Leung J., Tam T., Wong C.S., Young G., Chin F. Packing squares into square.Journal Parallel Distributed Compute,1990,10:271-275.
[107] Dowsland K.A., Dowsland W.B. Packing problems. European Journal ofOperational Research,1992,56:2-14.
[108] Jakobs S. On genetic algorithms for the packing of polygons. European Journal ofOperational Research,1996,88:165-181.
[109] Lai K.K., Chan W.M. An evolutionary algorithm for the rectangular cutting stockproblem. International Journal of Industrial Engineering,1997,4:130-139.
[110] Leung T.W., Chan C.K., Troutt M. Comparison of meta-heuristics for the twodimensional orthogonal packing problem. Working Paper, Department of AppliedMathematics, The Hong Kong Ploytechnic University, Hong Kong,2000.
[111] Leung T.W., Chan C.K., Troutt M.D. Application of a mixed simulated annealinggenetic algorithm heuristic for the two-dimensional orthogonal packing problem.European Journal of Operational Research,2003,145:530-542.
[112] Ortmann F.G., Ntene N., Vuuren J.H.V. New and improved level heuristic for therectangular strip packing and variable-sized bin packing problems. EuropeanJournal of Operational Research,2010,203:306-315.
[113] Baker B.S., Coffman J.E.G., Rivest R.L. Orthogonal packing in two dimensions.SIAM Journal on Computing,1980,9:846-855.
[114] Huang W., Chen D. A new heuristic algorithm for the rectangle packing. ComputerOperation Research,2007,34:3270-3280.
[115] Holland J.H. Adaptation in natural and artificial systems. Cambridge, MA: MITPress,1975.
[116]葛培明.改进的遗传算法及其在工程优化中的应用.西南交通大学博士论文,2006,45-49.
[117]张文修,梁怡.遗传算法的数学基础(第2版).西安交通大学出版社,西安,2006:150-154.
[118]石岩.基于遗传模拟退火算法的二维不规则多边形排样问题.西北工业大学硕士论文,2007,21-23.
[119] Davis L. Adapting operator probabilities in genetic algorithms. In Proceedings ofthe Third International Conference on Genetic Algorithms(ICGA3)，Schaffer, J.D.(ed.), San Mateo, CA: Morgan Kaufmann Publishers,1989:61-69.
[120] Lobo F.G., Goldberg D.E. Decision making in a hybrid genetic algorithm.Proceedings of the1997IEEE Conference on Evolutionary Computation，NewYork: IEEE Press,1997:121-125.
[121] Metroplis N., Rosenbluth A., Rosenbluth M. Equation of state calculations by fastcomputing machines. Journal of Cherimal Physics,1953,21:1087-1092.
[122] Kirkpatrick S., Gelatt J.C.D., Vecchi M.P. Optimization by simulated annealing.Science,1983,220:671-680.
[123]陈勇,唐敏,童若锋,董金祥.基于遗传模拟退火算法的不规则多边形排样.计算机辅助设计与图形学学报,2003,15:598-603.
[124]闫红超.基于遗传模拟退火算法的PCB贴装工艺优化研究.西安电子科技大学硕士论文,2006,31-32.
[125] Wang L., Zheng D.Z. An effective hybrid optimization strategy for job shopscheduling problems. Computer Operation Research,2001,28:585-596.
[126] Kobayashi S., Ono I., Yamamura M. An efficient genetic algorithm for job shopscheduling problems. In Proceedings of the6th International Conference onGenetic Algorithms,1995:506-511.
[127] Zhang C.Y., Rao Y.Q., Li P.G. An effective hybrid genetic algorithm for the jobshop scheduling problem. International Journal of Advanced ManufactoryTechnology,2008,39:965-974.
[128] Albano A., Sapuppo G. Optimal allocation of two-dimensional irregular shapesusing heuristic search methods. IEEE Transactions on Systems, Man CyberneticsSMC-10,1980,242-248.
[129] Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solvingthe two-dimensional irregular cutting problem. Annals of Operations Research,1993,41:313-325.
[130] Marques V.M.M., Bispo C.F.G., Sentieiro J.J.S. A system for the compaction oftwo-dimensional irregular shapes based on simulated annealing. Proceeding1991International Conference Industrial Electronics, Control andInstrumentation-IECON’91, Kobe, Japan,1991,3:1911-1916.
[131] Fujita K., Akagi S., Hirokawa N. Hybrid approach for optimal nesting using agenetic algorithm and a local minimization algorithm. Proceeding1993ASMEDesign Automation Conference,1993,65:477-484.
[132] Oliveira J.F., Ferreira J.S. Algorithms for nesting problems. Rene V. V. Vidal, ed.Applied Simulated Annealing, Lecture Notes in Economics and MathematicalSystems. Springer-Verlag, Berlin, Germany,1993:255-273.
[133] Dighe R., Jakiela M.J. Solving pattern nesting problems with genetic algorithmsemploying task decomposition and contact detection. Evolutionary Compute,1996,3:239-266.
[134] Jakobs S. On genetic algorithms for the packing of polygons. European Journal ofOperational Research,1996,88:165-181.
[135] Bounsaythip C., Maouche S. Irregular shape nesting and placing with evolutionaryapproach. Proceeding IEEE International Conference Systems, Man Cybernetics,1997,4:3425-3430.
[136] Oliveira J.F., Gomes A.M., Ferreira J.S. A new constructive algorithm for nestingproblems. OR Spektrum,2000,22:263-284.
[137] Hopper E., Turton B.C.H. An empirical investigation of metaheuristic and heuristicalgorithms for a2D packing problem. European Journal of Operational Research,2001,128:34-57.
[138] Gomes A.M., Oliveira J.F. A2-exchange heuristic for nesting problems. EuropeanJournal of Operational Research,2002,141:359-370.
[139] Burke E., Hellier R., Kendall G., Whitwell G. A new bottom-left-fill heuristicalgorithm for the two dimensional irregular packing problem. Operations Research,2006,54:587-601.
[140] Lee W.C., Ma H., Cheng B.W. A heuristic for nesting problems of irregular shapes.Computer Aided Design,2008,40:625-633.
[141]何援军.计算机图形学算法与实践.长沙:湖南科技出版社，1992.
[142]朱雅音,王化文,万丰,于雷.确定两个任意简单多边形交、并、差的算法.计算机研究与发展.2003,40:576-583.
[143]刘胡瑶.基于临界多边形的二维排样算法研究.上海交通大学博士论文，2007,44-65.
[144] Feito F.R., Torres J.C., Urena A. Orientation, simplicity, and inclusion test forplanar polygons. Computers&Graphics,1995,19:595-600.
[145] Bennell J.A., Dowsland K.A., Dowsland W.B. The irregular cutting-stock problem-a new procedure for deriving the no-fit polygon. Computers and OperationsResearch,2001,28:271-287.
[146] Milenkovic V., Daniels K., Li Z. Placement and compaction of non-convexpolygons for clothing manufacture. In: Proceedings of the4th CanadianConference on Computational Geometry, St. John's, Newfoundland,1993:236-243.
[147] Ghosh P. K. A unified computational framework for Minkowski operations.Computers and Graphics,1993,17:357-378.
[148] Glover F. Heuristics for integer programming using surrogate constraints. DecisionScience,1977,8:156-166.
[149] Reeves C. Genetic algorithms and neighborhood search. In Gogarty,1993,128:115-130.
[150]吕玉龙，沈青松，石铁流，王翼飞.基于禁忌搜索和遗传算法的智能化双聚类方法.应用科学学报,2009,27:282-287.
[151]贺一.禁忌搜索及其并行化研究.西南大学博士论文,2006,41-44.
[152]张超勇.基于自然启发式算法的作业车间调度问题理论与应用研究.华中科技大学博士论文,2006,65-69.
[153]段敬民,常跃军,李赞祥,崔建明.基于退火算法的物流配送网的求优研究.中国工程科学,2012,7:109-112.
[154] David F R.,石教英译．计算机图形学的算法基础．北京:机械工业出版社,2002:131-147.
[155]王树禾.图论及其算法．合肥:中国科学技术大学出版社,1990:9-19.
[156]舒贤林,徐志才.图论基础及其应用.北京:北京邮电学院出版社,1988:12-22.
[157]戴一奇,胡冠章.图论与代数结构.北京:清华大学出版社,1995,6:32-56.
[158] Dorigo M. Caro G.D., Gambardella L.M. Ant algorithms for discrete optimization.Artificial Life,1999,5:137-172.
[159]楚瑞.基于蚁群算法的无人机航路规划.西北工业大学硕士论文,2006,24-25.
[160]汪定伟,王俊伟,王洪峰,张瑞友,郭哲.智能优化方法.北京:高等教育出版社,2007,171-173.
[161]蔡力钢,饶运清,郭军,吕文林.面向集中下料的钣金排样编程系统.华中理工大学学报,1999,27:66-68.
[162]罗阳.机械制造车间生产作业多智能体规划原理与板材套料优化方法的研究.四川大学博士论文,2001,72-74.
[163]饶运清,高伟增,李培根.面向CIMS的板类零件下料工艺系统.制造业自动化,2002,24:5-8.
[164]饶运清,郭军,宋志刚,蔡力钢.集成钣金优化排料系统.制造技术与机床,1999,4:35-37.
[165]蔡力钢,饶运清,郭军,宋志刚.板类零件数控加工CAD/CAPP/CAM系统.机械设计与制造,1999,6:11-13.