###
DOI:
Journal of Software:2009.20(6):1511-1520

用于二维不规则排样的离散临界多边形模型
张德富,陈竞驰,刘永凯,陈火旺
(厦门大学 计算机科学系,福建 厦门 361005;东南融通博士后工作站,福建 厦门 361005;东南融通博士后工作站,福建 厦门 361005;国防科学技术大学 计算机学院,湖南 长沙 410073)
Discrete No-Fit Polygon, A Simple Structure for the 2-D Irregular Packing Problem
ZHANG De-Fu,CHEN Jing-Chi,LIU Yong-Kai,CHEN Huo-Wang
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3539   Download 4116
Received:January 22, 2008    Revised:March 31, 2008
> 中文摘要: 提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.新模型是只含有点和区间的简单模型,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地求解该问题.计算结果表明,基于离散临界多边型模型的排样算法是很有效的.
Abstract: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.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60773126 (国家自然科学基金); the Natural Science Foundation of Fujian Province of China under Grant No.A0710023 (福建省自然科学基金); the 985 Information Technology Fund of Xiamen University of China under Grant No.0000-X07204 (厦门大学985二期信息科技基金); the Academician Start-Up Fund of Xiamen University of China under Grant No.X01109 (厦门大学院士启动基金) Supported by the National Natural Science Foundation of China under Grant No.60773126 (国家自然科学基金); the Natural Science Foundation of Fujian Province of China under Grant No.A0710023 (福建省自然科学基金); the 985 Information Technology Fund of Xiamen University of China under Grant No.0000-X07204 (厦门大学985二期信息科技基金); the Academician Start-Up Fund of Xiamen University of China under Grant No.X01109 (厦门大学院士启动基金)
Foundation items:
Reference text:

张德富,陈竞驰,刘永凯,陈火旺.用于二维不规则排样的离散临界多边形模型.软件学报,2009,20(6):1511-1520

ZHANG De-Fu,CHEN Jing-Chi,LIU Yong-Kai,CHEN Huo-Wang.Discrete No-Fit Polygon, A Simple Structure for the 2-D Irregular Packing Problem.Journal of Software,2009,20(6):1511-1520