Software Engineering

| Peer-Reviewed |

Modified Method for One-Dimensional Cutting Stock Problem

Received: 03 September 2015    Accepted: 23 September 2015    Published: 19 October 2015
Views:       Downloads:

Share This Article

Abstract

Selection of feasible cutting patterns in order to minimize the rawmaterial wastage which is known as cutting stock problem has become a key factor of the success in today’s competitive manufacturing industries. In this paper, solving a one-dimensional cutting stock problem is discussed. Our study is restricted to rawmaterial (main sheet) in a rectangular shape (different sizes), and cutting items are also considered as rectangular shape with known dimensions (assume that lengths of the main sheets and cutting items are equal). Pattern generation technique is used to nest the pieces of cutting items within the main sheet by minimizing rawmaterial wastage. A computer program using Matlab software package is developed to generate feasible patterns using the above algorithm for 1D cutting stock problem. Location of each feasible cutting pattern inside the main sheet is given in Cartesian Coordinate Plane. The Branch and Bound approach in solving integer programming problems is used to solve the problem.

DOI 10.11648/j.se.20150303.11
Published in Software Engineering (Volume 3, Issue 3, September 2015)
Page(s) 12-17
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Cutting Stock Problem, Branch and Bound Algorithm, Pattern Generation, Matlab Software Package

References
[1] P. C. Gilmore and R. E. Gomory, “A Linear Programming Approach to the Cutting Stock Problem”, Operations Research, Vol. 9, No. 2 (1961), 849 - 859.
[2] Gilmore PC, Gomory RE. A Linear Programming Approach to the Cutting Stock Problem – Part II. Operations Research. 1963; 11(6):8 63–888.
[3] Saad M. A Suliman, “Pattern generating procedure for the cutting stock problem”, International Journal of Production Economics 74 (2001) 293-301.
[4] Sirirat Wongprakornkul and Peerayuth Charnsethikul, “Solving one-Dimensional Cutting Stock Problem with Discrete Demands and Capacitated Planning Objective”, Journal of Mathematics and Statistics 6 (2010) 79 – 83.
[5] Beasley JE. Algorithms for Unconstrained Two-Dimensional Guillotine Cutting. Journal of Operations Research Science. 1985; 36(4):297–306.
[6] Rodrigo WNP, Daundasekera WB, Perera AAI, “Pattern Generation for One-Dimensional Cutting Stock Problem”, Peradeniya University Research Session (PURSE), 2011.
[7] W. N. P Rodrigo, W. B. Daundasekera, A. A. I Perera “Pattern eneration for Two-Dimensional Cutting Stock Problem” International Journal of Mathematics Trends and Technology (IJMTT), Vol. 3 Issue2 (2012), 54-62.
[8] W. N. P. Rodrigo, W. B. Daundasekara and A. A. I. Perera “Pattern Generation for Two-Dimensional Cutting Stock Problem with Location”, Indian Journal of Computer Science and Engineering (IJCSE), Vol. 3, No 2, April-May 2012, 354-368.
[9] Coromoto Leon, Gara Miranda, Casiano Rodriguez, & Carlos Segura, “2D Cutting Stock Problem: A New Parallel Algorithm and Bounds”, (www.springerlink.com/index/906t32v338q7u641.pdf), 25th November 2010.
[10] Robert W. Haessler and Paul E. Sweeney, “Cutting Stock Problem and Solution Procedures”, European Journal of Operational research 54 (1991), 141 – 150.
Author Information
  • Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka

  • Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka

  • Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka

Cite This Article
  • APA Style

    Niluka Rodrigo, WB Daundasekera, AAI Perera. (2015). Modified Method for One-Dimensional Cutting Stock Problem. Software Engineering, 3(3), 12-17. https://doi.org/10.11648/j.se.20150303.11

    Copy | Download

    ACS Style

    Niluka Rodrigo; WB Daundasekera; AAI Perera. Modified Method for One-Dimensional Cutting Stock Problem. Softw. Eng. 2015, 3(3), 12-17. doi: 10.11648/j.se.20150303.11

    Copy | Download

    AMA Style

    Niluka Rodrigo, WB Daundasekera, AAI Perera. Modified Method for One-Dimensional Cutting Stock Problem. Softw Eng. 2015;3(3):12-17. doi: 10.11648/j.se.20150303.11

    Copy | Download

  • @article{10.11648/j.se.20150303.11,
      author = {Niluka Rodrigo and WB Daundasekera and AAI Perera},
      title = {Modified Method for One-Dimensional Cutting Stock Problem},
      journal = {Software Engineering},
      volume = {3},
      number = {3},
      pages = {12-17},
      doi = {10.11648/j.se.20150303.11},
      url = {https://doi.org/10.11648/j.se.20150303.11},
      eprint = {https://download.sciencepg.com/pdf/10.11648.j.se.20150303.11},
      abstract = {Selection of feasible cutting patterns in order to minimize the rawmaterial wastage which is known as cutting stock problem has become a key factor of the success in today’s competitive manufacturing industries. In this paper, solving a one-dimensional cutting stock problem is discussed. Our study is restricted to rawmaterial (main sheet) in a rectangular shape (different sizes), and cutting items are also considered as rectangular shape with known dimensions (assume that lengths of the main sheets and cutting items are equal). Pattern generation technique is used to nest the pieces of cutting items within the main sheet by minimizing rawmaterial wastage. A computer program using Matlab software package is developed to generate feasible patterns using the above algorithm for 1D cutting stock problem. Location of each feasible cutting pattern inside the main sheet is given in Cartesian Coordinate Plane. The Branch and Bound approach in solving integer programming problems is used to solve the problem.},
     year = {2015}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Modified Method for One-Dimensional Cutting Stock Problem
    AU  - Niluka Rodrigo
    AU  - WB Daundasekera
    AU  - AAI Perera
    Y1  - 2015/10/19
    PY  - 2015
    N1  - https://doi.org/10.11648/j.se.20150303.11
    DO  - 10.11648/j.se.20150303.11
    T2  - Software Engineering
    JF  - Software Engineering
    JO  - Software Engineering
    SP  - 12
    EP  - 17
    PB  - Science Publishing Group
    SN  - 2376-8037
    UR  - https://doi.org/10.11648/j.se.20150303.11
    AB  - Selection of feasible cutting patterns in order to minimize the rawmaterial wastage which is known as cutting stock problem has become a key factor of the success in today’s competitive manufacturing industries. In this paper, solving a one-dimensional cutting stock problem is discussed. Our study is restricted to rawmaterial (main sheet) in a rectangular shape (different sizes), and cutting items are also considered as rectangular shape with known dimensions (assume that lengths of the main sheets and cutting items are equal). Pattern generation technique is used to nest the pieces of cutting items within the main sheet by minimizing rawmaterial wastage. A computer program using Matlab software package is developed to generate feasible patterns using the above algorithm for 1D cutting stock problem. Location of each feasible cutting pattern inside the main sheet is given in Cartesian Coordinate Plane. The Branch and Bound approach in solving integer programming problems is used to solve the problem.
    VL  - 3
    IS  - 3
    ER  - 

    Copy | Download

  • Sections