带服务器的三台平行机排序问题的复杂性和近似算法

• 作者: 姚恩瑜 苏纯洁
• 来源期刊: 高校应用数学学报
• 学科: 数学
• 关键词: 算法 复杂性 最坏情况界
• 年，卷（期）: 2000,（2）
• 页码范围: 229-234
• 页数: 6页
• 分类号: O223
• 字数: 4167字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2000.02.017

摘要

讨论带有两个服务器的三台机的平行机排序问题,在这个问题的实例中,每一个工件都有一个时间长度为1的安装操作必须要由服务器来完成,而每一个服务器在同一时刻只能安装一个工件,用三段式描述表示此问题即为P3,S2/si=1/Cmax.证明了此问题为NP-C的,分别给出了在在线和离线条件下的近似算法,并且估计了算法的最坏情况界.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	苏纯洁	浙江大学应用数学系	1	6	1.0	1.0
2	姚恩瑜	浙江大学应用数学系	17	117	5.0	10.0