A near-optimal solution to a two-dimensional cutting stock problem

被引：138
|
作者：
Kenyon, C
Rémila, E
机构：
[1] Univ Paris Sud, LRI, F-91405 Orsay, France
[2] Univ St Etienne, IUT Roanne, Grima, F-42334 Roanne, France
[3] Ecole Normale Super Lyon, CNRS, Umr 5668, F-69364 Lyon, France
来源：
MATHEMATICS OF OPERATIONS RESEARCH | 2000年 / 25卷 / 04期
关键词：
cutting-stock; strip-packing; fully polynomial approximation scheme;
D O I：
10.1287/moor.25.4.645.12118
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We present an asymptotic fully polynomial approximation scheme for strip-packing, or packing rectangles into a rectangle of fixed width and minimum height, a classical NP-hard cutting-stock problem. The algorithm, based on a new linear-programming relaxation, finds a packing of n rectangles whose total height is within a factor of(1 + epsilon) of optimal (up to an additive term), and has running time polynomial both in n and in 1/epsilon.
引用
收藏
页码：645 / 656
页数：12
相关论文
共 48 条
  • [41] Application of column generation approach in minimizing waste and predicting future inventory of one dimensional cutting stock problem
    Lin, Pei-Chun
    JOURNAL OF STATISTICS & MANAGEMENT SYSTEMS, 2005, 8 (03) : 569 - 585
  • [42] A Biased Random-Key Genetic Algorithm for the 2-Dimensional Guillotine Cutting Stock Problem with Stack Constraints
    Guimaraes, Marcos V. A.
    Bogue, Eduardo T.
    Carvalho, Iago A.
    Pereira, Armando H.
    Noronha, Thiago F.
    Urrutia, Sebastian
    METAHEURISTICS AND NATURE INSPIRED COMPUTING, META 2021, 2022, 1541 : 155 - 169
  • [43] C-Sets-based sequential heuristic procedure for the one-dimensional cutting stock problem with pattern reduction
    Cui, Yaodong
    Liu, Zhiyong
    OPTIMIZATION METHODS & SOFTWARE, 2011, 26 (01) : 155 - 167
  • [44] Enhancing the Efficiency of Heuristic Placement Algorithm for Two-dimensional Orthogonal Knapsack Packing Problem
    Shiangjen, Kanokwatt
    Chaijaruwanich, Jeerayut
    Srisujjalertwaja, Wijak
    Somhom, Samerkae
    PROCEEDINGS OF 2015 6TH IEEE INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING AND SERVICE SCIENCE, 2015, : 33 - 36
  • [45] Applying triple-block patterns in solving the two-dimensional bin packing problem
    Cui, Yi-Ping
    Yao, Yi
    Zhang, Defu
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2018, 69 (03) : 402 - 415
  • [46] An algorithm for the constrained two-dimensional rectangular multiple identical large object placement problem
    Cui, Y.
    Gu, T.
    Hu, W.
    OPTIMIZATION METHODS & SOFTWARE, 2008, 23 (03) : 375 - 393
  • [47] Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem
    Pisinger, David
    Sigurd, Mikkel
    INFORMS JOURNAL ON COMPUTING, 2007, 19 (01) : 36 - 51
  • [48] A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due dates
    Polyakovskiy, Sergey
    M'Hallah, Rym
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2018, 266 (03) : 819 - 839
12345