nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.08.2016

A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang

verfasst von: Lei Wang, Aihua Yin

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents a quasi-human algorithm for the rectangular strip packing problem without guillotine constraint. The basic version of the algorithm works according to seven heuristic selection rules, which are designed to select a corner-occupying action. The strengthened version of the algorithm adopts a branching scheme in which the basic version of the algorithm is applied in a heuristic series of parallel branches. Computational tests carried on eight sets of well-known benchmark instances show that the algorithm is efficient for approximately solving the problem. In comparison with the best algorithms in the literature, the algorithm performs better for zero-waste instances and large scale non-zero-waste instances.

Vorheriger Artikel Multi-neighborhood based path relinking for two-sided assembly line balancing problem

Nächster Artikel Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Alvarez-Valdes A, Parreno F, Tamarit JM (2009) A branch and bound algorithm for the strip packing problem. OR Spect 31(2):431–459MathSciNetCrossRefMATH

Beasley JE (1985a) Algorithms for unconstrained two-dimensional guillotine cutting. J Oper Res Soc 36(4):297–306MathSciNetCrossRefMATH

Beasley JE (1985b) An exact two-dimensional non-guillotine cutting tree search procedure. Oper Res 33:49–64MathSciNetCrossRefMATH

Bengtsson BE (1982) Packing rectangular pieces—a heuristic approach. Comput J 25:353–357MathSciNetCrossRef

Berkey JO, Wang PY (1987) Two-dimensional finite bin packing algorithms. J Oper Res Soc 38:423–429CrossRefMATH

Bortfeldt A (2006) A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. Eur J Oper Res 172(3):814–837MathSciNetCrossRefMATH

Burke EK, Kendall G, Whitwell G (2004) A new placement heuristic for the orthogonal stock-cutting problem. Oper Res 52(4):655–671CrossRefMATH

Christofides N, Whitlock C (1977) An algorithm for two-dimensional cutting problems. Oper Res 25(1):30–44CrossRefMATH

Cui YD, Yang YL, Cehng X, Song PH (2008) A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem. Comput Oper Res 35(4):1281–1291CrossRefMATH

He K, Jin Y, Huang WQ (2013) Heuristic for two-dimensional strip packing problem with 90 rotations. Expert Syst Appl 40:5542–5550CrossRef

Hifi M (1998) Exact algorithms for the guillotine strip cutting/packing problem. Comput Oper Res 25:925–940CrossRefMATH

Hochbaum DS, Maass W (1985) Approximation schemes for covering and packing problems in image processing and VLSI. J ACM 32(1):130–136MathSciNetCrossRefMATH

Hopper E, Turton BCH (2001) An empirical investigation of meta-heuristic and heuristic algorithm for a 2D packing problem. Eur J Oper Res 128(1):34–57CrossRefMATH

Huang WQ, He K (2009) A carving degree approach for the single container loading problem. Eur J Oper Res 196(1):93–101MathSciNetCrossRefMATH

Huang WQ, He K (2009) A pure quasi-human algorithm for solving the cuboid packing problem. Sci China Ser F 52(1):52–58MathSciNetCrossRefMATH

Huang WQ, Chen DB, Xu RC (2007) A new heuristic algorithm for rectangle packing. Comput Oper Res 34(11):3270–3280MathSciNetCrossRefMATH

Jiang JQ, Liang YC, Shi XH, Lee HP (2004) A hybrid algorithm based on PSO and SA and its application for two-dimensional non-guillotine cutting stock problem. Lecture Notes in Computer Science, vol 3007, pp 666–669

Leung TW, Chan CK, Troutt MD (2003) Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. Eur J Oper Res 145(3):530–542MathSciNetCrossRefMATH

Leung SCH, Zhang DF (2011) A fast layer-based heuristic for non-guillotine strip packing. Expert Syst Appl 38:13032–13042MathSciNetCrossRef

Leung SCH, Zhang DF, Sim KM (2011) A two-stage intelligent search algorithm for the two-dimensional strip packing problem. Eur J Oper Res 215(1):57–69CrossRef

Lodi A, Martello S, Vigo D (1999) Heuristic and metaheuristic approaches for a class of two dimensional bin packing problem. INFORMS J Comput 11(2):345–357MathSciNetCrossRefMATH

Martello S, Vigo D (1998) Exact solution of the two-dimensional finite bin packing problem. Manag Sci 25:253–257MATH

Pinto E, Oliverira JF (2005) Algorithm based on graphs for the non-guillotinable two-dimensional packing problem. Second ESICP Meeting, Southampton

Valenzuela CL, Wang PY (2001) Heuristics for large strip packing problems with guillotine patterns: an empirical study. In: Proceedings of the 4th Metaheuristics International Conference. University of Porto, Porto, pp 417–421

Wei LJ, Zhang DF, Chen QS (2009) A least wasted first heuristic algorithm for the rectangular packing problem. Comput Oper Res 36(5):1608–1614MathSciNetCrossRefMATH

Zhang DF, Wei LJ, Leung SCH, Chen QS (2013) A binary search heuristic algorithm based on randomized local search for the rectangular strip-packing problem. INFORMS J Comput 25(2):332–345CrossRef

Titel: A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang
verfasst von: Lei Wang
Aihua Yin
Publikationsdatum: 01.08.2016
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9961-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2016

A proper total coloring distinguishing adjacent vertices by sums of planar graphs without intersecting triangles

A three-phased local search approach for the clique partitioning problem

Total and paired domination numbers of bundles over a cycle

Euclidean movement minimization

Tabu search for the real-world carpooling problem

Introduction: Special issue dedicated to the memory of professor Wenqi Huang