带约束的平行机排序的一个近似算法

• 作者: 何勇
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: 排序 近似算法 最坏情况分析
• 年，卷（期）: 2001,（1）
• 页码范围: 114-118
• 页数: 5页
• 分类号: O223
• 字数: 2955字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2001.01.019

摘要

讨论有资源约束和有机器准备时间的平行机排序问题，资源约束为每个机器至多可加工k个工件.在极小化makespan的目标下给出了一个匹配算法，证明其最坏情况紧界是2-m-1，并进一步给出了它的两个带参数的最坏情况界.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何勇	浙江大学数学系	511	9054	45.0	65.0