带机器准备时间的m台平行机在线和半在线排序

• 作者: 谭金芝
• 来源期刊: 应用数学
• 学科: 数学
• 关键词: 排序 在线 半在线 近似算法 竞争比
• 年，卷（期）: 2008,（3）
• 页码范围: 518-523
• 页数: 6页
• 分类号: O223
• 字数: 4316字
• 语种: 中文

摘要

本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谭金芝	温州大学数学与信息科学学院	3	3	1.0	1.0