Rational Use Of Resources: Development Of Method And Technologes

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 NP-hard cutting-packing 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 cutting-packing 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 multi-coherent 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 problemscutting-packing 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 All-Union 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 cutting-packing 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 lay-out; 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 NP-hard 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 cutting-packing models and methods are well-studied examples of the problem of optimum use of resources.

There exist linear cutting (one-dimensional) problems, rectangular (two-dimensional) and parallelepiped (three-dimensional) cutting-packing problems. And the guillotine cutting-packing 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’ non-intersection, 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 cutting-packing 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 1940-th 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 1948-1949. V. A. Zalgaller developed the method of integer indexes selection, and proposed the decision of the flat (two-dimensional) 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 cutting-packing 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 three-dimensional 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 two-dimensional 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 01 ). The strip has a fixed width, but its length can change in such a way that all rectangles fit into it. The researchers worked out an iterative algorithm of local search to minimize the strip length.

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 two-stage heuristics. At the first stage, certain templates for cutting material into items are generated, using the classic algorithms of two-dimensional packing. At the second stage, the integer LP problem is solved where the generated templates are used as variables.

See Full Size >

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 sub-problems.

The cutting-packing problems are typical representatives of NP-hard problems. As far as the exact algorithms for cutting-packing problems are of non-polynomial complexity, many authors of scientific papers have paid much attention to approximate methods, and when they develop exact algorithms they use procedures of full sorting-out reduction and of low border calculation.

Mathematical models of integer linear programming (ILP) are traditional for unitary cutting-packing 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 cutting-packing 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 d-dimensional 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 low-rise residential building is considered by V. M. Kartak and his co-authors. It is still another NP-hard 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 (multi-coherent 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}·\frac{P_{\text{resourse}}}{S_{\text{resourse}}}$,

where S _MOP and S _resourse are the areas of the MOP and of the resource correspondingly, P _T and P _resourse are summarized perimeters of the covering items and of the resource correspondingly;

• for the orthogonal cutting problem we define the cutting coefficient

$k_{cut}=\frac{\stackrel{m}{\underset{i=1}{?}}{w}_i·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 k _cov < 1.

If the problem is solved without any waste, i.e. there is no material loss, the cutting coefficient equals 1, otherwise k _cut <1.

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 cutting-packing 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: layer-by-layer, level; non-level; block technologies; matrix; based on special geometric structures.

Cutting-packing models and methods are well-studied 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 step-by-step fulfilment of algorithms used to solve every next stage (sub-problem).

Stage I: decomposition of the MOP. Geometrical component of the problem to be solved makes it difficult to transform the information while designing the solutions. It is connected with geometrical peculiarities of the area where items are being located. This stage is aimed at describing the initial MOP as a set of one-connected rectangular areas to be covered. To solve this stage, the authors of the given paper use a level algorithm (some modification of the level algorithm of sequential cuttings) and the matrix way of presenting geometric information (Dyaminova & Filippova, 2016).

Stage II: geometrical covering . The plan to cover each of the domains with rectangular items is found, provided that the rectangular items are of the maximum size for the given resource. It means that the sub-problem of geometrical covering for the rectangular domain is solved. For this purpose the following can be used:

• the simple single-pass 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 multi-pass algorithm that makes it possible to find the local-optimal covering plan;

• the multi-pass algorithm of local search for optimum based on the evolutional strategy (Mukhacheva et al., 2004).

Stage III: orthogonal cutting . The last stage implies solution of the cutting sub-problem where it is required to find a plan of cutting the resource into covering items. Any known algorithm for solving the rectangular packing problem can be used here. To implement this stage we used the following:

• the fast single-pass algorithm “first fitting” (Mukhacheva et al., 2004);

• the multi-pass algorithm of sequential value correction (Filippova & Valiakhmetova, 2014), it takes account of the per-detail material expenses when the ordered sequence of items to be cut is generated;

• the layer-by-layer algorithm with values (Dyaminova & Filippova, 2016), based on the layer-by-layer technology that takes account of the per-detail 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 so-called non-waste 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 sub-problem, and when and the layer-by-layer algorithm with values is used to solve the orthogonal cutting sub-problem.

The best result for solving the orthogonal cutting sub-problems shows the algorithm combination. It takes place when the evolutional algorithm is used at the stage of solving the geometrical covering sub-problem, and the sequential value correction algorithm is applied at the stage of solving the orthogonal cutting sub-problem.

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 non-waste examples with pre-set 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 NP-hard 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 NP-hard 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 19-07-00895.

References

1. 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), 42-51.
2. Cherri, L. H., Carravilla, M. A., & Toledo, F. M. B. (2016). A model-based heuristic for the irregular strip packing problem. Pesquisa Operacional, 36(3), 447-468.
3. 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, 134-141.
4. Filippova, A. S., & Valiakhmetova, J. I. (2014). Optimal use of resources: cutting-packing 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 Wing-kay Yeung, 37-50.
5. 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.
6. Kallrath, J., Rebennack, S., Kallrath, J., & Kusche, R. (2014). Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges. European Journal of Operational Research, 238, 374–389.
7. Kantorovich, L. V. (1939). Matematicheskie metody organizatsii i planirovaniya proizvodstva [Mathematical Methods of Production Management and Planning]. Leningrad: Leningrad Univ.
8. Kartak, V. M., Marchenko, A. A., Petunin, A. A., Sesekin, A. N., & Fabarisova, A. I. (2017). Optimal and heuristic algorithms of planning of low-rise residential buildings.  Electronic Materials, 17, 134-139.
9. Kartak, V. M., & Ripatti, A. V. (2018). The minimum raster set problem and its application to the d-dimensional orthogonal packing problem. European Journal of Operational Research, 271(1), 33-39.
10. Lua, H. C., & Huang, Y. H. (2015). An efficient genetic algorithm with a corner space algorithm for a cutting stock problem in the TFT-LCD industry. European Journal of Operational Research, 246, 51–66.
11. Mukhacheva, E. A. (1966). Effective cutting of rectangular sheets to rectangular items. Optimal planning, 6, 43-115.
12. 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, 2-17.
13. Paquay, C., Schyns, M., & Limbourg, S. (2016). A mixed integer programming formulation for the three-dimensional bin-packing problem deriving from an air cargo application. International Transactions in Operational Research, 23, 187–213.
14. Rothe, M., & Reyer, R. (2017). Process Optimization for Cutting Steel-Plates. Proc. of the 6th International Conference on Operations Research and Enterprise Systems ICORES 2017, 27-37.
15. 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), 421-425.