How much can lookahead help in online single machine scheduling

被引：11

作者：

Zheng, Feifeng ^{[1
]}

Xu, Yinfeng ^{[1
,2
]}

Zhang, E. ^{[3
]}

机构：

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

[2] State Key Lab Mfg Syst Engn, Xian 710049, Peoples R China

[3] Shanghai Univ Fin & Econ, Sch Informat Management & Engn, Shanghai 200433, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2008年 / 106卷 / 02期

基金：

中国国家自然科学基金;

关键词：

online strategies; scheduling; lookahead;

D O I：

10.1016/j.ipl.2007.10.008

中图分类号：

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

学科分类号：

0812 ;

摘要：

This paper studies online single machine scheduling where jobs have unit length and the objective is to maximize the number of completed jobs. Lookahead is considered to improve the competitiveness of online deterministic strategies. For preemption-restart model, we will prove a lower bound of ([LD] + 2)/([LD] + 1) for the case where LD >= 1 and 3/2 for the case where 0 <= LD < 1, in which LD is the length of time segment that online strategies can foresee at any time. For non-preemptive model, we mainly present a greedy strategy that has an optimal competitive ratio of 3/2 when 1 <= LD < 2 while its competitive ratio is bounded from above by 4/3 as LD goes larger. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：70 / 74

页数：5

共 8 条

[1]

Borodin A, 1998, ONLINE COMPUTATION C

[2]

Chrobak M, 2004, LECT NOTES COMPUT SC, V3142, P358

[3]

Coleman B, 2002, PROCEEDINGS OF THE 6TH JOINT CONFERENCE ON INFORMATION SCIENCES, P205

[4] Clairvoyant non-preemptive EDF scheduling [J].

Ekelin, Cecilia .

18TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS, PROCEEDINGS, 2006, :23-+

[5] Online scheduling with hard deadlines [J].

Goldman, SA ;

Parwatikar, J ;

Suri, S .

JOURNAL OF ALGORITHMS, 2000, 34 (02) :370-389

[6] On-line scheduling on a single machine: maximizing the number of early jobs [J].

Hoogeveen, H ;

Potts, CN ;

Woeginger, GJ .

OPERATIONS RESEARCH LETTERS, 2000, 27 (05) :193-197

[7]

Keskinocak P., 1999, ONLINE ALGORITHMS LO

[8] A LOOK-AHEAD HEURISTIC FOR SCHEDULING JOBS WITH RELEASE DATES ON A SINGLE-MACHINE [J].

MAO, WH ;

KINCAID, RK .

COMPUTERS & OPERATIONS RESEARCH, 1994, 21 (10) :1041-1050

← 1 →