Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem

被引:0
作者
M. Hifi
R. M’Hallah
T. Saadi
机构
[1] Université de Picardie Jules Verne,LaRIA
[2] Kuwait University,Department of Statistics and Operations Research
[3] Université Paris,CERMSEM, MSE
来源
Computational Optimization and Applications | 2009年 / 42卷
关键词
Combinatorial optimization; Cutting problems; Dynamic programming; Single constrained knapsack problem;
D O I
暂无
中图分类号
学科分类号
摘要
In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.
引用
收藏
页码:303 / 326
页数:23
相关论文
共 47 条
  • [31] Dynamic Programming and Hill-Climbing Techniques for Constrained Two-Dimensional Cutting Stock Problems
    Mhand Hifi
    Journal of Combinatorial Optimization, 2004, 8 : 65 - 84
  • [32] Dynamic programming and hill-climbing techniques for constrained two-dimensional cutting stock problems
    Hifi, M
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2004, 8 (01) : 65 - 84
  • [33] A recursive exact algorithm for weighted two-dimensional cutting
    Hifi, M
    Zissimopoulos, V
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 91 (03) : 553 - 564
  • [34] Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation
    Cintra, G. F.
    Miyazawa, F. K.
    Wakabayashi, Y.
    Xavier, E. C.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 191 (01) : 61 - 85
  • [35] Generating unconstrained two-dimensional non-guillotine cutting patterns by a Recursive Partitioning Algorithm
    Birgin, E. G.
    Lobato, R. D.
    Morabito, R.
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2012, 63 (02) : 183 - 200
  • [36] A parallel algorithm for constrained two-staged two-dimensional cutting problems
    Hifi, Mhand
    Negre, Stephane
    Ouafi, Rachid
    Saadi, Toufik
    COMPUTERS & INDUSTRIAL ENGINEERING, 2012, 62 (01) : 177 - 189
  • [37] 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
  • [38] Two-stage general block patterns for the two-dimensional cutting problem
    Cui, Yaodong
    Zhang, Xianquan
    COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (10) : 2882 - 2893
  • [39] An approximate algorithm for the two-dimensional air cargo revenue management problem
    Huang, Kuancheng
    Chang, Ko-chen
    TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW, 2010, 46 (03) : 426 - 435
  • [40] A Parallel Algorithm for Constrained Fixed Two-Staged Two-Dimensional Cutting/Packing Problems
    Hifi, M.
    Negre, S.
    Saadi, T.
    CIE: 2009 INTERNATIONAL CONFERENCE ON COMPUTERS AND INDUSTRIAL ENGINEERING, VOLS 1-3, 2009, : 328 - 330