Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem. (English) Zbl 0916.90234
Summary: This work deals with the problem of optimal allocation of objects of a so-called irregular form. The objects are allocated on a strip of given width and with defects. This problem is insufficiently studied, but it is typical for many industries and is also interesting for developing the theory of solving cutting and packing problems. An analytical model of the problem using only continuous variables is written in terms of classical mathematical programming, and it is constructed on the basis of the original theory of \(\Phi\)-functions and structures of linear inequalities. The presented theory allows one to easily describe the conditions of mutual non-overlapping of objects and their allocation in the stock region. The exact method for searching a local minimum of the problem from any feasible initial point is based on the application of the active set strategy ideas. A number of examples of solving practical problems are considered.
MSC:
| 90C27 | Combinatorial optimization |
References:
| [1] | Bailleul, I.; Tiaibia, K.; Soenen, R., Nesting two dimensional irregular shapes in anisotropic material, (Advances in CAD/CAM: Proc. PROLAMAT 82. Advances in CAD/CAM: Proc. PROLAMAT 82, Leningrad, USSR 161̄8 May 1982 (1983), North-Holland: North-Holland Amsterdam) |
| [2] | Beasley, J. E., An exact two-dimensional non-guillotine cutting tree search procedure, Operational Research, 33, 49-65 (1985) · Zbl 0569.90038 |
| [3] | Berge, Cl., Topological Spaces (1963), Oliver and Boyd: Oliver and Boyd Edinburgh · Zbl 0114.38602 |
| [4] | Chen, C.-S.; Ram, B.; Sarin, S., An integer programming model for a class of assortment problems, (Report Dept. of Ind. Eng., North Carolina (1989), A & T State University: A & T State University Greensboro) |
| [5] | Dowsland, K. A.; Dowsland, W. B., Packing problems, European Journal of Operational Research, 56, 2-14 (1992) · Zbl 0825.90355 |
| [6] | Dowsland, K. A.; Dowsland, W. B., Heuristic approaches to irregular cutting problems, (Working Paper (1993)), 1-15 · Zbl 1131.90440 |
| [7] | Dyckhoff, H., A typology of cutting and packing problems, European Journal of Operational Research, 44, 145-160 (1990) · Zbl 0684.90076 |
| [8] | Gill, P. E.; Murray, W.; Wright, M. H., Practical Optimization (1981), Academic Press: Academic Press London · Zbl 0503.90062 |
| [9] | Komyak, V. M., Optimization of the allocation of plane geometric objects in complex-shape regions, (Author’s Abstract Cand. Tech. Sci. Dissertation (1980), Kharkov Institute of Radioelectronics: Kharkov Institute of Radioelectronics Kharkov, Ukraine), (Russ.) |
| [10] | Kurosh, A. G., Lectures on General Algebra (1976), Nauka: Nauka Moscow, (in Russian) · Zbl 0384.00003 |
| [11] | Li, Zh.; Milenkovic, V., A compaction algorithm for non-convex polygons and its application, (9th Annual ACM Symposium on Computational Geometry. 9th Annual ACM Symposium on Computational Geometry, May 19-21 (1993)) |
| [12] | Magas, S. L., Methods of solving extremal problems in allocation of polygonal geometric objects on a strip, Author’s Abstract Cand. Phys.-Math. Sci. Dissertation (1984), Moscow (in Russian) |
| [13] | Marques, V. M.M.; Bispo, C. E.G.; Sentieiro, J. J.S., A system for the compaction of two dimensional irregular shapes based on simulated annealing, (IECON’91 (1991), IEEE), 1911-1916 |
| [14] | Milenkovic, V.; Daniels, K.; Li, Zh., Placement and compaction of non-convex polygons for clothing manufacture, (Fourth Canadian Conference on Computational Geometry. Fourth Canadian Conference on Computational Geometry, St. John’s, Newfoundland, Canada (1992)) |
| [15] | Novozhilova, M. V., Solution of the problem of searching for the global extremum of a linear objective function on a linear inequality structure, ((1988), Institute for Problem in Machinery of the Ukrainian SSR Academy of Sciences: Institute for Problem in Machinery of the Ukrainian SSR Academy of Sciences Kharkov, Ukraine), 292, (in Russian) |
| [16] | Novozhilova, M. V., Methods of searching for an extremum of a linear objective function on a structure of linear inequalities, Author’s Abstract Cand. Phys.-Math. Sci. Dissertation (1988), Kharkov, Ukraine (in Russian) · Zbl 0654.90052 |
| [17] | Oliveira, J. F.S.; Ferreira, J. A.S., Algorithms for Nesting Problems, (Vidal, R. V., Applied Simulated Annealing (1992), Springer Verlag), 255-275 |
| [18] | Opanasiuk, A. B., Automation of design of location and spacing charts for sheet materials with account of the assortment of sheets and complete set of parts, Author’s Abstract Cand. Tech. Sci. Dissertation (1986), Kiev, Ukraine (in Russian) |
| [19] | Ponomarenko, L. D.; Makmak, P. M., New approaches to minimization on permutations when packing geometric objects, (Theory and Methods of Automated Design, Minsk. Theory and Methods of Automated Design, Minsk, Ac. Sci. BSSR, 4 (1980), Inst. for Technical Cybernetics), (in Russian) |
| [20] | Rvachev, V. L., Theory of R-Functions and Some of Its Applications (1982), Naukova dumka: Naukova dumka Kiev, Ukraine, (in Russian) · Zbl 0521.65084 |
| [21] | Rvachev, V. L.; Stoyan, Yu. G., On the problem of optimal cutting of materials, (Problems in Theoretical Cybernetics (1965), Naukova dumka: Naukova dumka Kiev, Ukraine), 189-199, (in Russian) |
| [22] | Stoyan, Yu. G., R-function methods in the problems of optimal cutting, Author’s Abstract Cand. Tech. Sci. Dissertation (1966), Kiev, Ukrain, (in Russian) |
| [23] | Stoyan, Yu. G., On the optimal allocation of the geometric objects, Abstract Dr. Tech. Sci. Dissertation (1970), Moscow, Russia (in Russian) |
| [24] | Stoyan, Yu. G., Allocation of Geometric Objects (1975), Naukova dumka: Naukova dumka Kiev, Ukraine, (in Russian) · Zbl 0307.50007 |
| [25] | Stoyan, Yu. G., On one generalization of the dense allocation function, Reports Ukrainian SSR Academy of Science, 70-74 (1980), (in Russian) |
| [26] | Stoyan, Yu. G., Mathematical methods for geometrical design, (Advances in CAD/CAM: Proceedings PROLAMAT 82. Advances in CAD/CAM: Proceedings PROLAMAT 82, Leningrad, USSR 16-18 May 1982) (1983), North-Holland: North-Holland Amsterdam), 67-86 · Zbl 0987.90069 |
| [27] | Stoyan, Yu. G., A basic problem of optimal cutting of materials in blanks of arbitrary spatial form, (34th ORSA/17MS Joint National Meeting. 34th ORSA/17MS Joint National Meeting, San Francisco, Ca. (1992)) |
| [28] | Stoyan, Yu. G., Precise and approximate methods of problems in irregular allocation of non-convex polygons in a strip of minimal length, (Report on Conference IFORS. Report on Conference IFORS, Lisbon, 15-19 July (1993)) |
| [29] | Stoyan, Yu. G.; Gil’, N. I., Properties and methods of realization of the dense allocation function, ((1972), Institute for Cybernetics of the Ukrainian SSR Academy of Sciences: Institute for Cybernetics of the Ukrainian SSR Academy of Sciences Kiev, Ukraine), 72, (in Russian) |
| [30] | Stoyan, Yu. G.; Gil’, N. I., Method of asymptotic exhaustion of local extrema, ((1974), Institute for Problem in Machinery of the Ukrainian SSR Academy of Sciences: Institute for Problem in Machinery of the Ukrainian SSR Academy of Sciences Kharkov, Ukraine), 1, (in Russian) |
| [31] | Stoyan, Yu. G.; Gil’, N. I., Methods and Algorithms of Allocation of Planar Geometric Objects (1976), Naukova Dumka: Naukova Dumka Kiev, Ukraine, (in Russian) |
| [32] | Stoyan, Yu. G.; Novozhilova, M. X.; Kartashov, A. V., Mathematical model and optimization of linear Ek(R2)-allocation problems, ((1991), Institute for Problem in Machinery of the Ukrainian SSR Academy of Sciences: Institute for Problem in Machinery of the Ukrainian SSR Academy of Sciences Kharkov, Ukraine), 353, (in Russian) |
| [33] | Stoyan, Yu. G.; Ponomarenko, L. D., Minkowsky’s sum and the hodograph of the dense allocation vector-function, Reports Ukrainian SSR Academy of Science, 10 (1977), Ser. A |
| [34] | Stoyan, Yu. G.; Yakovlev, S. Vs., Mathematical Models and Optimization Methods in Geometric Design (1986), Naukova dumka: Naukova dumka Kiev, (in Russian) |
| [35] | Sweeney, P. E.; Ridenour, E. L., Cutting and packing problems: a categorized, application orientated research bibliography, (Working Paper 610 (1989), School of Business Administration, University of Michigan) · Zbl 0757.90055 |
| [36] | Tero, J. R.; Scheithauer, G., Modelling of packing problems, (working paper (1993)) |
| [37] | Yanasse, H. H.; Zinober, A. S.I.; Harris, R. G., Twodimensional cutting stock with multiple stock sizes, Journal of the Operational Research Society, 42, 8 (1991) · Zbl 0729.90755 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
