Paper Info
Title
Minimizing Total Flow Time and Total Completion Time with Immediate Dispatching
Abstract
We consider the problem of scheduling jobs arriving over time in a multiprocessor setting, with immediate dispatching, disallowing job migration. The goal is to minimize both the total flow time (total time in the system) and the total completion time. Previous studies have shown that while preemption (interrupt a job and later continue its execution) is inherent to make a scheduling algorithm efficient, migration (continue the execution on a different machine) is not. Still, the current non-migratory online algorithms suffer from a need for a central queue of unassigned jobs which is a "no option" in large computing systems, such as the Web. We introduce a simple online non-migratory algorithm IMD, which employs immediate dispatching, i.e., it immediately assigns released jobs to one of the machines. We show that the performance of this algorithm is within a logarithmic factor of the optimal migratory offline algorithm, with respect to the total flow time, and within a small constant factor of the optimal migratory offline algorithm, with respect to the total completion time. This solves an open problem suggested by Awerbuch et al. (STOC 99).
Year
DOI
Venue
2007
10.1007/s00453-006-0193-6
ACM Symposium on Parallel Algorithms and Architectures
Keywords
Field
DocType
migration,total completion time,current non-migratory online algorithm,open problem,dispatching,scheduling algorithm,logarithmic factor,scheduling.,completion time,flow time,total flow time,disallowing job migration,online,immediate dispatching,minimizing total flow time,small constant factor,competitive,total time,optimal migratory offline algorithm,online algorithm
Interrupt,Online algorithm,Preemption,Open problem,Job shop scheduling,Computer science,Scheduling (computing),Queue,Multiprocessing,Distributed computing
Journal
Volume
Issue
ISSN
47
3
0178-4617
ISBN
Citations 
PageRank 
1-58113-661-7
37
2.32
References 
Authors
13
2
Name
Order
Citations
PageRank
Nir Avrahami1372.32
Yossi Azar23330365.24