A tight lower bound for job scheduling with cancellation

被引：3

作者：

Zheng, FF

Chin, FYL

Fung, SPY ^{[1
]}

Poon, CK

Xu, YF

机构：

[1] Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

[2] Xian Jiaotong Univ, Sch Management, Xian 710049, Peoples R China

[3] City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2006年 / 97卷 / 01期

基金：

中国国家自然科学基金;

关键词：

on-line algorithms; scheduling; lower bounds;

D O I：

10.1016/j.ipl.2005.09.001

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：1 / 3

页数：3