带核元的带拒绝装箱问题

• 作者: 杨鼎强 蒋加伏
• 来源期刊: 长沙理工大学学报（自然科学版）
• 学科: 工学
• 关键词: 装箱问题 核元 组合优化 近似算法 最坏情况渐近性能比
• 年，卷（期）: 2007,（2）
• 所属期刊栏目: 计算机与数理科学
• 页码范围: 59-62
• 页数: 4页
• 分类号: TP301
• 字数: 3413字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-9331.2007.02.012

摘要

讨论了如下定义的带核元带拒绝装箱问题:设有许多等长的箱子,给定一个带核元的物品集,每个非核元有2个参数:大小和罚值.非核元物品可以放入箱子也可被拒绝放入箱子.如果某物品被拒绝放入箱中,则产生惩罚值,同时要求核元不允许被拒绝且每只箱子中所装核元个数不超过1,问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小.该问题是一个新的组合优化问题,在多处理器任务调度及内部互联网信息管理等问题中有着广泛的应用背景.提出了一个求解该问题的局外近似算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蒋加伏	长沙理工大学计算机与通信工程学院	62	490	14.0	18.0
2	杨鼎强	长沙理工大学计算机与通信工程学院	25	95	6.0	8.0