Online scheduling to minimize maximum weighted flow-time on a bounded parallel-batch machine

被引：6

作者：

Chai, Xing ^{[1
,2
]}

Li, Wenhua ^{[1
]}

Zhu, Yuejuan ^{[1
]}

机构：

[1] Zhengzhou Univ, Sch Math & Stat, Zhengzhou 450001, Peoples R China

[2] Henan Univ Technol, Coll Sci, Zhengzhou 450001, Peoples R China

来源：

ANNALS OF OPERATIONS RESEARCH | 2021年 / 298卷 / 1-2期

基金：

中国国家自然科学基金;

关键词：

Online scheduling; Batching; Maximum weighted flow-time; Competitive ratio;

D O I：

10.1007/s10479-019-03352-6

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

An online scheduling problem on a bounded parallel-batch machine to minimize the maximum weighted flow-time is considered in this paper. Jobs arrive over time with the identical processing time. The maximum ratio between the weights of any two jobs is w. The parallelbatch machine can process at most b jobs simultaneously as a batch, and the jobs in a batch have the same starting time and the same completion time. For this problem, a deterministic online algorithm is presented. The algorithm is showed to be the best possible with a competitive ratio of v 4w+1+1 2 when w. [1, 2], and to have a competitive ratio not greater than w when w. (2,+8).

引用

页码：79 / 93

页数：15

共 24 条

[1] Online scheduling of a single machine to minimize total weighted completion time [J].

Anderson, EJ ;

Potts, CN .

MATHEMATICS OF OPERATIONS RESEARCH, 2004, 29 (03) :686-697

[2]

[Anonymous], 1974, Introduction to sequencing and scheduling

[3] Minimizing Weighted Flow Time [J].

Bansal, Nikhil ;

Dhamdhere, Kedar .

ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (04)

[4] Online weighted flow time and deadline scheduling [J].

Becchetti, Luca ;

Leonardi, Stefano ;

Marchetti-Spaccamela, Alberto ;

Pruhs, Kirk .

JOURNAL OF DISCRETE ALGORITHMS, 2006, 4 (03) :339-352

[5]

Brucker P., 1998, Journal of Scheduling, V1, P31, DOI 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO

[6]

2-R

[7] Online scheduling on batching machines to minimise the total weighted completion time of jobs with precedence constraints and identical processing times [J].

Cao, Jianfa ;

Yuan, Jinjiang ;

Li, Wenjie ;

Bu, Hailin .

INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 2011, 42 (01) :51-55

[8]

Chekuri Chandra, 2001, P STOC, P84, DOI DOI 10.1145/380752.380778

[9] Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines [J].

Gu, Manzhan ;

Lu, Xiwen .

ANNALS OF OPERATIONS RESEARCH, 2011, 191 (01) :97-113

[10] A BEST POSSIBLE ONLINE ALGORITHM FOR SCHEDULING TO MINIMIZE MAXIMUM FLOW-TIME ON BOUNDED BATCH MACHINES [J].

Jiao, Chengwen ;

Li, Wenhua ;

Yuan, Jinjiang .

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2014, 31 (04)

← 1 2 3 →