Optimization Method for Guillotine Packing of Rectangular Items within an Irregular and Defective Slate
| Autor: | Shangping Zhong, Chen Kaizhi, Jiahao Zhuang, Song Zheng |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
0209 industrial biotechnology
Computer science General Mathematics Constraint (computer-aided design) guillotine cuts 0211 other engineering and technologies horizontal level packing 02 engineering and technology Permutation 020901 industrial engineering & automation Genetic algorithm Computer Science (miscellaneous) computational geometry genetic algorithm Rectangle Engineering (miscellaneous) 021103 operations research Basis (linear algebra) Heuristic lcsh:Mathematics Computational geometry lcsh:QA1-939 Packing problems defective irregular slate rectangle packing problems Algorithm |
| Zdroj: | Mathematics, Vol 8, Iss 1914, p 1914 (2020) Mathematics Volume 8 Issue 11 |
| ISSN: | 2227-7390 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|