两台平行机的实时到达在线排序

• 作者: 张国川 陈仕平
• 来源期刊: 应用数学学报
• 学科: 数学
• 关键词: 排序 在线算法 近似比
• 年，卷（期）: 2000,（1）
• 页码范围: 31-37
• 页数: 7页
• 分类号: O29
• 字数: 5403字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-3079.2000.01.004

摘要

本文考虑一类新的在线平行机排序模型-实时到达在线问题.该模型中,工件是陆续到达的.工件的个数及到达时间是事先未知的,而且只有当工件到达,才知其加工时间,所求目标是使所有工件都加工完的时间达到最小.对两台平行机的情形,Chen与Vestjens[2]给出了近似比为3/2的在线LPT算法,并证明不存在近似比小于(5-√5)/2的算法.我们利用黄金分割数设计了一个新的算法,其近似比不超过(18-√5)/11.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张国川	浙江大学应用数学系	8	90	3.0	8.0
2	陈仕平	浙江大学应用数学系	2	7	2.0	2.0