切割与包装优化入门：问题、建模方法与解决方案

5星 · 超过95%的资源需积分: 9 103 浏览量更新于2024-07-18 1 收藏 10.51MB PDF 举报

"Introduction to Cutting and Packing Optimization" 是一本关于运筹学与管理科学领域的电子书，专注于优化算法，特别是切割与包装优化问题的探讨。这本书由Guntram Scheithauer撰写，是国际运营研究与管理科学系列（International Series in Operations Research & Management Science）的一部分。切割与包装优化是运筹学中的一个重要领域，它主要关注如何有效地利用有限的资源，例如在制造业中如何切割原材料以最大化利用率，或者在物流和仓储中如何最优化地包装物品以节省空间。这本书深入介绍了这一主题，涵盖了问题定义、建模方法和解决方案策略。书中可能涉及的知识点包括： 1. **优化问题定义**：解释切割与包装优化问题的基本概念，如二维和三维空间的切割问题，以及如何量化和衡量效率。 2. **模型构建**：介绍如何使用线性规划、整数规划、动态规划等数学工具来建立问题模型，以及这些模型在解决实际问题中的应用。 3. **解决方案方法**：讨论各种求解策略，如精确算法（如分支定界法）、启发式算法（如遗传算法、模拟退火法）和近似算法，以及它们的优缺点和适用场景。 4. **实例分析**：通过实际案例分析，展示如何将理论应用于实践，如在金属板材切割、纺织品布局、集装箱装载等问题中的应用。 5. **计算技术**：可能涵盖现代计算工具和软件，如优化软件包（如GAMS, CPLEX, MATLAB的优化工具箱），以及如何使用这些工具进行模型求解。 6. **性能评估**：讨论如何评估和比较不同解决方案的性能，包括计算时间、解的质量和稳定性等指标。 7. **最新发展与趋势**：可能包含该领域的最新研究成果和技术进步，比如新的算法设计、大数据在优化问题中的应用等。 8. **应用领域扩展**：除了传统的制造和物流行业，还可能探讨其他领域的应用，如印刷、电子制造、建筑设计等。本书对于运筹学、管理科学、工业工程以及相关领域的学生和研究人员来说，是一本宝贵的参考资源，帮助他们理解和解决实际工作中的切割与包装优化问题。通过阅读此书，读者可以系统地学习这一领域的理论知识，并掌握解决此类问题的方法和技术。

xvi Acronyms and Notations

SPP Strip Packing Pro blem

s.t. Subject to

SVC Sequential Value Correction

TS Tabu Search

WF, WFD(H) Worst Fit, Worst Fit Decreasing (Height)

Notations

B Df0; 1g Set of binary numbers

N Df1; 2; 3; : : : g Set of natural numbers

Df0; 1; 2; : : : g Set of nonnegative integers

Z Df0; ˙1; ˙2;:::g Set of in tegers

m-dimensional Euclidean space, m 2 N

Dfx 2 R W x >0g

Dfx 2 R W x  0g

jIjDcard.I/ Cardinality of a ﬁnite set I

bxcDmaxfy 2 Z W y  xg Largest integer not larger than x (rounding down)

dxeDminfy 2 Z W y  xg Smallest integer not smaller than x (rounding up)

conv.S/ Convex hull of set S

cl.S/ Closure o f set S

int.S/ Interior of set S

Identity matrix of dime nsion n  n

D .0;:::;0;1;0:::;0/

i-th unit vector of appropriate dimension

nŠ D 1  2 n Factorial

.x/

D maxf0; xg

_ Logical or

^ Logical and

O.x/ Landau symbol; something is proportional to x

List of Figures

Fig. 1.1 Translation of triangle O by vector u .............................. 2

Fig. 1.2 Rotation and translation of object (triangle) O .................... 3

Fig. 1.3 Representation of a polygon ....................................... 6

Fig. 1.4 Example 1.2 ......................................................... 7

Fig. 2.1 Algorithm of Gilmore and Gomory ................................ 21

Fig. 2.2 Algorithm of Gilmore and Gomory with index information ...... 22

Fig. 2.3 Algorithm of Gilmore and Gomory: identiﬁcation

of a solution.......................................................... 23

Fig. 2.4 Longest Path Method ............................................... 24

Fig. 2.5 Partition into ˛

C 1 subproblems .................................. 26

Fig. 2.6 Branching tree: the entries within the ovals correspond

to k=y. The upper bounds are given with respect to the

initial problem ....................................................... 28

Fig. 2.7 General Branch-and-Bound algorithm ............................. 28

Fig. 2.8 Alternative concept: partition into two subproblems

(Qy D y  ˛

, ˛

kC1

DbQy=a

kC1

c) .................................. 29

Fig. 2.9 Lexicographic Longest Path Method ............................... 31

Fig. 2.10 Modiﬁed Longest Path Method ..................................... 34

Fig. 2.11 The Backward Dynamic Programming (BDP) algorithm ......... 36

Fig. 2.12 The Forward Dynamic Programming (FDP) algorithm ........... 36

Fig. 2.13 Algorithm to compute all solutions................................. 41

Fig. 3.1 Dual feasible functions y D u

.k/

.x/ for k D 1;:::;4 ............. 55

Fig. 3.2 Dual feasible function y D U

."/

.x/ ................................ 55

Fig. 3.3 Dual feasible functions y D 

."/

.x/ ................................ 56

Fig. 4.1 General step of the Revised Simplex Method ..................... 80

Fig. 4.2 Column generation for solving problem (4.8) ..................... 85

Fig. 4.3 Branch-and-bound algorithm for the 1CSP ........................ 91

Fig. 5.1 Horizontal bar relaxation for rectangle packing ................... 130

Fig. 5.2 A 3D container and the 1

bar relaxation (along W

) ............. 135

xvii

xviii List of Figures

Fig. 5.3 The horizontal contiguous bar relaxation does not provide

an OPP solution in general ......................................... 136

Fig. 5.4 An exemplary packing pattern , the complement

intersection graph s and their transitive orientations ............... 139

Fig. 5.5 Example of a feasible graph system where G

is non-interval .... 140

Fig. 5.6 A ‘degenerate’ 2OPP example from [13] .......................... 140

Fig. 5.7 The branching schema: enumerating by edges .................... 141

Fig. 5.8 Monotone packing according to the contour concept ............. 147

Fig. 5.9 Branch-and-bound algorithm for the 2OPP ........................ 148

Fig. 5.10 Horizontal and vertical bar relaxation ............................. 150

Fig. 6.1 Guillotine and non-guillotine cutting .............................. 158

Fig. 6.2 Applying a vertical or hor izontal guillotine cut ................... 159

Fig. 6.3 Optimal patterns for L  W D 160  105 and

L  W D 160  100 ................................................ 161

Fig. 6.4 Exact and non-exact 2-stage guillotine cutting patterns

with horizontal G-cuts in the ﬁrst stage ............................ 164

Fig. 6.5 A 3-stag e guillotine cutting pattern, exact case, vertical

G-cuts in the ﬁrst stage ............................................. 165

Fig. 6.6 A 3-stage guillotine cutting pattern, non-exact case .............. 166

Fig. 6.7 Optimal 3-stage p atterns of Example 6.3 .......................... 169

Fig. 6.8 1-group cutting pattern ............................................. 170

Fig. 6.9 2- and 3-block patterns ............................................. 170

Fig. 6.10 A schema of the Algorithm of Wang .............................. 172

Fig. 6.11 To the one-cut model of 2- and 3-stage guillotine cutting ........ 177

Fig. 6.12 Three-dimensional guillotine patterns ............................. 178

Fig. 7.1 Item 1  2 ﬁts in a pattern for the contiguous problem of

height 4, but not for the SPP ....................................... 194

Fig. 7.2 BL-packing for piece sequences  D .1;2;3;4;5;6;7/

and  D .7;6;5;4;3;2;1/ ......................................... 196

Fig. 7.3 BL

-patterns for sequences  D .1;2;3;4;5;6;7/and

 D .7;6;5;4;3;2;1/ .............................................. 197

Fig. 7.4 Patterns obtained by the NFDH and the FFDH heuristic ......... 198

Fig. 7.5 To the proof of Theorem 7.9 (a), pattern obtained for k D 3 ..... 199

Fig. 7.6 To the proof of Theorem 7.9 (c), pattern obtained for k D 4 ..... 200

Fig. 7.7 To the proof of Theorem 7.11 (b) .................................. 202

Fig. 7.8 NFS and FFS patterns .............................................. 204

Fig. 7.9 Normalized monotone packing pattern used in the contour

approach ............................................................. 212

Fig. 7.10 Branch-and-bound algorithm for the SPP .......................... 212

Fig. 7.11 2-, 3-, and 5-stag e guillotine cutting patterns ...................... 215

Fig. 7.12 Exact 2-stage, non-exact 2-stage, and general 3-stage

G-patterns ........................................................... 219

List of Figures xix

Fig. 7.13 Example with z

bhor

< z

chor

< H



............................... 225

Fig. 9.1 Finger-joining technology .......................................... 246

Fig. 9.2 Optimal value function of Example 9.1 ............................ 249

Fig. 9.3 Bounding function ub

of Example 9.2 ............................ 252

Fig. 9.4 Bounding function ub

of Example 9.2 ............................ 253

Fig. 9.5 Yield function h of Example 9.3 .................................... 254

Fig. 9.6 Possible situations which can occur during the update of h ....... 256

Fig. 9.7 A sketch of a branch-and-bound algorithm ........................ 258

Fig. 9.8 A sketch of an FDP algorithm ...................................... 259

Fig. 9.9 Yield functions h

;:::;h

........................................... 261

Fig. 9.10 Description of defects by rectangles ............................... 265

Fig. 9.11 Exact 3-stage guillotine cutting ..................................... 266

Fig. 9.12 Deﬁnition of set Y

.................................................. 269

Fig. 9.13 Cutting pattern of Example 9 .4 ..................................... 271

Fig. 9.14 A more general pattern of a strip ................................... 272

Fig. 9.15 Cutting pattern of Example 9 .5 ..................................... 273

Fig. 9.16 Optimal value functions of Exercise 9.3 (a)–(c) ................... 274

Fig. 9.17 Optimal value functions of Exercise 9.4 (a)–(c) ................... 275

Fig. 9.18 Bounding functions ub

and ub

of Exercise 9.5 (a)............... 276

Fig. 9.19 Bounding functions ub

and ub

of Exercise 9.5 (b) .............. 277

Fig. 10.1 Optimal pattern of the PLP instances .40; 25; 7; 3/ and

.52; 33; 9; 4/ ......................................................... 281

Fig. 10.2 Optimal 3-block pattern for .13; 11; 3; 2/ and optimal

4-block pattern for .17; 11; 3; 2/ ................................... 285

Fig. 10.3 Optimal 5-block pattern for .44;37;7;5/and optimal

7-block pattern for .37;22;7;3/.................................... 285

Fig. 10.4 Optimal 9-block p attern for .68; 52; 10; 7/ and optimal

diagonal-block pattern for .27; 25; 7; 3/ ............................ 286

Fig. 10.5 Notations used in the G4-recursion................................. 288

Fig. 10.6 Optimal patterns of the instances (57, 44, 12, 5) and (56,

52, 12, 5) ............................................................ 289

Fig. 10.7 The G4 heuristic for the PLP ....................................... 290

Fig. 10.8 Two types of `-strips. (a) vertical `-strip. (b) horizontal

`-strip ................................................................ 292

Fig. 10.9 Principal shape of a block-`-pattern ................................ 292

Fig. 10.10 Partition of L  W in three subregions ............................. 296

Fig. 10.11 Modulo function E.y/ D .5 C 4y/ mod 23 ........................ 297

Fig. 10.12 Optimal patterns of instance (40,25,7,3) for the GPLP ........... 301

Fig. 10.13 4-block-dissections of a pallet ...................................... 302

xx List of Figures

Fig. 10.14 Patterns of Example 10.4 regarding various additional

restrictions. (a) v D 992; 336.(b) v D 990; 198; t D 3.

II and IV. (e) v D 982; 154,

u D .20; 9; 5; 8; 11; 11/

(f) v D 963; 382,

u D .20; 9; 5; 8; 11; 11/

D .0;0;0;0;0;11/

.(g) v D 949; 136,

u D .20; 9; 5; 8; 11; 11/

, u D .0;0;0;8;0;11/

.(h)

v D 990; 198, with sequencing condition .......................... 304

Fig. 10.15 The MPLP algorithm ................................................ 307

Fig. 10.16 Distributing Procedure for the MPLP algorithm ................... 308

Fig. 10.17 Loading Procedure for the MPLP algorithm ....................... 310

Fig. 10.18 Layer-wise packing in Example 10.5............................... 312

Fig. 10.19 Patterns of Example 10.6 ........................................... 313

Fig. 10.20 G4-structure of a 5-block pattern ................................... 314

Fig. 10.21 G4-structure of a 7-block pattern ................................... 314

Fig. 11.1 Six possible orientations of a box .................................. 319

Fig. 11.2 Relation R

................................................... 325

Fig. 11.3 Non-monotone and monotone contour of Example 11.1 ......... 325

Fig. 11.4 Counterexample for an exclusive application of monotone

contours .............................................................. 326

Fig. 11.5 Packing pattern of Example 11.3 .................................. 332

Fig. 12.1 Polygons considered in Example 12.1 ............................. 349

Fig. 12.2 Mutual positions of two polygons ................................. 350

Fig. 12.3 Placements related to Example 12.2 ............................... 351

Fig. 12.4 Hodographs related to Example 12.2 .............................. 351

Fig. 12.5 Packing regions U

, i 2f1; 2; 3g, related to Example 12.3 ....... 353

Fig. 12.6 Some patterns belonging to Example 12.3 ........................ 353

Fig. 12.7 Allocation regions U

/ of Example 12.3 for

D .0; 0/, .0:5; 1/,and.1; 2/ ..................................... 354

Fig. 12.8 Patterns of Example 12.4 with m D 4 ............................. 354

Fig. 12.9 Rotation ranges in Example 12.5 .................................. 360

Fig. 12.10 Normalized ˆ-function and its approximation .................... 361

Fig. 12.11 Basic algorithm to obtain all allocation points ..................... 364

Fig. 12.12 Polygon P and region R ............................................ 366

Fig. 12.13 Some possible placements ......................................... 369

Fig. 12.14 Set of all allocation points .......................................... 369

Fig. 12.15 Polygons of Exercise 12.1 .......................................... 374

Fig. 12.16 No-ﬁt polygons of Exercise 12.1 ................................... 374

Fig. 12.17 Examples of Exercise 12.4 ......................................... 376

Fig. 12.18 Example-polygon of Exercise 12.5 ................................ 376

Fig. 12.19 Example-polygons of Exercise 12.9 ............................... 380

Fig. 13.1 Non-convexity of G ................................................. 388

Fig. 13.2 Non-convexity of feasible region ................................... 393

剩余428页未读，继续阅读

J-10

粉丝: 18
资源: 483

切割与包装优化入门：问题、建模方法与解决方案

Introduction to Global Optimization

INTRODUCTION TO DERIVATIVE-FREE OPTIMIZATION

Introduction to linear optimization

Introduction to Linear Optimization

Introduction to applied optimization

An Introduction To Optimization

An Introduction to Optimization - Chong and Zak.pdf

Introduction to Linear Optimization.pdf

【Free to Download】Introduction to Linear Optimization.pdf

An Introduction to Optimization Second Edition

最新资源