Preemptive scheduling on a small number of hierarchical machines

We consider preemptive offline and online scheduling on identical machines and uniformly related machines in the hierarchical model, with the goal of minimizing the makespan. In this model, each job can be assigned to a subset of the machines which is a prefix of the machine set. We design optimal offline and online algorithms for two uniformly related machines, both when the machine of higher hierarchy is faster and when it is slower, as well as for the case of three identical machines. Specifically, for each one of the three variants, we give a simple formula to compute the makespan of an optimal schedule, provide a linear time offline algorithm which computes an optimal schedule and design an online algorithm of the best possible competitive ratio. (c) 2008 Published by Elsevier Inc.