Optimization Method for Guillotine Packing of Rectangular Items within an Irregular and Defective Slate

Kaizhi Chen, Jiahao Zhuang, Shangping Zhong and Song Zheng
Additional contact information
Kaizhi Chen: Department of Mathematics and Computer Science, Fuzhou University, Fuzhou 350100, China
Jiahao Zhuang: Department of Mathematics and Computer Science, Fuzhou University, Fuzhou 350100, China
Shangping Zhong: Department of Mathematics and Computer Science, Fuzhou University, Fuzhou 350100, China
Song Zheng: College of Electrical Engineering and Automation Fuzhou University, Fuzhou University, Fuzhou 350108, China

Mathematics, 2020, vol. 8, issue 11, 1-16

Abstract: Research on the rectangle packing problems has mainly focused on rectangular raw material sheets without defects, while natural slate has irregular and defective characteristics, and the existing packing method adopts manual packing, which wastes material and is inefficient. In this work, we propose an effective packing optimization method for nature slate; to the best of our knowledge, this is the first attempt to solve the guillotine packing problem of rectangular items in a single irregular and defective slate. This method is modeled by the permutation model, uses the horizontal level (HL) heuristic proposed in this paper to obtain feasible solutions, and then applies the genetic algorithm to optimize the quality of solutions further. The HL heuristic is constructed on the basis of computational geometry and level packing. This heuristic aims to divide the irregular plate into multiple subplates horizontally, calculates the movable positions of the rectangle in the subplates, determines whether or not the rectangle can be packed in the movable positions through computational geometry, and fills the scraps appropriately. Theoretical analysis confirms that the rectangles obtained through the HL heuristic are inside the plate and do not overlap with the defects. In addition, the packed rectangles do not overlap each other and satisfy the guillotine constraint. Accordingly, the packing problem can be solved. Experiments on irregular slates with defects show that the slate utilization through our method is between 89% and 95%. This result is better than manual packing and can satisfy actual production requirements.

Keywords: defective irregular slate; rectangle packing problems; guillotine cuts; horizontal level packing; computational geometry; genetic algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/11/1914/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/11/1914/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:11:p:1914-:d:438603

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().