主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
张德富,陈竞驰,刘永凯,陈火旺.用于二维不规则排样的离散临界多边形模型.软件学报,2009,20(6):1511-1520
用于二维不规则排样的离散临界多边形模型
Discrete No-Fit Polygon, A Simple Structure for the 2-D Irregular Packing Problem
投稿时间:2008-01-22  修订日期:2008-03-31
DOI:
中文关键词:  不规则排样问题  禁止区  临界多边形  离散临界多边形
英文关键词:irregular packing problem  infeasible interval  no-fit polygon  discrete no-fit polygon
基金项目: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 (厦门大学院士启动基金)
作者单位
张德富 厦门大学 计算机科学系,福建 厦门 361005
东南融通博士后工作站,福建 厦门 361005 
陈竞驰 厦门大学 计算机科学系,福建 厦门 361005 
刘永凯 厦门大学 计算机科学系,福建 厦门 361005 
陈火旺 东南融通博士后工作站,福建 厦门 361005
国防科学技术大学 计算机学院,湖南 长沙 410073 
摘要点击次数: 3686
全文下载次数: 4257
中文摘要:
      提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.新模型是只含有点和区间的简单模型,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地求解该问题.计算结果表明,基于离散临界多边型模型的排样算法是很有效的.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利