### Nonclairvoyant scheduling to minimize the total flow time on single and parallel machinesNonclairvoyant scheduling to minimize the total flow time on single and parallel machines

Access Restriction
Subscribed

 Author Becchetti, Luca ♦ Leonardi, Stefano Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2004 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Probabilistic analysis ♦ Flow time ♦ Multilevel feedback ♦ Randomized algorithms Abstract Scheduling a sequence of jobs released over time when the processing time of a job is only known at its completion is a classical problem in CPU scheduling in time sharing operating systems. A widely used measure for the responsiveness of the system is the average flow time of the jobs, that is, the average time spent by jobs in the system between release and completion.The Windows NT and the Unix operating system scheduling policies are based on the Multilevel Feedback algorithm. In this article, we prove that a randomized version of the Multilevel Feedback algorithm is competitive for single and parallel machine systems, in our opinion providing one theoretical validation of the goodness of an idea that has proven effective in practice along the last two decades.The randomized Multilevel Feedback algorithm (RMLF) was first proposed by Kalyanasundaram and Pruhs for a single machine achieving an $\textit{O}(log$ $\textit{n}$ log log $\textit{n})$ competitive ratio to minimize the average flow time against the on-line adaptive adversary, where $\textit{n}$ is the number of jobs that are released. We present a version of RMLF working for any number $\textit{m}$ of parallel machines. We show for RMLF a first $\textit{O}(log$ $\textit{n}$ log $\textit{n}/\textit{m})$ competitiveness result against the oblivious adversary on parallel machines. We also show that the same RMLF algorithm surprisingly achieves a tight $\textit{O}(log$ $\textit{n})$ competitive ratio against the oblivious adversary on a single machine, therefore matching the lower bound for this case. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2004-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 51 Issue Number 4 Page Count 23 Starting Page 517 Ending Page 539

#### Open content in new tab

Source: ACM Digital Library