一类两阶段杂交流水作业的近似算法

• 作者: 蒋义伟 魏麒
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 流水作业 计算复杂性 近似算法 最坏情况界 最后完工工件完工时间
• 年，卷（期）: 2012,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 1073-1084
• 分类号: TP393|O223
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.00587

摘要

讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务:第1个任务可以在任何一台机器上加工,第2个任务只能在第1个任务完成后在第2台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作NSHFS.如果第2个任务可以在第1个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5的多项式时间近似算法.对于NSHFS模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3的多项式时间近似算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蒋义伟	浙江理工大学理学院	19	25	3.0	4.0
2	魏麒	浙江大学宁波理工学院	5	30	2.0	5.0