Open Access

ARTICLE

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

Mohammad Bozorgi¹, Morteza Mohammadi Zanjireh^1,*, Mahdi Bahaghighat¹, Qin Xin²

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:

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

Received 22 December 2020; Accepted 29 April 2021; Issue published 22 September 2021

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

---