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 条
  • [21] Constrained two-dimensional guillotine cutting problem: upper-bound review and categorization
    Russo, Mauro
    Boccia, Maurizio
    Sforza, Antonio
    Sterle, Claudio
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2020, 27 (02) : 794 - 834
  • [22] Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths
    Poldi, Kelly Cristina
    Arenales, Marcos Nereu
    COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (06) : 2074 - 2081
  • [23] A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems
    Alvarez-Valdes R.
    Parajon A.
    Tamarit J.M.
    OR Spectrum, 2002, 24 (2) : 179 - 192
  • [24] A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems
    Alvarez-Valdes, R
    Parajon, A
    Tamarit, JM
    OR SPECTRUM, 2002, 24 (02) : 179 - 192
  • [25] An effective solution for a real cutting stock problem in manufacturing plastic rolls
    Varela, Ramiro
    Vela, Camino R.
    Puente, Jorge
    Sierra, Maria
    Gonzalez-Rodriguez, Ines
    ANNALS OF OPERATIONS RESEARCH, 2009, 166 (01) : 125 - 146
  • [26] An effective solution for a real cutting stock problem in manufacturing plastic rolls
    Ramiro Varela
    Camino R. Vela
    Jorge Puente
    María Sierra
    Inés González-Rodríguez
    Annals of Operations Research, 2009, 166
  • [27] A heuristic for the one-dimensional cutting stock problem with pattern reduction
    Cui, Y.
    Zhao, X.
    Yang, Y.
    Yu, P.
    PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE, 2008, 222 (06) : 677 - 685
  • [28] THE ONE-DIMENSIONAL CUTTING STOCK PROBLEM USING 2 OBJECTIVES
    SINUANYSTERN, Z
    WEINER, I
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1994, 45 (02) : 231 - 236
  • [29] A heuristic for the one-dimensional cutting stock problem with usable leftover
    Cui, Yaodong
    Yang, Yuli
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 204 (02) : 245 - 250
  • [30] Heuristic for two-dimensional homogeneous two-segment cutting patterns
    Cui, Yaodong
    ENGINEERING OPTIMIZATION, 2013, 45 (01) : 89 - 105
12345