Abstract
The paper provides an overview of the main world and regional studies on the development of effective methods and technologies of rational use of resources. Scientific papers of the Nobel Prize winner Kantorovich L.V. are given. They have become the basis for the formation and development of the theory of optimum resource usage and the linear programming. Modern world achievements in the development of algorithms and methods of solving different problems are described. Some examples of problems of rational use of resources are given in the article, namely NPhard cuttingpacking problems, nesting problems and problems of geometrical covering. Some features and difficulties in solving these problems are noted. The research of the Ufa scientific school on the solution of problems of cuttingpacking and geometrical covering is briefly presented. The contribution of Ufa scientists who have been conducting research in this field for more than 60 years is noted. One of the last directions of the Ufa scientific school is the development of effective algorithms of solution based on matrix technology. The formulation of the complex problem of geometric covering and cutting is presented in more detail. In the problem, it is necessary to find a plan for covering the multicoherent orthogonal polygon (MOP) and a plan for cutting of rectangular resource to covering items. The results of evaluating the effectiveness of matrix algorithms are presented.
Keywords: Geometrical location problemscuttingpacking problemsoptimization
Introduction
Lean manufacturing technologies are in great demand in the modern world, and improvement of the methods and technologies for rational resource use is very urgent.
In 1939 professor Kantorovich (1939) published in Leningrad a brochure describing methods of production management and planning. This small book is considered to play the basic role in becoming and development of the theory of optimum use of resources and linear programming. In 1975 professor Kantorovich and an American economist T. Kupmans became winners of the Nobel Prize for Economics for their contributions to the theory of optimum use of resources.
The mentioned brochure considered various practical problems arising in manufacturing organization where it was necessary to find the best variant of decision. The book was written after consultation to several engineers of the AllUnion Plywood trust concerning the practical problems that could not be solved by the methods traditional at that time. Professor L. V. Kantorovich developed a method of resolving multipliers (indexes) that established a basic opportunity of finding the best decision for many problems of national economy as well as for the problem of stock cutting. Despite of a wide range of scientific interests L. V. Kantorovich repeatedly came back to the problem of rational cutting, see more details in (as cited in Filippova & Valiakhmetova, 2014).
Technological processes in different applied branches often use the engineering stage of cutting and location of items taking into account their geometric peculiarities. This stage is urgent for saving resources, though it is difficult for decision making (Filippova & Valiakhmetova, 2014).
Such problems are formulated as geometrical location problems. Geometrical location problems imply a wide class of problems including the classic cuttingpacking problems of various applied interpretations. This is the list of problems that can be referred to this class: stock material cutting; dense allocation of geometrical objects in a given area; knapsack loading; container packing; transport loading; choice of assortment; premises layout; ensuring the rhythm of production process; computer memory allocation; scheduling of multiprocessing systems; the problem of maximal (minimal) geometrical covering, etc. In its turn each of the above problems can be concretized in many different ways. They all belong to the class of NPhard problems. So it is urgent to develop and research new efficient methods of their solution nowadays.
The presence of two groups of objects is common to this class of problems. A correspondence between the elements of these groups is established and estimated.
The cuttingpacking models and methods are wellstudied examples of the problem of optimum use of resources.
There exist linear cutting (onedimensional) problems, rectangular (twodimensional) and parallelepiped (threedimensional) cuttingpacking problems. And the guillotine cuttingpacking problems stand out among these problems. And even more important are the problems of nesting, that is location of items of complex geometrical forms in a given area. The information about their specific forms, providing the items’ nonintersection, their coding, etc., are of special importance in such problems. The list of geometrical properties of the items and of the material can be supplemented and considered in a mathematical model with the help of some physical and/or economic parameters. The way the basic models of cuttingpacking problems are classified is shown in (Mukhacheva, Mukhacheva, Valeeva, & Kartak, 2004).
Problem Statement
L. V. Kantorovich and V. A. Zalgaller worked in Leningrad in the department of Mathematical Institute of the USSR Academy of Science. In the 1940th they were the first to consider in detail the cutting problems (as cited in Filippova & Valiakhmetova, 2014). The mathematical ways of solving these problems were tested in practice at the Carriage Works in Leningrad in 19481949. V. A. Zalgaller developed the method of integer indexes selection, and proposed the decision of the flat (twodimensional) problem by means of an auxiliary linear problem and described methods of cutting materials of mixed lengths, and offered various technical devices. Cutting problems were considered as examples of linear programming application (Linear Programming, LP). The first foreign publications on LP date back to 1949. No doubt this trend in science has been developed and widely used with the advent of computers. No calculation of rational maps for cutting of rectangular sheets to a large number of items (more than 60) was practically possible in 1960s. And problems of smaller dimensions took many hours of program work on computers (as cited in Mukhacheva, 1966).
Nowadays many researchers all over the world have to solve problems of efficient use of resources. The classic cuttingpacking problem varies greatly depending on the peculiarities and restrictions in any branch of science or industry where it is used.
The authors from Germany and the USA propose algorithms to solve the problem of cutting roll materials in the paper industry (Kallrath, Rebennack, Kallrath, & Kusche, 2014). Several variants of the problem are considered, such as: cutting roll materials of different widths; cutting of limited number of rolls; cutting when incomplete production is permissible.
The authors of the paper (Rothe & Reyer, 2017) solve the 3D problem of guillotine cutting steel plates into blocks of various sizes. One of the peculiarities of the production is the problem of reuse of waste material left after cutting to save resources.
The scientists from Belgium (Paquay, Schyns, & Limbourg, 2016) use mixed integer linear programming to solve the threedimensional problem of container loading. It is a typical problem in airline industry. And the approach offered by the authors takes into account a large number of restrictions, such as: cargo stability in transit; fragility of objects; even weight distribution in the container; rotation tolerance; container shape features.
In (Lua & Huang, 2015) the researchers from China and Taiwan also use the mixed model of integer programming to solve another actual problem, namely the problem of reduction of production costs due to minimization of waste during twodimensional cutting of glass sheets in the production of liquid crystal displays. The authors propose to use the genetic algorithm that includes a new location procedure, namely a corner space algorithm.
A separate area of research relevant to industry and popular nowadays is the irregular cutting where the items to be cut have a complex polygonal shape. For example, in (Imamichi, Yagiura, & Nagamochi, 2009) the authors consider the problem of irregular strip packing (Figure
Often, to find an effective solution, the problem is divided into several stages each of which becomes a separate problem. So in the paper (Bouaine, Lebbar, & Ha, 2018), the scientists from Morocco consider the real problem in furniture industry, namely minimization of wood waste when cutting beams of various sizes. The authors propose to solve this problem using twostage heuristics. At the first stage, certain templates for cutting material into items are generated, using the classic algorithms of twodimensional packing. At the second stage, the integer LP problem is solved where the generated templates are used as variables.
In paper (Cherri, Carravilla, & Toledo, 2016), the Brazilian researchers solve the irregular strip packing problem. They propose matheuristic to solve the problem. The method has three phases in which mixed integer programming exact models are used to solve the subproblems.
The cuttingpacking problems are typical representatives of NPhard problems. As far as the exact algorithms for cuttingpacking problems are of nonpolynomial complexity, many authors of scientific papers have paid much attention to approximate methods, and when they develop exact algorithms they use procedures of full sortingout reduction and of low border calculation.
Mathematical models of integer linear programming (ILP) are traditional for unitary cuttingpacking problems. But it should be noted other areas of research, for example the level, block and matrix technologies (Dyaminova & Filippova, 2016).
Next, we take a closer look at the development of the methods and technologies by the Ufa scientific school.
Research Questions
Researching and solving mass cutting problems with the help of the computer in early 1960s, became the first step for establishing of the Ufa scientific school run by Mukhacheva (1966). The Ufa scientific school (USS), has been actively engaged in applied operational research problems for more than 60 years. The scientists of the school developed the conditional optimization algorithms based on linear programming, they took into account the real industry specificity.
This goal has been achieved to some extent in mass and batch production. E. A. Muhacheva's book (Mukhacheva, 1966) was written and published under the guidance of L. V. Kantorovich. However, the cuttingpacking problems, as a matter of fact, belong to problems of discrete optimization. Their solution by means of linear programming is nothing more than continuous relaxation. It is expedient to use various ways of rounding of relaxation and construction of various remainder problems.
The exact algorithms based of linear integer programming have received their further development. German scientists and their colleague from Ufa G. N. Belov realized the approximation of continuous relaxation to the integer optimum (as cited in Filippova & Valiakhmetova, 2014). They proposed to solve the problems of linear and guillotine cutting by the method of secant planes developed by Gomory. And these scientists have been working on the problems so far.
In the paper (Kartak & Ripatti, 2018) the authors present an efficient algorithm for building instances with certain properties for the ddimensional orthogonal packing problems. Using the developed toolset the authors construct equivalent instances with a reduced number of raster points.
In the paper (Kartak, Marchenko, Petunin, Sesekin, & Fabarisova, 2017) the problem of the optimal layout of lowrise residential building is considered by V. M. Kartak and his coauthors. It is still another NPhard optimization problem with some additional conditions and technological restrictions.
For this problem, the researchers built a mathematical model and analysed its qualities. Then they proposed two algorithms to find the solution. They are: an exact algorithm based on integer linear programming and a rapid heuristic algorithm for problems of large dimension.
The scientists from Ufa have been actively researching and developing effective methods and algorithms to solve 1D, 2D, 3D location problems, taking into account various practical conditions and technological restrictions. In addition, theoretical researches of the problem’s properties are being conducted (as cited in Kartak & Ripatti, 2018).
The authors of the given paper also belong to the Ufa scientific school, and nowadays we are researching and developing technologies for solving the complex problem of geometrical covering and cutting.
Next we take a closer look at the matrix technology of rational use of resources. Using the term “technology” we mean the way of designing solutions on the basic idea that allows us to create new variants of algorithms with common structure.
Purpose of the Study
To begin, we examine a problem of rational use of resources as an example of the complex problem of geometrical covering and cutting.
Given: some information concerning MOP (multicoherent orthogonal polygon) and the sizes of rectangular resource. It is necessary to find a plan for the MOP covering and a plan of cutting the rectangular resource into covering items. And in this case, it is required to maximize the covering items’ sizes and to minimize the consumption (either the area or amount) of the resource to be cut. This problem is formalized by a mathematical model of the problem with two goal functions.
The goal functions make it possible to compare the quality of plans of geometrical location for the same sample problem. But they do not allow us to compare fairly and objectively the solution efficiency for different problems inasmuch as their values depend on the initial data, for example on the size of the resource and that of the MOP.
That is why the quality of the location plans is also evaluated with the help of two relative indicators:
for the geometrical covering problem we calculate the covering coefficient
${k}_{\mathrm{c}\mathrm{o}\mathrm{v}}=\frac{{S}_{MOP}}{{P}_{T}}\xb7\frac{{P}_{\text{resourse}}}{{S}_{\text{resourse}}}$,
where
for the orthogonal cutting problem we define the cutting coefficient
${k}_{cut}=\frac{\stackrel{m}{\underset{i=1}{?}}{w}_{i}\xb7{l}_{i}}{{S}_{\text{resourse}}}$.
The geometrical covering coefficient equals 1, if joints of the covering items are only on the boundaries of the MOP and do not go inside the inner area of the MOP, otherwise
If the problem is solved without any waste, i.e. there is no material loss, the cutting coefficient equals 1, otherwise
The covering and cutting coefficients contradict each other because the maximization of the sizes of covering items results in decrease of the cutting coefficient (waste increases). And vice versa, when the sizes of cutting items are small, the cutting coefficient increases but the covering one decreases.
Research Methods
The study of existing algorithms for solving cuttingpacking problems has shown that there are several common approaches or technologies to developing and designing new algorithms. The paper (Dyaminova & Filippova, 2016) describes the following technologies of designing algorithms for solving geometrical location problems: layerbylayer, level; nonlevel; block technologies; matrix; based on special geometric structures.
Cuttingpacking models and methods are wellstudied instances of the problem of optimal use of resources.
The level and matrix technologies are used for designing algorithms to solve complex problems of geometrical covering and cutting. Application of the level technology for this purpose is based on stepbystep fulfilment of algorithms used to solve every next stage (subproblem).
the simple singlepass algorithm “bottom left” (Mukhacheva et al., 2004); it starts working from the uncovered bottom left point and it covers the domain with a rectangle of the maximum admissible size at every pace;
the algorithm offered in (Telitsky, Valiakhmetova, & Hasanova, 2012); it is a modification of the sequential value correction method (Filippova & Valiakhmetova, 2014) and it takes account of excess expenditure of the covering resource; it is a multipass algorithm that makes it possible to find the localoptimal covering plan;
the multipass algorithm of local search for optimum based on the evolutional strategy (Mukhacheva et al., 2004).
the fast singlepass algorithm “first fitting” (Mukhacheva et al., 2004);
the multipass algorithm of sequential value correction (Filippova & Valiakhmetova, 2014), it takes account of the perdetail material expenses when the ordered sequence of items to be cut is generated;
the layerbylayer algorithm with values (Dyaminova & Filippova, 2016), based on the layerbylayer technology that takes account of the perdetail material consumption rate.
In the described below series of experiments we have used, as test examples, some specially generated initial data, they permit to provide the socalled nonwaste solution for the problem. In such examples there is the solution (the covering plan and the cutting plan) when coefficients of geometrical covering and cutting both equal 1.
Findings
When an algorithm based on the matrix technology is used, it results in higher efficiency of solution. In this case, the cutting coefficient differs insignificantly on average, while the geometrical covering coefficient is a bit higher on average.
On average, from the point of view of geometrical covering efficiency, the best result for solving a complex problem is received with the help of some combination of various algorithms. That is, when the evolutional algorithm is used to solve the geometrical covering subproblem, and when and the layerbylayer algorithm with values is used to solve the orthogonal cutting subproblem.
The best result for solving the orthogonal cutting subproblems shows the algorithm combination. It takes place when the evolutional algorithm is used at the stage of solving the geometrical covering subproblem, and the sequential value correction algorithm is applied at the stage of solving the orthogonal cutting subproblem.
Computing experiments were carried out to evaluate the results of the matrix technology used to solve the given problem. They have shown the advantage of the matrix technology as far as the covering quality is concerned. The structure of the matrix technology made it possible to realize variants of the matrix algorithm for the complex problem solution. The computing experiment singled out the best of them from the point of view of the effectiveness of covering and cutting.
Using the special nonwaste examples with preset optimal plans of covering and cutting to evaluate the efficiency makes it possible to come to conclusion that the algorithms under consideration do not find an optimal solution. It means that it is necessary to continue developing methods to improve the ways of designing algorithms for solving NPhard complex problems of geometrical covering and cutting.
Conclusion
The variety of problems of optimal use of resources and the importance of their rational solution calls forth the undying interest of skilled and young researchers of the world to this range of problems. Hence it follows the steady tendency of growth of a number of new methods and techniques for their solution.
The problems of geometrical covering and cutting are widely applied in practice. At that, they belong to the class of NPhard problems. This combination makes the range of problems be very important and challenging for new researches. Therefore, the ideas of L. V. Kantorovich will be used and developed in various spheres of scientific and practical life connected with the problem of saving resources.
Acknowledgments
The work is supported by Russian fund of fundamental research, project 190700895.
References
 Bouaine, A., Lebbar, M., & Ha, M. A. (2018). Minimization of the wood wastes for an industry of furnishing: a two dimensional cutting stock problem. Management and Production Engineering Review, 9(2), 4251.
 Cherri, L. H., Carravilla, M. A., & Toledo, F. M. B. (2016). A modelbased heuristic for the irregular strip packing problem. Pesquisa Operacional, 36(3), 447468.
 Dyaminova, E. I., & Filippova, A. S. (2016). Technologies of decisions designing in problems of geometrical placing. Applied mathematics and fundamental informatics: annual scientific log, 3, 134141.
 Filippova, A. S., & Valiakhmetova, J. I. (2014). Optimal use of resources: cuttingpacking problems. Advances in economics and optimization: collected scientific studies dedicated to the memory of L. V. Kantorovich / editors, Leon A. Petrosyan, Joseph V. Romanovsky & David Wingkay Yeung, 3750.
 Imamichi, T., Yagiura, M., & Nagamochi, H. (2009). An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem. Discrete Optimization, 6, 345–361.
 Kallrath, J., Rebennack, S., Kallrath, J., & Kusche, R. (2014). Solving realworld cutting stockproblems in the paper industry: Mathematical approaches, experience and challenges. European Journal of Operational Research, 238, 374–389.
 Kantorovich, L. V. (1939). Matematicheskie metody organizatsii i planirovaniya proizvodstva [Mathematical Methods of Production Management and Planning]. Leningrad: Leningrad Univ.
 Kartak, V. M., Marchenko, A. A., Petunin, A. A., Sesekin, A. N., & Fabarisova, A. I. (2017). Optimal and heuristic algorithms of planning of lowrise residential buildings. Electronic Materials, 17, 134139.
 Kartak, V. M., & Ripatti, A. V. (2018). The minimum raster set problem and its application to the ddimensional orthogonal packing problem. European Journal of Operational Research, 271(1), 3339.
 Lua, H. C., & Huang, Y. H. (2015). An efficient genetic algorithm with a corner space algorithm for a cutting stock problem in the TFTLCD industry. European Journal of Operational Research, 246, 51–66.
 Mukhacheva, E. A. (1966). Effective cutting of rectangular sheets to rectangular items. Optimal planning, 6, 43115.
 Mukhacheva, E. A., Mukhacheva, A. S., Valeeva, A. F., & Kartak, V. M. (2004). Metody lokalnogo pliska v zadachakh ortogonalnogo raskroia i upakovki: analitichesky obzor i perspektivy razvitiya [Methods of local search in tasks of orthogonal cutting and packing: review and prospects of development]. Informatsionnyie tehnologii, 5, annex, 217.
 Paquay, C., Schyns, M., & Limbourg, S. (2016). A mixed integer programming formulation for the threedimensional binpacking problem deriving from an air cargo application. International Transactions in Operational Research, 23, 187–213.
 Rothe, M., & Reyer, R. (2017). Process Optimization for Cutting SteelPlates. Proc. of the 6th International Conference on Operations Research and Enterprise Systems ICORES 2017, 2737.
 Telitsky, S. V., Valiakhmetova, J. I., & Hasanova, E. I. (2012). Gibridnyy algoritm na osnove posledovatelnogo utochneniya otsenok dlya zadach maksimalnogo ortogonalnogo pokrytiya [Hybrid algorithm on the basis of consecutive specification of estimates for the maximum orthogonal covering problems]. Vestnik Bashkirskogo universiteta, 17(1), 421425.
Copyright information
This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.
About this article
Publication Date
15 November 2020
Article Doi
eBook ISBN
9781802960921
Publisher
European Publisher
Volume
93
Print ISBN (optional)

Edition Number
1st Edition
Pages
11195
Subjects
Teacher, teacher training, teaching skills, teaching techniques, special education, children with special needs, computeraided learning (CAL)
Cite this article as:
Filippova, A., Dyaminova, E., Vasilyeva, L., & Startseva, O. (2020). Rational Use Of Resources: Development Of Method And Technologes. In & I. Murzina (Ed.), Humanistic Practice in Education in a Postmodern Age, vol 93. European Proceedings of Social and Behavioural Sciences (pp. 10111019). European Publisher. https://doi.org/10.15405/epsbs.2020.11.105