可截切开放式矩形布置问题的一种新精确算法

发布时间：2017-10-01 08:22

  本文关键词：可截切开放式矩形布置问题的一种新精确算法

  更多相关文章： 开放式矩形布置问题 截切约束 精确算法 解空间

【摘要】：开放式矩形布置问题是典型的NP-hard问题之一,其各子型在工业设计和生产管理中有广泛的实际应用。针对带截切约束的开放式矩形布置问题,指出并证明了其解空间存在组合冗余性质,得出了最大非冗余系数,提出了一组包括避开冗余解空间、利用最小浪费面积和动态隐性空间约束的剪枝策略,给出了一种整合以上剪枝策略并在整体架构上采用相近排序规则和带广度探索的深度优先混合搜索策略的新精确算法。算例实验表明本文算法在求解效率及可求解问题规模上优于现有文献中领先的精确算法,冗余解空间剪枝策略对本文算法的整体性能起到关键作用。
【作者单位】： 西安交通大学管理学院;机械制造系统工程国家重点实验室;过程控制与效率工程教育部重点实验室;
【关键词】： 开放式矩形布置问题 截切约束 精确算法 解空间
【基金】：“十二五”国家科技支撑计划课题(2012BAH08F06)
【分类号】：C931
【正文快照】： 1引言开放式矩形布置问题(Open Rectangular PackingProblem,ORP)广泛存在于纸张、玻璃、金属板材等的生产处理、柔性车间和多处理器系统的调度[1]、芯片硬模块布局(VLSI Floorplan Design for Hard Modules)[2]、平面设施布置(Planner Facilities Layout Problem)[3]等工业

【共引文献】

中国期刊全文数据库 前10条

1 朱日升,赵勇,郭建波;铁路机车车辆板材下料排样的优化算法[J];机车车辆工艺;2005年01期

2 张德富;韩水华;叶卫国;;求解矩形Packing问题的砌墙式启发式算法[J];计算机学报;2008年03期

3 高伟增,饶运清;排样智能的现状分析及实施策略[J];机械与电子;2001年04期

4 ;An Improved Heuristic Recursive Strategy Based on Genetic Algorithm for the Strip Rectangular Packing Problem[J];自动化学报;2007年09期

5 陈战胜;钮文良;王辉;胡正坤;;一种求解矩形块装填问题的启发式快速算法[J];科技通报;2013年09期

6 吴忻生;吴超成;刘海明;;基于改进遗传算法的矩形件排样优化算法[J];制造业自动化;2013年19期

7 王金敏;王保春;朱艳华;;求解矩形布局问题的一种混合SAGA算法[J];天津工程师范学院学报;2010年02期

8 尹树玲;杨玉丽;;浅谈智能排样算法[J];中国科技信息;2008年01期

9 邓冬梅;周来水;;矩形件排样的研究进展[J];宇航材料工艺;2006年05期

10 宗立成;叶聪;余隋怀;陈登凯;;载人潜水器舱室设备智能布局设计方法研究[J];中国造船;2013年03期

中国重要会议论文全文数据库 前1条

1 张克;林家恒;;二维下料问题的研究进展[A];第16届中国过程控制学术年会暨第4届全国故障诊断与安全性学术会议论文集[C];2005年

中国博士学位论文全文数据库 前8条

1 郑俊丽;船舶分段制造车间的模块空间调度模型及算法[D];上海交通大学;2011年

2 贾志欣;面向发电设备制造的下料优化排样原理与关键技术[D];四川大学;2002年

3 罗阳;机械制造车间生产作业多智能体规划原理与板材套料优化方法的研究[D];四川大学;2001年

4 岳琪;基于遗传退火算法板式家具大规模矩形件优化下料研究[D];东北林业大学;2005年

5 李明;智能优化排样技术研究[D];浙江大学;2006年

6 王俊岭;矩形装箱问题的协同决策模型[D];兰州大学;2013年

7 曾致中;求解不等球和不等圆Packing问题的高性能算法研究[D];华中科技大学;2013年

8 靳鹏;配料企业下料与调度协调优化模型研究[D];合肥工业大学;2013年

中国硕士学位论文全文数据库 前10条

1 宋雪枫;融合蚁群算法和遗传算法的矩形件排样问题研究[D];郑州大学;2011年

2 贺晋;冲压模CAD与排样系统研究[D];解放军信息工程大学;2010年

3 王姝;服装生产优化排料信息系统研究与应用[D];华侨大学;2011年

4 曹训;船舶建造中场地资源的建模及其配置优化方法与工具[D];哈尔滨工业大学;2011年

5 程晖;基于遗传模拟退火的服装排料算法的研究[D];东华大学;2012年

6 杨威;板材排样优化的计算智能方法研究[D];四川大学;2002年

7 方辉;大规模板材排样的分布式协同优化方法研究[D];四川大学;2003年

8 赵谊;动态规则在矩形毛坯单一排样[D];广西师范大学;2004年

9 洪灵;计算机辅助平面零件排样技术研究[D];浙江大学;2005年

10 万斌;二维钣金排套料的算法研究及软件设计[D];国防科学技术大学;2004年

【相似文献】

中国期刊全文数据库 前10条

1 胡祥培;丁秋雷;张漪;王旭坪;;干扰管理研究评述[J];管理科学;2007年02期

2 ;[J];;年期

3 ;[J];;年期

4 ;[J];;年期

5 ;[J];;年期

6 ;[J];;年期

7 ;[J];;年期

8 ;[J];;年期

9 ;[J];;年期

10 ;[J];;年期

，

本文编号：952402