A 2.28-COMPETITIVE ALGORITHM FOR ONLINE SCHEDULING ON IDENTICAL MACHINES

被引：6
作者：
Tao, Jiping [1 ]
Huang, Ronghuan [1 ]
Liu, Tundong [1 ]
机构：
[1] Xiamen Univ, Dept Automat, Xiamen 361005, Peoples R China
来源：
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION | 2015年 / 11卷 / 01期
基金：
中国国家自然科学基金;
关键词：
Identical machines scheduling; online algorithms; competitive analysis; instance reduction; AVERAGE COMPLETION-TIME; SINGLE-MACHINE;
D O I：
10.3934/jimo.2015.11.185
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
Online scheduling on identical machines is investigated in the setting where jobs arrive over time. The goal is to minimize the total completion time. A waiting strategy based online algorithm is designed and is proved to be 2.28-competitive. The result improves the current best online algorithm from the worse-case prospective.
引用
收藏
页码：185 / 198
页数：14
相关论文
共 17 条
  • [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] The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
    Chou, MC
    Queyranne, M
    Simchi-Levi, D
    [J]. MATHEMATICAL PROGRAMMING, 2006, 106 (01) : 137 - 157
  • [3] LP-based online scheduling: from single to parallel machines
    Correa, Jose R.
    Wagner, Michael R.
    [J]. MATHEMATICAL PROGRAMMING, 2009, 119 (01) : 109 - 136
  • [4] Fiat A, 1998, LECT NOTES COMPUT SC, V1442, P1, DOI 10.1007/BFb0029562
  • [5] Goemans MX, 1997, PROCEEDINGS OF THE EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P591
  • [6] 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
  • [7] 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
  • [8] Hoogeveen J. A., 1996, Integer Programming and Combinatorial Optimization. 5th International IPCO Conference Proceedings, P404
  • [9] Jiping Tao, 2012, Proceedings of the 2012 24th Chinese Control and Decision Conference (CCDC), P3184, DOI 10.1109/CCDC.2012.6244503
  • [10] On-line scheduling of parallel machines to minimize total completion times
    Liu, Peihai
    Lu, Xiwen
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (09) : 2647 - 2652
12