SDU
IMADA

COMPUTER SCIENCE COLLOQUIUM

Optimal Preemptive Scheduling on Uniform Processors
with Non-Decreasing Speed Ratios

Leah Epstein
The Interdisciplinary Center, Herzliya, Israel

Wednesday, July 4, 2001, at 1:15 PM
The Seminar Room

ABSTRACT

We study preemptive scheduling on uniformly related processors, where jobs are arriving one by one in an on-line fashion. We consider the class of machine sets where the speed ratios are non-decreasing as speed increases. For each set of machines in this class, we design an algorithm of optimal competitive ratio. This generalizes the known result for identical machines, and solves other interesting cases.

Host: Kim Skak Larsen


SDU IMADA [CS Colloquia]
Last modified: June 28, 2001.
Kim Skak Larsen (kslarsen@imada.sdu.dk)