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

Online deadline scheduling on faster machines

โœ Scribed by Jae-Hoon Kim; Kyung-Yong Chwa

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
112 KB
Volume
85
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 meet its deadline. The job instance is given such that the slack of each job is at least ฮบ times its processing time, where ฮบ is called patience. In this paper, online algorithms have faster machines than the adversary. We investigate the speed of machines on which the online algorithms can achieve the optimality and parametrize them by the patience.

๐Ÿ“œ SIMILAR VOLUMES

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-

Online Scheduling with Hard Deadlines
Online Scheduling with Hard Deadlines
โœ Sally A Goldman; Jyoti Parwatikar; Subhash Suri ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 157 KB

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 ne

Parallel machine batching and scheduling
Parallel machine batching and scheduling with deadlines
โœ T. C. Edwin Cheng; Mikhail Y. Kovalyov ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Springer US ๐ŸŒ English โš– 137 KB ๐Ÿ‘ 1 views

In this paper, we study the problem of scheduling n independent jobs non-preemptively on m unrelated parallel machines. Each job j has a processing time and a deadline, the time at which the job must be completed. On each machine, jobs may be grouped to form batches containing continuously scheduled

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