Discrete no-fit polygon, a simple structure for the 2-D irregular packing problem

被引：7
作者：
Zhang, De-Fu [1 ,2 ]
Chen, Jing-Chi [1 ]
Liu, Yong-Kai [1 ]
Chen, Huo-Wang [2 ,3 ]
机构：
[1] Department of Computer Science, Xiamen University
[2] Longtop Group Post-Doctoral Research Center
[3] School of Computer, National University of Defense Technology
来源：
Ruan Jian Xue Bao/Journal of Software | 2009年 / 20卷 / 06期
关键词：
Discrete no-fit polygon; Infeasible interval; Irregular packing problem; No-fit polygon;
D O I：
10.3724/SP.J.1001.2009.03331
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
This paper presents a model based on discrete no-fit polygon for the two-dimensional irregular packing problem. Burke et al. have presented an effective BLF algorithm to solve the irregular packing problem, however, their algorithm might generate invalid results for some special cases. To solve this problem, a model based on discrete no-fit polygon is proposed, and its correctness has been strictly proved. Only points and intervals are only considered by this model, which greatly decreases the geometry complexity of the original problem and makes the problem easily solved by many heuristic strategies. Computational results show that the algorithm based on discrete no-fit polygon model is very efficient. © by Institute of Software, the Chinese Academy of Sciences. All rights reserved.
引用
收藏
页码：1511 / 1520
页数：9
相关论文
共 16 条
  • [1] Cui Y.D., He D.L., Song X.X., Generating optimal two-section cutting patterns for rectangular blanks, Computers and Operations Research, 33, 6, pp. 1505-1520, (2006)
  • [2] Huang W.Q., Chen D.B., Xu R.C., A new heuristic algorithm for rectangle packing, Computers and Operations Research, 34, 11, pp. 3270-3280, (2007)
  • [3] Zhang D.F., Han S.H., Ye W.G., A bricklaying heuristic algorithm for the orthogonal rectangular packing problem, Chinese Journal of Computers, 31, 3, pp. 509-515, (2008)
  • [4] Bennell J.A., Oliveira J.F., The geometry of nesting problems: A tutorial, European Journal of Operational Research, 184, 2, pp. 397-415, (2008)
  • [5] Babu A.R., Babu N.R., A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms, Computer-Aided Design, 33, pp. 879-891, (2001)
  • [6] Bouganis A., Shanahan M., A vision-based intelligent system for packing 2-D irregular shapes, IEEE Trans. on Automation Science and Engineering, 4, 3, pp. 382-394, (2007)
  • [7] Zhang Y.P., Zhang C.L., Jiang S.W., An effective approach for leather nesting, Journal of Software, 16, 2, pp. 316-323, (2005)
  • [8] Heckmann R., Lengauer T., A simulated annealing approach to the nesting problem in the textile manufacturing industry, Annals of Operations Research, 57, pp. 103-133, (1995)
  • [9] Fischer A.D., Dagli C.H., Employing subgroup evolution for irregular-shape nesting, Journal of Intelligent Manufacturing, 15, pp. 187-199, (2004)
  • [10] Gomes A.M., Oliveira J.F., A 2-exchange heuristic for nesting problems, European Journal of Operational Research, 141, 2, pp. 359-370, (2002)
12