// Ret følgende tre linier, så der kommer den rette // titel + dit navn og email-adresse $title = "Research"; $name = "Lene Monrad Favrholdt"; $login = "lenem"; include("/home/www/Employees/svalle/PHP/template.php3"); ?>
We study a preemptive semi-online scheduling problem. Jobs with
non-increasing weights arrive one by one to be scheduled on two uniformly
related machines. We analyze the algorithms as a function of the speed
ratio (q>=1) between the two machines.
We design algorithms of optimal competitive ratio for all values of q,
and show that for q>2, idle time needs to be introduced. This is the
first preemptive scheduling problem over list, where idle time is provably
required.
The publication is available from ScienceDirect (subscription may be required).