Paper Info
Title
Online Scheduling of Parallel Communications with Individual Deadlines
Abstract
We consider the online competitiveness for scheduling a set of communication jobs (best described in terms of a weighted graph where nodes denote the communication agents and edges denote communication jobs and three weights associated with each edge denote its length, release time, and deadline, respectively), where each node can only send or receive one message at a time. A job is accepted if it is scheduled without interruption in the time interval corresponding to its length between release time and deadline. We want to maximize the sum of the length of the accepted jobs. When an algorithm is not able to preempt (i.e., abort) jobs in service in order to make room for better jobs, previous lower bound shows that no algorithm can guarantee any constant competitive ratio. We examine a natural variant in which jobs can be aborted and each aborted job can be rescheduled from start (called restart). We present simple algorithms under the assumptions on job length: 2-competitive algorithm for unit jobs under the discrete model of time and (6+4√2 ≈ 11:656)-competitive algorithm for jobs of arbitrary length. These upper bounds are compensated by the lower bounds 1.5, 8-Ɛ, respectively.
Year
Venue
Keywords
1999
ISAAC
individual deadlines,competitive algorithm,arbitrary length,release time,parallel communications,time interval,better job,aborted job,accepted job,2-competitive algorithm,online scheduling,simple algorithm,job length,upper bound,lower bound,competitive ratio
Field
DocType
Volume
Abort,Online algorithm,Scheduling (computing),Parallel communication,Parallel algorithm,Upper and lower bounds,Computer science,Communication complexity,Competitive analysis,Distributed computing
Conference
1741
ISSN
ISBN
Citations 
0302-9743
3-540-66916-7
3
PageRank 
References 
Authors
0.42
14
2
Name
Order
Citations
PageRank
Jae-Ha Lee114414.19
Kyung-Yong Chwa291997.10