A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects

Mohsen Afsharian, Ali Niknejad, Gerhard Wascher

    Research output: Contribution to journalArticle

    4 Citations (Scopus)

    Abstract

    This paper deals with a two-dimensional cutting problem in which small rectangular items of given types are to be cut from a rectangular large object which contains several defects. It is assumed that the number of pieces of each small item type which can be cut from the large object is not limited. In addition, all cuts are restricted to be of the guillotine-type and the number of stages necessary to perform all cuts is not limited. Furthermore, no small item must overlap with a defective region. The objective is to maximize the value of the cut small items. For the solution of the above-described problem, a heuristic, dynamic programming-based approach is presented which overcomes the structural and computational limitations of previously-proposed methods. In the presence of defects, the representation of the defective regions and the definition of discretization sets are revisited. This allows for an improvement of the computational efficiency as well as of the storage space requirements for solving the given problem with any number of defects in this approach. We further analyze the computational complexity of the algorithm and identify the factors which affect its running time. The proposed method is evaluated by means of a series of detailed numerical experiments which are performed on problem instances extracted from the literature, as well as on randomly generated instances. The experiments do not only illustrate how the suggested method is able to identify optimal solutions of the test problem instances, but they also explain why already existing methods fail to do so. Furthermore, the computational results indicate that the proposed method, equipped with the newly-proposed discretization sets, is capable of efficiently generating a high percentage of optimal solutions to the corresponding problem with defects.
    Original languageEnglish
    Pages (from-to)971-999
    JournalOR Spectrum
    Volume36
    Issue number4
    DOIs
    Publication statusPublished - 2014

    Fingerprint

    Heuristics
    Defects
    Dynamic programming
    Discretization
    Optimal solution
    Numerical experiment
    Experiment
    Computational complexity
    Factors

    Bibliographical note

    This article is not yet available in the repository.

    Keywords

    • Two-dimensional cutting
    • Defects
    • Computational complexity
    • Dynamic programming

    Cite this

    A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects. / Afsharian, Mohsen; Niknejad, Ali; Wascher, Gerhard.

    In: OR Spectrum, Vol. 36, No. 4, 2014, p. 971-999.

    Research output: Contribution to journalArticle

    Afsharian, Mohsen ; Niknejad, Ali ; Wascher, Gerhard. / A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects. In: OR Spectrum. 2014 ; Vol. 36, No. 4. pp. 971-999.
    @article{b18557576b5941a391dad9e77504861d,
    title = "A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects",
    abstract = "This paper deals with a two-dimensional cutting problem in which small rectangular items of given types are to be cut from a rectangular large object which contains several defects. It is assumed that the number of pieces of each small item type which can be cut from the large object is not limited. In addition, all cuts are restricted to be of the guillotine-type and the number of stages necessary to perform all cuts is not limited. Furthermore, no small item must overlap with a defective region. The objective is to maximize the value of the cut small items. For the solution of the above-described problem, a heuristic, dynamic programming-based approach is presented which overcomes the structural and computational limitations of previously-proposed methods. In the presence of defects, the representation of the defective regions and the definition of discretization sets are revisited. This allows for an improvement of the computational efficiency as well as of the storage space requirements for solving the given problem with any number of defects in this approach. We further analyze the computational complexity of the algorithm and identify the factors which affect its running time. The proposed method is evaluated by means of a series of detailed numerical experiments which are performed on problem instances extracted from the literature, as well as on randomly generated instances. The experiments do not only illustrate how the suggested method is able to identify optimal solutions of the test problem instances, but they also explain why already existing methods fail to do so. Furthermore, the computational results indicate that the proposed method, equipped with the newly-proposed discretization sets, is capable of efficiently generating a high percentage of optimal solutions to the corresponding problem with defects.",
    keywords = "Two-dimensional cutting, Defects, Computational complexity, Dynamic programming",
    author = "Mohsen Afsharian and Ali Niknejad and Gerhard Wascher",
    note = "This article is not yet available in the repository.",
    year = "2014",
    doi = "10.1007/s00291-014-0363-x",
    language = "English",
    volume = "36",
    pages = "971--999",
    journal = "Operations-Research-Spektrum",
    issn = "0171-6468",
    publisher = "Springer Verlag",
    number = "4",

    }

    TY - JOUR

    T1 - A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects

    AU - Afsharian, Mohsen

    AU - Niknejad, Ali

    AU - Wascher, Gerhard

    N1 - This article is not yet available in the repository.

    PY - 2014

    Y1 - 2014

    N2 - This paper deals with a two-dimensional cutting problem in which small rectangular items of given types are to be cut from a rectangular large object which contains several defects. It is assumed that the number of pieces of each small item type which can be cut from the large object is not limited. In addition, all cuts are restricted to be of the guillotine-type and the number of stages necessary to perform all cuts is not limited. Furthermore, no small item must overlap with a defective region. The objective is to maximize the value of the cut small items. For the solution of the above-described problem, a heuristic, dynamic programming-based approach is presented which overcomes the structural and computational limitations of previously-proposed methods. In the presence of defects, the representation of the defective regions and the definition of discretization sets are revisited. This allows for an improvement of the computational efficiency as well as of the storage space requirements for solving the given problem with any number of defects in this approach. We further analyze the computational complexity of the algorithm and identify the factors which affect its running time. The proposed method is evaluated by means of a series of detailed numerical experiments which are performed on problem instances extracted from the literature, as well as on randomly generated instances. The experiments do not only illustrate how the suggested method is able to identify optimal solutions of the test problem instances, but they also explain why already existing methods fail to do so. Furthermore, the computational results indicate that the proposed method, equipped with the newly-proposed discretization sets, is capable of efficiently generating a high percentage of optimal solutions to the corresponding problem with defects.

    AB - This paper deals with a two-dimensional cutting problem in which small rectangular items of given types are to be cut from a rectangular large object which contains several defects. It is assumed that the number of pieces of each small item type which can be cut from the large object is not limited. In addition, all cuts are restricted to be of the guillotine-type and the number of stages necessary to perform all cuts is not limited. Furthermore, no small item must overlap with a defective region. The objective is to maximize the value of the cut small items. For the solution of the above-described problem, a heuristic, dynamic programming-based approach is presented which overcomes the structural and computational limitations of previously-proposed methods. In the presence of defects, the representation of the defective regions and the definition of discretization sets are revisited. This allows for an improvement of the computational efficiency as well as of the storage space requirements for solving the given problem with any number of defects in this approach. We further analyze the computational complexity of the algorithm and identify the factors which affect its running time. The proposed method is evaluated by means of a series of detailed numerical experiments which are performed on problem instances extracted from the literature, as well as on randomly generated instances. The experiments do not only illustrate how the suggested method is able to identify optimal solutions of the test problem instances, but they also explain why already existing methods fail to do so. Furthermore, the computational results indicate that the proposed method, equipped with the newly-proposed discretization sets, is capable of efficiently generating a high percentage of optimal solutions to the corresponding problem with defects.

    KW - Two-dimensional cutting

    KW - Defects

    KW - Computational complexity

    KW - Dynamic programming

    U2 - 10.1007/s00291-014-0363-x

    DO - 10.1007/s00291-014-0363-x

    M3 - Article

    VL - 36

    SP - 971

    EP - 999

    JO - Operations-Research-Spektrum

    JF - Operations-Research-Spektrum

    SN - 0171-6468

    IS - 4

    ER -