Simple heuristic for the constrained two-dimensional cutting problem

被引：8
|
作者：
Cui, Y. [1 ]
Chen, Q. [1 ]
机构：
[1] Guangxi Univ, Sch Comp Elect & Informat, Nanning 530004, Peoples R China
来源：
PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE | 2012年 / 226卷 / B3期
关键词：
cutting stock; constrained two-dimensional cutting; guillotine cuts; ALGORITHM; OPTIMIZATION;
D O I：
10.1177/0954405411421996
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
This paper presents a heuristic for the constrained two-dimensional cutting problem in which a guillotine divides a plate into rectangular pieces. The objective of the proposed heuristic is to maximize the pattern value (that is, the total value of the pieces produced from the plate) while observing the constraint that the number produced of a piece can not exceed the demand for that piece. The algorithm uses a simple recursion approach to consider a set of cutting patterns with specified geometric features, and uses a bound technique to discard unpromising branches. It can give solutions competitive with those of other heuristic algorithms. Its solutions to some benchmark instances are better than those currently reported in the literature.
引用
收藏
页码：565 / 572
页数：8
相关论文
共 50 条
  • [21] An algorithm for the two-dimensional cutting problem of punched strips with blade length constraint
    Cui, Y.
    Zhang, X.
    Wang, Q.
    PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE, 2008, 222 (11) : 1443 - 1451
  • [22] A Hybrid Heuristic to Solve The Two Dimensional Cutting Stock Problem with Consideration of Forecasts
    Ayadi, Omar
    Cheikhrouhou, Naoufel
    Mellouli, Ahmed
    Masmoudi, Faouzi
    CIE: 2009 INTERNATIONAL CONFERENCE ON COMPUTERS AND INDUSTRIAL ENGINEERING, VOLS 1-3, 2009, : 221 - +
  • [23] High Performance Peer-to-Peer Distributed Computing with Application to Constrained Two-dimensional Guillotine Cutting Problem
    Hifi, Mhand
    Saadi, Toufik
    Haddadou, Nawel
    PROCEEDINGS OF THE 19TH INTERNATIONAL EUROMICRO CONFERENCE ON PARALLEL, DISTRIBUTED, AND NETWORK-BASED PROCESSING, 2011, : 552 - 559
  • [24] Extended block patterns for the two-dimensional cutting stock problem
    Cui, Yaodong
    ENGINEERING OPTIMIZATION, 2012, 44 (06) : 657 - 672
  • [25] Strip generation algorithms for constrained two-dimensional two-staged cutting problems
    Hifi, M
    M'Hallah, R
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 172 (02) : 515 - 527
  • [26] 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
  • [27] Two-stage general block patterns for the two-dimensional cutting problem
    Cui, Yaodong
    Zhang, Xianquan
    COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (10) : 2882 - 2893
  • [28] The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm
    Martin, Mateus
    Hokama, Pedro H. D. B.
    Morabito, Reinaldo
    Munari, Pedro
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2020, 58 (09) : 2712 - 2729
  • [29] 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
  • [30] 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
12345