题名 三维装箱问题的组合启发式算法
被引量:49
1
作者
张德富
魏丽军
陈青山
陈火旺
机构
厦门大学计算机科学系
东南融通博士后工作站
出处
《软件学报》
EI
CSCD
北大核心
2007年第9期2083-2089,共7页
基金
Supported by the Academician Start-Up Fund of China under Grant No.X01109(厦门大学院士启动基金)
the 985 Information Technology Fund of China under Grant No.0000-X07204(985信息科技平台资助)
文摘
通过组合拟人启发式和模拟退火算法,提出了三维装箱问题的组合启发式算法.拟人启发式算法的主要思想来源于日常砌墙中的策略.利用找点法以及水平和垂直参考线规则来控制装填过程.用模拟退火算法改进拟人启发式.经过一些数据的测试,实验结果表明,该算法能够同文献中的优秀算法竞争.
关键词
三维装箱
启发式算法
拟人
模拟退火算法
Keywords
three-dimensional packing
heuristic algorithm
personification
simulated annealing algorithm
分类号
TP301
[自动化与计算机技术—计算机系统结构]
题名 求解三维装箱问题的混合模拟退火算法
被引量:64
2
作者
张德富
彭煜
朱文兴
陈火旺
机构
厦门大学计算机科学系福建
东南融通博士后工作站
福州大学离散数学与理论计算机科学研究中心
国防科学技术大学计算机学院
出处
《计算机学报》
EI
CSCD
北大核心
2009年第11期2147-2156,共10页
文摘
提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟退火算法.三维装箱问题要求装载给定箱子集合的一个子集到容器中,使得被装载的箱子总体积最大.文中介绍的混合模拟退火算法基于三个重要算法:(1)复合块生成算法,与传统算法不同的是文中提出的复合块不只包含单一种类的箱子,而是可以在一定的限制条件下包含任意种类的箱子.(2)基础启发式算法,该算法基于块装载,可以按照指定装载序列生成放置方案.(3)模拟退火算法,以复合块生成和基础启发式算法为基础,将装载序列作为可行放置方案的编码,在编码空间中采用模拟退火算法进行搜索以寻找问题的近似最优解.文中采用1500个弱异构和强异构的装箱问题数据对算法进行测试.实验结果表明,混合模拟退火算法的填充率超过了目前已知的优秀算法.
关键词
三维装箱
启发式算法
模拟退火
Keywords
three-dimensional container loading
heuristic algorithm
simulated annealing algorithm
分类号
TP301
[自动化与计算机技术—计算机系统结构]
题名 用于二维不规则排样的离散临界多边形模型
被引量:11
3
作者
张德富
陈竞驰
刘永凯
陈火旺
机构
厦门大学计算机科学系
东南融通博士后工作站
国防科学技术大学计算机学院
出处
《软件学报》
EI
CSCD
北大核心
2009年第6期1511-1520,共10页
基金
国家自然科学基金No.60773126
福建省自然科学基金No.A07100234
+1 种基金
厦门大学985二期信息科技基金No.0000-X07204
厦门大学院士启动基金No.X01109~~
文摘
提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.新模型是只含有点和区间的简单模型,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地求解该问题.计算结果表明,基于离散临界多边型模型的排样算法是很有效的.
关键词
不规则排样问题
禁止区
临界多边形
离散临界多边形
Keywords
irregular packing problem
infeasible interval
no-fit polygon
discrete no-fit polygon
分类号
TP301
[自动化与计算机技术—计算机系统结构]
题名 R/W事务的并发控制方法
被引量:1
4
作者
李新
谭庆平
薛永生
机构
厦门大学计算机科学系
国防科技大学厦门东南融通博士后工作站
出处
《通讯和计算机(中英文版)》
2005年第6期36-40,共5页
文摘
两阶段封锁是经典事务并发控制的基本原则,它保证了事务的交叉调度结果的正确性。然而,两阶段封销的要求经常会降低系统的效率,特别是当事务申有用户参与交互遏程时,这种效率的降低往往会变得无法忍受。本文针对应用申广泛存在的一期事务——R/W事务,提出了一种新的封销机制,在绝大多数情况下,它能够克服两阶段封销的缺陷,同时确保事务交叉调度结果的正确性。
关键词
R/W事务
并发控制
可串行化
事务分解
Keywords
R/W Transaction
Concurrent Controlling
Serialized
Decomposing of the Transaction
分类号
TP311.13
[自动化与计算机技术—计算机软件与理论]