Greedy multiprocessor server scheduling

被引：12
|
作者：
Bussema, Carl [1 ]
Torng, Eric [1 ]
机构：
[1] Michigan State Univ, Dept Comp Sci & Engn, E Lansing, MI 48824 USA
来源：
OPERATIONS RESEARCH LETTERS | 2006年 / 34卷 / 04期
关键词：
online scheduling; algorithms; flow; multiprocessor; l(p) norm; greedy;
D O I：
10.1016/j.orl.2005.07.005
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We show that the greedy highest density first (HDF) algorithm is (1 + epsilon)-speed O(1) -competitive for the problem of minimizing the lp norms of weighted flow time on in identical machines. Similar results for minimizing unweighted flow provide insight into the power of migration. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：451 / 458
页数：8
相关论文
共 50 条
  • [41] Analysis of multiprocessor task scheduling
    Linn, JF
    Chen, SJ
    COMPUTER SYSTEMS SCIENCE AND ENGINEERING, 1996, 11 (02): : 117 - 120
  • [42] On parallelizing the multiprocessor scheduling problem
    Ahmad, I
    Kwok, YK
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1999, 10 (04) : 414 - 432
  • [43] Multiprocessor Scheduling of Elastic Tasks
    Orr, James
    Baruah, Sanjoy
    RTNS 2019: PROCEEDINGS OF THE 27TH INTERNATIONAL CONFERENCE ON REAL-TIME NETWORKS AND SYSTEMS (RTNS 2019), 2020, : 133 - 142
  • [44] A composite algorithm for multiprocessor scheduling
    Giuseppe Paletta
    Francesca Vocaturo
    Journal of Heuristics, 2011, 17 : 281 - 301
  • [45] On multiprocessor scheduling with cellular automata
    Swiecicka, A
    Seredynski, F
    INTELLIGENT INFORMATION SYSTEMS 2002, PROCEEDINGS, 2002, 17 : 371 - 380
  • [46] COUNTEREXAMPLE TO A CONJECTURE IN MULTIPROCESSOR SCHEDULING
    LAURENTINI, A
    ELECTRONICS LETTERS, 1976, 12 (10) : 246 - 248
  • [47] Phase transition in multiprocessor scheduling
    Bauke, H
    Mertens, S
    Engel, A
    PHYSICAL REVIEW LETTERS, 2003, 90 (15)
  • [48] Online randomized multiprocessor scheduling
    Seiden, SS
    ALGORITHMICA, 2000, 28 (02) : 173 - 216
  • [49] Iterative Robust Multiprocessor Scheduling
    Adyanthaya, Shreya
    Geilen, Marc
    Basten, Twan
    Voeten, Jeroen
    Schiffelers, Ramon
    PROCEEDINGS OF THE 23RD INTERNATIONAL CONFERENCE ON REAL-TIME AND NETWORKS SYSTEMS (RTNS) 2015, 2015, : 23 - 32
  • [50] Scheduling Independent Multiprocessor Tasks
    Algorithmica, 2002, 32 : 247 - 261
12345