Non-clairvoyant Scheduling for Weighted Flow Time and Energy on Speed Bounded Processors

We consider the online scheduling problem of minimizing total weighted flow time plus energy in the dynamic speed scaling model, where a processor can scale its speed dynamically between 0 and some maximum speed T. In the past few years this problem has been studied extensively under the clairvoyant setting, which requires the size of a job to be known at release time [AlF07,BPS07,BCL+08,LLT+esa08,LLT+spaa08,BCP09,GNS09,LLT+09]. For the non-clairvoyant setting, despite its practical importance, the progress is relatively limited. Only recently an online algorithm [LAPS] is known to be O(1)-competitive for minimizing (unweighted) flow time plus energy in the infinite speed model (i.e., T = ∞) [CEL+09,CEP09]. This paper makes two contributions to the non-clairvoyant scheduling. First, we resolve the open problem that the unweighted result of [LAPS] can be extended to the more realistic model with bounded maximum speed. Second, we show that another non-clairvoyant algorithm [WRR] is O(1)-competitive when weighted flow time is concerned. Note that [WRR] is not as efficient as [LAPS] for scheduling unweighted jobs as [WRR] has a much bigger constant hidden in its competitive ratio.