Operations Research · 2004 · 352 citations · 31 references
ComputingIndustrial EngineeringManufacturing EngineeringComputational GeometryDesign OptimizationOptimizationCombinatorial OptimizationGeometric OptimizationHeuristic OptimizationHeuristic SearchLayout OptimizationShape OptimizationExecution Time AnalysisMetaheuristic SearchPlacementShapeSolution GenerationSolution Quality Assessment
Placement algorithms typically sort shapes by properties such as height or area and then place them sequentially, and this study provides new problem instances to facilitate further research and comparison. The study introduces a new best‑fit heuristic for the two‑dimensional rectangular stock‑cutting problem and evaluates its performance against existing methods. The heuristic dynamically searches the list for better candidate shapes rather than fixing on the first shape, and its efficient implementation is designed to improve solution quality and execution time. The implementation outperforms other heuristic and metaheuristic approaches in solution quality and execution time.
This paper presents a new best-fit heuristic for the two-dimensional rectangular stock-cutting problem and demonstrates its effectiveness by comparing it against other published approaches. A placement algorithm usually takes a list of shapes, sorted by some property such as increasing height or decreasing area, and then applies a placement rule to each of these shapes in turn. The proposed method is not restricted to the first shape encountered but may dynamically search the list for better candidate shapes for placement. We suggest an efficient implementation of our heuristic and show that it compares favourably to other heuristic and metaheuristic approaches from the literature in terms of both solution quality and execution time. We also present data for new problem instances to encourage further research and greater comparison between this and future methods.
31
Orthogonal Packings in Two Dimensions
Brenda S. Baker, E. G. Coffman, Ronald L. Rivest · SIAM Journal on Computing · 1980 · 695 citations
A hybrid grouping genetic algorithm for bin packing
Emanuel Falkenauer · Journal of Heuristics · 1996 · 597 citations