Management Science · 1998 · 387 citations · 20 references
ManagementIndustrial EngineeringOperations ManagementInventory ManagementLogistics ManagementOptimizationApproximation AlgorithmsBranch And BoundCombinatorial OptimizationInteger ProgrammingBin PackingBin Packing ProblemCutting PlanesLower Bound TechniquesLower BoundsPacking ProblemsWorst-case ComplexityWorst-case Optimization
The Two‑Dimensional Finite Bin Packing Problem seeks the minimum number of standardized stock pieces needed to cut a set of rectangular pieces, is NP‑hard, and has many practical cutting‑and‑packing applications. The study aims to analyze a known lower bound’s worst‑case performance and to propose new lower bounds for use in a branch‑and‑bound algorithm solving the problem exactly. The authors analyze a classic lower bound’s worst‑case performance and develop new lower bounds incorporated into a branch‑and‑bound algorithm for exact solution. Extensive computational testing on problem instances from the literature involving up to 120 pieces shows the effectiveness of the proposed approach.
Given a set of rectangular pieces to be cut from an unlimited number of standardized stock pieces (bins), the Two-Dimensional Finite Bin Packing Problem is to determine the minimum number of stock pieces that provide all the pieces. The problem is NP-hard in the strong sense and finds many practical applications in the cutting and packing area. We analyze a well-known lower bound and determine its worst-case performance. We propose new lower bounds which are used within a branch-and-bound algorithm for the exact solution of the problem. Extensive computational testing on problem instances from the literature involving up to 120 pieces shows the effectiveness of the proposed approach.
20
Orthogonal Packings in Two Dimensions
Brenda S. Baker, E. G. Coffman, Ronald L. Rivest · SIAM Journal on Computing · 1980 · 695 citations