装填布局与斩断切割布局理论及方法的研究
|
摘要
本文较为系统地研究了二维装填布局和切割布局、三维装填布局的一些理论与方法。论文取得了如下创新成果:
在二维装填布局方面,提出了基于6块结构的长方形装填布局启发性算法,采用了Herz标准装填(切割)点,具有隐含枚举机制。提出了利用较习惯装填方法提高效率及理论上界(连续上界)评价方法,本文提出了较为严格的连续上界。通过计算,绝大部分优化结果接近理论上届。提出了圆的蛇形布局结构(snake array)启发性算法,提出了稳定性判据,推导的三圆关系公式是余量调整及判定稳定性依据公式。
在二维斩断切割布局方面,提出了基于4块结构的斩断切割启发性算法,并提供了切割次数及利用率上界公式。提出了基于条块结构二维斩断切割布局方案和启发性规则,建立了数学模型,此种方法兼容了条状切割布局方法,又保持3级切割的简单性,同时增加了寻优的选择性。通过计算表明上述两种方法的有效性。
对于Up Side Up箱型的定向装填布局(2+1维布局),提出了基于集装箱及基于子集装箱按比例装填布局启发性算法,并进行了计算。考虑远洋运输及全球气候变化,进行了纸箱堆码强度实验,重点考虑温度、湿度、尺寸对堆码强度的影响规律。将堆码强度作为约束引入到Up Side Up箱型的装填布局,提出了Up Side Up纸箱装填布局承载能力准则。
对于任意摆放箱型三维装填布局静态方法,提出了一种平面优化附加垂直方向摆层优化的方法—“平垂法”,具有装填结构简单的特点。提出了多种任意摆放箱型按比例装填的平垂法。提出的改进习惯装填方法采纳了习惯装填方法中实体部分又充分考虑了边缘剩余空间的利用。
对于任意摆放箱型三维装填布局动态方法,提出了基于Best-First规则和树搜索的全位法一步法及两步法。提出一种动态和静态混合方法---全位法与平垂法的混合法。混合法是集平垂法和全位法优点于一身的更好优化方法。总体上看,优化装填方法相对于习惯装填方法平均提高装填能力为11.36%。
本文得到了天津市自然科学基金及天津市高校发展基金“平面几何图形智能布局”项目、天津市教委“低温物流中关键技术及管理研究(子项目:低温物流中产品防护特性与装填布局研究)”重大专项的支持。
We systematically discuss some theory and methodology for the two-dimensional and three-dimensional packing problem, as well as two-dimensional guillotine cutting stock problem. We make following contributions in this dissertation
For the two-dimensional rectangular packing problem, a heuristic with 6 block pattern and the implicit enumeration mechanism is presented, where Herz normal points are adopted. Evaluation of the effectiveness is made, compared with continuous upper bound and results of experiential packing methods. Computational results approximately equal to the upper bound. For the two-dimensional circular packing problem, a heuristic with snake array pattern is proposed, the model for the relations of three circles is established and stability principle is put forward.
Guillotine cutting stock problems are considered. An algorithm based on 4 block structure is provided, including cutting times and upper bounds of area utilization ratio. New heuristic rules and models for the guillotine cutting stock problem with strip-block patterns are established, where the approach keeps 3 staged cutting and also covers strip cutting properties. The calculation results show the effectiveness of the above two heuristics, compared with those of benchmark instances.
For the fixed orientation packing problems of Up Side Up cardboard boxes, the algorithms with the constraints of proportional packing for the container and sub-container loading are discussed, and calculation are carried out. The effects of temperature, humidity, and cardboard box dimensions on the bearing strength of the box are systematically considered and a large quantity of experiment are made, as to find some regularity. Bearing strength constraint is included in Up Side Up cardboard boxes packing, and bearing strength safety rule is provided.
Two heuristics for the rotated box packing with static procedure are proposed. One is the approach combining the two-dimensional packing with optimal perpendicular layer loading in any of three directions, denoted by FP, which has simple packing structure property and is applied to proportional packing. The other is an improved method of experiential packing, where trade-off between space utilization of solid part and side space of the container is made as to raise the whole utilization ratio.
Based on Best-First rule and tree search, two heuristics for the rotated box packing with dynamic procedure are discussed. In the first heuristic, denoted by LIA, the layer with best utilization ratio is first considered to pack. In the second, denoted by 2LIA, two layers with best combined utilization ratio in two generations of the tree search are first packed. Finally, a mixed approach combining LIA and FP is put forward, which contains advantages both LIA and FP. Evaluation is made for the rotated box packing heuristics and utilization ratio is averagely raised 11.36%, compared with those of experiential packing methods.
This dissertation is complished under the several projects supported by Municipal Committee of Science and Technology, and Municipal Committee of Education.
在二维装填布局方面,提出了基于6块结构的长方形装填布局启发性算法,采用了Herz标准装填(切割)点,具有隐含枚举机制。提出了利用较习惯装填方法提高效率及理论上界(连续上界)评价方法,本文提出了较为严格的连续上界。通过计算,绝大部分优化结果接近理论上届。提出了圆的蛇形布局结构(snake array)启发性算法,提出了稳定性判据,推导的三圆关系公式是余量调整及判定稳定性依据公式。
在二维斩断切割布局方面,提出了基于4块结构的斩断切割启发性算法,并提供了切割次数及利用率上界公式。提出了基于条块结构二维斩断切割布局方案和启发性规则,建立了数学模型,此种方法兼容了条状切割布局方法,又保持3级切割的简单性,同时增加了寻优的选择性。通过计算表明上述两种方法的有效性。
对于Up Side Up箱型的定向装填布局(2+1维布局),提出了基于集装箱及基于子集装箱按比例装填布局启发性算法,并进行了计算。考虑远洋运输及全球气候变化,进行了纸箱堆码强度实验,重点考虑温度、湿度、尺寸对堆码强度的影响规律。将堆码强度作为约束引入到Up Side Up箱型的装填布局,提出了Up Side Up纸箱装填布局承载能力准则。
对于任意摆放箱型三维装填布局静态方法,提出了一种平面优化附加垂直方向摆层优化的方法—“平垂法”,具有装填结构简单的特点。提出了多种任意摆放箱型按比例装填的平垂法。提出的改进习惯装填方法采纳了习惯装填方法中实体部分又充分考虑了边缘剩余空间的利用。
对于任意摆放箱型三维装填布局动态方法,提出了基于Best-First规则和树搜索的全位法一步法及两步法。提出一种动态和静态混合方法---全位法与平垂法的混合法。混合法是集平垂法和全位法优点于一身的更好优化方法。总体上看,优化装填方法相对于习惯装填方法平均提高装填能力为11.36%。
本文得到了天津市自然科学基金及天津市高校发展基金“平面几何图形智能布局”项目、天津市教委“低温物流中关键技术及管理研究(子项目:低温物流中产品防护特性与装填布局研究)”重大专项的支持。
We systematically discuss some theory and methodology for the two-dimensional and three-dimensional packing problem, as well as two-dimensional guillotine cutting stock problem. We make following contributions in this dissertation
For the two-dimensional rectangular packing problem, a heuristic with 6 block pattern and the implicit enumeration mechanism is presented, where Herz normal points are adopted. Evaluation of the effectiveness is made, compared with continuous upper bound and results of experiential packing methods. Computational results approximately equal to the upper bound. For the two-dimensional circular packing problem, a heuristic with snake array pattern is proposed, the model for the relations of three circles is established and stability principle is put forward.
Guillotine cutting stock problems are considered. An algorithm based on 4 block structure is provided, including cutting times and upper bounds of area utilization ratio. New heuristic rules and models for the guillotine cutting stock problem with strip-block patterns are established, where the approach keeps 3 staged cutting and also covers strip cutting properties. The calculation results show the effectiveness of the above two heuristics, compared with those of benchmark instances.
For the fixed orientation packing problems of Up Side Up cardboard boxes, the algorithms with the constraints of proportional packing for the container and sub-container loading are discussed, and calculation are carried out. The effects of temperature, humidity, and cardboard box dimensions on the bearing strength of the box are systematically considered and a large quantity of experiment are made, as to find some regularity. Bearing strength constraint is included in Up Side Up cardboard boxes packing, and bearing strength safety rule is provided.
Two heuristics for the rotated box packing with static procedure are proposed. One is the approach combining the two-dimensional packing with optimal perpendicular layer loading in any of three directions, denoted by FP, which has simple packing structure property and is applied to proportional packing. The other is an improved method of experiential packing, where trade-off between space utilization of solid part and side space of the container is made as to raise the whole utilization ratio.
Based on Best-First rule and tree search, two heuristics for the rotated box packing with dynamic procedure are discussed. In the first heuristic, denoted by LIA, the layer with best utilization ratio is first considered to pack. In the second, denoted by 2LIA, two layers with best combined utilization ratio in two generations of the tree search are first packed. Finally, a mixed approach combining LIA and FP is put forward, which contains advantages both LIA and FP. Evaluation is made for the rotated box packing heuristics and utilization ratio is averagely raised 11.36%, compared with those of experiential packing methods.
This dissertation is complished under the several projects supported by Municipal Committee of Science and Technology, and Municipal Committee of Education.
引文
1 Gilmore P C, Gomory R E. A linear programming approach to the cutting-stock problem, Operations Research ,1961, 9: 849–859
2 Gilmore P C, Gomory R E. A linear programming approach to the cutting-stock problem-Part II, Operations Research ,1963, 11: 864–888
3 Gilmore P C, Gomory R E. Multistage cutting stock problems of two and more dimensions, Operations Research 1965, 13: 94–120
4 Dyckhoff H. A typology of cutting and packing problems, European Journal of Operational Research, 1990, 44: 145-159
5 Gerhard W?scher, Heike Hau?ner and Holger Schumann. An improved typology of cutting and packing problems, European Journal of Operational Research , 2007, 183(7):1109-1130
6 Andrea Lodi, Silvano Martello, Michele Monaci. Two-dimensional packing problem: A survey, European Journal of Operational Research, 2002,141(2): 241-252
7 Andrea Lodi, etc. Recent advances on two-dimensional bin packing, Discrete Applied Mathematics ,2002,123:379-396
8 Marc Peeters and Zeger Degraeve. Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem, European Journal of Operational Research, 2006,170: 416-439
9 Horacio Hideki Yanasse and Maria José Pinto Lamosa. An integrated cutting stock and sequencing problem , European Journal of Operational Research, Available online 2006
10 Cláudio Alves and J M Valério de Carvalho. Accelerating column generation for variable sized bin-packing problems, European Journal of Operational Research , 2007, 183(3):1353-1370
11 Cláudio Alves and Valério de Carvalho J M. A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem, Computers & Operations Research , Available online 2006
12 Xavier E C, Miyazawa F K. A one-dimensional bin packing problem with shelf divisions, Electronic Notes in Discrete Mathematics, 2005, 19: 329-335
13 Miro Gradisar, Peter Trkman. A combined approach to the solution to the general one-dimensional cutting stock problem, Computers & Operations Research, 2005, 32: 1793-1807
14 Alberto Caprara, Ulrich Pferschy. Modified subset sum heuristics for bin packing, Information Processing Letters, 2005, 96:18-23
15 Peter Trkman and Miro Gradisar. One-dimensional cutting stock optimization in consecutive time periods, European Journal of Operational Research, 2007, 179:291-301
16 Isabel Correia, Luís Gouveia and Francisco Saldanha-da-Gama. Solving the variable size bin packing problem with discretized formulations , Computer & Operations Research , Available online 2006
17 Steven S. Seiden, Rob van Stee, Leah Epstein. New bounds for variable-sized online bin packing, Siam Journal on Computing, 2003, 32(2):455-469
18 Shunji Umetani, etc. One-dimensional cutting stock problem to minimize the number of different patterns, European Journal of Operational Research, 2003,146: 388-402
19 . Belov G and Scheithauer G.. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths, European Journal of Operational Research,2002, 141(2): 274-294
20 Oliver Holthaus. Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths, European Journal of Operational Research,2002, 141(2): 295-312
21 Hildegard Foerster, Gerhard Wascher. Pattern reduction in one-dimensional cutting stock problems, International Journal of Production Research, 2000, 38(7):1657 – 1676
22 Pamela H Vance. Branch-and price algorithms for the one-dimensional cutting stock problem, Computational Optimization and Applications, 1998, 9: 211-228
23 Wenqi Huang, Duanbing Chen and Ruchu Xu. A new heuristic algorithm for rectangle packing, Computers & Operations Research, 2007, 34(11): 3270-3280
24 Jakob Puchinger and Günther R Raidl. Models and algorithms for three-stage two-dimensional bin packing, European Journal of Operational Research, 2007, 183(3):1304-1327
25 Belov G. and Scheithauer G.. A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting, European Journal of Operational Research , 2006, 171: 85-106
26 Suliman S M A. A sequential heuristic procedure for the two-dimensional cutting-stock problem, International Journal of Production Economics, 2006, 99: 177-185
27 Horacio Hideki Yanasse and Daniel Massaru Katsurayama. An enumeration scheme to generate constrained exact checkerboard patterns, Computer & Operations Research, Available online 2006
28 Jacques Carlier, Fran?ois Clautiaux and Aziz Moukrim. New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation,Computer & Operations Research , 2007, 34:223-2250
29 Francois Clautiaux, Jacques Carlier and Aziz Moukrim. A new exact method for the two-dimensional bin-packing problem with fixed orientation, Operations Research Letters, 2007, 35(3):357-364
30 Yaodong Cui, Dongli He and Xiaoxia Song. Generating optimal two-section cutting patterns for rectangular blanks, Computer & Operations Research , 2006, 33: 1505-1520
31 Yaodong Cui. Heuristic and exact algorithms for generating homogenous constrained three-staged cutting patterns, Computers & Operations Research, 2008, 35(1):212-225
32 Yaodong Cui, Yuli Yang, Xian Cheng and Peihua Song. A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem, Computer & Operations Research, Available online 2006
33 Yaodong Cui. An exact algorithm for generating homogenous T-shape cutting patterns , Computer & Operations Research, 2007, 34: 1107-1120
34 Yaodong Cui. Simple block patterns for the two-dimensional cutting problem, Mathematical and Computer Modelling, 2007, 45:943-953
35 Yaodong Cui. Simplest optimal cutting patterns for equal rectangles, Operations Research Letter, 2006, 34: 630-638
36 Yaodong Cui and Xianquan Zhang. Two-stage general block patterns for the two-dimensional cutting problem, Computer & Operations Research, 2007, 34(10):2882-2893
37 Mhand Hifi and Rym M’Hallah. Strip generation algorithms for constrained two-dimensional two-staged cutting problems, European Journal of Operational Research, 2006, 172 :515-527
38 Franca Rinaldi and Annamaria Franz. A two-dimensional strip cutting problem with sequencing constraint, European Journal of Operational Research , 2007, 183(3):1371-1384
39 Song X, Chu C B, Nie Y Y and Bennell J A. An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem, European Journal of Operational Research , 2006, 175: 1870-1889
40 Chauhan S S, Alain Martel and Sophie D’Amour. Roll assortment optimization in a paper mill: An integer programming approach, Computer & Operations Research, 2008, 35(2):614-627
41 Defu Zhang, Yan Kang and Ansheng Deng. A new heuristic recursive algorithm for the strip rectangular packing problem, Computers & Operations Research, 2006, 33: 2209-2217
42 Alvarez-Valdes R, Parre?o F and Tamarit J M. Reactive GRASP for the strip-packing problem, Computer & Operations Research, Available online 2006
43 Alvarez-Valdes R, Parre?o F and Tamarit J M. A tabu search algorithm for a two-dimensional non-guillotine cutting problem, European Journal of Operational Research, 2007, 183(3):1167-1182
44 Xiaodong Gu, etc. Average-case performance analysis of a 2D strip packing algorithm-NFDH, Journal of Combinatorial Optimization, 2005, 9: 19-34
45 David Pisinger, Mikkel Sigurd. The two-dimensional bin packing problem with variable bin size and costs, Discrete Optimization, 2005, 2 :154-167
46 黄红选,韩继业,数学规划,北京:清华大学出版社,2006
47 Guochuan Zhang. A 3-approximation algorithm for two-dimensional bin packing, Operations Research Letters, 2005, 33 : 121-126
48 Li V C and Curry G L. Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search , Computer & Operations Research, 2005, 32: 825-848
49 Andrea Lodi, etc. Models and bounds for two-dimensional level packing problem, Journal of Combinatorial Optimization , 2004, 8: 363-379,
50 Mhand Hifi. Dynamic programming and hill-climbing techniques for constrained two-dimensional cutting stock problems, Journal of Combinatorial Optimization, 2004, 8: 65-84
51 Martello S, Vigo D. Exact solution of the two dimensional finite bin packing problem, Management Science , 1998, 44: 388–399
52 Fekete S P, Schepers J. New classes of lower bounds for bin-packing problem, IPCO 98, Springer Lecture Notes in Computer Science , 1998, 1412:257–270
53 Fekete S P, Schepers J. On more-dimensional packing II: bounds,Tech Report 97.289, Universitat zu Koln, Germany, 2000a
54 Marco A Boschetti, Aristide Mingozzi. The two-dimensional finite bin packing problem. part Ⅰ: new lower bounds for the oriented case, 4OR , 2003, 1:27-42
55 Marco A Boschetti, Aristide Mingozzi. The two-dimensional finite bin packing problem. part Ⅱ: new lower and upper bounds, 4OR , 2003, 1: 135-147
56 Jacques Carlier, Fran?ois Clautiaux and Aziz Moukrim. New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation, Computer & Operations Research, 2007, 34 : 223-2250
57 Andrea Lodi, Michele Monaci. Integer linear programming models for 2-staged two-dimensional knapsack problem, Math. Program., 2003, Ser B 94: 257-278
58 Satoshi Fujita, Takeshi Hada. Two-dimensional on-line bin packing problem, theoretical computer science , 2002, 289: 939-952
59 Mhand Hifi. Approximate and exact algorithms for constrained (un)weighted two-dimensional two-staged cutting stock problems, Journal of Combinatorial Optimization, 2001, 5: 465-494
60 Mhand Hifi. exact algorithms for large-scale unconstrained two and three staged cutting problems, Computational Optimization and Applications, 2001, 8: 63-88
61 Van-Dat Cung, Mhand Hifi and Bertrand Le Cun. Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm, International transactions in operational research,2000, 7(3):185-210
62 Dequan Liu, Hongfei Teng. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles, European Journal of Operational Research, 1999, 112: 413-420
63 Guntram Scheithauer, Uta Sommerwei?. 4-Block heuristic for the rectangle packing problem, European Journal of Operational Research, 1998, 108: 509-526
64 Mhand Hifi. The DH/KD algorithm: a hybrid approach for unconstrained two-dimensional cutting problems, European Journal of Operational Research ,1997, 97: 41-52
65 Mhand Hifi. An improvement of viswanathan and bagchi's exact algorithm for constrained two-dimensional cutting stock, Computer & Operations Research, 1997, 24:727-731
66 Reinaldo Morabito, Marcos N Arenales. Staged and constrained two-dimensional guillotine cutting problems: An AND/OR-graph approach, European Journal of Operational Research , 1996, 94(3): 548-560
67 Eleni Hadjiconstantinou, Nocos Christofides. An exact algorithm for general, orthogonal, two-dimensional knapsack problems, European Journal of Operational Research, 1995, 83: 39-56
68 Wang P Y. Two algorithms for constrained two-dimensional cutting stock problems, Operations Research, 1983,31: 573–586.
69 Viswanathan K V and Bagchi A. Best-first search methods for constrained two-dimensional cutting stock problem, Operations Research, 1993, 41: 768-776.
70 Herz J C. Recursive computational procedure for two-dimensional stock cutting, IBM Journal of Research and Development, 1972, 16: 462–469
71 Christofides N and Whitlock C. An algorithm for two-dimensional cutting problems, Operations Research, 1977, 25: 30-44
72 Beasley J E. Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the Operational Research Society , 1985, 36: 297-306
73 Burke E K, Hellier R S R, Kendall G. and Whitwell G.. Complete and robust no-fit polygon generation for the irregular stock cutting problem , European Journal of Operational Research, 2007, 179: 27-49
74 Jens Egeblad, Benny K Nielsen and Allan Odgaard. Fast neighborhood search for two- and three-dimensional nesting problems, European Journal of Operational Research, 2007, 183(3):1249-1266
75 Birgin E G., Martínez J M, Nishihara F H and Ronconi D P. Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization, Computer & Operations Research, 2006, 33: 3535-3548
76 Hifi M and M’Hallah R. A dynamic adaptive local search algorithm for the circular packing problem, European Journal of Operational Research, 2007, 183(3):1280-1294
77 Wen Qi Huang, Yu Li, Chu Min Li and Ru Chu Xu. New heuristics for packing unequal circles into a circular container, Computer & Operations Research, 2006, 33(8):2125-2142
78 Wenqi Huang and Mao Chen. Note on: An improved algorithm for the packing of unequal circles within a larger containing circle, Computers & Industrial Engineering, 2006, 50: 338-344
79 Zhipeng Lü and Wenqi Huang. PERM for solving circle packing problem, Computer & Operations Research, Available online 2006
80 Markot M C, etc. A Reliable Area Reduction Technique for solving circle packing problem, Computing, 2006, 77: 147-162
81 Claudio Arbib and Fabrizio Marinelli. An optimization model for trim loss minimization in an automotive glass plant, European Journal of Operational Research , 2007, 183(3):1421-1432
82 Yaodong Cui. Generating optimal T-shape cutting patterns for the circular blanks, Computers & Operations Research, 2005, 32: 143-152
83 Yaodong Cui. A cutting stock problem and its solution in the manufacturing industry of large electric generators, Computers & Operations Research, 2005, 32: 1709-1721
84 Nanad Mladenovi?, etc. Reformulation descent applied to circle packing problems, Computer & Operations Research, 2005, 32: 2419-2434
85 Birgin E G.. Optimizing the packing of cylinders into a rectangular container: a nonlinear approach, European Journal of Operational Research, 2005, 160: 19-23
86 Andreas Bortfeldt and Daniel Mack. A heuristic for the three-dimensional strip packing problem, European Journal of Operational Research, 2007, 183(3):1267-1279
87 Jens Egeblad, Benny K Nielsen and Allan Odgaard. Fast neighborhood search for two- and three-dimensional nesting problems, European Journal of Operational Research, 2007, 183(3):1249-1266
88 Bischoff E E. Three-dimensional packing of items with limited load bearing strength, European Journal of Operational Research, 2006, 168: 952-966
89 Lim A, etc. 3-D container packing heuristics, Applied Intelligence, 2005, 22: 125-134
90 Leo Ho Wai Yeung, etc. A hybrid genetic approach for container loading in logistics industry, IEEE Transactions on Industrial Electronics, 2005, 52(2):617-627
91 Alvarez-Valdes R, etc. A branch-and-cut algorithm for the pallet loading problem, Computer & Operations Research , 2005, 32: 3007-3029
92 Glaydston Mattos Ribeiro and Luiz Antonio Nogueira Lorena. Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem, Computer & Operations Research , 2006, 34: 2695-2708
93 Marco A. Boschetti. New lower bounds for the three-dimensional finite bin packing problem, Discrete Applied Mathematics, 2004, 140:241-258
94 Andrea Lodi, Silvano Martello. Heuristic algorithms for the three-dimensional bin packing problem, European Journal of Operational Research,2002,141(2): 410-420
95 Michael Eley. Solving container loading problems by block arrangement, European Journal of Operational Research, 2002, 141(2):393-409
96 David Pisinger. Heuristics for the container loading problem, European Journal of Operational Research, 2002, 141(2): 382-392
97 Paul Davies A, Bischoff E E. Weight distribution considerations in container loading, European Journal of Operational Research, 1999, 114: 509-527
98 Liu F H F and Hsiao C-J, Three-dimensional pallet loading method for the single-size boxes, Journal of the Operational Research Society, 1997, 48: 726-735
99 Chien-Tung Yang, Tso-Chung Sung and Wei-Chu Weng. An improved tabu search approach with mixed objective function for one-dimensional cutting stock problems, Advances in Engineering Software, 2006, 37: 502-513
100 Eleni Hadjiconstantinou and Manuel Iori. A hybrid genetic algorithm for the two-dimensional single large object placement problem, European Journal of Operational Research, 2007, 183(3):1150-1166
101 José Fernando Gon?alves. A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem, European Journal of Operational Research, 2007, 183(3):1212-1229
102 Chang-Chun Lin. A genetic algorithm for solving the two-dimensional assortment problem, Computers & Industrial Engineering , 2006, 50: 175-184
103 Kevin J Binkley and Masafumi Hagiwara. Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners’ heuristic, European Journal of Operational Research, 2007, 183(3):12301-1248
104 Andreas Bortfeldt. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces, European Journal of Operational Research, 2006, 172: 814-837
105 Andreas Bortfeldt, Hermann Gehring. A hybrid genetic algorithm for the container loading problem, European Journal of Operation Research, 2001, 131: 143-161
106 Alev Soke and Zafer Bingul, Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems, Engineering Applications of Artificial Intelligence, 2006, 19: 557-567
107 Liu D S, Tan K C, Goh C K, Ho W K. On solving multiobjective bin packing problems using particle swarm optimization, 2006 IEEE Congress on Evolutionary Computation
108 De-fu Zhang, An-Sheng Deng. An effective hybrid algorithm for the problem of packing circles into a large containing circle, Computer & Operations Research, 2005, 32: 1941-1951
109 Alan Crispin, etc. Genetic algorithm coding methods for leather nesting, Applied Intelligence, 2005, 23: 9-21
110 James E Lewis, etc. A Distributed Chromosome Genetic Algorithm for Bin-Packing, Robotics and Computer-Integrated Manufacturing, 2005, 21: 486-495
111 陆一平,查建中,李建勇,鄂明成,复杂齿轮传动系统中齿轮空间挂接布局设计的聚类分析方法,计算机辅助设计与图形学学报,2001,13(6):505-508
112 陆一平,查建中,李建勇,鄂明成,一种基于邻接极小搜索的布局模式生成方法,北方交通大学学报,2000,24(4):52-56
113 滕弘飞,张宝,刘峻,李广强,孙治国,航天器布局方案设计,大连理工大学学报,2003,43(1):86-92
114 王金敏,王玉新,曾维川,姚遥,喻宏波,基于遗传算法的布局求解法,天津大学学报,2001,34(3):307-311
115 焦李成,刘静,钟伟才,协同进化计算与多智能体系统,北京:科技出版社,2006
116 《运筹学》教材编写,运筹学,北京:清华大学出版社,1990
117 傅家良,运筹学方法与模型,上海:复旦大学出版社,2006
118 Wayne L. Winston, Operations Research—Mathematical Programming, 北京:清华大学出版社,2004
119 刑文训,谢金星,现代优化计算方法,北京:清华大学出版社,2005
120 Bischoff E E, Ratcliff M S W. Issues in the development of approaches to container loading, Omega International Journal of Management Science, 1995, 23(4):377-390
121 中华人民共和国国家技术监督局,GB/4857.2-2005,运输包装件基本试验--第二部分,北京:中国标准出版社,2005
122 中华人民共和国国家技术监督局,GB/4857.3-1992,运输包装件静载荷堆码试验方法,北京:中国标准出版社,1992
123 中华人民共和国国家技术监督局,GB/4857.4-1992,运输包装件压力试验方法,北京:中国标准出版社,1992
124 中华人民共和国国家技术监督局,GB/4857.16-1990,采用压力试验机的堆码试验方法,北京:中国标准出版社,1990
125 傅京孙,蔡自星,徐光,人工智能及其应用,北京:清华大学出版社,1988
2 Gilmore P C, Gomory R E. A linear programming approach to the cutting-stock problem-Part II, Operations Research ,1963, 11: 864–888
3 Gilmore P C, Gomory R E. Multistage cutting stock problems of two and more dimensions, Operations Research 1965, 13: 94–120
4 Dyckhoff H. A typology of cutting and packing problems, European Journal of Operational Research, 1990, 44: 145-159
5 Gerhard W?scher, Heike Hau?ner and Holger Schumann. An improved typology of cutting and packing problems, European Journal of Operational Research , 2007, 183(7):1109-1130
6 Andrea Lodi, Silvano Martello, Michele Monaci. Two-dimensional packing problem: A survey, European Journal of Operational Research, 2002,141(2): 241-252
7 Andrea Lodi, etc. Recent advances on two-dimensional bin packing, Discrete Applied Mathematics ,2002,123:379-396
8 Marc Peeters and Zeger Degraeve. Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem, European Journal of Operational Research, 2006,170: 416-439
9 Horacio Hideki Yanasse and Maria José Pinto Lamosa. An integrated cutting stock and sequencing problem , European Journal of Operational Research, Available online 2006
10 Cláudio Alves and J M Valério de Carvalho. Accelerating column generation for variable sized bin-packing problems, European Journal of Operational Research , 2007, 183(3):1353-1370
11 Cláudio Alves and Valério de Carvalho J M. A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem, Computers & Operations Research , Available online 2006
12 Xavier E C, Miyazawa F K. A one-dimensional bin packing problem with shelf divisions, Electronic Notes in Discrete Mathematics, 2005, 19: 329-335
13 Miro Gradisar, Peter Trkman. A combined approach to the solution to the general one-dimensional cutting stock problem, Computers & Operations Research, 2005, 32: 1793-1807
14 Alberto Caprara, Ulrich Pferschy. Modified subset sum heuristics for bin packing, Information Processing Letters, 2005, 96:18-23
15 Peter Trkman and Miro Gradisar. One-dimensional cutting stock optimization in consecutive time periods, European Journal of Operational Research, 2007, 179:291-301
16 Isabel Correia, Luís Gouveia and Francisco Saldanha-da-Gama. Solving the variable size bin packing problem with discretized formulations , Computer & Operations Research , Available online 2006
17 Steven S. Seiden, Rob van Stee, Leah Epstein. New bounds for variable-sized online bin packing, Siam Journal on Computing, 2003, 32(2):455-469
18 Shunji Umetani, etc. One-dimensional cutting stock problem to minimize the number of different patterns, European Journal of Operational Research, 2003,146: 388-402
19 . Belov G and Scheithauer G.. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths, European Journal of Operational Research,2002, 141(2): 274-294
20 Oliver Holthaus. Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths, European Journal of Operational Research,2002, 141(2): 295-312
21 Hildegard Foerster, Gerhard Wascher. Pattern reduction in one-dimensional cutting stock problems, International Journal of Production Research, 2000, 38(7):1657 – 1676
22 Pamela H Vance. Branch-and price algorithms for the one-dimensional cutting stock problem, Computational Optimization and Applications, 1998, 9: 211-228
23 Wenqi Huang, Duanbing Chen and Ruchu Xu. A new heuristic algorithm for rectangle packing, Computers & Operations Research, 2007, 34(11): 3270-3280
24 Jakob Puchinger and Günther R Raidl. Models and algorithms for three-stage two-dimensional bin packing, European Journal of Operational Research, 2007, 183(3):1304-1327
25 Belov G. and Scheithauer G.. A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting, European Journal of Operational Research , 2006, 171: 85-106
26 Suliman S M A. A sequential heuristic procedure for the two-dimensional cutting-stock problem, International Journal of Production Economics, 2006, 99: 177-185
27 Horacio Hideki Yanasse and Daniel Massaru Katsurayama. An enumeration scheme to generate constrained exact checkerboard patterns, Computer & Operations Research, Available online 2006
28 Jacques Carlier, Fran?ois Clautiaux and Aziz Moukrim. New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation,Computer & Operations Research , 2007, 34:223-2250
29 Francois Clautiaux, Jacques Carlier and Aziz Moukrim. A new exact method for the two-dimensional bin-packing problem with fixed orientation, Operations Research Letters, 2007, 35(3):357-364
30 Yaodong Cui, Dongli He and Xiaoxia Song. Generating optimal two-section cutting patterns for rectangular blanks, Computer & Operations Research , 2006, 33: 1505-1520
31 Yaodong Cui. Heuristic and exact algorithms for generating homogenous constrained three-staged cutting patterns, Computers & Operations Research, 2008, 35(1):212-225
32 Yaodong Cui, Yuli Yang, Xian Cheng and Peihua Song. A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem, Computer & Operations Research, Available online 2006
33 Yaodong Cui. An exact algorithm for generating homogenous T-shape cutting patterns , Computer & Operations Research, 2007, 34: 1107-1120
34 Yaodong Cui. Simple block patterns for the two-dimensional cutting problem, Mathematical and Computer Modelling, 2007, 45:943-953
35 Yaodong Cui. Simplest optimal cutting patterns for equal rectangles, Operations Research Letter, 2006, 34: 630-638
36 Yaodong Cui and Xianquan Zhang. Two-stage general block patterns for the two-dimensional cutting problem, Computer & Operations Research, 2007, 34(10):2882-2893
37 Mhand Hifi and Rym M’Hallah. Strip generation algorithms for constrained two-dimensional two-staged cutting problems, European Journal of Operational Research, 2006, 172 :515-527
38 Franca Rinaldi and Annamaria Franz. A two-dimensional strip cutting problem with sequencing constraint, European Journal of Operational Research , 2007, 183(3):1371-1384
39 Song X, Chu C B, Nie Y Y and Bennell J A. An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem, European Journal of Operational Research , 2006, 175: 1870-1889
40 Chauhan S S, Alain Martel and Sophie D’Amour. Roll assortment optimization in a paper mill: An integer programming approach, Computer & Operations Research, 2008, 35(2):614-627
41 Defu Zhang, Yan Kang and Ansheng Deng. A new heuristic recursive algorithm for the strip rectangular packing problem, Computers & Operations Research, 2006, 33: 2209-2217
42 Alvarez-Valdes R, Parre?o F and Tamarit J M. Reactive GRASP for the strip-packing problem, Computer & Operations Research, Available online 2006
43 Alvarez-Valdes R, Parre?o F and Tamarit J M. A tabu search algorithm for a two-dimensional non-guillotine cutting problem, European Journal of Operational Research, 2007, 183(3):1167-1182
44 Xiaodong Gu, etc. Average-case performance analysis of a 2D strip packing algorithm-NFDH, Journal of Combinatorial Optimization, 2005, 9: 19-34
45 David Pisinger, Mikkel Sigurd. The two-dimensional bin packing problem with variable bin size and costs, Discrete Optimization, 2005, 2 :154-167
46 黄红选,韩继业,数学规划,北京:清华大学出版社,2006
47 Guochuan Zhang. A 3-approximation algorithm for two-dimensional bin packing, Operations Research Letters, 2005, 33 : 121-126
48 Li V C and Curry G L. Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search , Computer & Operations Research, 2005, 32: 825-848
49 Andrea Lodi, etc. Models and bounds for two-dimensional level packing problem, Journal of Combinatorial Optimization , 2004, 8: 363-379,
50 Mhand Hifi. Dynamic programming and hill-climbing techniques for constrained two-dimensional cutting stock problems, Journal of Combinatorial Optimization, 2004, 8: 65-84
51 Martello S, Vigo D. Exact solution of the two dimensional finite bin packing problem, Management Science , 1998, 44: 388–399
52 Fekete S P, Schepers J. New classes of lower bounds for bin-packing problem, IPCO 98, Springer Lecture Notes in Computer Science , 1998, 1412:257–270
53 Fekete S P, Schepers J. On more-dimensional packing II: bounds,Tech Report 97.289, Universitat zu Koln, Germany, 2000a
54 Marco A Boschetti, Aristide Mingozzi. The two-dimensional finite bin packing problem. part Ⅰ: new lower bounds for the oriented case, 4OR , 2003, 1:27-42
55 Marco A Boschetti, Aristide Mingozzi. The two-dimensional finite bin packing problem. part Ⅱ: new lower and upper bounds, 4OR , 2003, 1: 135-147
56 Jacques Carlier, Fran?ois Clautiaux and Aziz Moukrim. New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation, Computer & Operations Research, 2007, 34 : 223-2250
57 Andrea Lodi, Michele Monaci. Integer linear programming models for 2-staged two-dimensional knapsack problem, Math. Program., 2003, Ser B 94: 257-278
58 Satoshi Fujita, Takeshi Hada. Two-dimensional on-line bin packing problem, theoretical computer science , 2002, 289: 939-952
59 Mhand Hifi. Approximate and exact algorithms for constrained (un)weighted two-dimensional two-staged cutting stock problems, Journal of Combinatorial Optimization, 2001, 5: 465-494
60 Mhand Hifi. exact algorithms for large-scale unconstrained two and three staged cutting problems, Computational Optimization and Applications, 2001, 8: 63-88
61 Van-Dat Cung, Mhand Hifi and Bertrand Le Cun. Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm, International transactions in operational research,2000, 7(3):185-210
62 Dequan Liu, Hongfei Teng. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles, European Journal of Operational Research, 1999, 112: 413-420
63 Guntram Scheithauer, Uta Sommerwei?. 4-Block heuristic for the rectangle packing problem, European Journal of Operational Research, 1998, 108: 509-526
64 Mhand Hifi. The DH/KD algorithm: a hybrid approach for unconstrained two-dimensional cutting problems, European Journal of Operational Research ,1997, 97: 41-52
65 Mhand Hifi. An improvement of viswanathan and bagchi's exact algorithm for constrained two-dimensional cutting stock, Computer & Operations Research, 1997, 24:727-731
66 Reinaldo Morabito, Marcos N Arenales. Staged and constrained two-dimensional guillotine cutting problems: An AND/OR-graph approach, European Journal of Operational Research , 1996, 94(3): 548-560
67 Eleni Hadjiconstantinou, Nocos Christofides. An exact algorithm for general, orthogonal, two-dimensional knapsack problems, European Journal of Operational Research, 1995, 83: 39-56
68 Wang P Y. Two algorithms for constrained two-dimensional cutting stock problems, Operations Research, 1983,31: 573–586.
69 Viswanathan K V and Bagchi A. Best-first search methods for constrained two-dimensional cutting stock problem, Operations Research, 1993, 41: 768-776.
70 Herz J C. Recursive computational procedure for two-dimensional stock cutting, IBM Journal of Research and Development, 1972, 16: 462–469
71 Christofides N and Whitlock C. An algorithm for two-dimensional cutting problems, Operations Research, 1977, 25: 30-44
72 Beasley J E. Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the Operational Research Society , 1985, 36: 297-306
73 Burke E K, Hellier R S R, Kendall G. and Whitwell G.. Complete and robust no-fit polygon generation for the irregular stock cutting problem , European Journal of Operational Research, 2007, 179: 27-49
74 Jens Egeblad, Benny K Nielsen and Allan Odgaard. Fast neighborhood search for two- and three-dimensional nesting problems, European Journal of Operational Research, 2007, 183(3):1249-1266
75 Birgin E G., Martínez J M, Nishihara F H and Ronconi D P. Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization, Computer & Operations Research, 2006, 33: 3535-3548
76 Hifi M and M’Hallah R. A dynamic adaptive local search algorithm for the circular packing problem, European Journal of Operational Research, 2007, 183(3):1280-1294
77 Wen Qi Huang, Yu Li, Chu Min Li and Ru Chu Xu. New heuristics for packing unequal circles into a circular container, Computer & Operations Research, 2006, 33(8):2125-2142
78 Wenqi Huang and Mao Chen. Note on: An improved algorithm for the packing of unequal circles within a larger containing circle, Computers & Industrial Engineering, 2006, 50: 338-344
79 Zhipeng Lü and Wenqi Huang. PERM for solving circle packing problem, Computer & Operations Research, Available online 2006
80 Markot M C, etc. A Reliable Area Reduction Technique for solving circle packing problem, Computing, 2006, 77: 147-162
81 Claudio Arbib and Fabrizio Marinelli. An optimization model for trim loss minimization in an automotive glass plant, European Journal of Operational Research , 2007, 183(3):1421-1432
82 Yaodong Cui. Generating optimal T-shape cutting patterns for the circular blanks, Computers & Operations Research, 2005, 32: 143-152
83 Yaodong Cui. A cutting stock problem and its solution in the manufacturing industry of large electric generators, Computers & Operations Research, 2005, 32: 1709-1721
84 Nanad Mladenovi?, etc. Reformulation descent applied to circle packing problems, Computer & Operations Research, 2005, 32: 2419-2434
85 Birgin E G.. Optimizing the packing of cylinders into a rectangular container: a nonlinear approach, European Journal of Operational Research, 2005, 160: 19-23
86 Andreas Bortfeldt and Daniel Mack. A heuristic for the three-dimensional strip packing problem, European Journal of Operational Research, 2007, 183(3):1267-1279
87 Jens Egeblad, Benny K Nielsen and Allan Odgaard. Fast neighborhood search for two- and three-dimensional nesting problems, European Journal of Operational Research, 2007, 183(3):1249-1266
88 Bischoff E E. Three-dimensional packing of items with limited load bearing strength, European Journal of Operational Research, 2006, 168: 952-966
89 Lim A, etc. 3-D container packing heuristics, Applied Intelligence, 2005, 22: 125-134
90 Leo Ho Wai Yeung, etc. A hybrid genetic approach for container loading in logistics industry, IEEE Transactions on Industrial Electronics, 2005, 52(2):617-627
91 Alvarez-Valdes R, etc. A branch-and-cut algorithm for the pallet loading problem, Computer & Operations Research , 2005, 32: 3007-3029
92 Glaydston Mattos Ribeiro and Luiz Antonio Nogueira Lorena. Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem, Computer & Operations Research , 2006, 34: 2695-2708
93 Marco A. Boschetti. New lower bounds for the three-dimensional finite bin packing problem, Discrete Applied Mathematics, 2004, 140:241-258
94 Andrea Lodi, Silvano Martello. Heuristic algorithms for the three-dimensional bin packing problem, European Journal of Operational Research,2002,141(2): 410-420
95 Michael Eley. Solving container loading problems by block arrangement, European Journal of Operational Research, 2002, 141(2):393-409
96 David Pisinger. Heuristics for the container loading problem, European Journal of Operational Research, 2002, 141(2): 382-392
97 Paul Davies A, Bischoff E E. Weight distribution considerations in container loading, European Journal of Operational Research, 1999, 114: 509-527
98 Liu F H F and Hsiao C-J, Three-dimensional pallet loading method for the single-size boxes, Journal of the Operational Research Society, 1997, 48: 726-735
99 Chien-Tung Yang, Tso-Chung Sung and Wei-Chu Weng. An improved tabu search approach with mixed objective function for one-dimensional cutting stock problems, Advances in Engineering Software, 2006, 37: 502-513
100 Eleni Hadjiconstantinou and Manuel Iori. A hybrid genetic algorithm for the two-dimensional single large object placement problem, European Journal of Operational Research, 2007, 183(3):1150-1166
101 José Fernando Gon?alves. A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem, European Journal of Operational Research, 2007, 183(3):1212-1229
102 Chang-Chun Lin. A genetic algorithm for solving the two-dimensional assortment problem, Computers & Industrial Engineering , 2006, 50: 175-184
103 Kevin J Binkley and Masafumi Hagiwara. Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners’ heuristic, European Journal of Operational Research, 2007, 183(3):12301-1248
104 Andreas Bortfeldt. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces, European Journal of Operational Research, 2006, 172: 814-837
105 Andreas Bortfeldt, Hermann Gehring. A hybrid genetic algorithm for the container loading problem, European Journal of Operation Research, 2001, 131: 143-161
106 Alev Soke and Zafer Bingul, Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems, Engineering Applications of Artificial Intelligence, 2006, 19: 557-567
107 Liu D S, Tan K C, Goh C K, Ho W K. On solving multiobjective bin packing problems using particle swarm optimization, 2006 IEEE Congress on Evolutionary Computation
108 De-fu Zhang, An-Sheng Deng. An effective hybrid algorithm for the problem of packing circles into a large containing circle, Computer & Operations Research, 2005, 32: 1941-1951
109 Alan Crispin, etc. Genetic algorithm coding methods for leather nesting, Applied Intelligence, 2005, 23: 9-21
110 James E Lewis, etc. A Distributed Chromosome Genetic Algorithm for Bin-Packing, Robotics and Computer-Integrated Manufacturing, 2005, 21: 486-495
111 陆一平,查建中,李建勇,鄂明成,复杂齿轮传动系统中齿轮空间挂接布局设计的聚类分析方法,计算机辅助设计与图形学学报,2001,13(6):505-508
112 陆一平,查建中,李建勇,鄂明成,一种基于邻接极小搜索的布局模式生成方法,北方交通大学学报,2000,24(4):52-56
113 滕弘飞,张宝,刘峻,李广强,孙治国,航天器布局方案设计,大连理工大学学报,2003,43(1):86-92
114 王金敏,王玉新,曾维川,姚遥,喻宏波,基于遗传算法的布局求解法,天津大学学报,2001,34(3):307-311
115 焦李成,刘静,钟伟才,协同进化计算与多智能体系统,北京:科技出版社,2006
116 《运筹学》教材编写,运筹学,北京:清华大学出版社,1990
117 傅家良,运筹学方法与模型,上海:复旦大学出版社,2006
118 Wayne L. Winston, Operations Research—Mathematical Programming, 北京:清华大学出版社,2004
119 刑文训,谢金星,现代优化计算方法,北京:清华大学出版社,2005
120 Bischoff E E, Ratcliff M S W. Issues in the development of approaches to container loading, Omega International Journal of Management Science, 1995, 23(4):377-390
121 中华人民共和国国家技术监督局,GB/4857.2-2005,运输包装件基本试验--第二部分,北京:中国标准出版社,2005
122 中华人民共和国国家技术监督局,GB/4857.3-1992,运输包装件静载荷堆码试验方法,北京:中国标准出版社,1992
123 中华人民共和国国家技术监督局,GB/4857.4-1992,运输包装件压力试验方法,北京:中国标准出版社,1992
124 中华人民共和国国家技术监督局,GB/4857.16-1990,采用压力试验机的堆码试验方法,北京:中国标准出版社,1990
125 傅京孙,蔡自星,徐光,人工智能及其应用,北京:清华大学出版社,1988