Cutting Stock Problem Based on the Linear Programming Approach

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
This thesis considers the application of the Cutting Stock Problem based on the Linear Programming Approach. This is applied in the cutting of paper, glass, steel rod, wood etc. In this thesis, we apply a variant of it, the One-dimensional Cutting Stock Problem, to the cutting of wood in a sawmill. In a sawmill, boards are first cut along their width (rip) into strips, then the obtained strips are cut along their length (strip cut) into cut-pieces with specific length and demand. The thesis focuses on using simplex algorithm to find optimal cutting patterns. In the simplex algorithm, to determine the entering column (pattern), we solve sub-problem. The sub-problem is of a knapsack type and we solve it using dynamic programming. We develop a computer program based on the above approach to generate optimal cutting patterns.
A thesis submitted to the Department of Mathematics, Kwame Nkrumah University of Science and Technology, Kumasi in partial fulfilment of the requirements for the degree of Master of Science Industrial Mathematics
Linear programming, One-dimensional Cutting Stock Problem, knapsack problem, simplex algorithm, dynamic programming