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 条
  • [1] The two-dimensional cutting stock problem revisited
    Steven S. Seiden
    Gerhard J. Woeginger
    Mathematical Programming, 2005, 102 : 519 - 530
  • [2] The two-dimensional cutting stock problem revisited
    Seiden, SS
    Woeginger, GJ
    MATHEMATICAL PROGRAMMING, 2005, 102 (03) : 519 - 530
  • [3] A TWO-STEP MATH HEURISTIC SOLUTION APPROACH FOR THE TWO-DIMENSIONAL CUTTING STOCK PROBLEM
    Erdem, Banu Icmen
    Kasimbeyli, Refail
    JOURNAL OF NONLINEAR AND CONVEX ANALYSIS, 2023, 24 (04) : 681 - 699
  • [4] The Two-Dimensional Guillotine Cutting Stock Problem with Stack Constraints
    Bogue, Eduardo T.
    Guimaraes, Marcos V. A.
    Noronha, Thiago F.
    Pereira, Armando H.
    Carvalho, Iago A.
    Urrutia, Sebastian
    2021 XLVII LATIN AMERICAN COMPUTING CONFERENCE (CLEI 2021), 2021,
  • [5] A Scalable Approach for the K-Staged Two-Dimensional Cutting Stock Problem
    Dusberger, Frederico
    Raidl, Guenther R.
    OPERATIONS RESEARCH PROCEEDINGS 2015, 2017, : 385 - 391
  • [6] A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem
    Vanderbeck, F
    MANAGEMENT SCIENCE, 2001, 47 (06) : 864 - 879
  • [7] Strips minimization in two-dimensional cutting stock of circular items
    Cui, Yaodong
    Xu, Dao-yun
    COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (04) : 621 - 629
  • [8] Simple block patterns for the two-dimensional cutting problem
    Cui, Yaodong
    MATHEMATICAL AND COMPUTER MODELLING, 2007, 45 (7-8) : 943 - 953
  • [9] Simple heuristic for the constrained two-dimensional cutting problem
    Cui, Y.
    Chen, Q.
    PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE, 2012, 226 (B3) : 565 - 572
  • [10] Two dimensional guillotine cutting stock and scheduling problem in printing industry
    Mostajabdaveh, Mahdi
    Salman, F. Sibel
    Tahmasbi, Nadia
    COMPUTERS & OPERATIONS RESEARCH, 2022, 148
12345