一类带约束的装箱问题的在线算法

• 作者: 余国松 毛燕玲 肖教燎
• 来源期刊: 南昌大学学报（理科版）
• 学科: 数学
• 关键词: 组合优化 装箱问题 算法分析
• 年，卷（期）: 2006,（6）
• 页码范围: 522-524
• 页数: 3页
• 分类号: O223
• 字数: 2574字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-0464.2006.06.003

摘要

A型装箱问题(ASBP)是BP(Backing Problem)的一种变型问题,与经典的BP问题不同的是,在ASBP中物品有两个参数:高度和半径.在装箱过程中,除了要求箱子中所有物品的高度和不大于1之外,还要求后到达的物品放在先到达的物品之上且上层物品的半径不超过下层物品的半径.分析了无穷数目的不同半径和有限数目的不同半径两种情形.对于无穷数目的不同半径的情形,我们证明了NF(Next Fit)、FF(First Fit)、BF(Best Fit)、RBF(Radius Best Fit)和AF(Any Fit)算法的渐近最坏比为无穷大;对于有限数目的不同半径的情形,我们得到了FF、RBF算法的精确渐近最坏界.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	毛燕玲	南昌大学管理科学与工程系	19	97	6.0	9.0
2	余国松	南昌大学管理科学与工程系	7	25	2.0	5.0
3	肖教燎	南昌大学管理科学与工程系	14	78	6.0	8.0