Online scheduling with hard deadlines

被引：43
作者：
Goldman, SA [1 ]
Parwatikar, J [1 ]
Suri, S [1 ]
机构：
[1] Washington Univ, St Louis, MO 63130 USA
来源：
JOURNAL OF ALGORITHMS | 2000年 / 34卷 / 02期
基金：
美国国家科学基金会;
关键词：
* An earlier version appears in Proceedings of the Workshop on Algorithms and Data Structures; pages; 258—271; August 1997. ²Supported in part by NSF Grant CCR-9110108 and NSF National Young Investigator Grant CCR-9357707 with matching funds provided by Xerox PARC and WUTA. ³Research supported in part by Defense Advanced Research Projects Agency under Contract DABT-63-95-C-0083. §Research supported in part by National Science Foundation Grant CCR-9501494;
D O I：
10.1006/jagm.1999.1060
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We study non-preemptive, online admission control in the hard deadline model: each job must either be serviced prior to its deadline or be rejected. Our setting consists of a single resource that services an online sequence of jobs; each job has a length indicating the length of time for which it needs the resource and a delay indicating the maximum time it can wait for the service to be started. The goal is to maximize total resource utilization. The jobs are non-preemptive and exclusive, meaning once a job begins, it runs to completion, and at most one job fan use the resource at any time. We obtain a series of results, under varying assumptions of job lengths and delays. (C) 2000 Academic Press.
引用
收藏
页码：370 / 389
页数：20
相关论文
共 13 条
  • [1] AWERBUCH B, 1994, PROCEEDINGS OF THE FIFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P321
  • [2] Awerbuch B., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), P32, DOI 10.1109/SFCS.1993.366884
  • [3] Awerbuch B., 1994, Proceedings. 35th Annual Symposium on Foundations of Computer Science (Cat. No.94CH35717), P412, DOI 10.1109/SFCS.1994.365675
  • [4] AWERBUCH B, 1994, PROCEEDINGS OF THE FIFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P312
  • [5] ON THE POWER OF RANDOMIZATION IN ONLINE ALGORITHMS
    BENDAVID, S
    BORODIN, A
    KARP, R
    TARDOS, G
    WIGDERSON, A
    [J]. ALGORITHMICA, 1994, 11 (01) : 2 - 14
  • [6] AN OPTIMAL ONLINE ALGORITHM FOR METRICAL TASK SYSTEM
    BORODIN, A
    LINIAL, N
    SAKS, ME
    [J]. JOURNAL OF THE ACM, 1992, 39 (04) : 745 - 763
  • [7] FELDMANN A, 1995, CMUCS95102 SCH COMP
  • [8] Garay J. A., 1993, Proceedings of the 2nd Israel Symposium on Theory and Computing Systems (Cat. No.93TH0520-7), P285, DOI 10.1109/ISTCS.1993.253460
  • [9] GARAY JA, 1992, P IEEE INFOCOM, P1043
  • [10] Goldwasser MH, 1999, PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P396
12