具有树和路约束的平行机排序问题

• 作者: 李伟东 程佳乐
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 平行机排序 K-树 最短路径树 最短路 近似算法
• 年，卷（期）: 2018,（12）
• 所属期刊栏目: 人工智能与数据挖掘
• 页码范围: 2273-2279
• 页数: 7页
• 分类号: TP301.6
• 字数: 8876字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2018.12.024

摘要

考虑具有树和路约束的平行机排序问题, 其工件集对应于无向图 (有向图) 的边 (弧) 集.目标是选取工件集的一个子集使其满足树或路的约束, 将其放在平行机上处理, 使得机器的最大完工时间 (makespan) 尽可能地小.通过分析此类问题的组合性质, 得到如下结论:在K-树约束下, 利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下, 通过构造辅助实例以控制边的权重, 分析辅助实例的输出值与目标实例最优值之间的关系, 利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下, 根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下, 在所有的两点间最短路构成的子图基础上, 通过构造新的辅助图以控制弧的权重, 再利用最短路的性质可以得到一个1.618-近似算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李伟东	云南大学数学与统计学院	13	35	3.0	5.0
2	程佳乐	云南大学数学与统计学院	1	0	0.0	0.0