Modified Method for One-Dimensional Cutting Stock Problem
Volume 3, Issue 3, September 2015, Pages: 12-17
Received: Sep. 3, 2015;
Accepted: Sep. 23, 2015;
Published: Oct. 19, 2015
Views 3867 Downloads 161
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
Follow on us
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.
Cutting Stock Problem, Branch and Bound Algorithm, Pattern Generation, Matlab Software Package
To cite this article
Modified Method for One-Dimensional Cutting Stock Problem, Software Engineering.
Vol. 3, No. 3,
2015, pp. 12-17.
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.
Gilmore PC, Gomory RE. A Linear Programming Approach to the Cutting Stock Problem – Part II. Operations Research. 1963; 11(6):8 63–888.
Saad M. A Suliman, “Pattern generating procedure for the cutting stock problem”, International Journal of Production Economics 74 (2001) 293-301.
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.
Beasley JE. Algorithms for Unconstrained Two-Dimensional Guillotine Cutting. Journal of Operations Research Science. 1985; 36(4):297–306.
Rodrigo WNP, Daundasekera WB, Perera AAI, “Pattern Generation for One-Dimensional Cutting Stock Problem”, Peradeniya University Research Session (PURSE), 2011.
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.
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.
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.
Robert W. Haessler and Paul E. Sweeney, “Cutting Stock Problem and Solution Procedures”, European Journal of Operational research 54 (1991), 141 – 150.