|
|||||
|
|
A tight lower bound for job scheduling with cancellation |
|
| Authors: | Feifeng Zheng Chung Keung Poon |
| Affiliation: | a School of Management, Xi'an Jiao Tong University, China b Department of Computer Science, The University of Hong Kong, Hong Kong, China c Department of Computer Science, City University of Hong Kong, China |
| Abstract: | 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. |
| Keywords: | On-line algorithms Scheduling Lower bounds |
| 本文献已被 ScienceDirect 等数据库收录！ | |