=Paper=
{{Paper
|id=Vol-2098/paper3
|storemode=property
|title=Research and Development of an Algorithm for Solving
the Problem of Control over the Input–Output Material
Flows of an Industrial Company
|pdfUrl=https://ceur-ws.org/Vol-2098/paper3.pdf
|volume=Vol-2098
|authors=Nina V. Baranova,Yurii A. Mezentsev
}}
==Research and Development of an Algorithm for Solving
the Problem of Control over the Input–Output Material
Flows of an Industrial Company==
https://ceur-ws.org/Vol-2098/paper3.pdf
Research and Development of an Algorithm for Solving
the Problem of Control over the Input–Output Material
Flows of an Industrial Company
Nina V. Baranova1 and Yurii A. Mezentsev2
1
Novosibirsk State Technical University, Novosibirsk, Russia
2
Novosibirsk State Technical University, Novosibirsk, Russia
mesyan@yandex.ru
Abstract. A discussion is given of a universal mathematical economic model
designed to find optimal strategies for controlling the production and logistics
subsystems (subsystem components) of a company. The declared universal
character of the model allows a systematic consideration of both production
components, including constraints associated with how raw materials and com-
ponents are converted into goods for sale, and resource-based and logical con-
straints on input–output material flows. The model and the generated control
problems are developed within a single approach allowing the implementation
of logical conditions of any complexity and the formulation of the correspond-
ing formal optimization problems. An explanation is provided for the meaning
behind the criteria and constraints. An approximate polynomial algorithm is
proposed for solving the formulated mixed programming optimization problems
of actual dimension. The results are presented of testing the algorithm for prob-
lem instances over a wide range of dimensions.
Keywords: Discrete optimization problems · Mixed integer linear program-
ming · Production, supply, and sales control · Discount functions · Efficient al-
gorithm.
1 Introduction
The aim of this work is to solve one of the problems associated with control over
production and economic systems and processes. Within its framework, we developed
a model and an algorithm, based on mathematical programming methods, for synthe-
sizing optimal solutions. Studies like this one most often focus on specific topics
(problems): location, supplier selection [1], job assignment, inventory management,
supply chain management, logistics [2, 3], and production [4]. In this work, we used a
comprehensive system approach to optimize the control over the product line and
material flows of an industrial company [5].
The composition of the product line depends on the specific weight of each product
type in the total share of production and its profitability. A large product line allows
Copyright © by the paper’s authors. Copying permitted for private and academic purposes.
In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
34 N. V. Baranova, Yu. A. Mezentsev
the company to satisfy the various demands of customers and, thus, increase the out-
put and sales. To maximize profits, however, managers must make sure that the prod-
uct line composition is rational. They should assess the relevance of the product pro-
gram in terms of economic efficiency as early as during the development of the pro-
gram. It should be noted that there is no generally accepted methodology for deter-
mining an optimal product line for an industrial company. We analyzed the literature
on this subject, from which we elicited a few approaches to product line determina-
tion and optimization. One can speak only of calculation systems/techniques designed
and applied by industrial companies or researchers on a case-by-case basis, depending
on a specific problem. Therefore, it would be irrational to widely apply these individ-
ual techniques.
At present, optimization problems are widely used in the various areas of produc-
tion [6]. In [7], e.g., a process is described for finding a solution to the problem of
multi-objective optimization of material traffic in a logistics network by means of a
control system based on fuzzy logic as well as the simulated annealing methodology
and a genetic algorithm.
In [8], the authors point out the relevance of studying supply chain optimization—
in today's competitive and flexible environment, companies need effective planning
that is based primarily on modern technology and calculations. One such technology
is dynamic modeling tools, i.e., discrete-event simulation (DES).
The multi-objective optimization problem as applied to supplier selection and the
order release mechanism has long been the focus of research for a team of scientists
from Youngstown State University in the United States [9, 10]. They consider one of
the alternative decision support systems with several criteria, i.e., visual interactive
goal programming (VIG).
Researchers from Sweden [11] focus on production logistics optimization, which is
also relevant for Russian companies. They discuss the results of the combined use of
DES and simulation-based multi-objective optimization (SBO) for analysis and im-
provement of logistics and production systems.
2 Conceptual Problem Statement
Control actions: selection of suppliers, determination of amounts of procurement
for all items in the product line, transportation, production, storage, and sales [5, 12,
13].
Production and economic activity features considered in the model: the high unit
price for all items in the product line (e.g., electronic chips, plant seeds, or jewelry;
this condition has no substantial effect on the structure of the formal model); relative-
ly small supply by volume; in-house production is considered in the general scheme
as in-house supply. Transportation costs are considered insignificant. Remoteness of
suppliers affects only the time of delivery, which is compensated by a necessary
amount of stocks in the warehouse. Supply conditions can be considered significant if
they are characterized by wholesale discounts, whose dependence on the amounts of
supply by value is shown in Fig. 1.
Algorithm for Problem of Control over the Input–Output Material Flows 35
Discount
gjk(t)
gj2(t)
gj1(t)
hj1(t) hj2(t) hjk(t) Order amount
Fig. 1. Product supply conditions.
Here and below, wavy dashed lines show breaks in the plots.
The dependence of the supplier prices on sales is presented in Fig. 2.
Price per unit
cjk(t)
cj2(t)
cj1(t)
hj1(t) hj2(t) hjk(t) Order amount
Fig. 2. Dependence of the unit price on the order amount.
The most important factor in the model is demand. In the worst-case scenario,
there is only an average demand forecast estimate; in the best-case one, there is a
forecast of the demand function for all the items in the product line. The demand
function for each product item may look as in Fig. 3.
Another feature is the presence of several consumers groups (wholesale and retail
customers, persons entitled to privileges, and holders of discount cards).
36 N. V. Baranova, Yu. A. Mezentsev
Price per unit
pilk(t)
sil1(t) silk(t) Demand
Fig. 3. Product supply conditions.
Considering the above circumstances, the control problem can be formulated as
follows.
It is necessary to devise such a procurement strategy (select suppliers and supply
amounts, in view of the discounts) and such a sales price policy by consumer group
that maximize the criterion (the net income or working capital at the end of the plan-
ning period) under constraints on the working capital at the beginning of the period
and on the warehouse capacity. The term procurement strategy means a set of planned
amounts of procurement for the entire product line, including the selected prices and
discounts from all potential suppliers; the amounts are determined for each time inter-
val within the planning period. The term sales strategy means a set of planned
amounts of sales for the entire product line to all consumers groups; the amounts are
determined from demand data for each time interval within the planning period.
The constraints of the problem are logical conditions that consider changes over
time in the discounts associated with procurement and sales [5] as well as in consum-
er demand and in the company’s warehouse and production capacities and financial
capabilities [12].
It should also be noted that the production cycle in the case under consideration is
much shorter than any interval of the planning period.
3 Formal Statement
We use the following notation:
t is the number of the time interval used as a measure of discreteness when deter-
mining the simulation time (hereinafter, the month number);
j is the supplier number ( j 1, J ); i is the product number in the supply product
line ( i 1, I ); l is the consumer type index ( l 1, L ); k is the number of the interval
on the discount ( k 1, K ) and demand ( k 1, K ' ) scales;
Algorithm for Problem of Control over the Input–Output Material Flows 37
yij (t ) is the amount of procurement of product i by volume from supplier j in
month t ;
Oi (t ) is the stock of product i in the warehouse at the beginning of month t ;
Cij (t ) is the base wholesale price of product i from supplier j in month t ;
d j (t ) is the amount of procurement by value from supplier j in month t at the
base price (without discounts);
h jk (t ) is the right boundary of interval k on the scale of discounts given by sup-
plier j in month t ;
g jk (t ) is the discount given by supplier j in month t in interval k on the corre-
sponding scale (in percentage);
w jk (t ) is an indicator that a given amount of procurement falls within interval k
on the scale of the discounts given by supplier j in month t ;
xilk (t ) is the amount of sales of product i by volume to a consumer of type l in
month t in interval k on the demand-function scale;
pilk (t ) is the unit price of product i for a consumer of type l in month t in inter-
val z of the demand function;
Q(t ) is the size of working capital in month t ;
N (t ) is the wages and overheads in month t ;
silk (t ) is the right boundary of interval k on the scale of the demand function for
product i by a consumer of type l in month t .
A mathematical economic model (MEM) for optimal control over the supply and
sales of inhomogeneous products manufactured by a company is as follows:
I
C (t ) y (t ) d (t ) , j 1, J , t 1,T ;
i 1
ij ij j (1)
d j (t ) h jk (t )wjk (t ) 0 , j 1, J , t 1, T ; (2)
0 wjk (t ) 1 , w jk (t ) are integer numbers; (3)
yij (t ) 0 , i 1, I j 1, J , t 1, T , k 1, K ; (4)
J K
[d (t ) d (t ) g (t )w (t )] Q(t ) , t 1,T ,
j 1
j j
k 1
jk jk (5)
g j1 (t ) if d j (t) h j1 (t ) ,
g (t ) if h (t ) d (t) h (t ),
j2
where g jk (t )
j1 j j2
j 1, J , t 1, T ; (6)
...
g jK (t ) if d j (t) h jK (t ) ,
38 N. V. Baranova, Yu. A. Mezentsev
xil1 (t ) sil1 (t ) , i 1, I , l 1, L , t 1, T ; (7)
k 1
xilk (t ) silk (t ) xilk ' (t ) , i 1, I , l 1, L , k 1, K , t 1, T ; (8)
k ' 1
J L K
y (t ) O (t 1) x (t ) , i 1, I , t 1,T ;
j 1
ij i
l 1 k 1
ilk (9)
J L K
Oi (t ) yij (t ) Oi (t 1) xilk (t ) , i 1, I , t 1, T ; (10)
j 1 l 1 k 1
I L K J K
Q(t 1) pilk (t ) xilk (t ) N (t ) [d j (t ) d j (t ) g jk (t )w jk (t )] , t 1, T ; (11)
i 1 l 1 k 1 j 1 k 1
T T
(t )Q(t ) max provided that 0 (t ) 1, (t ) 1 ;
t 2 t 2
(12)
Q(T ) max . (13)
Relations (1) define the amount of procurement by value, ignoring the discounts, in
month t from supplier j; relations (2) and (3) are logical constraints on the presence of
discounts and on their size; (4) are constraints on the amount of procurement by val-
ue, considering the discounts, in month t from all the suppliers; (5) and (6) are de-
mand constraints for each product for all types of consumers in month t . Relations
(7) are logical constraints: the total amounts of procurement and stock in the ware-
house for each product item in each month must not be lower than the corresponding
amounts of sales. Relations (8) define the time changes in the warehouse stock for the
entire product line; (9) define the time changes in net income; (10) is a criterial indi-
cator of efficiency, meaning the time-weighted average of net income; (11) is a spe-
cial case: the net income at the end of the planning period.
Since the problem under consideration includes the manufacturing component of
the process, the above constraints can be supplemented by another one, i.e., on the
ways to transform raw materials and components Y into goods for sale X:
X AY, (14)
where A is the tensor of technological coefficients. It should be noted that although
we calculate several output values (considering consumer types and discount scales)
for each output good, the calculations for all these values use the same coefficients of
the A tensor for this good. This is reflected in the following group of constraints:
K' L I J
xilk (t ) Avi (t ) yij (t ), i 1, I ,t 1, T . (15)
k 1 l 1
v 1 j 1
Algorithm for Problem of Control over the Input–Output Material Flows 39
4 Estimating the Potential Complexity of Solving the
Optimization Problem Instances
We assume that aij A, i 1.I , j 1, J is an element of a continuous set A . We
use the following notation: M (aij ) I J is the number of elements in the set A ;
M cont is the number of continuous variables; M int is the number of integer variables;
and M constr is the number of constraints in the model.
Let us consider a typical example of applying model (1)–(13) with the following
parameters:
I 2000 is the product line; J 10 is the number of suppliers; T 3 is the plan-
ning period; K 3 is the number of intervals on the discount scale; K ' 3 is the
number of intervals on the demand scale; and L 2 is the number of types of con-
sumers.
Then, if we leave out the constraints on continuous variables, we have
M ( yij (t )) 60000, M ( xilk (t )) 36000, M (w jk (t )) 90, M cont M ( yij (t ))
M ( xilk (t )) 96000, M int M (w jk (t )) 90, M constr
=10·3+10·3+2000·10·3+3+2000·2·3+ 2000·2·3·3+2000·3+2000·3+2000·3=126063.
The number M constr is formed by those constraints that include the solution varia-
bles: (1), (2), and (3) for procurement-related variables; (4)–(8) and (13).
M ( yij (t )) is the maximum possible estimate. If there is no complete intersection of
the suppliers’ product lines, the estimate will be lower.
Thus, an order-of-magnitude estimate for the number of dimensions and, hence, for
the complexity of a control problem with parameters as close as possible to actual
ones is as follows: 104 continuous variables and 102 integer variables. Moreover, the
model contains nonlinear constraints (4) and (9) and a nonlinear objective function
(10)–(11).
It also follows directly from the problem statement that the problem belongs to the
class of NLP and MIP with potential NP-hardness.
5 Approximate Algorithm for Solving the Problem of Optimal
Control over Supply, Production, and Sales
As noted above, if we ignore the specific features of the problem statement, prob-
lem (1)–(13) of any actual dimension is, at given parameters of computational com-
plexity, formally unsolvable by known methods. To solve this problem, we construct
an algorithm best tailored to the specific features of the problem. Note that all the
discount functions g jk (t ) are nondecreasing ones; hence, all the functions of whole-
sale prices and demand are nonincreasing ones. In view of these circumstances, we
propose the following algorithm to search for an optimal solution of problem (1)–
(13):
40 N. V. Baranova, Yu. A. Mezentsev
Preliminary Step. We define the relaxed problem for (1)–(13) as follows. We select
any g j (t ) {g jk (t )} , j 1, J , t 1, T , and form on the basis of problem (1)–(13) a linear
subproblem:
I J
C (t ) y (t ) d (t ) , j 1, J , t 1,T , [d (t ) d (t ) g (t )] Q(t ) , t 1,T , or
i 1
ij ij j
j 1
j j j
J I
C (t ) y (t )[1 g (t )] Q(t ) , t 1,T ;
j 1 i 1
ij ij j (16)
yij (t ) 0 , i 1, I , j 1, J , t 1, T ; (17)
xil1(t ) sil1(t ) , i 1, I , l 1, L , t 1, T ; (18)
k 1
xilk (t ) silk (t ) xilk ' (t ) , i 1, I , l 1, L , k 1, K , t 1, T ; (19)
k ' 1
J L K
y (t ) O (t 1) x (t ) , i 1, I , t 1,T ;
j 1
ij i
l 1 k 1
ilk (20)
J L K
Oi (t ) yij (t ) Oi (t 1) xilk (t ) , i 1, I , t 1, T ; (21)
j 1 l 1 k 1
K' L I J
x (t ) A (t ) y (t ), i 1, I ,t 1,T ;
ilk vi ij (22)
k 1 l 1 v 1 j 1
I L K I
Q(t 1) pilk (t ) xilk (t ) N (t ) Cij (t ) yij (t )[1 g j (t )] , t 1, T ; (23)
i 1 l 1 k 1 i 1
T T
z (t )Q(t ) max provided that 0 (t ) 1, (t ) 1 , or
t 2 t 2
Q(T ) max . (24)
We now add new notation to that introduced above. Let n be the number of the step
in the algorithm. We denote as Y n , X n and z n the solution of the relaxation problem
at step n (the amounts of procurement and sales and the value of the efficiency criteri-
on). We denote as G n the set of intervals of discounts at step n ( g j (t ) ). Below we
give a stepwise representation of the algorithm for solving the problem.
Step One. We assume that g j (t ) max{g jk (t )} g jK (t ) , j 1, J , t 1, T and make up
k
the relaxed subproblem (14)–(22). We denote its solution as Y 0 , X 0 , z 0 . ( Y 0 y 0 (t ) , ij
X xilk (t ) , z z( X ,Y ) ) We determine the matrix identity: g j (t ) G .
0 0 0 0 0 0
Algorithm for Problem of Control over the Input–Output Material Flows 41
Step n. Based on the solution obtained at the previous step, i.e., Y n 1, X n 1, z n 1 at
n 1
G , we determine the new values of g (t ) : j
g j1 (t ) if d j (t) h j1 (t ) ,
n 1 n 1 g (t ) if h (t ) d (t) h (t ),
g (t ) if y (t ) 0 j2
g j (t ) j
ij j1 j j2
n 1
, where g (t ) and
g jk (t ) if yij (t ) 0
...
jk
g jK (t ) if d j (t) h jK (t ) ,
I
d j (t ) Cij (t ) y ijn 1 (t ) , j 1, J , t 1, T .
i 1
Using the implementation of the barrier algorithm in the IBM ILOG CPLEX opti-
mization studio [13], the main computing tool in the software implementation of the
algorithm, we solve problem (14)–(22), find new values of Y n , X n , z n , and check them
for optimality. If z n z n 1 is a small number setting the calculation accuracy),
then we have obtained at this step an optimal solution of (1)–(13). If the condition is
not satisfied, we proceed to the next step (n+1), determining the new values of g (t ) j
n
from Y .
It is obvious that the algorithm converges in a finite number of steps, which cannot
be greater than J K T . This is due to the specific features of the discount functions
g jk (t ) . In our example, J K T = 90. However, a statistical estimate for the number of
steps in this example for varying initial data is 5.
Thus, the proposed algorithm converts problem (1)–(13) into a polynomially solv-
able one with respect to dimension. If we use this algorithm, problem (1)–(13) falls
into another class of (linear) models with an ordinal number of continuous variables
of 104 and a complete absence of integer variables [13].
6 Results and Discussion
The universal character of the model, the algorithm, and the implementation soft-
ware with respect to the types of enterprises is achieved through the tensor of techno-
logical coefficients, which determines the ways of converting raw materials and com-
ponents into goods for sale and participates in a group of constraints (12)–(13) of the
problem. The technological coefficients in the tests are nonnegative. They were gen-
erated in the range from 0 to 1 for a general instance of the problem of managing a
trading and manufacturing company.
Table 1 shows the input parameters and the program results for each of the tests,
which are displayed in the table rows. The right-hand side of the table contains the
input dimensions, i.e., the following numbers for a given case (test): items in the sup-
pliers’ product line (I), consumer-type indices (L), suppliers (J), intervals on the dis-
count (K) and demand (K1) scales, and time intervals (T). The second part of Table 1
shows the resulting indicators, such as the time of execution of the program (in se-
conds and fractions of a second), the number of steps in which the problem was
solved (q), and the number of constraints in the problem.
42 N. V. Baranova, Yu. A. Mezentsev
The columns Number of Continuous Variables and Number of Boolean Variables
show the number of variables that participate in solving the problem. These include
all the tensor components yij (t ) , xilk (t ) , and w jk (t ) , considering their differences for
each of the time intervals.
The column Number of Constraints shows the number of problem constraints,
which depends on the input values of the variables. The number of constraints was
calculated in the same way as the indicator M constr in the section Estimating the Com-
plexity of the Model, i.e., by considering constraints (1)–(3) for the procurement-
related variables, (4)–(8), and (13).
Table 1. Results of testing the program given the presence of in-house production
K (intervals on the discount
Computing time (seconds)
K1 (intervals on the de-
Number of continuous
Number of constraints
Number of Boolean
L (consumer types)
I (product types)
J (suppliers)
T (months)
mand scale)
q (steps)
variables
variables
No.
scale)
1 10 5 10 4 3 6 4.25 5 1500 240 2046
2 10 5 10 5 4 6 4.77 5 1800 300 1656
3 7 4 4 4 3 6 2.59 3 672 96 1020
4 7 4 4 5 4 6 2.8 3 840 120 1188
5 6 3 3 4 3 6 2.69 3 432 72 690
6 6 3 3 5 4 6 3.28 4 540 90 798
7 10 5 10 3 2 6 4.78 5 1200 180 1806
This testing section shows three blocks of tests, each including the same I, L, and J
indicators and two different tests for different K and K1. The planning period was the
same for all the tests in this section. One can see how the time increases linearly for
tests of higher dimension, i.e., with larger K and K1 in the rows with the same I, L,
and J, which confirms the efficiency of the algorithm. The number of steps in the tests
of higher dimension is greater than or equal to that in the corresponding pairwise tests
of lower dimension.
7 Conclusions
The initial problem of control over the external material flows of a company was
examined and supplemented with a production component. A program was developed
Algorithm for Problem of Control over the Input–Output Material Flows 43
that implements the modified algorithm, and the relevant tests were performed. As a
result, a new decision support tool was obtained.
Thus, this program can be successfully applied to problems of actual dimension
that arise in the production sector, in terms of applying MEMs to company logistics,
and can provide support of decision-making in the planning of procurement, produc-
tion, and sales, from the perspective of maximization of working capital balances.
According to expert estimates, the potential for improving the performance in the
search for the best solutions to logistics problems is on average 30% or higher [14,
15].
Acknowledgement. This work was supported by the Russian Ministry of Educa-
tion and Science, according to the research project No 2.2327.2017/4.6.
References
1. Butusov, O., Dubinin, M.: Decision support system for supplier selection in supply chain.
Scientific peer-reviewed journal Izvestiya MGTU MAMI 4, 268-271 (2013)
2. Parunakjan, V., Sizova, E.: Increase of efficiency of interaction of production and transport
in the logistic chains of material traffic of enterprises. Transport problems 3(3), 95-104
(2008)
3. Bosov, A., Khalipova, N.: formation of separate optimization models for the analysis of
transportation-logistics systems 3 - 3 (87), 11-20 (2017)
4. Kolga, M., De Smedt, V., Van Nerom, L.: Planning principles in metallurgy. Vestnik of
Nosov Magnitogorsk State Technical University 5 (45), 78-80 (2013)
5. Mezentsev, Yu.: Mathematical Models of Management of Logistics Subsystems at Enter-
prises. Automation and Modern Technologies 8, 46-55 (2008)
6. Arshinsky, L., Zhang, K.: The application of operations research in logistics. Information
technology and the problems of mathematical modeling of complex systems 10, 5-12
(2012)
7. Mehrsai, A., Karimi, HR, Thoben, KD, Scholz-Reiter. B.:: Using Metaheuristic and Fuzzy
System for the Optimization of Material Pull in a Push-Pull Flow Logistics Network.
Mathematical Problems in Engineering (2013)
8. Wang, Q., Ingham, N.: A discrete event modelling approach for supply chain simulation.
International Journal of Simulation Modelling 7(3), 124–134 (2008)
9. Karpak, B., Kumcu, E., Kasuganti, R.: Purchasing materials in the supply chain: Managing
a multi-objective task. European Journal of Purchasing & Supply Management 7, 209–216
(2001)
10. Karpak, B., Kumcu, E., Kasuganti, R.: Multi-objective decision-making in supplier selec-
tion: an application of visual interactive goal programming. Journal of Applied Business
Research 15, 57–71 (2011)
11. Ruiz Z´u˜niga, E.: A simulation-based approach for optimization of production logistics
with consideration to production layout. Research Proposal (2016)
12. Mezentsev, Yu.A., Pavlov, P.S.: To the program realization of the decomposition algo-
rithm for solving a class of discrete optimization problems with semi-definite relaxation.
Information Technologies 2 (186), 54-59. Publishing house "New Technologies", Moscow
(2012)
44 N. V. Baranova, Yu. A. Mezentsev
13. Mezentsev, Yu.A., Pavlov, P.S.: Realization of the algorithm for solving special problems
of semi-definite programming using IBM ILOG CPLEX. Scientific Bulletin of NSTU 4
(45), 25-34 (2011)
14. Stock, D., Lambert, D.: Strategic Management of Logistics, INFRA-M, Moscow (2005)
15. Sergeev, V.: Corporate Logistics. 300 Answers to Questions of Professionals. INFRA-M,
Moscow (2005)