A Best Possible Online Algorithm for the Parallel-Machine Scheduling to Minimize the Maximum Weighted Completion Time

被引：12
作者：
Li, Wenjie [1 ]
机构：
[1] Luoyang Normal Univ, Sch Math Sci, Luoyang 471022, Henan, Peoples R China
来源：
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH | 2015年 / 32卷 / 04期
基金：
中国国家自然科学基金;
关键词：
Scheduling; online algorithms; weighted makespan; competitive ratio;
D O I：
10.1142/S021759591550030X
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper, we consider the online scheduling on m identical machines in which jobs arrive over time. The goal is to determine a nonpreemptive schedule that minimizes the weighted makespan, i.e., the maximum weighted completion time of jobs. When m = 1, we first present a lower bound 2, and then provide an online algorithm with a competitive ratio of 3. For the case in which m >= 1, and all jobs have a common processing time p > 0, we obtain a best possible online algorithm with a competitive ratio of (1+root 5)/2.
引用
收藏
页数：10
相关论文
共 15 条
  • [1] [Anonymous], 2004, Handbook of Scheduling-Algorithms, Models, and Performance Analysis, DOI DOI 10.1201/9780203489802.CH15
  • [2] Cai YH, 2012, ASIA PACIFIC J OPERA, V29, P1
  • [3] Scheduling on identical machines: How good is LPT in an on-line setting?
    Chen, B
    Vestjens, APA
    [J]. OPERATIONS RESEARCH LETTERS, 1997, 21 (04) : 165 - 169
  • [4] Chen B., 1998, Handbook of Combinatorial Optimization, P1493, DOI [DOI 10.1007/978-1-4613-0303-9_25, 10.1007/978-1-4613-0303-925, DOI 10.1007/978-1-4613-0303-925]
  • [5] [冯琪 Feng Qi], 2007, [运筹学学报, OR Transactions], V11, P121
  • [6] STRONG NP-COMPLETENESS RESULTS - MOTIVATION, EXAMPLES, AND IMPLICATIONS
    GAREY, MR
    JOHNSON, DS
    [J]. JOURNAL OF THE ACM, 1978, 25 (03) : 499 - 508
  • [7] Graham R L., 1969, SIAM J APPL MATH, V17, P263
  • [8] BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES
    GRAHAM, RL
    [J]. BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09): : 1563 - +
  • [9] Online scheduling of precedence constrained tasks
    Huo, YM
    Leung, JYT
    [J]. SIAM JOURNAL ON COMPUTING, 2005, 34 (03) : 743 - 762
  • [10] Optimal Semi-Online Algorithm for Scheduling on Two Parallel Batch Processing Machines
    Liu, Ming
    Zheng, Feifeng
    Zhu, Zhanguo
    Chu, Chengbin
    [J]. ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2014, 31 (05)
12