Advances in Mathematical
Sciences and Applications
Vol. 26, No. 1 (2017), pp. 175–191

GAKKOTOSHOTOKYO JAPANPRODUCTION PLANNING OF A MANUFACTURING
INDUSTRY USING LINEAR PROGRAMMING

Glaucia Maria Bressan ∗; Giovanna Peral Salvadeo;
André Luis Machado Martinez; Elenice Weber Stiegelmeier;
Roberto Molina de Souza
Federal University of Technology of Parana - Brazil
Mathematics Department
1640, Alberto Carazzai, 86300-000, Cornélio Procópio(E-mail: glauciabressan@utfpr.edu.br)

Abstract.
Considering the intensification of technology in the 21st century, studies
of optimization models have been necessary for the control and planning of productive
systems. In this scenario, the goal of this paper is to minimize the production costsof a manufactory by applying the Combined Problem, which couples the lot sizing andstock cutting problems. Numerical data are collected from a small-scale furniture plant,
located in Cornélio Procópio city, in the state of Paraná, Brazil. Two production planningscenarios are considered: first, costs and demands of the final products are constants;
second, costs and demands vary over periods of planning. Case study involving larger data
is simulated. Numerical solutions are obtained from the application of the Simplex methodwith computational support and indicates the quantity to be produced in each planning
period. These results are compared with the case experienced by the manufactory, whose
production is made considering the demand by period. The production planning obtainedby linear programming provides support to the decision make of the manufactory.
∗

corresponding author: glauciabressan@utfpr.edu.br
Communicated by Editors; Received July 7, 2017.
AMS Subject Classification: 90B30, 90C05, 90C10, 90C90.
Keywords: Modeling, Optimization, Numerical Simulation, Lot sizing, Stock cutting, Simplex Method.

175

176

1

Introduction

Due to technological and computational advances, manufacturing industries have beenencouraged to make their processes more efficient and competitive, while minimizing
global production costs. Reducing expensive raw material waste is an important goalin the industry. Thus, the study of optimization models for the control and production planning becomes an essential tool for industrial advancement, motivating academic
researches.
In this scenario, the Operational Research has great importance and can be defined
as a science that solves problems quantitatively, using mathematical and statistical methods, and it helps making the best decisions. The scientific component is related to themathematical modeling of decision problems, determining the objectives and constraints
under which to operate [2].
Production management within an industry is responsible for planning and controlling
the transformation of raw materials into final products. The system responsible for thismanagement is called Production Planning and Control (PPC) [4], which coordinates theactivities, from the acquisition of raw materials to the delivery of the final products. Thisway, the Operational Research and its optimization methods have great utility in solving
problems, especially those involving productive processes, decision making and systems
management, selecting the best decisions, among all possible ones [9].
Usually, industries produce pieces of different sizes and materials in order to constructa final product. In this process, industries worry about the waste of raw materials, since
this implies a profit reduction. Then, the question is to solve an optimization problem,
which consists of cutting objects, observing these issues.
In [5], two robust mixed integer programming models are proposed. In the first one,the non-overlapping constraints are stated based on direct trigonometry and in the second
one, pieces are decomposed into convex parts and then the non-overlapping constraints
are written based on nofit polygons of the convex parts. Two-dimensional irregular strip
packing problems consist of cutting and packing problems in which an object must be cut
in small pieces, involving a non-trivial handling of geometry. Computational experimentswith benchmark instances show that second model outperforms the first one and also thebest exact model published in the literature.
In this sense, in [11], two-dimensional irregular cutting stock problem with demand isstudied, in which the required pieces has to be produced from large rectangular sheet minimizing material waste. Greedy randomized adaptive search procedure (GRASP) metaheuristic algorithm is adapted to tackle the problem by providing high-quality solution in
an appropriate time.
About three-dimensional cutting problems, in [14] the cutting problem of a marble
processing factory is described. In order to minimize total spoilage of marble while finding
the cutting designs of marble blocks and marble planes, integer programming approaches
were developed and satisfactory results were reached.
In [1], an integrated production planning and cutting stock problem is investigated.
This kind of problem appears frequently in small-scale furniture plants. The production
costs contained in the manufacturing process and the products demands are not known.
Since there are uncertainties, robust optimization models were proposed. These models

177
control the conservatism of the solution according to the attitude of the decision makertowards risk.
The purpose of [6] is to solve the problem of optimizing the production on the basis of
the commercial value of the cuts, since the loss of raw materials in wood cutting industries
has reached high. This work was completed with the design and the presentation of asoftware package called cutting optimizer.
The study of [15] deals with a case in which there are several stock lengths available
in limited quantities. The heuristic methods are empirically analyzed by solving a set of
randomly generated instances and a set of instances from the literature. The proposed
methods presented very small objective function value gaps.
Fast heuristics, Integer Linear Programming models and a truncated Branch-andPrice algorithm for a wooden board Cutting Stock Problem are proposed in [10]. They
consider the maximization of the cutting equipment productivity, which can be obtainedby cutting identical boards in parallel. Experiments show that the productivity can be
improved with a minimal increase in the total area of used boards.
In the context of stock cutting and lot sizing problems, the goal of this work is to
propose the application of a mathematical model to a real case of a manufactory, inorder to minimize the global production costs. Real data are collected from a small-scalefurniture plant, located in Cornélio Procópio city, in the state of Paraná, Brazil. Costs anddemands vary over periods of planning, which represents a more realistic situation. Two
production planning scenarios are considered: costs and demands of the final products
constants and costs and demands vary over periods of planning. Case study involving
big data is simulated. Numerical results from this study are compared with the casewhose production is made considering the demand by period. The main contribution isto propose an efficient production planning, using linear programming, providing support
to the decision make of the manufacturing industry.

2

The Combined Problem

In the process of cutting a board into smaller pieces, for producing items, material loss
tends to be increasingly reduced if the cuts are rearranged in a convenient way on theboard. Due to this fact, there is an economic pressure to manufacture some products
in advance in order to minimize losses. However, this stock can generate costs that canmake the production slower [3]. This decision problem is called Combined Problem, which
couples two optimization problems: the lot sizing and cutting stock [8].
The lot sizing problem is to plan the amount of items to be produced in various stages
in each period over a horizon of finite time, in order to meet demand and to optimize an
objective function, as minimizing production and storage costs[2]. It can be classified as
mono-stage, where items are independently produced, and multistage, where productionsof items are dependent.
The cutting stock problem consists in optimizing the process of cutting boards into
smaller pieces in quantities and sizes demanded. Cutting pattern is defined as the arrangement of the pieces within each board, that is, the way an object (piece) is cut toproduce demanded items. Some rules are defined, such as guillotine cuts (where each cut

178
made on a rectangular board produces two new rectangles), limiting pieces (restricted orunrestricted cuts), number of stages (2-stages is when Only one change in the directionof guillotine cuts is allowed: horizontal / vertical or vertical / horizontal). In addition,
the problem will be two-dimensional when two dimensions are relevant for cutting.
Thus, the goal of the combined problem is to decide the number of final products to be
produced in each planning horizon period in order to minimize production, preparationand storage costs (lot sizing) and the number of boards to be cut, as well as cutting
patterns to compose final products (cutting stock) [8]. In real situations, most industries
approach these two problems separately, which can raise global costs.
One approach to the combined problem disregards preparation costs and relaxes theintegrality of the variables representing the number of boards cut in a given pattern, which
requires a large demand. This approach can be applied in the furniture industry where
wooden boards must be cut to produce items. It is considered that there is only one typeof board and parameters like costs and demands are varied [3].
Indexes:
t=1, ..., T number of periods of time.
p=1, ..., P number of different pieces to be cut.
j=1, ..., N number of different cutting pattern.
i=1, ..., M number of different final products.
Parameters:
cit : production cost of the final product i in the period t.
hit : stocking cost of the final product i in the period t.
hppt : stocking cost of the piece p in the period t.
dit : demand of the final product i in the period t.
rpi : number of pieces p required to make product i.
vj : time to cut a board using cutting pattern j.
apj : number of piece p cut using cutting pattern j.
ut : maximum time of saw capacity.
cp: cost of the board to be cut.
Decision Variables:
xit : number of final product i produced in the period t.
eit : number of final product i stocked in the end of the period t.
eppt : number of piece p stocked in the end of the period t.
yjt : number of boards cut using cutting pattern j in the period t.
The mathematical model is formulated according to [3] and it is described as equations(1) to (5).
min

M X
T
X
i=1 t=1

subject to:(cit xit + hit eit ) +N X
TX
j=1 t=1

cpyjt +P X
TX
p=1 t=1

hppt eppt

(1)

179

xit + ei,t−1 − eit = ditNX

apj yjt + epp,t−1 − eppt =

j=1

M
X

rpi xit(2)∀ t = 1...T

(3)

i=1
N
X

vj yjt ≤ ut

(4)

j=1

xit , eit , yjt , eppt ≥ 0(5)

The restrictions (2) are related to the stock balance equations in relation to final
products, which ensures that the demand for items from each period will be met. The
restrictions (3) are related to stock balance equations in relation to pieces, which ensuresthat the demand for pieces will be satisfied. These restrictions are those that couple the
lot sizing and stock cutting problems since both include the xit variables, which define
the lots size and yjt , which define the number of boards cut in a certain cutting pattern.
The restrictions (4) are related to saw capacity, which ensures that the time spent in the
cutting process of the boards in the various cutting patterns does not exceed the available
capacity of the saw, that is, its maximum operating time. And, finally, (5) represents
non-negativity conditions.
The application of Simplex Method [2, 9] with columns generation [7] has been presented, in the literature, as a very efficient strategy to solve this kind of linear problem.

3

Simplex Method

The Simplex Method, applied to provide the solution of Linear Programming Problems,
can be used to solve real situations that involve lot sizing and cutting stock problems[2, 9].
The Simplex Method, developed in 1947 by the North American mathematician George
B. Dantzig, consists of an iterative numerical procedure, which executes repeatedly a sequence of steps, in order to reach the best solution of the problem, called optimal solution,
if it exists. The procedure starts from a viable basic solution, belonging to a vertex, ofthe system of equations that represents the constraints of the problem. From this initial solution, the algorithm identifies new viable solutions of equal or better value thancurrent. Thus, the process finds new vertices of the convex envelope of the problem anddetermines if this vertex is optimal or not, that is, if the change of variables in the basecan still improve the objective function. Since the Simplex Method is an iterative process,can be implemented using any programming language to execute its iterations [3].
The algorithm of the Primal Simplex Method is described below.

180
phase I
Find a primal-feasible basic partition: A = (B, N ).
Do STOP=FALSE, IT=0
(It will be FALSE until the optimality condition is verified. IT indicates the iteration
number.)phase II
While NOT STOP do:• Determine the basic feasible primal solution: xB = B −1 b.
• Optimality test:
Determine the dual basic solution: y T = cTB B −1 ;Find xk with relative cost: ck − y T ak < 0.
If ck − y T ak ≥ 0, ∀ k = 1, . . . , n − m, then the IT iteration solution is optimal.
STOP=TRUE.
Else:• Find the simple direction: dB = −B −1 ak , of change in the values of the basic
variables.
o
n x0
Be
0
• Determine the step:  = min − dB |dBe < 0, i = 1, . . . , m .
e
If dB ≥ 0, the problem does not have optimal finite solution.
STOP=TRUE.
else:• Update the basic partition: aBl ↔ ak , IT ← IT + 1.
end while.

4

Case Study

In order to execute the Combined Problem, values were assigned to its parameters derived from data provided by a small-scale furniture plant, located in the city of Cornélio
Procópio, in the state of Paraná, Brazil. So that it was possible to decide on two productions scenarios described below. Both consider producing two types of end products:
tables and chairs. In addition, in both cases, it is considered that there is no stock in
the previous period t − 1. For each scenario, it is firstly assumed that costs and demandvalues are constant throughout the production planning periods and, subsequently, thevariation of these parameters over the periods.

181

4.1

The First Production Planning Scenario

Considering costs and the demand for final products constants, the following data isavailable in the first production planning scenario:
t = 6 time periods
p = 3 pieces
j = 5 types of board cutting patterns
i = 2 final product (table and chair)
The pieces for the composition of the final products are:
Piece 1: cover
Piece 2: footPiece 3: seat/backrest
The variable x1t represents the product “table”, whose production cost is c1t =R$255
and the demand is d1t =2 for t = 1, ..., 6. The variable x2t represents the product “chair”,
whose production cost is c2t =R$80 and the demand is d2t =3 for t = 1, ..., 6. The numberof pieces p required to make final product i can be seen in Table 1. The other parametersprovided from the manufactory are:cp = R$120,
ut = 300 hours per period,
apj can be seen in Table 2,
r11 = 1, r21 = 5, r32 = 2, r22 = 6,
h1t = 3, h2t = 1,
hp1t = 0, 2, hp2t = 0, 3, hp3t = 0, 5.
Table 1: Number of pieces p required to make product i
Piece Table Chair
p=1
1
0
p=2
5
6
p=3
0
2

Table 2: Cutting Patterns: first production planning scenario
Pattern Piece 1 Piece 2 Piece 3 Time
j=1
2
0
0
v1 =1sj=2
1
880
v2 =1.2s
j=30035
v3 =1.5s
j=40045
v4 =1.4s
j=51
815
v5 =1.5s

The pieces to be cut are cover (p = 1), foot (p = 2) and seat/backrest (p = 3). The
cutting patterns shown in Table 2 are pre-set by the manufactory, according to the ca-

182
pacity of the equipment and the available labor.
The second production planning considers that costs and demands are variables throughout the planning periods. The new parameters provided by the manufactory under study
are described below. The production costs of final products can be seen in Table 3, whichcorresponds to parameters cit .
The cost of the board to be cut is cp = 135.07. The stocking costs of the final products
are shown in Table 4 (parameters hit ) and the stocking costs of the pieces are shown in
Table 5 (parameters hppt ).
Table 6 shows the demands (dit ) of the final products.

Table 3: Production costs of the final product i in the period taaaTime periodaaaaaFinal productaaa
a

Table
Chair

t=1

t=2

t=3

t=4

t=5

t=6

R$ 255
R$ 80

R$ 255
R$ 80

R$ 255
R$ 80

R$ 267.75
R$ 84

R$ 267.75
R$ 84

R$ 267.75
R$ 84

Table 4: Stocking cost of the final product i in the period taaaa Time period
aa
t=1
aa
a
Final product aa
a

Table
Chair

R$ 3
R$ 1

t=2

t=3

t=4

t=5

t=6

R$ 3
R$ 1

R$ 5
R$ 3

R$ 5
R$ 3

R$ 5
R$ 3

R$ 5
R$ 3

Table 5: Stocking cost of the piece p in the period taaaa Time periodaaaaaa
Pieces
aa

p=1
p=2
p=3

t=1

t=2

t=3

t=4

t=5

t=6

R$ 0.20
R$ 0.30
R$ 0.50

R$ 0.20
R$ 0.30
R$ 0.50

R$ 0.50
R$ 0.60
R$ 0.80

R$ 0.50
R$ 0.60
R$ 0.80

R$ 0.50
R$ 0.60
R$ 0.80

R$ 0.50
R$ 0.60
R$ 0.80

The optimal solution of these two problems, following the application of the algorithm
Simplex, should indicate in which period of the planning horizon and in what quantity
the final products must be produced, so as to obtain the minimum cost of cutting andstock, respecting the stock balance restriction to final products and boards, the capacity
constraint of the saw and the non-negativity conditions.

183

Table 6: Demand of the final product i in the period taaaa Time period
aa
t=1
aa
a
Final product aa
a

Table
Chair

2
3

t=2

t=3

t=4

t=5

t=6

3
5

2
4

4
6

1
3

3
4

The design of table and chair (final products) produced in this scenario is illustrated
in Figure 1.

Figure 1: Design of table and chair

4.2

The Second Production Planning Scenario

Considering costs and the demand for final products constants, the following data are
obtained in the second production planning scenario:
t = 6 time periods
p = 7 pieces
j = 6 types of board cutting patterns
i = 2 final product (table and chair)
The pieces for the composition of the final products are:
Piece 1: cover
Piece 2: backrest
Piece 3: seat
Piece 4: chair support
Piece 5: foot of the chair
Piece 6: table support
Piece 7: foot of the table184
In this case, the new cutting patterns for the production of parts are described in Table
7. These are pre-set by the manufactory, according to the capacity of the equipment andthe available labor.
Table 7: Cutting Patterns: second production planning scenario
Pattern p=1 p=2 p=3 p=4 p=5 p=6 p=7 Time
j=1
0
34
34
0
0
0
0
v1 =3s
j=2
15
8
7
0
0
0
0
v2 =2s
j=3
12
12
13
0
0
0
0
v3 =4s
j=4
0
0
0
8
1
2
0
v4 =4s
j=5
0
0
0
2
3
4
0
v5 =3s
j=6
0
0
0
0
0
0
4
v6 =2sThe variable x1t represents the product “table”, whose production cost is R$60 anddemand is 10, and the variable x2t represents “chair”, whose production cost is R$40 anddemand is 20. The parameters (production cost, stock and cut time) were changed, sincedata from other types of wood and other cutting patterns were used. It is also consideredthat there is no stock in the previous period t − 1.
Parameters provided by the manufactory:
cp = R$135.07
ut = 240 hours per period
The number of pieces p required to make product i, which corresponds to parameters rpi ,can be seen in Table 8.
Table 8: Number of pieces p required to make product i
Piece Table Chair
p=1
1
0
p=2
0
1
p=3
3
1
p=4
0
2
p=5
0
4
p=6
2
0
p=7
4
0

The second production planning, considers that costs and demands are variables
throughout the planning periods. The new parameters provided from the manufactoryunder study are described below. The costs of the final products, cit , are provided inTable 9.
The cost of the board to be cut is cp = 135.07.
The stocking costs of the final products, hit , can be seen in Table 10 and the stocking
costs of the pieces, hppt , are provided in Table 11.
Demands of the final products are given in Table 12.

185

Table 9: Production cost of the final product i in the period taaaa Time period
aa
t=1
aa
a
Final product aa
a

Table
Chair

R$60
R$40

t=2

t=3

t=4

t=5

t=6

R$60
R$40

R$60
R$42

R$75
R$45

R$75
R$45

R$78
R$50

Table 10: Stocking cost of the final product i in the period taaaa Time period
aa
t=1
aa
a
Final product aa
a

Table
Chair

R$4
R$2

t=2

t=3

t=4

t=5

t=6

R$4
R$2

R$4
R$3

R$5
R$3

R$5
R$4

R$5
R$5

After running the new combined model using algorithm Simplex, the optimal solution
will indicate in which period of the planning horizon and in what quantity the final
products must be produced in these two problems, in order to obtain the minimum cost,
respecting restrictions (2) to (5) of the Combined Problem.

4.3

Simulations

Some simulations are executed in order to exemplify larger production scenarios. For
that, two types of furniture have been added in final products: stool and wardrobe. Costs
and demands parameters were considered as constants over the time periods of production
planning, since the manufactory data history shows that the value variation is not relevant
for the last six months.
Simulating the first production planning scenario, described in Section 4.1, the following data is obtained from the manufactory history:t = 6 time periods (maximum planning of the manufactory)
p = 3 pieces
j = 5 types of board cutting patterns
i = 4 final product (table, chair, stool and wardrobe)
The pieces used to compose the final products are:
Piece 1: cover
Piece 2: footPiece 3: seat/backrest
The variable x1t represents the product “table”, whose production cost is c1t =R$255
and the demand is d1t =2 for t = 1, ..., 6. The variable x2t represents the product “chair”,
whose production cost is c2t =R$80 and the demand is d2t =3 for t = 1, ..., 6. The variable

186

Table 11: Stocking cost of the piece p in the period taaaa Time periodaaaaaa
Pieces
aa

p=1
p=2
p=3
p=4
p=5
p=6
p=7

t=1

t=2

t=3

t=4

t=5

t=6

R$ 0.40
R$ 0.35
R$ 0.25
R$ 0.13
R$ 0.15
R$ 0.18
R$ 0.23

R$ 0.40
R$ 0.35
R$ 0.25
R$ 0.13
R$ 0.15
R$ 0.18
R$ 0.23

R$ 0.40
R$ 0.40
R$ 0.30
R$ 0.15
R$ 0.20
R$ 0.18
R$ 0.23

R$ 0.50
R$ 0.50
R$ 0.30
R$ 0.20
R$ 0.30
R$ 0.25
R$ 0.30

R$ 0.50
R$ 0.50
R$ 0.50
R$ 0.20
R$ 0.30
R$ 0.25
R$ 0.30

R$ 0.50
R$ 0.60
R$ 0.70
R$ 0.30
R$ 0.50
R$ 0.25
R$ 0.30

Table 12: Demand of the final product i in the period taaaa Time period
aa
t=1
aa
Final productaaa
a

Table
Chair

10
20

t=2

t=3

t=4

t=5

t=6

6
16

8
12

14
24

12
14

13
18

x3t represents the product “stool”, whose production cost is c3t =R$50 and the demand is
d3t =6 for t = 1, ..., 6. Finally, the variable x4t represents the product “wardrobe”, whose
production cost is c4t =R$1440 and the demand is d4t =2 for t = 1, ..., 6.
The other parameters provided from the manufactory are:cp = R$120,
ut = 300 hours per period,
apj the same as Table 2,
h1t = 3, h2t = 1, h3t = 1, h4t = 5
hp1t = 0.2, hp2t = 0.3, hp3t = 0.5.
The number of pieces p required to make product i, rpi , is given in Table 13.
Table 13: Number of pieces p required to make product i
Piece Table Chair Stool Wardrobe
p=1
1
0
0
8
p=2
5
6
4
0
p=3
0
2
1
0

Simulating the second production planning scenario, described in Section 4.2, andconsidering costs and demands for final products constants, the following data is obtained
from the manufactory history:

187
t = 6 time periods
p = 7 pieces
j = 6 types of board cutting patterns
i = 4 final product (table, chair, stool and wardrobe)
The pieces required to compose the final products are:
Piece 1: cover
Piece 2: backrest
Piece 3: seat
Piece 4: chair support
Piece 5: foot of the chair
Piece 6: table support
Piece 7: foot of the table
The variable x1t represents the product “table”, whose production cost is R$60 anddemand is 10 per period, and the variable x2t represents “chair”, whose production cost is
R$40 and demand is 20. The variable x3t represents the product “stool”, whose production
cost is R$30 and demand is 12. And the variable x4t represents the product “wardrobe”,
whose production cost is R$240 and demand is 5 per period.
Other parameters provided by the history manufactory are:cp= R$135.07,
ut = 240 hours per period,
apj : the same as Table 7.
The number of pieces p required to make product i, rpi , is given in Table 14.
Table 14: Number of pieces p required to make product i
Piece Table Chair Stool Wardrobe
p=1
1
0
0
14
p=2
0
1
0
0
p=3
3
1
1
0
p=4
0
2
4
0
p=5
0
4
0
0
p=6
2
0
0
0
p=7
4
0
0
0

4.4

Numerical Results

Optimum solutions were obtained from the execution of the previously described models with computational support of the LINDO software (Linear Interactive and Discrete
Optimizer) from the execution of algorithm Simplex.
For the first production planning scenario, considering the costs and demand of final
products constants, the optimal solution obtained then suggests anticipating the production of chairs, x21 = 18, generating stock, postponing table production, x13 = 12. Thus,

188
the optimal solution yields savings 15.2% of profit for each period, when it is comparedwith the production cost that satisfies the demand in each time period (without optimization).
Still in the first production scenario, but now considering a variation in costs anddemand, the optimal solution obtained suggests to anticipate the production of chairs
x21 = 25 and postpone the production of tables, x13 = 15. Compared to the production
cost that satisfies the demand in each time period, this optimal solution provides a totalsavings 29.7% of profit.
For the second production planning scenario, considering costs and demand for final
products constants, the solution suggests the production of chairs in the third period
x23 = 120 and the production of tables in the fifth period x15 = 60. Comparing to thecost of non-optimized production, this optimal solution provides a total savings 3.9% ofprofit.
Considering the variation of costs and demand in the second production planningscenario, the optimal solution obtained suggests the production of tables x12 = 63 andchairs x22 = 104, both in the second period. This solution provides a total savings 17.13%
of profit, when compared to the production cost that satisfies the demand in each time
period.
Simulating larger production scenarios, considering the first production planning scenario and costs and demands of final products constants (according to the manufactorydata history), the optimal solution suggests anticipating for first period the productionof tables and stools, x11 = 12 e x31 = 36, generating stock. In addiction, it suggests to
produce chairs in the second period, x22 = 18, and postponing wardrobe production in
the sixth period, x46 = 12. Thus, the optimal solution saves 22.04% of profit for eachperiod, when it is compared with the production cost that satisfies the demand in eachtime period.
Simulating the second production planning scenario, the optimal solution suggests
anticipating for first period the production of tables and some of chairs, x11 = 60 e
x21 = 37.53, generating stock. It also suggests to produce stools in the second period,
x32 = 72, and postponing wardrobe and the rest of chairs production in the sixth period,
x46 = 30 e x26 = 82.46. This optimal solution saves 27.93% of profit for each period, when
it is compared with the production cost that satisfies the demand in each time period.
For the solutions comparison purposes, the Branch-and-bound [13] algorithm wasapplied in all considered scenarios of production. This algorithm consists in dividing the problem into smaller sub-problems, until those can be solved using just entire decision variables [9, 2]. Since Branch and Bound aims to obtain just integer solutions, for all scenarios, except for the last simulation, entire optimal solutions are
the same as the ones obtained from Simplex. For the last simulation the results are:x11 = 60, x21 = 38, x46 = 30, x32 = 72 and x26 = 82. Thus, both algorithms are efficient toprovide the best solutions of considered linear programming problems. They may differ in
the number of iterations performed to obtain the optimal solution, as informed in Table
15. In this table, “scenario1-const” corresponds to the first production planning scenario,
described in Section 4.1, considering the parameters constants and “scenario1-var” considering the variation of the parameters. In addiction, “scenario2-const” corresponds tothe second production planning scenario, described in Section 4.2, considering the param-

189
eters constants and “scenario2-var” considering the variation of the parameters. Still inthe table, “simulation 1” is the simulation of the first production planning scenario and“simulation 2” corresponds to the second one.
Table 15: Number of iterations
Model
Simplex Branch and Boundscenario1-const
4
7
scenario1-var
4
7
scenario2-const
3
4
scenario2-var
3
4
simulation 1
5
6simulation 2
615

5Conclusion

This paper presented a study case in two programming scenarios of Combined Problem
production and two simulations, which involves two important problems of linear optimization: lot sizing and cutting stock.
Treating them separately can raise global production costs, especially if a significant
portion of the cost of the final product is formed by the material to be cut. Despite thefact that the combination of these problems is still little explored in the literature, therelevance of this combination in different situations elects this problem as an important
issue to be researched.
In order to obtain the optimal solution in both production planning scenarios, theSimplex Method was applied, knowing that in the literature this method, together withthe generation of columns, is the most recommended for the solution of the Combined
Problem.
The optimal solutions to the problems were analyzed in both production planningscenarios, considering constant the costs and demand of final products and, subsequently,
the variations of such costs and demand, for 6 periods. In both cases it was possible
to observe the optimization, through the profit obtained using the Combined Problem
in conjunction with the Simplex Method, when compared to the production cost thatsatisfies the demand in each time period. Larger production scenarios were considered andsimulated, illustrating the real situation experienced by the manufactory. The obtained
results from the simulations indicate similar behavior of numerical solutions, which provide
profits and avoids the waste of raw material.
In practical situations, a strategy can be applied to round fractional variables toassume integer values, in order to obtain a viable solution [12]. Because the number ofboards in a solution must be integer, an optimal solution must use at least one board.
Thus, if the solution obtained by rounding is not optimal, at most one more board is usedthan the optimal solution.

190
As future works, we intend to build a computational interface so that users can obtain
the optimal solution easily, just inserting the known parameters of the problem, even
without understanding the mathematical model.

References[1] Alem, D., Morabito R.: The integrated problem of production planning and cutting stock under uncertainties: Application in small-scale furniture plants. Gestão e
Produção 20(1), 111-133 (2013).
[2] Bazaraa, M. S., Jarvis, J. J., Sherali, H. D.: Linear Programming and Network Flows.
4th edition, John Wiley (2010).
[3] Bressan, G. M.: Soluo de Sistemas Lineares Esparsos: aplicao programao de lotes e
cortes (in Portuguese). Master Thesis, São Paulo University, Brazil (2003).
[4] Chapman, S. N.: The Fundamentals of Production Planning and Control. New York:
Pearson (2006).
[5] Cherri, L. H., Mundim, L. R., Andretta, M., Toledo, F. M. B., Oliveira, J. F.,
Carravilla, M. A.: Robust mixed-integer linear programming models for the irregular
strip packing problem. European Journal of Operational Research 253(3), 570-583(2016).
[6] Danwé, R., Bindzia, I., Meva’a L.: Optimisation of cutting in primary wood transformation industries. Journal of Industrial Engineering and Management 5(1), 115-132(2012).
[7] Gilmore P. C., Gomory, R. E.: A linear programming approach to the cutting-stock
problem. Operations Research 9, 849-859 (1961).
[8] Gramani M. C. M., França, P.: The combined cutting stock and lot-sizing problem inindustrial processes. European Journal of Operational Research, 174, 509-521 (2006).
[9] Luenberger D. G., Ye Y.: Linear and Nonlinear Programming. Fourth Edition,
Springer (2008).
[10] Malagutti E., Duran, R. M.: P. Toth. Approaches to real world twodimensional
cutting problem. Omega (47), 99-115 (2014).
[11] MirHassani, S. A., Bashirzadeh, A. J.: A Grasp metha-heuristic for two-dimensional
irregular cutting stock problem. The International Journal of Advanced Manufacturing Technology 81(1),455-464 (2015).
[12] Miyazawa, F. K.: Integer Programming, State University of Campinas (2015). Available in <www.ic.unicamp.br/~fkm/lectures/progint.pdf>. Accessed in: November, 27.2015.

191[13] Nemhauser, G. L., Wolsey, L. A.: Integer and Combinatorial Optimization, Interscience Series in Discrete Mathematics and Optimization, Jonh Wiley & Sons, New
York, NY (1988).
[14] Ozfirat, P. M.: An integer programming approach for the three-dimensional cutting planning problem of marble processing industry. The International Journal ofAdvanced Manufacturing Technology 59(9),1057-1064 (2012).
[15] Poldi, K. C., Arenales, M. N.: Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths. Computers and Operations Research 36(6),2074- 2081 (2009).