|
扩展功能
|
|
| 本文信息 | |
 |
补充材料 |
|
PDF(895KB) |
|
[HTML全文] |
|
参考文献 |
| 服务与反馈 | |
|
加入引用管理器 |
|
引用本文 |
|
Email Alert |
|
文章反馈 |
|
浏览反馈信息 |
| 本文关键词相关文章 | |
|
Packing问题 |
|
封装级别 |
|
空间距离 |
|
生成序数 |
| 本文作者相关文章 | |
| PubMed | |
一种求解带有时间调度的四维长方体装填问题的启发式算法
李未1*, 黄文奇2, 蒋东辰1, 刘祥龙1
1.北京航空航天大学, 软件开发环境国家重点实验室, 北京 100191
2.华中科技大学, 计算机科学与技术学院, 武汉 430074
长方体的Packing问题被证明是NP-hard问题. 对于低维度Packing问题, 国内外学者给出了模拟退火算法、遗传算法、分枝限界算法、拟人算法等求解算法. 文中针对带有时间调度的三维长方体的Packing问题, 引入封装级别、空间距离和周边生成序数等评判标准, 提出了一种基于贪心策略的启发式算法. 该算法对每个长方体每一占角位置进行评判, 依据空间利用率选择给定格局下的 最佳放置长方体及其放置方式, 并进行填放. 算法的运算复杂度是一个与容器参数A,B,C,T以及长方体数目n有关的多项式O(A2B2C2T2n5). 利用该算法对非闸断模式和闸断模式测试样例进行实验, 算法求解得到非闸断模式测试样例的平均空间利用率为98.81\%, 闸断模式测试样例的空间平均利用率为99.87\%. 并且, 对于一半以上样例, 该算法能够求出最优解. 实验说明该算法对于求解带有时间调度的三维长方体Packing问题十分有效.
国家重点基础研究发展计划(批准号: 2005CB321901)和国家高技术研究发展计划(批准号: 2007AA010301-02)资助项目