Online Scheduling with Bounded Migration

被引：73
作者：
Sanders, Peter [1 ]
Sivadasan, Naveen [2 ]
Skutella, Martin [3 ]
机构：
[1] Univ Karlsruhe TH, Fak Informat, D-76128 Karlsruhe, Germany
[2] Max Planck Inst Informat, D-66123 Saarbrucken, Germany
[3] TU Berlin, Inst Math, D-10623 Berlin, Germany
来源：
MATHEMATICS OF OPERATIONS RESEARCH | 2009年 / 34卷 / 02期
关键词：
scheduling; approximation; online algorithm; sensitivity analysis; BIN-PACKING; ALGORITHMS; TIME;
D O I：
10.1287/moor.1090.0381
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
Consider the classical online scheduling problem, in which jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by some constant times the size of the arriving job. This constant is called the migration factor. For small migration factors, we obtain several simple online algorithms with constant competitive ratio. We also present a linear time "online approximation scheme," that is, a family of online algorithms with competitive ratio arbitrarily close to 1 and constant migration factor.
引用
收藏
页码：481 / 498
页数：18
相关论文
共 35 条
  • [1] Online algorithms: a survey
    Albers, S
    [J]. MATHEMATICAL PROGRAMMING, 2003, 97 (1-2) : 3 - 26
  • [2] Better bounds for online scheduling
    Albers, S
    [J]. SIAM JOURNAL ON COMPUTING, 1999, 29 (02) : 459 - 473
  • [3] Improved bounds for on-line load balancing
    Andrews, M
    Goemans, MX
    Zhang, L
    [J]. ALGORITHMICA, 1999, 23 (04) : 278 - 301
  • [4] [Anonymous], P 40 ANN IEEE S FDN
  • [5] [Anonymous], P SPAA
  • [6] Azar Y., 1998, Journal of Scheduling, V1, P67, DOI 10.1002/(SICI)1099-1425(199808)1:2<67::AID-JOS6>3.0.CO
  • [7] 2-Y
  • [8] New algorithms for an ancient scheduling problem
    Bartal, Y
    Fiat, A
    Karloff, H
    Vohra, R
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1995, 51 (03) : 359 - 366
  • [9] A LOWER-BOUND FOR RANDOMIZED ONLINE SCHEDULING ALGORITHMS
    CHEN, B
    VANVLIET, A
    WOEGINGER, GJ
    [J]. INFORMATION PROCESSING LETTERS, 1994, 51 (05) : 219 - 222
  • [10] COFFMAN EG, 1978, SIAM J COMPUT, V7, P1, DOI 10.1137/0207001
1234