English

运筹学学报

• 运筹学 • 上一篇    下一篇

具有服务等级的两台同型机实时在线排序

侯丽英1,*   

  1. 1. 南京农业大学理学院, 南京 210095
  • 收稿日期:2015-05-08 出版日期:2016-06-15 发布日期:2016-06-15
  • 通讯作者: 侯丽英 lyhou@njau.edu.cn
  • 基金资助:

    国家自然科学基金(No. 11426133), 南京农业大学青年科技创新基金(No. 0506J0116)

Online hierarchical service scheduling on two identical machines with release times

HOU Liying1,*   

  1. 1. College of Science, Nanjing Agricultural University, Nanjing 210095, China
  • Received:2015-05-08 Online:2016-06-15 Published:2016-06-15

PDF

418

摘要：

考虑具有服务等级的两台同型机在线排序问题, 其中工件带有到达时间, 目标为最小化最大完工时间, 设计了竞争比为\frac{7}{4}的在线算法.

关键词: 在线排序, 服务等级, 到达时间, 竞争比

Abstract:

This paper considers online scheduling problem on two identical machines under a grade of service, where jobs arrive online over time. The objective is to minimize the maximum completion time. We propose an online algorithm with competitive ratio \frac{7}{4}.

Key words: online scheduling, grade of service, release time, competitive ratio