id: 06101533
dt: a
an: 06101533
au: Chan, Ho-Leung; Lam, Tak-Wah; Li, Rongbin
ti: Online flow time scheduling in the presence of preemption overhead.
so: Gupta, Anupam (ed.) et al., Approximation, randomization, and combinatorial
    optimization. Algorithms and techniques. 15th international workshop,
    APPROX 2012, and 16th international workshop, RANDOM 2012, Cambridge,
    MA, USA, August 15‒17, 2012. Proceedings. Berlin: Springer (ISBN
    978-3-642-32511-3/pbk). Lecture Notes in Computer Science 7408, 85-97
    (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-32512-0_8
ab: Summary: 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+\frac{1}ϵ)$-competitive
    for minimizing total flow time on a single processor. We also extend
    the result to the multiprocessor setting.
rv: