main| new issue| archive| editorial board| for the authors| publishing house|
Πσρρκθι
Main page
New issue
Archive of articles
Editorial board
For the authors
Publishing house

 

 


ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 11. Vol. 30. 2024

DOI: 10.17587/it.30.555-564

A. A. Andrianova, Ph.D, Associate Professor,
Kazan (Volga Region) Federal University, Kazan, Russian Federation

Heuristic Approaches for Using an Exact Model to Obtain the Placement of a Set of Rectangles on a Half-Strip

There is considered the problem of the compact orthogonal placement, which consists in placing of the set of rectangles on the half-strip and its solution by constructing an optimization model that reduces to solving a high-dimensional linear partial Boolean programming problem. The main method of solving the problem is the algorithm of branches and boundaries, providing consistent fiXation of the Boolean variables. The direct use of this algorithm represents significant computational difficulties and is used only for the small size of the initial set of rectangles. In this paper are proposes approaches that reduce the computational complexity of the solution of this optimization model by using heuristic approaches to fix individual Boolean variables. Most of the variables responsible for the relative arrangement of all pairs of rectangles relative to each other are fixed on the basis of generating the permutation of rectangles and special code that determines the direction by which the intersection of the location of the rectangles should be monitored. Thus, the direct computing complexity of the method of branches and the boundaries of solving the problem becomes insignificant. To generate pre-fixation of the Boolean variables, genetic algorithms and local search algorithms are used. Computational experiments showed that the used techniques of fixing the Boolean variables allowed to reduce the volume of calculations and the quality of the resulting approximate solution, in general, it turns out acceptable.
Keywords: problem of compact orthogonal placement of a set of rectangles on a half-strip, optimization exact model, linear partial Boolean programming model, branch and bound method, Land and Doig method, reducing computational complexity, permutation placement, genetic algorithms, local search algorithms, approximate solution

Acknowledgments: This paper has been supported by the Kazan Federal University Strategic Academic Leadership Program ("PRIORITY-2030").

P. 555-564

References

  1. Levin M. Sh. Packing in containers (perspective models, examples), Informatsionnyye protsessy, 2017, vol. 17, no 1, pp. 43—60 (in Russian).
  2. Guo B., Zhang Y., Hu J., Li J., Wu F., Peng Q., Zhang Q. Two-dimensional irregular packing problems: A review, Frontiers in Mechanical Engineering, 2022, vol. 8, doi: 10.3389/fmech.2022.966691.
  3. Oliveira O., Gamboa D., Silva E. An introduction to the two-dimensional rectangular cutting and packing problem, Intl. Trans. in Op. Res., 2023, no. 30, pp. 3238— 3266, doi: https://doi.org/10.1111/itor.13236.
  4. Mukhacheva E. A. Rational cutting of industrial materials. Application in automated control systems, Novosibirsk, Nauka, 1987, 274 p. (in Russian).
  5. Hifi M. A local search-based method for sphere packing problems, European Journal of Operational Research, 2019, vol. 274, no. 2, pp. 482—500.
  6. Chekanin V. A. Multimethod genetic algorithm for solving problems of cutting and packing rectangular objects, Vestnik MGTU "Stankin", 2019, no. 4 (51), pp. 14—18. (in Russian)
  7. Guerriero F., Saccomanno F. P. A hierarchical hyper-heuristic for the bin packing problem, Soft Comput., 2023, vol. 27, pp. 12997—13010.
  8. Kokten E. S., Sel Q. A cutting stock problem in the wood products industry: a two-stage solution approach, International Transactions in Operational Research, 2020, vol. 29, no 2, pp. 879—907.
  9. Arnaout J. P., ElKhoury C., Karayaz G. Solving the multiple level warehouse layout problem using ant colony optimization, Oper. Res. Int. J., 2020, vol. 20 (1), pp. 473—490, doi: 10.1007/s12351-017-0334-5.
  10. Erzin A., Melidi G., Nazarenko S., Plotnikov R. A 3/2-ap-proximation for big two-bar charts packing, J. Comb. Optim., 2021, vol. 42 (1), pp. 71—84, doi:10.1007/s10878-021-00741-1.
  11. Gardeyn J., Wauters T. A goal-driven ruin and recreate heuristic for the 2D variable-sized bin packing problem with guillotine constraints, European Journal of Operational Research, 2 022, vol. 301 (2), pp. 432—444, doi: 10.1016/j.ejor.2021.11.031
  12. Zhang H., Liu Q., Wei L. J., Zeng J., Leng J., Yan D. An iteratively doubling local search for the two-dimensional irregular bin packing problem with limited rotations, Comput. Operations Res., 2022, vol. 137, p. 105550, doi: 10.1016/j.cor.2021.105550.
  13. Wu L., Tian X., Zhang J., Liu Q., Xiao W., Yang Y. An improved heuristic algorithm for 2d rectangle packing area minimization problems with central rectangles, Eng. Appl. Artif. Intell., 2017, vol. 66, pp. 1—16, doi: 10.1016/j.engappai.2017.08.012.
  14. Russo M., Boccia M., Sforza A., Sterle C. Constrained two-dimensional guillotine cutting problem: upper-bound review and categorization, International Transactions in Operational Research, 2020, vol. 27, no. 2, pp. 794—834.
  15. Leao A. A. S., Toledo F. M. B., Oliveira J. F., Carravilla M. A., Alvarez-Vald e s R. Irregular packing problems: A review of mathematical models, European Journal of Operational Research, 2020, vol. 282 (3), pp. 803—822, doi: 10.1016/j.ejor.2019.04.045
  16. Wang T., Hu Q., Lim A. An exact algorithm for two-dimensional vector packing problem with volumetric weight and general costs, European Journal of Operational Research, 2022, vol. 300 (1), pp. 20—34, doi: 10.1016/j.ejor.2021.10.011.
  17. Iori M., de Lima V. L., Martello S., Miyazawa F. K., Monaci M. Exact solution techniques for two-dimensional cutting and packing, European Journal of Operational Research, 2021, vol. 289, no. 2, pp. 399—415, doi: https://doi.org/10.1016/j.ejor.2020.06.050.
  18. Andrianova A. A., Mukhtarova T. M., Fazylov V. R. Models of non-guillotine placement of a set of rectangular parts on a sheet and half-strip, Uchen. zap. Kazan. un-ta. Ser. Fiz.matem. nauki, 2013, vol. 155, no. 2, pp. 5—18 (in Russian).
  19. Land A. H., Doig A. G. An automatic method of solving discrete programming problems, Econometrica, 1960, vol. 28, no. 3, pp. 497—520.
  20. Chekanin V. A. Development of a packaging compaction algorithm to improve the efficiency of rectangular cutting, Prikladnaya informatika, 2018, vol. 13, no. 3 (75), pp. 35—46 (in Russian).

 

To the contents