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 NP-hard. 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 multi-pass 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 two-criterion complex problem of geometrical location. The stages of solving the problem are described. The computing experiment results based on the specially generated non-waste 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
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 (one-dimensional) material cutting;
Cutting of sheets to rectangular items;
Packing three-dimensional 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 sub-problem. 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 double-criterion one: it is needed to minimize the material consumption and to maximize the covering items’ sizes. Another variant of developing a combined cutting-covering 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.
To begin, we examine a
To describe MOP covering areas we enter the rectangular coordinate system: here the axes
Required: to find a plan of covering MOP
is a set of
To formalize the problem, we enter some additional variables
, so that
), 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 ,
For the orthogonal cutting problem we define the cutting coefficient as follows .
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 cutting-packing 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: layer-by-layer; level; non-level; 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 (sub-problems).
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 once-covered or iteratively-covered 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 multi-coherent 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 two-dimensional 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 sub-problem of geometrical covering for the rectangular area is being solved. For this, the following can be used:
the simple single-pass 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 multi-pass algorithm that makes it possible to find the local-optimum covering plan;
the multi-pass algorithm of local search for optimum based on the evolutional strategy ( Mukhacheva et al., 2004).
At the last stage, a cutting sub-problem 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 one-pass algorithm “first fitting”;
multi-pass algorithm of sequential value correction ( Mukhacheva et al., 2004), it takes account of the per-detail expenses when the ordered sequence of items to be cut is generated;
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, as test examples we used some specially generated initial data providing the so-called non-waste 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 three-step methods of solving the problem, here at each step one sub-problem is solved by one of the possible algorithms. The output information of one sub-problem 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 sub-problems of covering and cutting. They are:
M1based on the matrix technology that uses the following:
stage 1 – the sub-problem of MOP decomposition: matrix decomposition algorithm,
stage 2 – the geometrical covering sub-problem: - “bottom left” algorithm,
stage 3 – the cutting sub-problem: “first fitting” algorithm;
L1based on the level technology that employs the following:
stage 1 – the problem of MOP decomposition: level algorithm,
stage 2 – the geometrical covering sub-problem: - “bottom left” algorithm,
stage 3 – the cutting sub-problem: “first fitting” algorithm.
Ten non-waste 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 sub-problems at each stage:
stage 1 – the sub-problem of MOP decomposition: matrix decomposition algorithm (
stage 2 – the geometrical covering sub-problem: “bottom left” algorithm (
stage 3 – the cutting sub-problem: “first fitting” algorithm (
Thus, we received the following variants of the general algorithm
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 sub-problem and the layer-by-layer algorithm with values to solve the orthogonal cutting sub-problem. All other algorithm combinations are considerably behindhand as for the geometrical covering coefficient is concerned, both in separate examples and on average.
The algorithm combination M+E+V (M8) shows the best result for the orthogonal cutting sub-problems. At the stage of solving the geometrical covering sub-problem, the evolutional algorithm was used. At the stage of solving the orthogonal cutting sub-problem, 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 sub-problems, and the layer-by-layer with values algorithm and the first fitting one are applied at the stage of solving the orthogonal cutting sub-problem. It is also significant that only one algorithm variant shows the optimal solution for the cutting sub-problem. It is the algorithm with M+BL+L (M3) combination. Neither variant gives the optimal covering plan.
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 non-waste 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 NP-hard complex problems of geometrical covering and cutting.
The work is supported by Russian fund of fundamental research (project 19-07-00895, 19-07-00780).
- 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.
- Chazelle, B. (1983). The bottom-left bin packing heuristic: An efficient implementation. IEEE Trans. on Comput, 2, 697-707.
- 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.
- Dykhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational research, 44, 145-159.
- 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.
- 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.
- 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, 14, 234-235.
- 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.
- 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 multi-coherent orthogonal polygon with boundary obstacles taking into account design and technological restrictions]. Vestnik RGTRU, 4(50), part 2, 75-82.
- 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.
- 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, 2-17.
- 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.
- 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.
- 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.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
About this article
15 November 2020
Print ISBN (optional)
Teacher, teacher training, teaching skills, teaching techniques, special education, children with special needs, computer-aided 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. 1020-1030). European Publisher. https://doi.org/10.15405/epsbs.2020.11.106