๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Online Scheduling with Hard Deadlines

โœ Scribed by Sally A Goldman; Jyoti Parwatikar; Subhash Suri

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
157 KB
Volume
34
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 can use the resource at any time. We obtain a series of results, under varying assumptions of job lengths and delays.

๐Ÿ“œ SIMILAR VOLUMES

Online deadline scheduling on faster mac
Online deadline scheduling on faster machines
โœ Jae-Hoon Kim; Kyung-Yong Chwa ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 112 KB

Online deadline scheduling is to determine which jobs are accepted or rejected, where jobs have the deadline by which they must finish their processing and they arrive in the online fashion. The slack of a job is the gap between its arrival time and the last time when it can first be scheduled to me

Batch scheduling with deadlines on paral
Batch scheduling with deadlines on parallel machines: An NP-hard case
โœ Mikhail Y. Kovalyov; Yakov M. Shafransky ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 529 KB

The problem of scheduling groups of jobs on unrelated parallel machines in batches subject to group deadlines was studied by Brucker et al. ( 1997) and Kovalyov and Shafransky ( 1994). A classification of computational complexities of special cases was provided only for the situation when all groups

Online real-time preemptive scheduling o
Online real-time preemptive scheduling of jobs with deadlines on multiple machines
โœ Bhaskar Das Gupta; Michael A. Palis ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Springer US ๐ŸŒ English โš– 139 KB

In this paper, we derive bounds on performance guarantees of online algorithms for real-time preemptive scheduling of jobs with deadlines on K machines when jobs are characterized in terms of their minimum stretch factor (or, equivalently, their maximum execution rate r = 1= ). We consider two well-

Scheduling with tails and deadlines
Scheduling with tails and deadlines
โœ Francis Sourd; Wim Nuijten ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Springer US ๐ŸŒ English โš– 299 KB
On Nonpreemptive LCFS Scheduling with De
On Nonpreemptive LCFS Scheduling with Deadlines
โœ U. Schmid; J. Blieberger ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 947 KB

We investigate some real time behaviour of a (discrete time) single server system with nonpreemptive LCFS task scheduling. The main results deal with the probability distribution of a random variable \(\operatorname{SRD}(T)\), which describes the time the system operates without any violation of a f