总完工时间最短的恒速机排序

• 作者: 李岩 田海龙
• 来源期刊: 吉林化工学院学报
• 学科: 数学
• 关键词: 恒速机 排序 总完工时间 到达时间
• 年，卷（期）: 2009,（3）
• 页码范围: 83-85
• 页数: 3页
• 分类号: O223
• 字数: 2528字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-2853.2009.03.024

摘要

研究了可中断的带有到达时间的使总完工时间最小的恒速机排序问题.工件最多被截断2N次,其时间复杂性为N(nlogn).此问题是NP-难的,对一些特殊情况进行分析,给出了最优算法.