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 [J].

BENDAVID, S ;

BORODIN, A ;

KARP, R ;

TARDOS, G ;

WIGDERSON, A .

ALGORITHMICA, 1994, 11 (01) :2-14

[6] AN OPTIMAL ONLINE ALGORITHM FOR METRICAL TASK SYSTEM [J].

BORODIN, A ;

LINIAL, N ;

SAKS, ME .

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

← 1 2 →