Modified Method for One-Dimensional Cutting Stock Problem

Niluka Rodrigo; WB Daundasekera; AAI Perera

doi:doi:10.11648/j.se.20150303.11

| Peer-Reviewed

Modified Method for One-Dimensional Cutting Stock Problem

Niluka Rodrigo, WB Daundasekera, AAI Perera

Published in Software Engineering (Volume 3, Issue 3)

Received: 3 September 2015 Accepted: 23 September 2015 Published: 19 October 2015

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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.

Published in	Software Engineering (Volume 3, Issue 3)
DOI	10.11648/j.se.20150303.11
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), 2015. 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.

Cite This Article

Plain Text BibTeX RIS

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://article.sciencepublishinggroup.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

Author Information

Niluka Rodrigo

Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka
WB Daundasekera

Department of Mathematics, Faculty of Science, University of Peradeniya, Peradeniya, Sri Lanka
AAI Perera

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

Download PDF

Sections

Plain Text BibTeX RIS

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://article.sciencepublishinggroup.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