Open Access iconOpen Access

ARTICLE

crossmark

A Time-Efficient and Exploratory Algorithm for the Rectangle Packing Problem

Mohammad Bozorgi1, Morteza Mohammadi Zanjireh1,*, Mahdi Bahaghighat1, Qin Xin2

1 Computer Engineering Department, Imam Khomeini International University, Qazvin, Iran
2 Faculty of Science and Technology, University of the Faroe Islands, Faroe Islands

* Corresponding Author: Morteza Mohammadi Zanjireh. Email: email

Intelligent Automation & Soft Computing 2022, 31(2), 885-898. https://doi.org/10.32604/iasc.2022.016075

Abstract

Today, resource waste is considered as one of the most important challenges in different industries. In this regard, the Rectangle Packing Problem (RPP) can affect noticeably both time and design issues in businesses. In this study, the main objective is to create a set of non-overlapping rectangles so that they have specific dimensions within a rectangular plate with a specified width and an unlimited height. The ensued challenge is an NP-complete problem. NP-complete problem, any of a class of computational problems that still there are no efficient solution for them. Most substantial computer-science problems such as the traveling salesman problem, satisfiability problems (sometimes called propositional satisfiability problem and abbreviated SAT or B-SAT), and graph-covering problems are belong to this class. Essentially, it is complicated to spot the best arrangement with the highest rate of resource utilization by emphasizing the linear computation time. This study introduces a time-efficient and exploratory algorithm for the RPP, including the lowest front-line strategy and a Best-Fit algorithm. The obtained results confirmed that the proposed algorithm can lead to a good performance with simplicity and time efficiency. Our evaluation shows that the proposed model with utilization rate about 94.37% outperforms others with 87.75%, 50.54%, and 87.17% utilization rate, respectively. Consequently, the proposed method is capable to of achieving much better utilization rate in comparison with other mentioned algorithms in just 0.023 s running-time, which is much faster than others.

Keywords


Cite This Article

M. Bozorgi, M. Mohammadi Zanjireh, M. Bahaghighat and Q. Xin, "A time-efficient and exploratory algorithm for the rectangle packing problem," Intelligent Automation & Soft Computing, vol. 31, no.2, pp. 885–898, 2022.



cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 1678

    View

  • 806

    Download

  • 0

    Like

Related articles

Share Link