A tight lower bound for job scheduling with cancellation

Feifeng Zheng; Francis Y.L. Chin; Stanley P.Y. Fung; Chung Keung Poon; Yinfeng Xu

doi:10.1016/j.ipl.2005.09.001

A tight lower bound for job scheduling with cancellation

Feifeng Zheng
, Francis Y.L. Chin
, Stanley P.Y. Fung
, Chung Keung Poon
, Yinfeng Xu

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

4 Citations (Scopus)

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. © 2005 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	1-3
Journal	Information Processing Letters
Volume	97
Issue number	1
DOIs	https://doi.org/10.1016/j.ipl.2005.09.001
Publication status	Published - 16 Jan 2006

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

✩ The work described in this paper was fully supported by a grant from NSF of China [No. 10371094] and two grants from the Research Grants Council of the Hong Kong SAR, China [CityU 1071/02E and HKU 7142/03E]. * Corresponding author. E-mail addresses: [email protected] (F. Zheng), [email protected] (F.Y.L. Chin), [email protected] (S.P.Y. Fung), [email protected] (C.K. Poon), [email protected] (Y. Xu).

Research Keywords

Lower bounds
On-line algorithms
Scheduling

Access Output

10.1016/j.ipl.2005.09.001

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{ddf5686d0cdf4ee4b38044887c0ca9af,

title = "A tight lower bound for job scheduling with cancellation",

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. {\textcopyright} 2005 Elsevier B.V. All rights reserved.",

keywords = "Lower bounds, On-line algorithms, Scheduling",

author = "Feifeng Zheng and Chin, \{Francis Y.L.\} and Fung, \{Stanley P.Y.\} and Poon, \{Chung Keung\} and Yinfeng Xu",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "2006",

month = jan,

day = "16",

doi = "10.1016/j.ipl.2005.09.001",

language = "English",

volume = "97",

pages = "1--3",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A tight lower bound for job scheduling with cancellation

AU - Zheng, Feifeng

AU - Chin, Francis Y.L.

AU - Fung, Stanley P.Y.

AU - Poon, Chung Keung

AU - Xu, Yinfeng

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2006/1/16

Y1 - 2006/1/16

N2 - 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. © 2005 Elsevier B.V. All rights reserved.

AB - 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. © 2005 Elsevier B.V. All rights reserved.

KW - Lower bounds

KW - On-line algorithms

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=27844494751&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-27844494751&origin=recordpage

U2 - 10.1016/j.ipl.2005.09.001

DO - 10.1016/j.ipl.2005.09.001

M3 - RGC 21 - Publication in refereed journal

SN - 0020-0190

VL - 97

SP - 1

EP - 3

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

A tight lower bound for job scheduling with cancellation

Abstract

Bibliographical note

Funding

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this