Abstract
The problem of resource saving on the example of geometric location of objects is considered. Such processes are known as problems of cutting, packing and geometrical covering. The majority of these problems are NPhard. Nowadays there are still no algorithms of polynomial complexity to find optimum solutions for the above problems. Therefore, in the modern world much attention is paid to the study and development of approximate efficient algorithms for their solution. In practice, it is profitable to use heuristic multipass algorithms. They make it possible to find a rational solution but do not guarantee the optimum. The paper describes the matrix data processing technology to construct solutions for geometrical location problems. Thus, it is possible to form different variants of algorithms with a common structure. And further study of the effectiveness of the obtained algorithms allows us to determine the best of them. This process is described in the given paper. The estimation of efficiency of algorithms constructed on the basis of the described technology is checked on the example of the solution of a twocriterion complex problem of geometrical location. The stages of solving the problem are described. The computing experiment results based on the specially generated nonwaste examples with a unitary coefficient of covering and cutting are given. The variants of the algorithm for the rational use of resources are determined.
Keywords: Problem of geometrical coveringresource saving
Introduction
Technological processes often use the step of item cutting or location taking into account their geometric peculiarities. This step is urgent for resource saving and it is difficult for decision making.
Currently, many scientists are developing effective algorithms for practical problems of resource saving ( Bouaine, Lebbar, & Ha, 2018; Kallrath, Rebennack, Kallrath & Kusche, 2014; Kartak, Marchenko, Petunin, Sesekin, & Fabarisova, 2017; Kartak & Ripatti, 2018; Kulga & Menshikov, 2014; Lua & Huang, 2015; Paquay, Schyns, & Limbourg, 2016; Rothe & Reyer, 2017).
Technological process is the way to design solutions and to create various algorithms with a common structure. The paper summarizes several techniques of developing and creating algorithms to solve geometrical location problems.
We can list basic problems of geometrical location ( Filippova & Valiakhmetova, 2014; Wang & Wascher, 2002):
Linear (onedimensional) material cutting;
Cutting of sheets to rectangular items;
Packing threedimensional containers;
Cutting and location of shaped objects in the given area;
Maximum covering of linear material;
Rectangular geometrical covering.
The classification of basic models for geometrical location problems is given in ( Dykhoff, 1990; Mukhacheva, Mukhacheva, Valeeva, & Kartak, 2004).
The problem of optimum geometrical location occurs in practice both as an autonomous problem and as a subproblem. Besides, complex problems are being researched nowadays. The first example is a problem of geometrical covering and cutting ( Filippova & Valiakhmetova, 2014), where it is required to find a plan of covering some area (for example, floor) and a plan of cutting some material to covering items (for example, linoleum). The problem is a doublecriterion one: it is needed to minimize the material consumption and to maximize the covering items’ sizes. Another variant of developing a combined cuttingcovering problem represents a problem of covering some special technical objects, such as shells, with sheet material ( Kulga & Menshikov, 2014).
Despite a great variety of the location problems, all of them have the same structure. There exist two groups of objects, and a correspondence between the elements of these groups is established and estimated. This structure makes it possible to develop and use similar approaches to generating solutions for different problems.
Problem Statement
To begin, we examine a
To describe MOP covering areas we enter the rectangular coordinate system: here the axes
Research Questions
Required: to find a plan of covering MOP
Where $T=\left\{m,\text{}w=({w}_{1},{w}_{2},...,{w}_{m}),\text{}l=({l}_{1},{l}_{2},...,{l}_{m})\right\}$
is a set of
To formalize the problem, we enter some additional variables
${z}_{ij}^{x}$,
${z}_{ij}^{y}$,
${\stackrel{~}{z}}_{i\nu}^{x}$ and
${\stackrel{~}{z}}_{i\nu}^{y}$, so that
${z}_{ij}^{x}=1$ (
${z}_{ij}^{y}=1$), if the rectangular element’s projection
Then it is necessary to find the following:
1. A set
The conditions (
2. The plan to cut the orthogonal resource to rectangular items of the set
The conditions (
The goal functions min F _{cov}(T) and min F _{cut}(T) make it possible to compare the quality of different solutions for the same problem, but do not make it possible to compare the solution efficiency for different problems as their values depend on the initial data, for example, on the sizes of the resource and of the MOP.
That is why the quality of solutions is also estimated 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 as follows ${k}_{cut}=\frac{\stackrel{m}{\underset{i=1}{\sum}}{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 MOP and do not go into the inner area, otherwise
If the problem is solved without any waste material the cutting coefficient equals 1, otherwise
The covering and cutting coefficients contradict each other because maximization of the sizes of covering items results in decrease of the cutting coefficient (waste increases). And vice versa, when the sizes of cutting elements are small, the cutting coefficient increases but the covering one decreases.
Purpose of the Study
The study of algorithms for solving cuttingpacking problems has shown that there exist several common approaches, i.e. 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; matrix; based on special geometric structures. The level and matrix technologies are used for designing algorithms to solve the formulated above problem.
Application of the level technology for the complex problem of geometrical covering and cutting is based on sequential execution of algorithms for solving each of the following stages (subproblems).
The geometrical component of the above problem makes imposes certain difficulties in the transformation of information while designing solutions. It is connected with geometrical peculiarities of the area in which items are located. This stage is aimed at describing the initial MOP as a set of rectangular areas to be covered.
To solve this stage, the authors of the given paper use a level algorithm ( Simonis & O’Sullivan, 2008) and a matrix method of presenting geometric information ( Dyaminova & Filippova, 2016).
Every area to be covered is presented as a matrix in the above algorithm of ( Dyaminova & Filippova, 2016). In the 2D matrix every cell represents a pixel on a plane. The matrix elements show whether an area is uncovered, or oncecovered or iterativelycovered by geometrical items.
Earlier, the authors of the given paper proposed an algorithm based on the matrix method to solve the following problem.
The rectangle location problem in a multicoherent orthogonal polygon (MOP). There is given an orthogonal polygonal area, it is enveloped by a rectangle with the known width
of rectangular obstacles inside the area (Figure
The algorithm based on the matrix technology of designing rectangular item location inside a polygonal area is described in detail in ( Dyaminova & Filippova, 2016), where the MOP presents a twodimensional binary array.
All faces of the obstacles are lined through. So the area with obstacles becomes covered with a network (Figure
The algorithms based on matrix technology have shown high efficiency on both real and generated test examples of problems of rectangular location and of geometrical covering ( Dyaminova & Filippova, 2016; Kulga & Menshikov, 2014).
The covering plan to each area is found provided that rectangular items to be located are of the maximum size for the given resource. It means that the subproblem of geometrical covering for the rectangular area is being solved. For this, the following can be used:
the simple singlepass algorithm “bottom left” ( Chazelle, 1983), it starts working from the uncovered bottom left point and covers the area with a rectangle of the maximum admissible size at every pace;
the algorithm offered in, it is a modification of the sequential value correction ( Mukhacheva et al., 2004) and it takes into account the covering resource excess expenditure; it is a multipass algorithm that makes it possible to find the localoptimum covering plan;
the multipass algorithm of local search for optimum based on the evolutional strategy ( Mukhacheva et al., 2004).
At the last stage, a cutting subproblem is solved, when it is required to find the plan for cutting resource to covering items. Any known algorithm for solving the rectangular packing problem can be used here. For this purpose we used the following:
fast onepass algorithm “first fitting”;
multipass algorithm of sequential value correction ( Mukhacheva et al., 2004), it takes account of the perdetail expenses when the ordered sequence of items to be cut is generated;
layerbylayer algorithm with values ( Dyaminova & Filippova, 2016), based on the layerbylayer technology that takes account of the perdetail material consumption rate.
Research Methods
In the described below series of experiments, as test examples we used some specially generated initial data providing the socalled nonwaste solution for the problem. In such examples there exist a solution (the covering plan and the cutting plan) when coefficients of geometrical covering and of cutting both equal 1.
These are the threestep methods of solving the problem, here at each step one subproblem is solved by one of the possible algorithms. The output information of one subproblem becomes the initial data for the next problem. We have investigated the efficiency of two general algorithms in which simple heuristics are used for solving subproblems of covering and cutting. They are:
one algorithm
M1 based on the matrix technology that uses the following:stage 1 – the subproblem of MOP decomposition: matrix decomposition algorithm,
stage 2 – the geometrical covering subproblem:  “bottom left” algorithm,
stage 3 – the cutting subproblem: “first fitting” algorithm;
another algorithm
L1 based on the level technology that employs the following:stage 1 – the problem of MOP decomposition: level algorithm,
stage 2 – the geometrical covering subproblem:  “bottom left” algorithm,
stage 3 – the cutting subproblem: “first fitting” algorithm.
Ten nonwaste problems have been solved and the results of the experiment №1 are shown in the tables
As one can see from the tables
So we have used the matrix algorithms in the next experiment for researching the effectiveness of the algorithm variants based on one technology.
The effectiveness of nine general algorithms on the basis of the matrix technology has been studied. The following algorithms were used for solving subproblems at each stage:
stage 1 – the subproblem of MOP decomposition: matrix decomposition algorithm (
stage 2 – the geometrical covering subproblem: “bottom left” algorithm (
stage 3 – the cutting subproblem: “first fitting” algorithm (
Thus, we received the following variants of the general algorithm
Tables
On average, the best result for solving a complex problem, from the point of view of geometrical covering efficiency, is received with the help of the combination M+E+L (M9), in case when the evolutional algorithm is used to solve the geometrical covering subproblem and the layerbylayer algorithm with values to solve the orthogonal cutting subproblem. All other algorithm combinations are considerably behindhand as for the geometrical covering coefficient is concerned, both in separate examples and on average.
Findings
The algorithm combination M+E+V (M8) shows the best result for the orthogonal cutting subproblems. At the stage of solving the geometrical covering subproblem, the evolutional algorithm was used. At the stage of solving the orthogonal cutting subproblem, the sequential value correction algorithm was applied. It is worth noting that other algorithm combinations also result in quite efficient solutions. The orthogonal cutting coefficient differs insignificantly in cases with M+V+L (M6) and M+V+F (M4) combinations. It occurs when the sequential value correction algorithm is used at the stage of solving the geometrical covering subproblems, and the layerbylayer with values algorithm and the first fitting one are applied at the stage of solving the orthogonal cutting subproblem. It is also significant that only one algorithm variant shows the optimal solution for the cutting subproblem. It is the algorithm with M+BL+L (M3) combination. Neither variant gives the optimal covering plan.
Conclusion
We propose schemes of implementation of variants of algorithms for solving the complex problem of geometrical covering and cutting, these variants are based on the level and the matrix technologies. One of the computing experiments has 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 nine variants of the matrix algorithm for solving the complex problem. The computing experiment singled out the best of them from the point of view of effectiveness of covering and cutting.
We have used the special nonwaste examples with preset optimal plans of covering and cutting to evaluate the efficiency and we come to conclusion that neither algorithm under consideration has got the optimal solution. It means that it is necessary to keep on improving the ways of designing algorithms for solving NPhard complex problems of geometrical covering and cutting.
Acknowledgments
The work is supported by Russian fund of fundamental research (project 190700895, 190700780).
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.
 Chazelle, B. (1983). The bottomleft bin packing heuristic: An efficient implementation. IEEE Trans. on Comput, 2, 697707.
 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.
 Dykhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational research, 44, 145159.
 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.
 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.
 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, 14, 234235.
 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.
 Kulga, K. S., & Menshikov, P. V. (2014). Optimizatsiyia geometricheskogo pokrytiya mnogo kogerentnogo ortogonalnogo mnogougolnika s granichnymi prepyatstviyami s uchetom konstruktivnykh i tekhnologicheskikh ogranicheny [Optimization of geometrical covering of the multicoherent orthogonal polygon with boundary obstacles taking into account design and technological restrictions]. Vestnik RGTRU, 4(50), part 2, 7582.
 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., Mukhacheva, A. S., Valeeva, A. F., & Kartak, V. M. (2004). Methods of local search in tasks of orthogonal cutting and packing: review and prospects of development. Information Technologies, 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.
 Simonis, H., & O’Sullivan, B. (2008). Search strategies for rectangle packing. LNCS, 5202, 52–66.
 Wang, P., & Wascher, G. (2002). Special issue: Cutting Packing Problems. European Journal of Operational research, 141.
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., & Valiahmetova, Y. (2020). Matrix Data Processing Technology For Resource Saving. In I. Murzina (Ed.), Humanistic Practice in Education in a Postmodern Age, vol 93. European Proceedings of Social and Behavioural Sciences (pp. 10201030). European Publisher. https://doi.org/10.15405/epsbs.2020.11.106