-
题名超尺寸物品装箱问题及其算法
被引量：4
- 1
-
-
作者
邢文训
陈锋
-
机构
清华大学数学科学系
-
出处
《应用数学学报》
CSCD
北大核心
2002年第1期8-14,共7页
-
基金
清华大学基础基金(JC2001019号)部分资助.
-
文摘
本文探讨一类新的装箱问题—超尺寸物品装箱问题．针对实际解决该问题的两步法，我们提出了一个评价效率更高的目标函数，证明了在此目标函数下两步法的渐近最坏比不小于２，并给出了渐近最坏比与拆分次数的关系．最后本文提出了一种不同于两步法的新的在线算法ＭＡ，证明了在新目标函数下其渐近最坏比不超过 ．
-
关键词
超尺寸物品装箱问题
启发式算法
最坏情形分析
-
Keywords
bin packing problem with over-sized items, heuristics, worst-case analysis
-
分类号
O224
[理学—运筹学与控制论]
-
-
题名超尺寸物品装箱问题
被引量：1
- 2
-
-
作者
陈锋
邢文训
-
机构
清华大学数学科学系
-
出处
《运筹学学报》
CSCD
北大核心
2002年第1期85-90,共6页
-
基金
国家自然科学基金69904007
校基础基金JC2001019部分资助
-
文摘
本文给出一类新的装箱问题,超尺寸物品装箱问题.就实际解决该问题所 普遍采用的两步法,证明了当采用经典目标函数并且拆分次数不超过2时,第二步采用FFDLR的渐进最坏比为3/2.进而针对超尺寸物品装箱问题的算法提出了一个评价效率更高的目标函数.证明了在此目标函数下,当不限制物品的最大尺寸时,第二步采用最优装法的两步法的渐近最坏比为2.最后,给出了渐近最坏比与拆分次数的关系.
-
关键词
超尺寸物品装箱问题
启发式算法
最坏情形分析
-
Keywords
bin packing problem with over-sized items
heuristics
worst-case analysis.
-
分类号
O224
[理学—运筹学与控制论]
-
