Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2018 | OriginalPaper | Buchkapitel

31. Cutting and Packing

verfasst von: Ramón Alvarez-Valdes, Maria Antónia Carravilla, José Fernando Oliveira

Erschienen in: Handbook of Heuristics

Verlag: Springer International Publishing

share
TEILEN

Abstract

Cutting and Packing (C&P) problems arise in many industrial and logistics applications, whenever a set of small items, with different shapes, has to be assigned to large objects with specific shapes so as to optimize some objective function. Besides some characteristics common to combinatorial optimization problems, the distinctive feature of this field is the existence of a geometric subproblem, to ensure that the items do not overlap and are completely contained in the large objects. The geometric tools required to deal with this subproblem depend on the shapes (rectangles, circles, irregular) and on the specific conditions of the problem being solved. In this chapter, after an introduction that describes and classifies Cutting and Packing problems, we review the basic strategies that have appeared in the literature for designing constructive algorithms, local search procedures, and metaheuristics for problems with regular and irregular shapes.
Literatur
1.
Zurück zum Zitat Albano A, Sapuppo G (1980) Optimal allocation of two-dimensional irregular shapes using heuristic search methods. IEEE Trans Syst Man Cybern 10(5):242–248 Albano A, Sapuppo G (1980) Optimal allocation of two-dimensional irregular shapes using heuristic search methods. IEEE Trans Syst Man Cybern 10(5):242–248
2.
Zurück zum Zitat Alonso M, Alvarez-Valdes R, Parreño F, Tamarit J (2014) A reactive GRASP algorithm for the container loading problem with load-bearing constraints. Eur J Ind Eng 8:669–694 Alonso M, Alvarez-Valdes R, Parreño F, Tamarit J (2014) A reactive GRASP algorithm for the container loading problem with load-bearing constraints. Eur J Ind Eng 8:669–694
3.
Zurück zum Zitat Alvarez-Valdes R, Parajon A, Tamarit J (2002) A computational study of LP-based heuristic algorithms for the two-dimensional guillotine cutting stock problems. OR Spectr 24:179–192 Alvarez-Valdes R, Parajon A, Tamarit J (2002) A computational study of LP-based heuristic algorithms for the two-dimensional guillotine cutting stock problems. OR Spectr 24:179–192
4.
Zurück zum Zitat Alvarez-Valdes R, Parajon A, Tamarit J (2002) A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Comput Oper Res 29:925–947 Alvarez-Valdes R, Parajon A, Tamarit J (2002) A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Comput Oper Res 29:925–947
5.
Zurück zum Zitat Alvarez-Valdes R, Parreño F, Tamarit J (2005) A tabu search algorithm for the pallet loading problem. OR Spectr 27:43–61 Alvarez-Valdes R, Parreño F, Tamarit J (2005) A tabu search algorithm for the pallet loading problem. OR Spectr 27:43–61
6.
Zurück zum Zitat Alvarez-Valdes R, Parreño F, Tamarit J (2007) A tabu search algorithm for a two-dimensional non-guillotine cutting problem. Eur J Oper Res 183:1167–1182 Alvarez-Valdes R, Parreño F, Tamarit J (2007) A tabu search algorithm for a two-dimensional non-guillotine cutting problem. Eur J Oper Res 183:1167–1182
7.
Zurück zum Zitat Alvarez-Valdes R, Marti R, Parajon A, Tamarit J (2007) GRASP and path relinking for the two-dimensional two-stage cutting-stock problem. INFORMS J Comput 19:261–272 Alvarez-Valdes R, Marti R, Parajon A, Tamarit J (2007) GRASP and path relinking for the two-dimensional two-stage cutting-stock problem. INFORMS J Comput 19:261–272
8.
Zurück zum Zitat Alvarez-Valdes R, Parreño F, Tamarit J (2008) Reactive GRASP for the strip packing problem. Comput Oper Res 35:1065–1083 Alvarez-Valdes R, Parreño F, Tamarit J (2008) Reactive GRASP for the strip packing problem. Comput Oper Res 35:1065–1083
9.
Zurück zum Zitat Alvarez-Valdes R, Parreño F, Tamarit J (2013) A GRASP/Path relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems. Comput Oper Res 40: 3081–3090 Alvarez-Valdes R, Parreño F, Tamarit J (2013) A GRASP/Path relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems. Comput Oper Res 40: 3081–3090
10.
Zurück zum Zitat Alvarez-Valdes R, Martinez A, Tamarit J (2013) A branch & bound algorithm for cutting and packing irregularly shaped pieces. Int J Prod Econ 145(2):463–477 Alvarez-Valdes R, Martinez A, Tamarit J (2013) A branch & bound algorithm for cutting and packing irregularly shaped pieces. Int J Prod Econ 145(2):463–477
11.
Zurück zum Zitat Araujo O, Armentano V (2007) A multi-start random constructive heuristic for the container loading problem. Pesquisa Operacional 27(2):311–331 Araujo O, Armentano V (2007) A multi-start random constructive heuristic for the container loading problem. Pesquisa Operacional 27(2):311–331
12.
Zurück zum Zitat Arenales M, Morabito R (1995) An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems. Eur J Oper Res 84:599–617 Arenales M, Morabito R (1995) An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems. Eur J Oper Res 84:599–617
13.
Zurück zum Zitat Art RC (1966) An approch to the two dimensional, irregular cutting stock problem. IBM Cambridge Scientific Center Report, pp 1–35 Art RC (1966) An approch to the two dimensional, irregular cutting stock problem. IBM Cambridge Scientific Center Report, pp 1–35
14.
15.
Zurück zum Zitat Below G, Scheithauer G, Mukhacheva E (2008) One-dimensional heuristics adapted for two-dimensional rectangular strip packing. J Oper Res Soc 59:823–832 CrossRef Below G, Scheithauer G, Mukhacheva E (2008) One-dimensional heuristics adapted for two-dimensional rectangular strip packing. J Oper Res Soc 59:823–832 CrossRef
16.
Zurück zum Zitat Bennell JA, Dowsland KA (2001) Hybridising tabu search with optimisation techniques for irregular stock cutting. Manag Sci 47(8):1160–1172 CrossRef Bennell JA, Dowsland KA (2001) Hybridising tabu search with optimisation techniques for irregular stock cutting. Manag Sci 47(8):1160–1172 CrossRef
17.
Zurück zum Zitat Bennell JA, Oliveira JF (2008) The geometry of nesting problems: a tutorial. Eur J Oper Res 184(2):397–415 MathSciNetCrossRef Bennell JA, Oliveira JF (2008) The geometry of nesting problems: a tutorial. Eur J Oper Res 184(2):397–415 MathSciNetCrossRef
18.
Zurück zum Zitat Bennell JA, Song X (2010) A beam search implementation for the irregular shape packing problem. J Heuristics 16(2):167–188 CrossRef Bennell JA, Song X (2010) A beam search implementation for the irregular shape packing problem. J Heuristics 16(2):167–188 CrossRef
19.
Zurück zum Zitat Bennell J, Lee L, Potts C (2013) A genetic algorithm for two-dimensional bin packing with due dates. Int J Prod Econ 145:547–560 CrossRef Bennell J, Lee L, Potts C (2013) A genetic algorithm for two-dimensional bin packing with due dates. Int J Prod Econ 145:547–560 CrossRef
20.
Zurück zum Zitat Bortfeldt A, Gehring H (2001) A hybrid algorithm for the container loading problem. Eur J Oper Res 131:143–161 CrossRef Bortfeldt A, Gehring H (2001) A hybrid algorithm for the container loading problem. Eur J Oper Res 131:143–161 CrossRef
21.
Zurück zum Zitat Burke E, Kendall G, Whitwell G (2004) A new placement heuristic for the orthogonal stock-cutting problem. Oper Res 52(4):655–671 CrossRef Burke E, Kendall G, Whitwell G (2004) A new placement heuristic for the orthogonal stock-cutting problem. Oper Res 52(4):655–671 CrossRef
22.
Zurück zum Zitat Burke E, Kendall G, Whitwell G (2009) A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock-cutting problem. INFORMS J Comput 21(3):505–516 CrossRef Burke E, Kendall G, Whitwell G (2009) A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock-cutting problem. INFORMS J Comput 21(3):505–516 CrossRef
23.
Zurück zum Zitat Burke E, Hyde M, Kendall G (2011) A squeaky wheel optimization methodology for two-dimensional strip packing. Comput Oper Res 38:1035–1044 CrossRef Burke E, Hyde M, Kendall G (2011) A squeaky wheel optimization methodology for two-dimensional strip packing. Comput Oper Res 38:1035–1044 CrossRef
24.
Zurück zum Zitat Ceschia S, Schaerf A (2013) Local search for a multi-drop multi-container loading problem. J Heuristics 19:275–294 CrossRef Ceschia S, Schaerf A (2013) Local search for a multi-drop multi-container loading problem. J Heuristics 19:275–294 CrossRef
25.
Zurück zum Zitat Chazelle B (1983) The bottom-left bin-packing heuristic: an efficient implementation. IEEE Trans Comput 32(8):697–707 CrossRef Chazelle B (1983) The bottom-left bin-packing heuristic: an efficient implementation. IEEE Trans Comput 32(8):697–707 CrossRef
26.
Zurück zum Zitat Chen W, Zhai P, Zhu H, Zhang Y (2014) Hybrid algorithm for the two-dimensional rectangular layer-packing problem. J Oper Res Soc 65:1068–1077 CrossRef Chen W, Zhai P, Zhu H, Zhang Y (2014) Hybrid algorithm for the two-dimensional rectangular layer-packing problem. J Oper Res Soc 65:1068–1077 CrossRef
27.
Zurück zum Zitat Cherri L, Toledo F, Carravilla MA (2016) A model-based heuristic for the irregular strip packing problem. Pesquisa Operacional 36(3):447–468 CrossRef Cherri L, Toledo F, Carravilla MA (2016) A model-based heuristic for the irregular strip packing problem. Pesquisa Operacional 36(3):447–468 CrossRef
28.
Zurück zum Zitat Christensen S, Rousoe D (2009) Container loading with multi-drop constraints. Int Trans Oper Res 16:727–743 CrossRef Christensen S, Rousoe D (2009) Container loading with multi-drop constraints. Int Trans Oper Res 16:727–743 CrossRef
29.
Zurück zum Zitat da Silveira J, Miyazawa F, Xavier E (2013) Heuristics for the strip packing problem with unloading constraints. Comput Oper Res 40:991–1003 MathSciNetCrossRef da Silveira J, Miyazawa F, Xavier E (2013) Heuristics for the strip packing problem with unloading constraints. Comput Oper Res 40:991–1003 MathSciNetCrossRef
30.
Zurück zum Zitat Dowsland KA, Dowsland WB, Bennell JA (1998) Jostling for position: local improvement for irregular cutting patterns. J Oper Res Soc 49:647–658 CrossRef Dowsland KA, Dowsland WB, Bennell JA (1998) Jostling for position: local improvement for irregular cutting patterns. J Oper Res Soc 49:647–658 CrossRef
31.
Zurück zum Zitat Dowsland KA, Vaid S, Dowsland WB (2002) An algorithm for polygon placement using a bottom-left strategy. Eur J Oper Res 141(2):371–381 MathSciNetCrossRef Dowsland KA, Vaid S, Dowsland WB (2002) An algorithm for polygon placement using a bottom-left strategy. Eur J Oper Res 141(2):371–381 MathSciNetCrossRef
32.
33.
Zurück zum Zitat Egeblad J, Nielsen BK, Odgaard A (2007) Fast neighborhood search for two- and three-dimensional nesting problems. Eur J Oper Res 183(3):1249–1266 MathSciNetCrossRef Egeblad J, Nielsen BK, Odgaard A (2007) Fast neighborhood search for two- and three-dimensional nesting problems. Eur J Oper Res 183(3):1249–1266 MathSciNetCrossRef
34.
35.
Zurück zum Zitat Elkeran A (2013) A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering. Eur J Oper Res 231(3):757–769 MathSciNetCrossRef Elkeran A (2013) A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering. Eur J Oper Res 231(3):757–769 MathSciNetCrossRef
36.
Zurück zum Zitat Fanslau T, Bortfeldt A (2010) A tree search algorithm for solving the container loading problem. INFORMS J Comput 22(2):222–235 MathSciNetCrossRef Fanslau T, Bortfeldt A (2010) A tree search algorithm for solving the container loading problem. INFORMS J Comput 22(2):222–235 MathSciNetCrossRef
37.
Zurück zum Zitat Faroe O, Pisinger D, Zachariasen M (2003) Guided local search for the three-dimensional bin-packing problem. INFORMS J Comput 15(3):267–283 MathSciNetCrossRef Faroe O, Pisinger D, Zachariasen M (2003) Guided local search for the three-dimensional bin-packing problem. INFORMS J Comput 15(3):267–283 MathSciNetCrossRef
38.
Zurück zum Zitat Fischetti M, Luzzi I (2009) Mixed-integer programming models for nesting problems. J Heuristics 15(3):201–226 CrossRef Fischetti M, Luzzi I (2009) Mixed-integer programming models for nesting problems. J Heuristics 15(3):201–226 CrossRef
39.
40.
Zurück zum Zitat Gilmore P, Gomory R (1963) A linear programming approach to the cutting-stock problem – part II. Oper Res 11:863–888 CrossRef Gilmore P, Gomory R (1963) A linear programming approach to the cutting-stock problem – part II. Oper Res 11:863–888 CrossRef
41.
Zurück zum Zitat Gilmore P, Gomory R (1965) Multistage cutting stock problems of two and more dimensions. Oper Res 13:94–120 CrossRef Gilmore P, Gomory R (1965) Multistage cutting stock problems of two and more dimensions. Oper Res 13:94–120 CrossRef
42.
43.
Zurück zum Zitat Gomes AM, Oliveira JF (2006) Solving irregular strip packing problems by hybridising simulated annealing and linear programming. Eur J Oper Res 171(3):811–829 CrossRef Gomes AM, Oliveira JF (2006) Solving irregular strip packing problems by hybridising simulated annealing and linear programming. Eur J Oper Res 171(3):811–829 CrossRef
44.
Zurück zum Zitat Gonçalves J, Resende M (2013) A biased random key genetic algorithm for 2D and 3D bin packing problems. Int J Prod Econ 145:500–510 CrossRef Gonçalves J, Resende M (2013) A biased random key genetic algorithm for 2D and 3D bin packing problems. Int J Prod Econ 145:500–510 CrossRef
45.
Zurück zum Zitat Hifi M, M’Hallah R (2009) A literature review on circle and sphere packing problems: models and methodologies. Adv Oper Res 2009(150624):1–22 MATH Hifi M, M’Hallah R (2009) A literature review on circle and sphere packing problems: models and methodologies. Adv Oper Res 2009(150624):1–22 MATH
46.
Zurück zum Zitat Hifi M, Michrafy M, Sbihi A (2004) Heuristic algorithms for the multiple-choice multidimensional knapsack problem. J Oper Res Soc 55:1323–1332 CrossRef Hifi M, Michrafy M, Sbihi A (2004) Heuristic algorithms for the multiple-choice multidimensional knapsack problem. J Oper Res Soc 55:1323–1332 CrossRef
47.
Zurück zum Zitat Hopper E, Turton B (2001) An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. Eur J Oper Res 128:34–57 CrossRef Hopper E, Turton B (2001) An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. Eur J Oper Res 128:34–57 CrossRef
48.
Zurück zum Zitat Imamichi T, Yagiura M, Nagamochi H (2009) An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem. Discret Optim 6(4): 345–361 MathSciNetCrossRef Imamichi T, Yagiura M, Nagamochi H (2009) An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem. Discret Optim 6(4): 345–361 MathSciNetCrossRef
49.
Zurück zum Zitat Iori M, Martello S, Monaci M (2003) Metaheuristic algorithms for the strip packing problem. In: Pardalos PM, Korotkikh V (eds) Optimization in industry: new frontiers. Kluwer Academic Publishers, Dordrecht, pp 159–179 CrossRef Iori M, Martello S, Monaci M (2003) Metaheuristic algorithms for the strip packing problem. In: Pardalos PM, Korotkikh V (eds) Optimization in industry: new frontiers. Kluwer Academic Publishers, Dordrecht, pp 159–179 CrossRef
50.
Zurück zum Zitat Jakobs S (1996) On genetic algorithms for the packing of polygons. Eur J Oper Res 88: 165–181 CrossRef Jakobs S (1996) On genetic algorithms for the packing of polygons. Eur J Oper Res 88: 165–181 CrossRef
51.
Zurück zum Zitat Lai K, Chan J (1997) Developing a simulated annealing algorithm for the cutting stock problem. Comput Ind Eng 32:115–127 CrossRef Lai K, Chan J (1997) Developing a simulated annealing algorithm for the cutting stock problem. Comput Ind Eng 32:115–127 CrossRef
52.
Zurück zum Zitat Lesh N, Mitzenmacher M (2006) Bubblesearch: a simple heuristic for improving priority-based greedy algorithms. Inf Process Lett 97(4):161–169 MathSciNetCrossRef Lesh N, Mitzenmacher M (2006) Bubblesearch: a simple heuristic for improving priority-based greedy algorithms. Inf Process Lett 97(4):161–169 MathSciNetCrossRef
53.
Zurück zum Zitat Lesh N, Marks J, McMahon A, Mitzenmacher M (2003) New heuristic and interactive approaches to 2D rectangular strip packing. Technical report TR2003-18. Mitsubishi Electric Research Laboratories, Cambridge Lesh N, Marks J, McMahon A, Mitzenmacher M (2003) New heuristic and interactive approaches to 2D rectangular strip packing. Technical report TR2003-18. Mitsubishi Electric Research Laboratories, Cambridge
54.
Zurück zum Zitat Leung T, Chan C, Troutt M (2003) Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. Eur J Oper Res 145:530–542 MathSciNetCrossRef Leung T, Chan C, Troutt M (2003) Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. Eur J Oper Res 145:530–542 MathSciNetCrossRef
55.
Zurück zum Zitat Leung S, Zhang D, Sim K (2011) A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem. Eur J Oper Res 215:57–69 CrossRef Leung S, Zhang D, Sim K (2011) A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem. Eur J Oper Res 215:57–69 CrossRef
56.
Zurück zum Zitat Leung S, Zhang D, Zhou C, Wu T (2012) A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem. Comput Oper Res 39:64–73 CrossRef Leung S, Zhang D, Zhou C, Wu T (2012) A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem. Comput Oper Res 39:64–73 CrossRef
57.
Zurück zum Zitat Leung SC, Lin Y, Zhang D (2012) Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem. Comput Oper Res 39(3):678–686 MathSciNetCrossRef Leung SC, Lin Y, Zhang D (2012) Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem. Comput Oper Res 39(3):678–686 MathSciNetCrossRef
58.
Zurück zum Zitat Liu D, Teng H (1999) An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. Eur J Oper Res 112:413–420 CrossRef Liu D, Teng H (1999) An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. Eur J Oper Res 112:413–420 CrossRef
59.
Zurück zum Zitat Liu D, Tan K, Huang S, Goh C, Ho W (2008) On solving multiobjective bin packing problems using evolutionary particle swarm optimization. Eur J Oper Res 190:357–382 MathSciNetCrossRef Liu D, Tan K, Huang S, Goh C, Ho W (2008) On solving multiobjective bin packing problems using evolutionary particle swarm optimization. Eur J Oper Res 190:357–382 MathSciNetCrossRef
60.
Zurück zum Zitat Lodi A, Martello S, Vigo D (2004) TSpack: a unified tabu search code for multi-dimensional bin packing problems. Ann Oper Res 131:203–213 MathSciNetCrossRef Lodi A, Martello S, Vigo D (2004) TSpack: a unified tabu search code for multi-dimensional bin packing problems. Ann Oper Res 131:203–213 MathSciNetCrossRef
61.
Zurück zum Zitat Martinez Sykora A (2013) Nesting problems: exact and heuristic algorithms. Phd thesis, Univesity of Valencia Martinez Sykora A (2013) Nesting problems: exact and heuristic algorithms. Phd thesis, Univesity of Valencia
62.
Zurück zum Zitat Martinez-Sykora A, Alvarez-Valdes R, Bennell J, Tamarit JM (2015) Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts. Omega 52:15–32 CrossRef Martinez-Sykora A, Alvarez-Valdes R, Bennell J, Tamarit JM (2015) Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts. Omega 52:15–32 CrossRef
63.
Zurück zum Zitat Milenkovic VJ, Daniels K (1999) Translational polygon containment and minimal enclosure using mathematical programming. Int Trans Oper Res 6:525–554 MathSciNetCrossRef Milenkovic VJ, Daniels K (1999) Translational polygon containment and minimal enclosure using mathematical programming. Int Trans Oper Res 6:525–554 MathSciNetCrossRef
64.
Zurück zum Zitat Moura A, Oliveira JF (2008) An integrated approach to the vehicle routing and container loading problems. OR Spect 31(4):775–800 MathSciNetCrossRef Moura A, Oliveira JF (2008) An integrated approach to the vehicle routing and container loading problems. OR Spect 31(4):775–800 MathSciNetCrossRef
65.
Zurück zum Zitat Mukhacheva E, Belov G, Kartak V, Mukhacheva A (2000) Linear one-dimensional cutting-packing problems: numerical experiments with sequential value correction method (SVC) and a modified branch-and-bound method (MBB). Pesquisa Operacional 20:153–168 CrossRef Mukhacheva E, Belov G, Kartak V, Mukhacheva A (2000) Linear one-dimensional cutting-packing problems: numerical experiments with sequential value correction method (SVC) and a modified branch-and-bound method (MBB). Pesquisa Operacional 20:153–168 CrossRef
66.
Zurück zum Zitat Oliveira JF, Ferreira JS (1993) Algorithms for nesting problems. In: Vidal RVV (ed) Applied simulated annealing. Lecture notes in economics and mathematical systems. Springer, Berlin, pp 256–279 Oliveira JF, Ferreira JS (1993) Algorithms for nesting problems. In: Vidal RVV (ed) Applied simulated annealing. Lecture notes in economics and mathematical systems. Springer, Berlin, pp 256–279
67.
Zurück zum Zitat Oliveira JF, Gomes AM, Ferreira JS (2000) TOPOS – a new constructive algorithm for nesting problems. OR Spektr 22(2):263–284 MathSciNetCrossRef Oliveira JF, Gomes AM, Ferreira JS (2000) TOPOS – a new constructive algorithm for nesting problems. OR Spektr 22(2):263–284 MathSciNetCrossRef
68.
Zurück zum Zitat Parreño F, Alvarez-Valdes R, Oliveira J, Tamarit J (2010) Neighbourhood structures for the container loading problem: a VNS implementation. J Heuristics 16(1):1–22 CrossRef Parreño F, Alvarez-Valdes R, Oliveira J, Tamarit J (2010) Neighbourhood structures for the container loading problem: a VNS implementation. J Heuristics 16(1):1–22 CrossRef
70.
Zurück zum Zitat Pureza V, Morabito R (2006) Some experiments with a simple tabu search algorithm for the manufacturers pallet loading problem. Comput Oper Res 33:804–819 CrossRef Pureza V, Morabito R (2006) Some experiments with a simple tabu search algorithm for the manufacturers pallet loading problem. Comput Oper Res 33:804–819 CrossRef
71.
Zurück zum Zitat Ren J, Tian Y, Sawaragi T (2011) A tree search method for the container loading problem with shipment priority. Eur J Oper Res 214:526–535 CrossRef Ren J, Tian Y, Sawaragi T (2011) A tree search method for the container loading problem with shipment priority. Eur J Oper Res 214:526–535 CrossRef
72.
Zurück zum Zitat Riehme J, Scheithauer G, Terno J (1996) The solution of two-stage guillotine cutting stock problems having extremely varying order demands. Eur J Oper Res 91:543–552 CrossRef Riehme J, Scheithauer G, Terno J (1996) The solution of two-stage guillotine cutting stock problems having extremely varying order demands. Eur J Oper Res 91:543–552 CrossRef
73.
Zurück zum Zitat Sato AK, Martins TC, Tsuzuki MSG (2012) An algorithm for the strip packing problem using collision free region and exact fitting placement. Comput Aided Des 44(8):766–777 CrossRef Sato AK, Martins TC, Tsuzuki MSG (2012) An algorithm for the strip packing problem using collision free region and exact fitting placement. Comput Aided Des 44(8):766–777 CrossRef
74.
Zurück zum Zitat Segenreich SA, Braga LMPF (1986) Optimal nesting of general plane figures: a Monte Carlo heuristical approach. Comput Graph 10(3):229–237 CrossRef Segenreich SA, Braga LMPF (1986) Optimal nesting of general plane figures: a Monte Carlo heuristical approach. Comput Graph 10(3):229–237 CrossRef
75.
Zurück zum Zitat Song X, Bennell Ja (2013) Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem. J Oper Res Soc 65(7):1037–1052 CrossRef Song X, Bennell Ja (2013) Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem. J Oper Res Soc 65(7):1037–1052 CrossRef
76.
Zurück zum Zitat Stadtler H (1990) A one-dimensional cutting stock problem in the aluminium industry and its solution. Eur J Oper Res 44:209–223 CrossRef Stadtler H (1990) A one-dimensional cutting stock problem in the aluminium industry and its solution. Eur J Oper Res 44:209–223 CrossRef
77.
Zurück zum Zitat Stoyan YG, Novozhilova MV, Kartashov AV (1996) Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem. Eur J Oper Res 92(1):193–210 CrossRef Stoyan YG, Novozhilova MV, Kartashov AV (1996) Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem. Eur J Oper Res 92(1):193–210 CrossRef
78.
Zurück zum Zitat Takahara S, Kusumoto Y, Miyamoto S (2003) Solution for textile nesting problems using adaptive meta-heuristics and grouping. Soft Comput 7:154–159 CrossRef Takahara S, Kusumoto Y, Miyamoto S (2003) Solution for textile nesting problems using adaptive meta-heuristics and grouping. Soft Comput 7:154–159 CrossRef
79.
Zurück zum Zitat Toledo FMB, Carravilla MA, Ribeiro C, Oliveira JF, Gomes AM (2013) The dotted-board model: a new MIP model for nesting irregular shapes. Int J Prod Econ 145:478–487 CrossRef Toledo FMB, Carravilla MA, Ribeiro C, Oliveira JF, Gomes AM (2013) The dotted-board model: a new MIP model for nesting irregular shapes. Int J Prod Econ 145:478–487 CrossRef
80.
Zurück zum Zitat Umetani S, Yagiura M, Imahori S, Imamichi T, Nonobe K, Ibaraki T (2009) Solving the irregular strip packing problem via guided local search for overlap minimization. Int Trans Oper Res 16(6):661–683 MathSciNetCrossRef Umetani S, Yagiura M, Imahori S, Imamichi T, Nonobe K, Ibaraki T (2009) Solving the irregular strip packing problem via guided local search for overlap minimization. Int Trans Oper Res 16(6):661–683 MathSciNetCrossRef
81.
Zurück zum Zitat Valerio de Carvalho J (2002) LP models for bin packing and cutting stock problems. Eur J Oper Res 141:253–273 MathSciNetCrossRef Valerio de Carvalho J (2002) LP models for bin packing and cutting stock problems. Eur J Oper Res 141:253–273 MathSciNetCrossRef
82.
Zurück zum Zitat Wäscher G, Hauß ner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183:1109–1130 Wäscher G, Hauß ner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183:1109–1130
83.
Zurück zum Zitat Wei L, Lim A (2015) A bidirectional building approach for the 2D constrained guillotine knapsack packing problem. Eur J Oper Res 242:63–71 MathSciNetCrossRef Wei L, Lim A (2015) A bidirectional building approach for the 2D constrained guillotine knapsack packing problem. Eur J Oper Res 242:63–71 MathSciNetCrossRef
84.
Zurück zum Zitat Wei L, Oon W, Zhu W, Lim A (2011) A skyline heuristic for the 2D rectangular packing and strip packing problems. Eur J Oper Res 215:337–346 MathSciNetMATH Wei L, Oon W, Zhu W, Lim A (2011) A skyline heuristic for the 2D rectangular packing and strip packing problems. Eur J Oper Res 215:337–346 MathSciNetMATH
85.
Zurück zum Zitat Wu Y, Huang W, Lau S, Wong C, Young G (2002) An effective quasi-human based heuristic for solving the rectangle packing problem. Eur J Oper Res 141:341–358 MathSciNetCrossRef Wu Y, Huang W, Lau S, Wong C, Young G (2002) An effective quasi-human based heuristic for solving the rectangle packing problem. Eur J Oper Res 141:341–358 MathSciNetCrossRef
86.
Zurück zum Zitat Zhu W, Oon W, Lim A, Weng Y (2012) The six elements to block-building approaches for the single container loading problem. Appl Intell 37:431–445 CrossRef Zhu W, Oon W, Lim A, Weng Y (2012) The six elements to block-building approaches for the single container loading problem. Appl Intell 37:431–445 CrossRef
Metadaten
Titel
Cutting and Packing
verfasst von
Ramón Alvarez-Valdes
Maria Antónia Carravilla
José Fernando Oliveira
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_43

Premium Partner