Campus Event Calendar
Event Entry
What and Who
Non-clairvoyant scheduling
S. Anand
IIT Delhi
AG1 Mittagsseminar (own work)
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 19 June 2009
13:00
30 Minutes
E1 4
023
Saarbrücken
Abstract
We consider the problem of scheduling jobs on a single machine so that total flow time is minimized. We consider the non-clairvoyant case, i.e. the job size is not known in advance and is only determined when the job has finished executing. This is clearly the case in many practical problems.
It can be shown that there are no constant competitive non-clairvoyant on-line algorithms for this problem. Thus we give the online scheduler slightly more speed than the adversary. It is known that Shortest-Elapsed-Time-First is constant-competitive in this case.
We give a simpler proof of this based on the concept of fractional flow time.
Contact
Naveen Garg
--email hidden
passcode not visible
logged in users only
Naveen Garg, 06/18/2009 18:38
Naveen Garg, 06/09/2009 18:34 -- Created document.
Naveen Garg, 06/09/2009 18:34 -- Created document.