Paper Info
Title
Non-clairvoyant Weighted Flow Time Scheduling on Different Multi-processor Models
Abstract
We study non-clairvoyant scheduling to minimize weighted flow time on two different multi-processor models. In the first model, processors are all identical and jobs can possibly be speeded up by running on several processors in parallel. Under the non-clairvoyant model, the online scheduler has no information about the actual job size and degree of speed-up due to parallelism, yet it has to determine dynamically when and how many processors to run the jobs. The literature contains several O (1)-competitive algorithms for this problem under the unit-weight multi-processor setting (Edmonds, Theor. Comput. Sci. 235(1), 109---141, 2000 ; Edmonds and Pruhs, in Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), 685---692, 2009 ) as well as the weighted single-processor setting (Bansal and Dhamdhere, ACM Trans. Algorithms 3(4), 2007 ). This paper shows the first O (1)-competitive algorithm for weighted flow time in the multi-processor setting.In the second model, we consider processors with different functionalities and only processors of the same functionality can work on the same job in parallel. Here a job is modeled as a sequence of non-clairvoyant demands of different functionalities. This model is derived naturally from the classical job shop scheduling; but as far as we know, there is no previous work on scheduling to minimize flow time. In this paper we take a first step to study non-clairvoyant scheduling on this multi-processor model. Motivated by the literature on 2-machine job shop scheduling, we focus on the special case when processors are divided into two types of functionalities, and we show a non-clairvoyant algorithm that is O (1)-competitive for weighted flow time.
Year
DOI
Venue
2011
10.1007/s00224-013-9475-y
Theory of Computing Systems
Keywords
DocType
Volume
Online algorithms,Non-clairvoyant scheduling,Weighted flow time,Multiprocessor scheduling,Competitive analysis
Conference
56
Issue
ISSN
Citations 
1
1432-4350
1
PageRank 
References 
Authors
0.36
8
3
Name
Order
Citations
PageRank
Jianqiao Zhu141.09
Ho-Leung Chan247125.23
Tak-Wah Lam31860164.96