Online Scheduling of Equal-Length Jobs: Randomization And Restarts Help

We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is speci ed by its release time and deadline. The goal is to determine a single-processor, non-preemptive schedule of these jobs that maximizes the number of completed jobs. In the online version, each job arrives at its release time. We give two online algorithms with competitive ratios below 2 and show several lower bounds on the competitive ratios. First, we give a 3 -competitive randomized algorithm. Our algorithm needs only one fair random bit, as it chooses one of two (nearly identical) deterministic algorithms, each with probability 2 . We also show a lower bound of 2 for barely random algorithms, that (with arbitrary probability) choose one of two deterministic algorithms. Next, we give a deterministic 2 -competitive algorithm in the model that allows restarts, and we show that in this model the ratio 2 is optimal. For randomized algorithms with restarts we show a lower bound of 5