## Scheduling on a single machine to minimize total flow time with job rejections

Proceedings of the 2nd
Multidisciplinary
International Conference on Scheduling: Theory & Applications
(MISTA), pp. 562-572, 2005.

**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.