DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE UNIVERSITY OF SOUTHERN DENMARK, ODENSE 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 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