Online flow time scheduling in the presence of preemption overhead

Abstract

This paper revisits the online problem of preemptive scheduling to minimize the total flow time. Previous theoretical results often assume that preemption is free, which is not true for most systems. This paper investigates the complexity of the problem when a processor has to perform a certain amount of overhead (extra work) before it resumes the execution of a job preempted before. Such overhead causes delay to all unfinished jobs. In this paper we first consider single-processor scheduling. We show that no online algorithm can be competitive for total flow time in the presence of preemption overhead (note that the well-known online algorithm SRPT is 1-competitive when preemption overhead is zero). We then consider resource augmentation and show a simple algorithm that is (1 + ε)-speed (1 + 1/ε)-competitive for minimizing total flow time on a single processor. We also extend the result to the multiprocessor setting. © 2012 Springer-Verlag.