English

运筹学学报 >

2016 , Vol. 20 >Issue 2: 49 - 58

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.02.004

运筹学

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

展开
  • 1. 南京农业大学理学院, 南京 210095

收稿日期: 2015-05-08

  网络出版日期: 2016-06-15

基金资助

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

收起

Online hierarchical service scheduling on two identical machines with release times

Expand
  • 1. College of Science, Nanjing Agricultural University, Nanjing 210095, China

Received date: 2015-05-08

  Online published: 2016-06-15

Fold

摘要

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

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

本文引用格式

侯丽英 . 具有服务等级的两台同型机实时在线排序[J]. 运筹学学报, 2016 , 20(2) : 49 -58 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.004

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

参考文献

[1] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: A survey [J]. Annals of Discrete Mathematics, 1979, 5: 287-326.
[2] Chen B, Vestjens A P A. Scheduling on identical machines: How good is LPT in an on-line setting [J]. Operations Research Letters, 1997, 21: 165-169.
[3] Noga J, Seiden S S. An optimal online algorithm for scheduling two machines with release times [J]. Theoretical Computer Science, 2001, 268: 133-143.
[4] Bar-Noy A, Freund A, Naor J. On-line load balancing in a hierarchical server topology [J]. SIAM Journal on Computing, 2001, 31: 527-549.
[5] Chassid O, Epstein L. The hierarchical model for load balancing on two machines [J]. Journal of Combinatorial Optimization, 2008, 15: 305-314.
[6] Hwang H C, Chang S Y, Lee K. Parallel machine scheduling under a grade of service provision [J]. Computers \& Operations Research, 2004, 31: 2055-2061.
[7] Park J, Chang S Y, Lee K. Online and semi-online scheduling of two machines under a grade of service provision [J]. Operations Research Letters, 2006, 34: 692-696.
[8] Tan Z Y, Zhang A. A note on hierarchical scheduling on two uniform machines [J]. Journal of Combinatorial Optimization, 2010, 20: 85-95.
[9] Zhang A, Jiang Y W, Tan Z Y. Online parallel machines scheduling with two hierarchies [J]. Theoretical Computer Science, 2009, 410: 3597-3605.
[10] Lee K, Leung J Y T, Pinedo M L. Scheduling jobs with equal processing times subject to machine eligibility constraints [J].Journal of Scheduling, 2010, 14(1): 27-38.
[11] Lee K, Leung J Y T, Pinedo M L. Makespan minimization in online scheduling with machine eligibility [J]. Annals of Operations Research, 2013, 204(1): 189-222.
 
Options
文章导航

/

〈 〉