Abstract:
We consider the problem of minimizing flow time on a single machine supporting preemption that can reject jobs at a cost. Even if all jobs have the same rejection cost, we show that no online algorithm can have competitive ratio better than (2+sqrt(2))/2 = 1.707... in general or e/(e-1) = 1.581... if all jobs are known to have the same processing time. We also give an optimal offline algorithm for unit-length jobs with arbitrary rejection costs. This leads to a pair of 2-competitive online algorithms for unit-length jobs, one when all rejection costs are equal and one when they are arbitrary. Finally, we show that the offline problem is NP-hard even when each job's rejection cost is proportional to its processing time.
Note: This seems to be an ill-fated paper. Two previous (unpublished, but posted) versions of this paper contained erroneous proofs. I originally gave an NP-completeness proof that involved creating too large a problem instance and claimed that RR(e/(e-1)) is e/(e-1)-competitive. (I found another NP-hardness proof to resolve the first problem. I cannot currently prove that RR has a competitive ratio better than 2, but the posted version correctly describes by results.) Sorry about any confusion this may have caused.