Randomized on-line scheduling on three processors

被引：2
|
作者：
Tichy, T [1 ]
机构：
[1] AS CR, Inst Math, CZ-11567 Prague 1, Czech Republic
来源：
OPERATIONS RESEARCH LETTERS | 2004年 / 32卷 / 02期
关键词：
scheduling; makespan; competitive analysis; on-line algorithm; lower bound;
D O I：
10.1016/j.orl.2003.05.003
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We consider a randomized on-line scheduling problem where each job has to be scheduled on any of m identical processors. The objective is to minimize the expected makespan. We show that the competitive ratio of any randomized algorithm for 27 m = 3 processors must be strictly greater than 27/19. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：152 / 158
页数：7
相关论文
共 50 条
  • [1] Semi on-line scheduling on three processors with known sum of the tasks
    Angelelli, Enrico
    Grazia Speranza, Maria
    Tuza, Zsolt
    JOURNAL OF SCHEDULING, 2007, 10 (4-5) : 263 - 269
  • [2] Semi on-line scheduling on three processors with known sum of the tasks
    Enrico Angelelli
    Maria Grazia Speranza
    Zsolt Tuza
    Journal of Scheduling, 2007, 10 : 263 - 269
  • [3] Randomized on-line scheduling similar jobs to minimize makespan on two identical processors
    Du D.-L.
    Acta Mathematicae Applicatae Sinica, 2005, 21 (3) : 485 - 488
  • [4] On-Line Parallelizable Task Scheduling on Parallel Processors
    Khludova, Marina
    PARALLEL COMPUTING TECHNOLOGIES (PACT 2013), 2013, 7979 : 229 - 233
  • [5] Preemptive on-line scheduling for two uniform processors
    Wen, JJ
    Du, DL
    OPERATIONS RESEARCH LETTERS, 1998, 23 (3-5) : 113 - 116
  • [6] Dynamic on-line task scheduling on parallel processors
    Xia, CH
    Michailidis, G
    Bambos, N
    PERFORMANCE EVALUATION, 2001, 46 (2-3) : 219 - 233
  • [7] Geometric representation for semi on-line scheduling on uniform processors
    Angelelli, Enrico
    Speranza, Maria Grazia
    Szoldatics, Jozsef
    Tuza, Zsolt
    OPTIMIZATION METHODS & SOFTWARE, 2010, 25 (03): : 421 - 428
  • [8] Randomized on-line scheduling of parallel jobs
    Sgall, J
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1996, 21 (01): : 149 - 175
  • [9] Randomized on-line scheduling on two uniform machines
    Epstein, L
    Noga, J
    Seiden, S
    Sgall, J
    Woeginger, G
    JOURNAL OF SCHEDULING, 2001, 4 (02) : 71 - 92
  • [10] A lower bound for randomized on-line multiprocessor scheduling
    Sgall, J
    INFORMATION PROCESSING LETTERS, 1997, 63 (01) : 51 - 55
12345