A 2.5-competitive Online Algorithm for Pm|rj|∑wjCj

摘要：

The classical identical machine scheduling problem with the objective of minimizing total weighted completion time is considered in the online setting where jobs arrive over time. An online algorithm is presented and is proven to be (2.5-1/2m)-competitive based on the idea of instances reduction.

关键词： identical machine scheduling online algorithm competitive analysis total weighted completion time

作者: Jiping Tao Hao Jiang Tundong Liu

作者单位: Department of Automation, XiamenUniversity, Xiamen 361005, China Department of Automation, Xiamen University, Xiamen 361005, China

会议类型: 国际会议

会议名称: The 24th Chinese Control and Decision Conference (第24届中国控制与决策学术年会 2012 CCDC)

会议地点: 太原

会议语种:英文

页码: 3196-3200

在线出版日期: 2012-05-23（万方平台首次上网日期，不代表论文的发表时间）