  When a computer system schedules jobs there is typically a significant cost
associated with preempting a job during execution. This cost can be from the
expensive task of saving the memory's state and loading data into and out of
memory. It is desirable to schedule jobs non-preemptively to avoid the costs of
preemption. There is a need for non-preemptive system schedulers on desktops,
servers and data centers. Despite this need, there is a gap between theory and
practice. Indeed, few non-preemptive \emph{online} schedulers are known to have
strong foundational guarantees. This gap is likely due to strong lower bounds
on any online algorithm for popular objectives. Indeed, typical worst case
analysis approaches, and even resource augmented approaches such as speed
augmentation, result in all algorithms having poor performance guarantees. This
paper considers on-line non-preemptive scheduling problems in the worst-case
rejection model where the algorithm is allowed to reject a small fraction of
jobs. By rejecting only a few jobs, this paper shows that the strong lower
bounds can be circumvented. This approach can be used to discover algorithmic
scheduling policies with desirable worst-case guarantees. Specifically, the
paper presents algorithms for the following two objectives: minimizing the
total flow-time and minimizing the total weighted flow-time plus energy under
the speed-scaling mechanism. The algorithms have a small constant competitive
ratio while rejecting only a constant fraction of jobs. Beyond specific
results, the paper asserts that alternative models beyond speed augmentation
should be explored to aid in the discovery of good schedulers in the face of
the requirement of being online and non-preemptive.
