Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time

被引：0

作者：

Li, Wenjie ^{[1
]}

Liu, Hailing ^{[2
]}

Li, Shisheng ^{[3
]}

机构：

[1] Luoyang Normal Univ, Sch Math Sci, Luoyang 471934, Henan, Peoples R China

[2] Henan Inst Engn, Coll Sci, Zhengzhou 451191, Henan, Peoples R China

[3] Zhongyuan Univ Technol, Dept Informat & Computat Sci, Zhengzhou 450007, Henan, Peoples R China

来源：

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH | 2018年 / 35卷 / 04期

基金：

中国国家自然科学基金;

关键词：

Scheduling; online algorithm; kind release time; total weighted completion time; SINGLE-MACHINE; REJECTION COST; RELEASE DATES; ALGORITHMS; PLUS;

D O I：

10.1142/S0217595918500240

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper studies online scheduling on m identical parallel machines under the KRT environment, where jobs arrive over time and "KRT" means that in the online setting no jobs can be released when all of the machines are busy. The goal is to determine a feasible schedule to minimize the total of weighted completion times. When m = 1, we prove that WSPT is an optimal online algorithm. When m >= 2, we first present a lower bound m(2)-2+root m(4)-4m+4/2m(m-1), and then show that WSPT is a 2-competitive online algorithm for the case m = 2. For the case in which m = 2 and all jobs have equal processing times, we provide a best possible online algorithm with a competitive ratio of 1+root 3/2.

引用

页数：12

共 20 条

[1] Online scheduling of a single machine to minimize total weighted completion time
Anderson, EJ
Potts, CN
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 2004, 29 (03) : 686 - 697
[2] [Anonymous], 2004, Handbook of Scheduling-Algorithms, Models, and Performance Analysis, DOI DOI 10.1201/9780203489802.CH15
[3] SCHEDULING WITH RELEASE DATES ON A SINGLE-MACHINE TO MINIMIZE TOTAL WEIGHTED COMPLETION-TIME
BELOUADAH, H
POSNER, ME
POTTS, CN
[J]. DISCRETE APPLIED MATHEMATICS, 1992, 36 (03) : 213 - 231
[4] LP-based online scheduling: from single to parallel machines
Correa, Jose R.
Wagner, Michael R.
[J]. MATHEMATICAL PROGRAMMING, 2009, 119 (01) : 109 - 136
[5] Single machine scheduling with release dates
Goemans, MX
Queyranne, M
Schulz, AS
Skutella, M
Wang, YG
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2002, 15 (02) : 165 - 192
[6] Scheduling to minimize average completion time: Off-line and on-line approximation algorithms
Hall, LA
Schulz, AS
Shmoys, DB
Wein, J
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1997, 22 (03) : 513 - 544
[7] LPT online strategy for parallel-machine scheduling with kind release times
Li, Wenjie
Yuan, Jinjiang
[J]. OPTIMIZATION LETTERS, 2016, 10 (01) : 159 - 168
[8] Improved online algorithms for the batch scheduling of equal-length jobs with incompatible families to maximize the weighted number of early jobs
Li, Wenjie
Yuan, Jinjiang
[J]. OPTIMIZATION LETTERS, 2014, 8 (05) : 1691 - 1706
[9] AN IMPROVED 2.11-COMPETITIVE ALGORITHM FOR ONLINE SCHEDULING ON PARALLEL MACHINES TO MINIMIZE TOTAL WEIGHTED COMPLETION TIME
Ma, Ran
Tao, Jiping
[J]. JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2018, 14 (02) : 497 - 510
[10] Online scheduling to minimize the total weighted completion time plus the rejection cost
Ma, Ran
Yuan, Jinjiang
[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (02) : 483 - 503

← 1 2 →