A tight lower bound for job scheduling with cancellation
The Job Scheduling with Cancellation problem is a variation of classical scheduling problems in which jobs can be cancelled while waiting for execution. In this paper we prove a tight lower bound of 5 for the competitive ratio of any deterministic online algorithm for this problem, for the case where all jobs have the same processing time. (c) 2005 Elsevier B.V. All rights reserved.
lower bounds scheduling on-line algorithms