Online lazy bureaucrat scheduling with a machine deadline

被引：0

作者：

Gai, Ling ^{[1
]}

Zhang, Guochuan ^{[2
]}

机构：

[1] Shanghai Univ, Sch Management, Shanghai 200444, Peoples R China

[2] Zhejiang Univ, Coll Comp Sci, Hangzhou 310027, Zhejiang, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2018年 / 35卷 / 02期

关键词：

Online algorithm; Competitive ratio; Lazy bureaucrat scheduling; RESOURCE BIN PACKING;

D O I：

10.1007/s10878-017-0180-7

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The lazy bureaucrat scheduling problem was first introduced by Arkin et al. (Inf Comput 184:129-146, 2003). Since then, a number of variants have been addressed. However, very little is known on the online version. In this note we focus on the scenario of online scheduling, in which the jobs arrive over time. The bureaucrat (machine) has a working time interval. Namely, he has a deadline by which all scheduled jobs must be completed. A decision is only based on released jobs without any information on the future. We consider two objective functions of [min-makespan] and [min-time-spent]. Both admit best possible online algorithms with competitive ratio of .

引用

页码：530 / 537

页数：8

共 12 条

[1] The lazy Bureaucrat scheduling problem [J].

Arkin, EM ;

Bender, MA ;

Mitchell, JSB ;

Skiena, SS .

INFORMATION AND COMPUTATION, 2003, 184 (01) :129-146

[2] The maximum resource bin packing problem [J].

Boyar, Joan ;

Epstein, Leah ;

Favrholdt, Lene M. ;

Kohrt, Jens S. ;

Larsen, Kim S. ;

Pedersen, Morten M. ;

Wohlk, Sanne .

THEORETICAL COMPUTER SCIENCE, 2006, 362 (1-3) :127-139

[3]

Epstein L, 2005, LECT NOTES COMPUT SC, V3580, P602

[4]

Esfahbod B, 2003, LECT NOTES COMPUT SC, V2748, P59

[5] On lazy bureaucrat scheduling with common deadlines [J].

Gai, Ling ;

Zhang, Guochuan .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2008, 15 (02) :191-199

[6] Hardness of lazy packing and covering [J].

Gai, Ling ;

Zhang, Guochuan .

OPERATIONS RESEARCH LETTERS, 2009, 37 (02) :89-92

[7]

Gourves Laurent, 2014, Theoretical Computer Science. 8th IFIP TC 1/WG 2.2 International Conference, TCS 2014. Proceedings: LNCS 8705, P66, DOI 10.1007/978-3-662-44602-7_6

[8]

Gourves Laurent, 2013, Fundamentals of Computation Theory. 19th International Symposium, FCT 2013. Proceedings: LNCS 8070, P171, DOI 10.1007/978-3-642-40164-0_18

[9]

Hepner C, 2002, LECT NOTES COMPUT SC, V2368, P40

[10]

Kiraly T., 2011, INT C INT KATHM NEP, P1

← 1 2 →