Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

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

Chan, S.-H., Lam, T.-W., Lee, L.-K., Ting, H.-F. and Zhang, P.

    We consider the online scheduling problem of minimizing total weighted flow time plus energy on a processor that 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 when it is released [1, 4, 5, 8, 12, 15, 16, 17]. 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 = ∞) [10, 11]. 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.
Cite as: Chan, S.-H., Lam, T.-W., Lee, L.-K., Ting, H.-F. and Zhang, P. (2010). Non-clairvoyant Scheduling for Weighted Flow Time and Energy on Speed Bounded Processors. In Proc. 16-th Computing: The Australasian Theory Symposium (CATS 2010) Brisbane, Australia. CRPIT, 109. Viglas, T. and Potanin, A. Eds., ACS. 3-10
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS