圆形件优化排样问题研究
|
摘要
计算机辅助优化排样是计算机辅助设计与制造(CAD/CAM)技术的重要分支之一,解决的问题就是在给定的原材料上放置所需求的各种毛坯零件,使毛坯的布局最优,目的是在满足毛坯需求的前提下,最大限度地提高原材料的利用率,降低生产成本。
在生产实践中,优化排样问题广泛存在于机械制造业、服装加工业、家具制造业、木材加工业以及皮革制品制造业等行业,大量应用于线材、卷材、板材以及三维物品的分割排样。传统的排样工作都是由人工完成,存在时间耗费大而且下料利用率低等缺点,造成原材料的浪费,加大了企业的生产成本。因此,对排样问题进行研究、设计行之有效的排样算法具有深远的理论和实际意义。
对优化排样问题的研究,国内外的学者都给予了足够的重视,特别是针对矩形毛坯和二维不规则件的排样问题提出了许多算法,如:动态规划算法、多项式时间算法、连分数算法以及分支定界算法等确定性算法,也有禁忌搜索算法、蚁群算法、遗传算法、神经网络算法等概率性算法。然而,针对圆形件优化排样问题的研究却比较少,圆形件优化排样作为二维优化排样的一个分支,在实际生产当中也非常普遍。因此,针对圆形片排样问题开展研究非常必要。
本文研究的是圆形件剪冲排样问题:在指定长度和宽度的板材上,首先在剪切阶段用剪床将板材切割成水平或竖直条带,每根条带中所含圆片的直径相同;然后在冲裁阶段用冲床从条带上冲出圆片。生成的排样方案应在满足所有圆形毛坯需求量的前提下,使得所消耗的板材尽可能地少,以达到提高利用率、节约生产成本的目的。
本文的主要内容包括以下两个方面:
第一,设计实现了圆片无约束排样算法,用于生成排样方式。采用动态规划算法和背包算法相结合的方式,在精确求解的基础上,选取规范尺寸的子集进行计算,确定条带在板材上的最优布局,使得板材所含圆片的总价值最大。
第二,将圆片无约束排样算法和线性规划方法(LP:Linear Programming)相结合来求解大规模的二维圆片剪冲下料问题:已知库存板材尺寸、m种圆片的直径和需求量,对库存板材进行剪冲下料,要求确定排样方案,在满足所有毛坯需求的前提下,使得所消耗板材的总成本最小。本文使用单纯形法来求解线性规划问题,在求解过程中,需要反复迭代调用圆片无约束排样算法,根据毛坯的当前价值,生成一个能使目标改善的排样方式,最终生成最优圆片下料排样方案。
由于使用单纯形法求解线性规划问题的过程中需要反复调用无约束排样算法,因此无约束排样算法的效率对于整个排样方案生成算法的效率至关重要。本文在实现无约束排样算法时,引入了规范尺寸以及合适的规范尺寸子集选取策略对其进行优化,以提高算法的运行效率。
设计开发了圆形件下料排样系统,并采用了文献中报道的例题和生产实例对本文算法的有效性进行检验。对排样方式例题的计算结果表明,本文算法生成的排样方式的利用率比部分三块排样方式以及全部T型排样方式的利用率都有所提高,与精确算法生成的排样方式的利用率相同,计算时间却相对较少;对下料方案例题的计算结果表明,本文算法生成的排样方案的利用率比全部T型排样方案以及直切排样方案的利用率都有所提高;对生产实例的计算结果表明,本文算法的计算时间能满足实际生产应用的要求,生成的排样方案效果明显优于多段排样方案及直切排样方案的效果。因此,本文所提的圆形件下料排样算法在生产实践当中是一种行之有效的算法。
The computer aided optimal layout is an important branch of the computer aided design and manufacturing (CAD/CAM), whose purpose is to find out the optimal arrangement of blanks of different sizes, to maximize the material utilization and reduce its cost as long as the demand of all blanks are satisfied.
In real production, cutting stock problems appear in many industries, such as machine building industry, garment processing industry, furniture manufacturing, wood-processing industry and leather and leather products industry. It’s always been applied in the cutting and packing of wire rod, coiled material, plank stuff and three-dimensional material. Traditional works are completed by men, which leads to the waste of raw material and increased product cost because of long working hours and low material utilization. Accordingly, there is an importantly theoretic and actual purport for the research of cutting stock problems and the design of efficient algorithm.
Academicians in and aboard have worked deeply on the research of cutting problem, especially on the rectangle and two-dimensional irregular packing problems, many advanced algorithms have been put forward, there are some deterministic ones like dynamic programming, polynomial time algorithm, continued fraction algorithm, branch-and-bound algorithm and so on, also some probabilistic algorithms such as tabu search algorithm, ant colony algorithm, genetic algorithms and neural networks algorithm have been used. However, there are a few algorithms for the circle cutting problem, as a branch of two-dimensional packing problem, it is frequently encountered in real production. Therefore, it is extremely necessary to do some research on the circle cutting stock problem.
This paper focuses on the circle cutting problem, which can be described as follows: there are sheets with specified length and width, first the sheet is cut into horizontal or vertical strips by a guillotine shear, and each strip contains blanks with the same diameter; then the blanks demanded are cut from the strips by a stamping press. Provided the optimal design meets the demand of circular blanks, the quantity of raw material and the cost of production can be minimized.
The thesis falls into two parts:
Firstly, the algorithm for the unconstrained circle cutting problem has been designed and realized in order to generate the cutting pattern. Based on the exact algorithm, dynamic programming and knapsack algorithm combined, the subset of normal size is chosen to calculate the result in the unconstrained algorithm, which determines the optimal layout of the strip in the sheet to make the total value of circular blanks reach its maximum.
Secondly, the unconstrained algorithm and the linear programming (LP) are combined to solve the large-scale two-dimensional circle cutting stock problem: the size of sheet, the diameter and demand of m circular blanks are known, the cutting plan must be determined to minimize the cost of sheet on the basis of satisfying the blank’s demand. This paper adopts the simplex algorithm to solve the linear programming. In the procedure for solution, it calls the unconstrained algorithm again and again to generate a new pattern which can make the current solution better according to the current blank values, and establishes the best circle cutting stock plan at last.
Because the unconstrained algorithm is called reiteratively in the linear programming by simplex algorithm, the efficiency of the unconstrained algorithm is extraordinarily important to the algorithm for generating the cutting stock plan. In the process of realizing the unconstrained algorithm, the paper has introduced the concept named normal size and the strategy of choosing its subset to optimize it to enhance its efficiency.
A layout system is developed, and effectiveness of the presented algorithm is checked up by the benchmark in other literatures and production instance, the results of the benchmark for cutting pattern show that the material usage of my pattern is higher than part of those generated by the three-block pattern, and all of those generated by T-shape pattern; it is same as that generated by exact algorithm with less computation time; computing the instances of cutting solution, the results indicate that the material utilization of my solution is more desirable than all those cutting solutions generated by T-shape and uni-segment algorithm; the results of the practical instances demonstrate that the algorithm of this paper can not only fulfill the practical industrial need, but also work obviously better than those multi-segment and uni-segment in terms of generating cutting solution. To draw a conclusion, the algorithm presented in this paper is efficient in the practical manufacture.
在生产实践中,优化排样问题广泛存在于机械制造业、服装加工业、家具制造业、木材加工业以及皮革制品制造业等行业,大量应用于线材、卷材、板材以及三维物品的分割排样。传统的排样工作都是由人工完成,存在时间耗费大而且下料利用率低等缺点,造成原材料的浪费,加大了企业的生产成本。因此,对排样问题进行研究、设计行之有效的排样算法具有深远的理论和实际意义。
对优化排样问题的研究,国内外的学者都给予了足够的重视,特别是针对矩形毛坯和二维不规则件的排样问题提出了许多算法,如:动态规划算法、多项式时间算法、连分数算法以及分支定界算法等确定性算法,也有禁忌搜索算法、蚁群算法、遗传算法、神经网络算法等概率性算法。然而,针对圆形件优化排样问题的研究却比较少,圆形件优化排样作为二维优化排样的一个分支,在实际生产当中也非常普遍。因此,针对圆形片排样问题开展研究非常必要。
本文研究的是圆形件剪冲排样问题:在指定长度和宽度的板材上,首先在剪切阶段用剪床将板材切割成水平或竖直条带,每根条带中所含圆片的直径相同;然后在冲裁阶段用冲床从条带上冲出圆片。生成的排样方案应在满足所有圆形毛坯需求量的前提下,使得所消耗的板材尽可能地少,以达到提高利用率、节约生产成本的目的。
本文的主要内容包括以下两个方面:
第一,设计实现了圆片无约束排样算法,用于生成排样方式。采用动态规划算法和背包算法相结合的方式,在精确求解的基础上,选取规范尺寸的子集进行计算,确定条带在板材上的最优布局,使得板材所含圆片的总价值最大。
第二,将圆片无约束排样算法和线性规划方法(LP:Linear Programming)相结合来求解大规模的二维圆片剪冲下料问题:已知库存板材尺寸、m种圆片的直径和需求量,对库存板材进行剪冲下料,要求确定排样方案,在满足所有毛坯需求的前提下,使得所消耗板材的总成本最小。本文使用单纯形法来求解线性规划问题,在求解过程中,需要反复迭代调用圆片无约束排样算法,根据毛坯的当前价值,生成一个能使目标改善的排样方式,最终生成最优圆片下料排样方案。
由于使用单纯形法求解线性规划问题的过程中需要反复调用无约束排样算法,因此无约束排样算法的效率对于整个排样方案生成算法的效率至关重要。本文在实现无约束排样算法时,引入了规范尺寸以及合适的规范尺寸子集选取策略对其进行优化,以提高算法的运行效率。
设计开发了圆形件下料排样系统,并采用了文献中报道的例题和生产实例对本文算法的有效性进行检验。对排样方式例题的计算结果表明,本文算法生成的排样方式的利用率比部分三块排样方式以及全部T型排样方式的利用率都有所提高,与精确算法生成的排样方式的利用率相同,计算时间却相对较少;对下料方案例题的计算结果表明,本文算法生成的排样方案的利用率比全部T型排样方案以及直切排样方案的利用率都有所提高;对生产实例的计算结果表明,本文算法的计算时间能满足实际生产应用的要求,生成的排样方案效果明显优于多段排样方案及直切排样方案的效果。因此,本文所提的圆形件下料排样算法在生产实践当中是一种行之有效的算法。
The computer aided optimal layout is an important branch of the computer aided design and manufacturing (CAD/CAM), whose purpose is to find out the optimal arrangement of blanks of different sizes, to maximize the material utilization and reduce its cost as long as the demand of all blanks are satisfied.
In real production, cutting stock problems appear in many industries, such as machine building industry, garment processing industry, furniture manufacturing, wood-processing industry and leather and leather products industry. It’s always been applied in the cutting and packing of wire rod, coiled material, plank stuff and three-dimensional material. Traditional works are completed by men, which leads to the waste of raw material and increased product cost because of long working hours and low material utilization. Accordingly, there is an importantly theoretic and actual purport for the research of cutting stock problems and the design of efficient algorithm.
Academicians in and aboard have worked deeply on the research of cutting problem, especially on the rectangle and two-dimensional irregular packing problems, many advanced algorithms have been put forward, there are some deterministic ones like dynamic programming, polynomial time algorithm, continued fraction algorithm, branch-and-bound algorithm and so on, also some probabilistic algorithms such as tabu search algorithm, ant colony algorithm, genetic algorithms and neural networks algorithm have been used. However, there are a few algorithms for the circle cutting problem, as a branch of two-dimensional packing problem, it is frequently encountered in real production. Therefore, it is extremely necessary to do some research on the circle cutting stock problem.
This paper focuses on the circle cutting problem, which can be described as follows: there are sheets with specified length and width, first the sheet is cut into horizontal or vertical strips by a guillotine shear, and each strip contains blanks with the same diameter; then the blanks demanded are cut from the strips by a stamping press. Provided the optimal design meets the demand of circular blanks, the quantity of raw material and the cost of production can be minimized.
The thesis falls into two parts:
Firstly, the algorithm for the unconstrained circle cutting problem has been designed and realized in order to generate the cutting pattern. Based on the exact algorithm, dynamic programming and knapsack algorithm combined, the subset of normal size is chosen to calculate the result in the unconstrained algorithm, which determines the optimal layout of the strip in the sheet to make the total value of circular blanks reach its maximum.
Secondly, the unconstrained algorithm and the linear programming (LP) are combined to solve the large-scale two-dimensional circle cutting stock problem: the size of sheet, the diameter and demand of m circular blanks are known, the cutting plan must be determined to minimize the cost of sheet on the basis of satisfying the blank’s demand. This paper adopts the simplex algorithm to solve the linear programming. In the procedure for solution, it calls the unconstrained algorithm again and again to generate a new pattern which can make the current solution better according to the current blank values, and establishes the best circle cutting stock plan at last.
Because the unconstrained algorithm is called reiteratively in the linear programming by simplex algorithm, the efficiency of the unconstrained algorithm is extraordinarily important to the algorithm for generating the cutting stock plan. In the process of realizing the unconstrained algorithm, the paper has introduced the concept named normal size and the strategy of choosing its subset to optimize it to enhance its efficiency.
A layout system is developed, and effectiveness of the presented algorithm is checked up by the benchmark in other literatures and production instance, the results of the benchmark for cutting pattern show that the material usage of my pattern is higher than part of those generated by the three-block pattern, and all of those generated by T-shape pattern; it is same as that generated by exact algorithm with less computation time; computing the instances of cutting solution, the results indicate that the material utilization of my solution is more desirable than all those cutting solutions generated by T-shape and uni-segment algorithm; the results of the practical instances demonstrate that the algorithm of this paper can not only fulfill the practical industrial need, but also work obviously better than those multi-segment and uni-segment in terms of generating cutting solution. To draw a conclusion, the algorithm presented in this paper is efficient in the practical manufacture.
引文
[1]崔耀东.计算机排样及其应用[M].北京:机械工业出版社,2004.1.
[2]戴瑞,陈炳森.单一形状冲裁件的优化排样算法[J].机械制造,2002, 40 (2): 33-35.
[3]屈晓刚.建立计算机辅助焊接生产管理系统提高钢板下料的材料利用率[J],成组技术与生产现代化,1998 (2): 42-46.
[4] Liu H, Zeng G, Lin Z. A system of optimizing nesting with analogical learning mechanism [J]. Computers & Industrial Engineering, 1997, 32 (4): 713-725.
[5] Lee H F, Sewell E C. The strip-packing problem for a boat manufacturing firm [J]. IIE Transactions, 1999, 31 (7): 639-651.
[6] Kathryn A. Dowsland. Optimising the palletisation of cylinders in cases [J]. OR Spektrum, 1991, 13 (1): 204-212.
[7] Fraser H J, George J A. Integrated container loading software for pulp and paper industry [J]. European Journal of Operational Research, 1994, 17 (3): 466-474.
[8] Graham R L, Lubachevsky B D. Repeated patterns of dense packings of equaldisks in a square [J], The Electronic Journalof Combinatorics. 1996, 3 (Report No. 16).
[9] George J A, George J M, Lamar B W. Packing different-sized circles into a rectangular container [J]. European Journal of Operational Research, 1995, 84 (3): 693-712.
[10] Hifi M, Paschos V T, Zissimopoulos V. A simulated annealing approach for the circular cutting problem [J]. European Journal of Operational Research, 2004, 159 (2): 430-448.
[11]贾志欣,殷国富,罗阳等.矩形件排样的模拟退火算法求解[J].四川大学学报(工程科学版),2001, 33 (5): 35-38.
[12] Hifi M, M’Hallah R. A best-local position procedure-based heuristic for the two-dimensional layout problem [J]. Studia Informatica Universalis International Journal on Informatics (Special Issue on Cutting, Packing and Knapsacking), 2002, 2 (1): 33-56.
[13] Hifi M, M’Hallah R. Approximate algorithms for constrained circular cutting problems [J]. Computers & Operations Research, 2004, 31 (5): 675-694.
[14]宋晓霞,李勇.一种求解圆形下料问题的快速算法[J].微计算机信息(测控自动化),2006, 22 (5-1): 261-263.
[15]宋晓霞,李勇.混合遗传算法在圆形件优化排样中的应用研究[J].微计算机信息,2006, 22 (10-1): 170-172.
[16] Stoyan Y G, Yaskov G N. Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints [J]. International Transactions in Operational Research, 1998, 5 (1): 45-57.
[17]凌少东,曹炬,刘毅.卷料上的圆形件优化排样[J].锻压技术,2005, 30 (5): 30-32.
[18] Cui Y, Chen Y, Wu J. Selecting the best sheet length for the steel stock used in circular blank production [J]. IIE Transactions, 2006, 38 (10): 829-836.
[19]黄文奇,许如初,陈卫东等.解packing及CNF-SAT问题的拟物拟人方法[J].华中理工大学学报,1998, 26 (9): 5-7.
[20]许如初,黄文奇.解不等圆packing问题拟物拟人算法初态选取[J].华中理工大学学报,1998, 26 (4): 1-3.
[21]康雁,黄文奇.基于禁忌搜索的启发式算法求解圆形packing问题[J].计算机研究与发展,2004, 41 (9): 1554-1558.
[22] Locatelli M, Raber U. Packing equal circles in a square: a deterministic global optimization approach [J]. Discrete Applied Mathematics, 2002, 122 (1-3): 139-166.
[23] Hifi M, Paschos V T, Zissimopoulos V. A simulated annealing approach for the circular cutting problem [J]. European Journal of Operational Research, 2004, 159 (2): 430-448.
[24] Akeb H, Hifi M, M’Hallah R. A Beam Search Algorithm for the Circular Packing Problem [J]. Computers & Operations Research, 2009, 36 (5): 1513-1528.
[25] Cui Y. Generating optimal T-shape cutting patterns for circular blanks [J]. Computers & Operations Research, 2005, 32 (1): 143-152.
[26] Cui Y. Generating optimal multi-segment cutting patterns for circular blanks in the manufacturing of electric motors [J]. European Journal of Operational Research, 2006, 169 (1): 30-40.
[27] Cui Y, Wu J, Chen H. Generating multi-section silicon steel sheet cutting patterns in the manufacturing industry of electric generators [J]. International Journal of Advanced Manufacturing Technology, 2007, 34 (4): 1107-1120.
[28]陈菲.基于三块结构的圆形片剪冲排样算法[D].桂林:广西师范大学, 2009.6.
[29]卢开澄.组合数学:算法与分析(上、下册)[M].北京:清华大学出版社, 1983.9.
[30]刘振宏,蔡茂诚.组合最优化:算法和复杂性[M].北京:清华大学出版社. 1988.6.
[31] Dyckhoff H. A typology of cutting and packing problem [J]. European Journal of Operational Research, 1990, 44 (2): 145-159.
[32] Nye T J. Optimal nesting of irregular convex blanks in strips via an exact algorithm [J]. International Journal of Machine Tools & Manufacture, 2001, 41 (7): 991-1002.
[33] Joshi S, Sudit M. Procedures for solving single-pass strip layout problems [J]. IIE Transactions, 1994, 26 (1): 27-37.
[34]王华昌,李志钢.冲裁件优化排样算法的研究[J].中国机械工程,2001, 12 (2): 199-202.
[35] George J A, George J M. Bruce W. Lamar. Packing different-size circles into a rectangular container [J]. European Journal of Operational Research, 1995, 84 (3): 693-712.
[36] Cui Y, Zhou R. Generating Optimal Cutting Patterns for Rectangular Blanks of A Single Size [J].Journal of the Operational Research Society, 2002, 53 (12): 1338-1346.
[37]郭耀煌等编著.运筹学与工程系统分析[M].北京:中国建筑工业出版社,1986.12.
[38] Bellman R. Dynamic Programming [M]. Princeton University Press, 1957.2.
[39]王晓东编著.计算机算法设计与分析(第二版)[M].北京:电子工业出版社,2006.5.
[40]王会颖,贾瑞玉,章义刚等.一种求解0-1背包问题的快速蚁群算法[J].计算机技术与发展,2007, 17 (1): 104-107.
[41]王莉,绍定宏,陆金桂.基于遗传算法的0/1背包问题求解[J].计算机仿真,2006, 23 (3): 154-156.
[42]王苫社,张宏礼.混合背包问题的算法设计与分析[J].长江大学学报(自然科学版),2009, 6 (1): 117-118.
[43]梁开福.背包问题的性质研究[J].数学理论与应用,2000, 20 (2): 23-27.
[44] Gilmore P C, Gomory R E. A Linear Programming Approach to the Cutting Stock Problem [J]. Operations Research, 1961, 9 (6): 849-859.
[45] Gilmore P C, Gomory R E. Multistage Cutting Stock Problems of Two and More Dimensions [J]. Operations Research, 1965, 13 (1): 94-120.
[46] Cui Y. Wang Q. Exact and heuristic algorithms for the circle-cutting problem in the manufacturing industry of electric motors [J]. Journal of Combinatorial Optimization, 2007, 14 (1): 35-44.
[47] CUI Y, Song X. Applying parallelogrammic strips for cutting circles from stainless steel rolls [J]. Journal of Materials Processing Technology, 2008, 205 (1-3): 138-145.
[48]陈菲,刘勇,刘睿等.基于三块结构的圆形片剪冲排样算法[J].计算机工程,2009, 35 (14): 195-197.
[49]崔耀东,黄健民,张显全.矩形毛料无约束两维剪切排样的递归算法[J].计算机辅助设计与图形学学报,2006, 18 (7): 948-951.
[50] Cui Y, Zhang X, Zhang H et al. Dynamic programming algorithms for the cutting problem of equal circles [J]. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2007, 221 (3): 387-395.
[51] Cui Y, Gu T, Hu W. Simplest optimal guillotine cutting patterns for strips of identical circles [J]. Journal of Combinatorial Optimization, 2008, 15 (4): 357-367.
[2]戴瑞,陈炳森.单一形状冲裁件的优化排样算法[J].机械制造,2002, 40 (2): 33-35.
[3]屈晓刚.建立计算机辅助焊接生产管理系统提高钢板下料的材料利用率[J],成组技术与生产现代化,1998 (2): 42-46.
[4] Liu H, Zeng G, Lin Z. A system of optimizing nesting with analogical learning mechanism [J]. Computers & Industrial Engineering, 1997, 32 (4): 713-725.
[5] Lee H F, Sewell E C. The strip-packing problem for a boat manufacturing firm [J]. IIE Transactions, 1999, 31 (7): 639-651.
[6] Kathryn A. Dowsland. Optimising the palletisation of cylinders in cases [J]. OR Spektrum, 1991, 13 (1): 204-212.
[7] Fraser H J, George J A. Integrated container loading software for pulp and paper industry [J]. European Journal of Operational Research, 1994, 17 (3): 466-474.
[8] Graham R L, Lubachevsky B D. Repeated patterns of dense packings of equaldisks in a square [J], The Electronic Journalof Combinatorics. 1996, 3 (Report No. 16).
[9] George J A, George J M, Lamar B W. Packing different-sized circles into a rectangular container [J]. European Journal of Operational Research, 1995, 84 (3): 693-712.
[10] Hifi M, Paschos V T, Zissimopoulos V. A simulated annealing approach for the circular cutting problem [J]. European Journal of Operational Research, 2004, 159 (2): 430-448.
[11]贾志欣,殷国富,罗阳等.矩形件排样的模拟退火算法求解[J].四川大学学报(工程科学版),2001, 33 (5): 35-38.
[12] Hifi M, M’Hallah R. A best-local position procedure-based heuristic for the two-dimensional layout problem [J]. Studia Informatica Universalis International Journal on Informatics (Special Issue on Cutting, Packing and Knapsacking), 2002, 2 (1): 33-56.
[13] Hifi M, M’Hallah R. Approximate algorithms for constrained circular cutting problems [J]. Computers & Operations Research, 2004, 31 (5): 675-694.
[14]宋晓霞,李勇.一种求解圆形下料问题的快速算法[J].微计算机信息(测控自动化),2006, 22 (5-1): 261-263.
[15]宋晓霞,李勇.混合遗传算法在圆形件优化排样中的应用研究[J].微计算机信息,2006, 22 (10-1): 170-172.
[16] Stoyan Y G, Yaskov G N. Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints [J]. International Transactions in Operational Research, 1998, 5 (1): 45-57.
[17]凌少东,曹炬,刘毅.卷料上的圆形件优化排样[J].锻压技术,2005, 30 (5): 30-32.
[18] Cui Y, Chen Y, Wu J. Selecting the best sheet length for the steel stock used in circular blank production [J]. IIE Transactions, 2006, 38 (10): 829-836.
[19]黄文奇,许如初,陈卫东等.解packing及CNF-SAT问题的拟物拟人方法[J].华中理工大学学报,1998, 26 (9): 5-7.
[20]许如初,黄文奇.解不等圆packing问题拟物拟人算法初态选取[J].华中理工大学学报,1998, 26 (4): 1-3.
[21]康雁,黄文奇.基于禁忌搜索的启发式算法求解圆形packing问题[J].计算机研究与发展,2004, 41 (9): 1554-1558.
[22] Locatelli M, Raber U. Packing equal circles in a square: a deterministic global optimization approach [J]. Discrete Applied Mathematics, 2002, 122 (1-3): 139-166.
[23] Hifi M, Paschos V T, Zissimopoulos V. A simulated annealing approach for the circular cutting problem [J]. European Journal of Operational Research, 2004, 159 (2): 430-448.
[24] Akeb H, Hifi M, M’Hallah R. A Beam Search Algorithm for the Circular Packing Problem [J]. Computers & Operations Research, 2009, 36 (5): 1513-1528.
[25] Cui Y. Generating optimal T-shape cutting patterns for circular blanks [J]. Computers & Operations Research, 2005, 32 (1): 143-152.
[26] Cui Y. Generating optimal multi-segment cutting patterns for circular blanks in the manufacturing of electric motors [J]. European Journal of Operational Research, 2006, 169 (1): 30-40.
[27] Cui Y, Wu J, Chen H. Generating multi-section silicon steel sheet cutting patterns in the manufacturing industry of electric generators [J]. International Journal of Advanced Manufacturing Technology, 2007, 34 (4): 1107-1120.
[28]陈菲.基于三块结构的圆形片剪冲排样算法[D].桂林:广西师范大学, 2009.6.
[29]卢开澄.组合数学:算法与分析(上、下册)[M].北京:清华大学出版社, 1983.9.
[30]刘振宏,蔡茂诚.组合最优化:算法和复杂性[M].北京:清华大学出版社. 1988.6.
[31] Dyckhoff H. A typology of cutting and packing problem [J]. European Journal of Operational Research, 1990, 44 (2): 145-159.
[32] Nye T J. Optimal nesting of irregular convex blanks in strips via an exact algorithm [J]. International Journal of Machine Tools & Manufacture, 2001, 41 (7): 991-1002.
[33] Joshi S, Sudit M. Procedures for solving single-pass strip layout problems [J]. IIE Transactions, 1994, 26 (1): 27-37.
[34]王华昌,李志钢.冲裁件优化排样算法的研究[J].中国机械工程,2001, 12 (2): 199-202.
[35] George J A, George J M. Bruce W. Lamar. Packing different-size circles into a rectangular container [J]. European Journal of Operational Research, 1995, 84 (3): 693-712.
[36] Cui Y, Zhou R. Generating Optimal Cutting Patterns for Rectangular Blanks of A Single Size [J].Journal of the Operational Research Society, 2002, 53 (12): 1338-1346.
[37]郭耀煌等编著.运筹学与工程系统分析[M].北京:中国建筑工业出版社,1986.12.
[38] Bellman R. Dynamic Programming [M]. Princeton University Press, 1957.2.
[39]王晓东编著.计算机算法设计与分析(第二版)[M].北京:电子工业出版社,2006.5.
[40]王会颖,贾瑞玉,章义刚等.一种求解0-1背包问题的快速蚁群算法[J].计算机技术与发展,2007, 17 (1): 104-107.
[41]王莉,绍定宏,陆金桂.基于遗传算法的0/1背包问题求解[J].计算机仿真,2006, 23 (3): 154-156.
[42]王苫社,张宏礼.混合背包问题的算法设计与分析[J].长江大学学报(自然科学版),2009, 6 (1): 117-118.
[43]梁开福.背包问题的性质研究[J].数学理论与应用,2000, 20 (2): 23-27.
[44] Gilmore P C, Gomory R E. A Linear Programming Approach to the Cutting Stock Problem [J]. Operations Research, 1961, 9 (6): 849-859.
[45] Gilmore P C, Gomory R E. Multistage Cutting Stock Problems of Two and More Dimensions [J]. Operations Research, 1965, 13 (1): 94-120.
[46] Cui Y. Wang Q. Exact and heuristic algorithms for the circle-cutting problem in the manufacturing industry of electric motors [J]. Journal of Combinatorial Optimization, 2007, 14 (1): 35-44.
[47] CUI Y, Song X. Applying parallelogrammic strips for cutting circles from stainless steel rolls [J]. Journal of Materials Processing Technology, 2008, 205 (1-3): 138-145.
[48]陈菲,刘勇,刘睿等.基于三块结构的圆形片剪冲排样算法[J].计算机工程,2009, 35 (14): 195-197.
[49]崔耀东,黄健民,张显全.矩形毛料无约束两维剪切排样的递归算法[J].计算机辅助设计与图形学学报,2006, 18 (7): 948-951.
[50] Cui Y, Zhang X, Zhang H et al. Dynamic programming algorithms for the cutting problem of equal circles [J]. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2007, 221 (3): 387-395.
[51] Cui Y, Gu T, Hu W. Simplest optimal guillotine cutting patterns for strips of identical circles [J]. Journal of Combinatorial Optimization, 2008, 15 (4): 357-367.