| 在线A形装箱问题: 模型及算法研究 |
| |
| 引用本文： | 陆一江,邢文训. 在线A形装箱问题: 模型及算法研究[J]. 清华大学学报(自然科学版), 2001, 41(12): 1-4 |
| |
| 作者姓名： | 陆一江 邢文训 |
| |
| 作者单位： | 清华大学数学科学系,北京,100084 |
| |
| 基金项目： | 国家自然科学基金资助项目(69904007) |
| |
| 摘 要： | A形装箱问题是由生产实际引发的一个新的数学模型,它是经典一维装箱问题的一种变形--每样物品有高度和半径两个参数.把装箱问题的经典算法推广到在线A形装箱问题,并分别从最坏情形分析与数值模拟两方面对算法进行了比较,得到了不同而且有趣的结果. 证明了 First Fit算法的渐近竞争比为2, 而其它在线启发式算法如Next Fit, Worst Fit, Best Fit(BF), Almost Worst Fit, Harmonic的渐近竞争比皆为无界; 通过数值模拟,在平均意义下BF的性质最好.
|
| 关 键 词： | 组合优化问题 装箱问题 启发式算法 |
| 文章编号： | 1000-0054(2001)12-0001-04 |
| 修稿时间： | 2001-02-15 |
On-line A-shaped bin packing problem: models and analysis of heuristics |
| |
| LU Yijiang,XING Wenxun. On-line A-shaped bin packing problem: models and analysis of heuristics[J]. Journal of Tsinghua University(Science and Technology), 2001, 41(12): 1-4 |
| |
| Authors: | LU Yijiang XING Wenxun |
| |
| Abstract: | This paper presents a new model, the A Shaped Bin Packing Problem (ASBP), for industrial manufacturing systems. It is a variant of the classical one dimensional bin packing problem in which each item has two parameters, height and diameter. The classic algorithms for the bin packing problem were extended to the on line ASBP. Comparisons of the worst case analysis and simulation lead to interesting results. The asymptotic competitive ratios in the worst case version of on line heuristics such as Next Fit, Worst Fit, Best Fit (BF), Almost Worst Fit and Harmonic are all infinite, whereas the competitive ratio of First Fit is 2. The BF had the best average. |
| |
| Keywords: | combinatorial optimization bin packing heuristics |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
