Energy usage has been an important concern in recent research on online scheduling. In this paper we extend the study of the tradeoff between flow time and energy from the single-processor setting [8, 6] to the multi-processor setting. Our main result is an analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m ≥ 2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. This result still holds even if the comparison is made against the optimal migratory offline algorithm (the competitive ratio increases by a factor of 2.5). As a special case, our work also contributes to the traditional online flow-time scheduling. Specifically, for minimizing flow time only, CRR can yield a competitive ratio one or even arbitrarily smaller than one, when using sufficiently faster processors. Prior to our work, similar result is only known for online algorithms that needs migration [21, 23], while the best non-migratory result can achieve an O(1) competitive ratio [14].

Energy usage has been an important concern in recent research on online job scheduling, where processors are allowed to vary the speed dynamically so as to save energy whenever possible. Notice that providing good quality of service such as response time (flow time) and conserving energy are conflicting objectives. An interesting problem for scheduling is how to optimize an economic tradeoff of flow time and energy. To this end, the past two years have witnessed significant progress in the single-processor setting, and online algorithms with performance close to optimal have been obtained. In this paper we extend the study of optimizing the tradeoff between flow time and energy to the multi-processor setting. We derive and analyze a simple non-migratory online algorithm that makes use of the classified-round-robin (CRR) strategy to dispatch jobs. Even in the worst case, its performance is within O(log P) times of the optimal migratory offline algorithm, where P is the ratio of the maximum job size to the minimum job size. Technically speaking, this online result stems from a non-trivial solution to an offline problem of eliminating migration, which is also interesting by itself.

In this paper we consider multiprocessor scheduling with hard deadlines and investigate the cost of eliminating migration in the online setting. Let I be any set of jobs that can be completed by some migratory offline schedule on m processors. We show that I can also be completed by a nonmigratory online schedule using m speed-5.828 processors (i.e., processors 5.828 times faster). This result supplements the previous results that I can also be completed by a nonmigratory offline schedule using 6m unit-speed processors [B. Kalyanasundaram and K. R. Pruhs, J. Algorithms, 38 (2001), pp. 2--24] or a migratory online schedule using m speed-2 processors [C. A. Phillips et al., Algorithmica, 32 (2002), pp. 163--200]. Our result is based on a simple conservative scheduling algorithm called PARK, which commits a processor to a job only when the processor has zero commitment before its deadline. A careful analysis of PARK further shows that the processor speed can be reduced arbitrarily close to 1 by exploiting more processors (say, using 16m speed-1.8 processors). PARK also finds application in overloaded systems; it gives the first online nonmigratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm.

This paper is concerned with the extra-resource analysis of online scheduling algorithms. In particular, it studies how to make use of multiple processors to counteract the lack of future information in online deadline scheduling. Our results extend the previous work that are primarily based on using a faster processor to obtain a performance guarantee. The challenge arises from the fact that jobs are sequential in nature and cannot be executed on more than one processor at the same time. Thus, a faster processor can speed up a job while multiple unit-speed processors cannot help.

We consider the problem of scheduling jobs with deadlines in an on-line single-processor system. It is known for long that unless the system is underloaded, any on-line algorithm is not optimal in the sense that it may fail to match the optimal offline algorithm on the total work of jobs meeting their deadlines. In this paper, we extend this fact with two new lower bound results. First, we show that even if the on-line scheduler can use a processor s times faster than the offline scheduler, where s 1 is any real number less than the golden ratio (i.e. (1 + 5)=2 1:618), no online algorithm can be optimal. Furthermore, if we restrict our attention to on-line algorithms that decide at the release time of a job whether the job will be processed to meet its deadline, then the speed requirement for optimal on-line algorithms is at least 2. These lower bound results should be contrasted with the recent upper bound result [11] that with a two times faster processor, a simple extension of the earliest deadline first strategy (EDF) is optimal.