工件可预处理的单台机排序问题

• 作者: 何勇 魏麒
• 来源期刊: 浙江大学学报（理学版）
• 学科: 数学
• 关键词: 单机排序 最优算法 计算复杂性
• 年，卷（期）: 2006,（4）
• 所属期刊栏目: 数学与计算机科学
• 页码范围: 383-388
• 页数: 6页
• 分类号: O223
• 字数: 6274字
• 语种: 中文
• DOI: 10.3321/j.issn:1008-9497.2006.04.007

摘要

考虑一个工件可预处理的单机排序问题.要求在所有工件能够按时完工的前提下,使得预处理工件的费用最小.证明了对于一般情况,该问题是NP-难的,并给出了动态规划算法.进一步,得到当每个工件的预处理费用都相同时该问题是多项式可解的,并给出了强多项式时间算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	何勇	浙江大学数学系	511	9054	45.0	65.0
2	魏麒	浙江大学宁波理工学院基础部	5	30	2.0	5.0