Preemptive semi-online scheduling with tightly-grouped processing times

被引：6

作者：

He, Y ^{[1
]}

Jiang, YW

机构：

[1] Zhejiang Univ, Dept Math, Hangzhou 310027, Peoples R China

[2] Zhejiang Univ, State Key Lab CAD & CG, Hangzhou 310027, Peoples R China

来源：

JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY | 2004年 / 19卷 / 06期

基金：

中国国家自然科学基金;

关键词：

semi-online; scheduling; preemption; competitive ratio;

D O I：

10.1007/BF02973433

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper investigates a preemptive semi-online scheduling problem on m identical parallel machines where m = 2, 3. It is assumed that all jobs have their processing times in between p and rp (p > 0, r greater than or equal to 1). The goal is to minimize the makespan. Best possible algorithms are designed for any r greater than or equal to 1 when m = 2,3.

引用

页码：733 / 739

页数：7

共 9 条

[1] An optimal algorithm for preemptive on-line scheduling [J].

Chen, B ;

vanVliet, A ;

Woeginger, GJ .

OPERATIONS RESEARCH LETTERS, 1995, 18 (03) :127-131

[2] Bin stretching revisited [J].

Epstein, L .

ACTA INFORMATICA, 2003, 39 (02) :97-117

[3] Optimal preemptive semi-online scheduling to minimize makespan on two related machines [J].

Epstein, L ;

Favrholdt, LM .

OPERATIONS RESEARCH LETTERS, 2002, 30 (04) :269-275

[4] Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios [J].

Epstein, L .

OPERATIONS RESEARCH LETTERS, 2001, 29 (02) :93-98

[5] Semi on-line scheduling on two identical machines [J].

He, Y ;

Zhang, G .

COMPUTING, 1999, 62 (03) :179-187

[6] Some new formulations of smoothness conditions and conformality conditions for bivariate splines [J].

Hong, D ;

Liu, HW .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2000, 40 (01) :117-125

[7]

HE Y, 2002, SEMIONLINE SCHEDULIN

[8] SCHEDULING WITH DEADLINES AND LOSS FUNCTIONS [J].

MCNAUGHTON, R .

MANAGEMENT SCIENCE, 1959, 6 (01) :1-12

[9] Semi-online scheduling with decreasing job sizes [J].

Seiden, S ;

Sgall, J ;

Woeginger, G .

OPERATIONS RESEARCH LETTERS, 2000, 27 (05) :215-221

← 1 →