A beam search implementation for the irregular shape packing problem

DOI10.1007/s10732-008-9095-xzbMath1190.90154OpenAlexW2029050146MaRDI QIDQ964846

Julia A. Bennell, Xiang Song

Publication date: 21 April 2010

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10732-008-9095-x

zbMATH Keywords

beam searchcutting and packingnesting problemsirregular shape

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

A clique covering MIP model for the irregular strip packing problem ⋮ Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes ⋮ An effective heuristic for the two-dimensional irregular bin packing problem ⋮ Solving a large cutting problem in the glass manufacturing industry ⋮ Algorithms for nesting with defects ⋮ Dealing with nonregular shapes packing ⋮ Irreducible bin packing and normality in routing open shop ⋮ A parallel biased random-key genetic algorithm with multiple populations applied to irregular strip packing problems ⋮ Matheuristics for the irregular bin packing problem with free rotations ⋮ A beam search approach to solve the convex irregular bin packing problem with guillotine guts ⋮ A fast implementation for the 2D/3D box placement problem ⋮ Raster penetration map applied to the irregular packing problem ⋮ An improved best-fit heuristic for the orthogonal strip packing problem ⋮ Irregular packing: MILP model based on a polygonal enclosure

Uses Software

• TOPOS

Cites Work

• A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms
• Solving irregular strip packing problems by hybridising simulated annealing and linear program\-ming
• Complete and robust no-fit polygon generation for the irregular stock cutting problem
• On genetic algorithms for the packing of polygons
• Computing closely matching upper and lower bounds on textile nesting problems
• TOPOS -- A new constructive algorithm for nesting problems
• Beam-ACO--hybridizing ant colony optimization with beam search: an application to open shop scheduling
• Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach
• Job shop scheduling with beam search
• A 2-exchange heuristic for nesting problems
• An algorithm for polygon placement using a bottom-left strategy
• A simulated annealing approach to the nesting problem in the textile manufacturing industry
• A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums
• An improved typology of cutting and packing problems
• Fast neighborhood search for two- and three-dimensional nesting problems
• Jostling for position: local improvement for irregular cutting patterns
• A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem
• A tabu thresholding implementation for the irregular stock cutting problem