Solving a cutting Stock Problem using Optimization تقليل الفاقد في تقطيع المخزون باستخدام البرمجة الخطية
Hey everyone! It's me Shouq. This is a project for an Industrial Engineering class called Operational research / optimization - OR1 - IE335 which I took in Fall 2017 in the American University of the Middle East (AUM) in Kuwait.
Abstract
The objective
of this report is to show our work in how to solve a cutting stock problem using
the operational research method. First, a clear description of the problem is provided
with every detail regarding it. Then the decision variables are identified as
well as the objective functions and the constraints of the problem. After that
a final linear programming formulation will be presented. Also, the problem is solved
using Lingo and Excel solver to find the answer of the linear programming
problem. As well as a what-if will be presented after a sensitivity analysis is
found.
Keywords: cutting, stock, analysis, problem, operational,
research.
Introduction
Cutting stock
problem is a serious problem that many industries suffer from for several
reasons. The cutting stock problem is the problem of cutting specific sized
pieces of stock material. It is an operational research problem where we need to
follow an optimization approach to try and find the best cutting patterns where
the amount of wasted material during this process will be minimized. It shows
that many company working with stocks suffers from this kind of lose.
The cutting
stock problem is interesting due to its complication due to the linear
programming formulation being unclear from first sight as well as the fact that
most people will choose the pattern where the waste is zero, but that is not necessarily
the right solution as we need legs for the different sizes of chairs and not
just one specific type. Being able to solve the cutting stock problem is very
important as it will not only help companies and factories, but will help individuals
as well as the cost of the product may be reduced when the amount of waste is
being minimized.
The cutting stock problem could occur in many industries including
the steel industry as well as in the paper roll industry, wood industry, glass
industry as well as in cloth industries and other industries too where we try
to minimize the amount of waste after cutting.
One of the companies that face the cutting stock problem is Ikea as
it works with woods and building furniture.
Background and literature
review
We are not the earliest or the first people ever to work on the
cutting stock problem as it is a very common issue that has a history that goes
years ago.
The cutting stock problem is very common in the paper industry as
when customers ask for specific orders based on the cutting patterns, it may
end up with some waste that when get added together will cost the company. The
cutting stock problem was first showed to the world by a Russian man called Kantorovich
in 1939 (Kantorovich, 1939). The purpose behind it is
minimizing the number of rolls in order to cut specific things and satisfy the
required demands while not wasting much material at the same time. He won the
Nobel Prize for that study regarding the Mathematical Methods of Organizing and
Planning Production.
In 1983 a person called Vasek Chvantal tried to solve the cutting
stock problem in paper industry as well where there was a fixed width equal to
100 inches (Chvatal, 1983). Chvantl tried
to find the cutting patterns of the rolls which can give him roll of widths 14,
31, 36, and 45 inches as well as minimizing the waste as possible (Chvatal, 1983).
Description and presentation
In this project we have a company
that produces desks for students from different ages which indicates that the
length of the legs of the desks should vary.
We have two different steel bars which are 150
cm bar and 200 cm bar. Even though the diameters of the legs are the same, they
vary when it comes to the length of it. The lengths of the legs are 40 cm for
the kindergarten students, 65 cm for the primary and secondary students, while
for university students the length of the leg will be 85 cm.
It is very
clear that we are facing a cutting stock problem in this situation where we will
most likely end up having some trim loss. If we took the steel bar of 200 cm,
we can cut it by taking 3 legs where each one of them is 65 cm. In this case
the waste will be 5 cm which is very small compared to the other amount of waste
that will be found if we used another cutting pattern. We are still facing a
problem which is the fact that each chair will need 4 legs as well as the fact
that we do not have any legs of size 40 cm or even size 85 cm. It is very
important to have chairs of legs of size 40 cm, 65 cm and 85 cm.
Another cutting
pattern that we can use by taking the steel bar of size 500 cm is by cutting
one of size 40 cm and one of size 85. Even in this cutting patter we are facing
some problems. The first one is to not have any cutting patterns in 65.
In general, we
know that in a bar of size 200 cm, we have 19 cutting patterns where all of
them have an amount of waste. The same strategy goes to the steel bar of size
500 cm which has 32 different cutting patterns. The purpose of all of these
different cutting patterns with the two different sizes of steel bars is to
satisfy constrains as well as to minimize the waste. You can see the table of
patterns in Appendix A.
The Linear Programming formulation
Decision variable
Objective function
Equation 1
The objective function of the problem is minimization
where we have to minimize the loss for every single one of the 60th different
cutting patterns. From Equation 1 above, we know that the Z is equal to the
summation of coefficients multiply by variable of objective functions
corresponding to the number of patterns Xi that we have
where I could be any number between 1 and 60.
Subject to
Equation 2
From equation 2, we know that the first constraint
represents the number of cutting patterns Xi that are used
for product 1. We also know that the summation of Xi multiplied by
coefficients present of number of cutting patterns should be greater than or
equal to the demand. The demand for the first demand is equal to 175. So in
order of us to satisfy the need, we multiplied the demand with 4 as we have
four legs for each table for product one. That means 175 multiplied with 4 which
will be equal to 700.
Equation 3
From equation 3, the second constraint represents the
number of cutting patterns Xi that are used
for product 2. We also know that the summation of Xi multiplied by
coefficients present of number of cutting patterns should be greater than or
equal to the demand. The demand given for the second demand is equal to 156. So
in order to satisfy the need, we multiplied the demand with 4 as we have four
legs for each table for product two. That means 156 multiplied with 4 which
will be equal to 624.
Equation 4
From equation 4, the third constraint represents the
number of cutting patterns Xi that are used for product 3. We also know that
the summation of Xi multiplied by
coefficients present of number of cutting patterns should be greater than or
equal to the demand. The demand given for the second demand is equal to 141. So
in order to satisfy the need, we multiple the demand with 4 as we have four
legs for each table for product three. That means 141 multiplied with 4 which
will be equal to 564.
Equation 5
From equation 5, it is a non-negativity constraint as
for every Xi the value has to
be zero or more than zero which means a positive number only as it does not
make any sense to produce a negative numbers of products, so the smallest
number for the production is either zero where we produce nothing or the amount
of more than zero.
Conclusion
Figure 1: The final linear programming
Solution
In order to find the solution of the above
problem, we are going to solve it using Lingo and Excel solver as well. First
we will start by using Lingo and its functions. Then we will use Excel solver to
find the
Lingo
We will first
start by solving the problem in Lingo, and for Lingo we will use sets function.
As shown in Appendix C the variables regarding the problem was introduced at
first. After that the data provided in Appendix A will be fully copied in Lingo
with the patterns divided by types as 1 and 2. We also used several functions
in order to reach the final solutions. Some of the functions that we used are
Gin and Sum functions as our problem is a minimization problem. The use of the
Gin function is for making sure that integer only can be used in the pattern
utilization. The constraints that are mentioned in the final linear formulation
were written on the Lingo coding with everything else.
Excel
In this
project, we used the Excel and specifically Excel solver to find the final
solution of the linear programming model of the provided problem. As showed in Appendix
D, we defined the objective function of the problem that is minimization to
minimize the loss for every single one of the 60th different
patterns. Moreover, we get the value of (Z) by summation of coefficients
multiplying by the variable of losses with the decision variables. In addition;
we figured out the number of objective function (Minimize Z = 6129) by using
the Excel solver. Therefore; we defined the constraints which are: small,
medium, large as the lengths of legs by multiplying the number of legs with the
decision variables. As shown, the value of the constraints does not exceed the
number of 700, 624, and 564 which are perfect.
Sensitivity analysis
The optimal solution of the earlier linear
programming problem is to produce zero chairs of all patterns except pattern number 3 where we need to
produce one chair only. Also, from pattern number 9 we have to produce 564 chairs. Then we will
end with having to produce 19 chairs of pattern 35. The solution mentioned
above in Appendix E shows that we have a daily goal of making 700 chairs of
size small while when it comes to chairs of medium size, the goal is 624 chairs. Finally, the
goal of chairs of size large is 564,
and actually these values are exactly equal to the constraints.
What if analysis
1.
What will happen if we decrease the right hand side (RHS) by 1 unit for of product?
Coefficient of X3 and by decreasing 1 unit X3 = 4 ,
which it in the range.
So Ƶ = 4 (1) + 10 (564) + 25 (19) = 6119 .There is a change in Z by 1 unit.
2.
Assume increasing Large by 20 what will be the value of Z and is it
feasible?
From the second
table of Appendix E, Large C3 = 564 – 20 = 544 (in the range). Ƶ = 6120 + 3*D1 + 2*D2 + 5*D3 = 6120+ 5*20 = 6220 unit.
3.
Assume we want to decrease
the Z value to 6100? And how can we achieve this?
Ƶ = 6120 – 6100 =
20 And since Ƶ = 6120 + 3*D1 + 2*D2 + 5*D3, we have the following options:
·
D1=
20/3 = 6
C1= 700 + 6 = 706 so increase the demand of small to 706.
·
D2=
20/2 = 10
C2= 624 +10 = 634 so increase the demand of medium to 634.
·
D3=
20/5 = 4
·
C3=
564 + 4 = 568 so increase the demand of large to 568.
4.
What will happen if we
increase the right hand side (RHS) by 2 units for of product?
Coefficient of X4 = 30 and by increasing 2 units X4 = 32,
which is out of the range. And there is no change in Z because the final value for X4 is zero which will have no effect with
multiplying.
5.
What will happen if we increase the right hand side (RHS) by 3 units for of product?
Coefficient of X4 = 30 and by increasing 3 units X4 = 33,
which is out of the range. And there is no change in Z because the final value for X4 is zero which will have no effect with
multiplying.
Difficulties and challenges
We have faced many problems while trying solving this
linear programming. First of all, the problem for the project was not well
explained, so we had to do a lot of searches regarding the cutting stock
problems to know more about it and to understand the best way to solve it. The
reason behind all of that was to find linear programming model which was the
hardest part as it was not a familiar problem. That was very challenging.
Another problem we faced while trying to solve
this cutting stock program was the fact that we had to use specific software programs
like MS project and Lingo to make the Gantt chart and find the solution of the
LP problem using Lingo. We do not have these programs at home, and it was
difficult to find empty labs to do the work as these software programs are not
even in the university library.
Finally,
the problem has a higher amount of information that is important and difficult
for students to process. This fact caused us to spent longer time trying to try
and to distinguish between the objective, the constraints, and the decision
variables which was very tricky.
Work schedule and Gantt chart
Saturday
|
Sunday
|
Monday
|
Tuesday
|
Wednesday
|
Thursday
|
Friday
|
|
9am -10 am
|
|||||||
10 am - 11 am
|
Meeting to work on the project
|
||||||
11 am - 12 am
|
|||||||
12 am - 1 pm
|
Meeting
to work on lab report
|
||||||
1 am - 2 pm
|
|||||||
|
In order to organize the
project work between group mates, a work schedule is being made. Every week
there is a meeting from 10 am until 11 am in both Sunday and Saturday. These
meetings are important for the project to be done in the right time following
all the requirements for it. On the other hand, another meeting will take place
on Wednesday from 12 am until 1 pm
to discus things regarding lab reports.
In the Gantt chart in Figure 6 we noticed
that all the steps that are needed in order to finish every single deliverable of
the project are being mentioned. Also, the names of the students that are
responsible of these steps are written up there in the timeline that is on the
right side of the Gantt chart.
Deliverable one of the project has been
completed already. It was a collaborative work between all group members. On
the other hand, the second deliverable of the project is under the process and
will be done in several hours. The second deliverable of the project includes
many parts and steps which can be seen clearly in Appendix B.
Conclusion
In conclusion, in the project we talked
about the cutting stock problems and we talked about the industries that go
through this problem. Also, a background and literature review regarding the
cutting stock problem was written. Not to mention the fact that we discussed
the problem that we have to solve and we wrote a description regarding it. Then
we found the linear programming formulation of the problem. Finally, a solution
of the problem was found using Lingo and Excel solver. We also did a
sensitivity and what-if analysis.
In order to organize all the processes
regarding the project, a Gantt chart and a work schedule were formatted. It
also helps to make students understand what is required from them and what they
should start working on next.
References
Chvatal, V. (1983). The Cutting Stock Problem | NEOS. Neos-guide.org. Retrieved 21
October 2017, from https://neos-guide.org/content/cutting-stock-problem
Kantorovich, L. (1939). Mathematical Methods of Organizing
and Planning Production. Ideas.repec.org.
Retrieved 21 October 2017, from https://ideas.repec.org/a/inm/ormnsc/v6y1960i4p366-422.html
Gilmore, P., & Gomoy, R. (1963). A linear programming approach to
the cutting porblem - part II. Retrieved 21 October 2017, from http://www4.ncsu.edu/~kksivara/ma505/handouts/gilmore-gomory2.pdf
Appendix
Appendix
A: The table of patterns
pattern
|
Leg types
|
loss
|
|||
Raw Material 1 length 200
|
40
|
65
|
85
|
in cm
|
|
1
|
0
|
2
|
0
|
70
|
|
2
|
0
|
1
|
1
|
50
|
|
3
|
1
|
1
|
1
|
10
|
|
4
|
0
|
3
|
0
|
5
|
|
5
|
1
|
0
|
1
|
75
|
|
6
|
4
|
0
|
0
|
40
|
|
7
|
0
|
0
|
2
|
30
|
|
8
|
3
|
0
|
0
|
80
|
|
9
|
2
|
0
|
1
|
35
|
|
10
|
0
|
3
|
0
|
5
|
|
11
|
1
|
2
|
0
|
30
|
|
12
|
1
|
1
|
0
|
95
|
|
13
|
3
|
1
|
0
|
15
|
|
14
|
0
|
0
|
1
|
115
|
|
15
|
2
|
1
|
0
|
55
|
|
16
|
1
|
0
|
0
|
160
|
|
17
|
2
|
0
|
0
|
120
|
|
18
|
0
|
1
|
0
|
135
|
|
19
|
0
|
0
|
0
|
200
|
|
raw material 2 length 500
|
20
|
1
|
0
|
1
|
375
|
21
|
1
|
1
|
1
|
310
|
|
22
|
0
|
2
|
2
|
200
|
|
23
|
2
|
2
|
3
|
35
|
|
24
|
1
|
2
|
2
|
160
|
|
25
|
2
|
2
|
2
|
120
|
|
26
|
0
|
7
|
0
|
45
|
|
27
|
7
|
3
|
0
|
25
|
|
28
|
10
|
0
|
0
|
100
|
|
29
|
6
|
0
|
0
|
260
|
|
30
|
7
|
0
|
0
|
220
|
|
31
|
4
|
2
|
0
|
210
|
|
32
|
9
|
0
|
1
|
55
|
|
33
|
0
|
1
|
0
|
435
|
|
34
|
0
|
0
|
0
|
500
|
|
35
|
1
|
1
|
2
|
225
|
|
36
|
0
|
1
|
2
|
265
|
|
37
|
1
|
4
|
2
|
30
|
|
38
|
2
|
2
|
0
|
290
|
|
39
|
0
|
1
|
1
|
350
|
|
40
|
0
|
2
|
1
|
285
|
|
41
|
0
|
4
|
2
|
70
|
|
42
|
3
|
0
|
3
|
125
|
|
43
|
4
|
1
|
0
|
275
|
|
44
|
3
|
1
|
0
|
315
|
|
45
|
2
|
0
|
0
|
420
|
|
46
|
4
|
0
|
0
|
340
|
|
47
|
5
|
0
|
0
|
300
|
|
48
|
1
|
0
|
0
|
460
|
|
49
|
3
|
0
|
1
|
295
|
|
50
|
11
|
0
|
0
|
60
|
|
51
|
0
|
2
|
2
|
200
|
|
52
|
2
|
0
|
2
|
250
|
|
Appendix B: Gantt chart
Appendix
C: The lingo coding of the mentioned problem
SETS:
TYPE: RAW, LEG1, LEG2, LEG3, LOSS,
PATTERNUTILIZATION, PRODUCEDWASTE;
ENDSETS
DATA:
TYPE RAW LEG1
LEG2 LEG3 LOSS=
1 1 0 2 0 70
2 1 0 1 1 50
3 1 1 1 1 10
4 1 0 3 0 5
5 1 1 0 1 75
6 1 4 0 0 40
7 1 0 0 2 30
8 1 3 0 0 80
9 1 2 0 1 35
10 1 0 3 0 5
11 1 1 2 0 30
12 1 1 1 0 95
13 1 3 1 0 15
14 1 0 0 1 115
15 1 2 1 0 55
16 1 1 0 0 160
17 1 2 0 0 120
18 1 0 1 0 135
19 1 0 0 0 200
20 2 1 0 1 375
21 2 1 1 1 310
22 2 0 2 2 200
23 2 2 2 3 35
24 2 1 2 2 160
25 2 2 2 2 120
26 2 0 7 0 45
27 2 7 3 0 25
28 2 10 0 0 100
29 2 6 0 0 260
30 2 7 0 0 220
31 2 4 2 0 210
32 2 9 0 1 55
33 2 0 1 0 435
34 2 0 0 0 500
35 2 1 1 2 225
36 2 0 1 2 265
37 2 1 4 2 30
38 2 2 2 0 290
39 2 0 1 1 350
40 2 0 2 1 285
41 2 0 4 2 70
42 2 3 0 3 125
43 2 4 1 0 275
44 2 3 1 0 315
45 2 2 0 0 420
46 2 4 0 0 340
47 2 5 0 0 300
48 2 1 0 0 460
49 2 3 0 1 295
50 2 11 0 0 60
51 2 0 2 2 200
52 2 2 0 2 350;
ENDDATA
MIN=@SUM(TYPE(I):PRODUCEDWASTE(I));
@FOR(TYPE(I):PRODUCEDWASTE(I)=PATTERNUTILIZATION(I)*LOSS(I));
@FOR(TYPE(I):@GIN(PATTERNUTILIZATION(I)));
@SUM(TYPE(I):PATTERNUTILIZATION(I)*LEG1(I))>=175;
@SUM(TYPE(I):PATTERNUTILIZATION(I)*LEG2(I))>=156;
@SUM(TYPE(I):PATTERNUTILIZATION(I)*LEG2(I))>=141;
Appendix
D: The table used to find the solution in Excel
Appendix
E: The sensitivity analysis
The students who worked in this project are
Knowing that not all students in the group have put equal efforts while working on this project. Some students worked harder than others, and it is normal when it comes to working on groups.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||