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 条
  • [21] Multiprocessor scheduling with few preemptions
    Andersson, Bjorn
    Tovar, Eduardo
    12TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS, PROCEEDINGS, 2006, : 322 - +
  • [22] Evolutionary multiprocessor task scheduling
    Montazeri, Faezeh
    Sahnani-Jelodar, Mehdi
    Fakhraie, S. Najmeh
    Fakhraie, S. Mehdi
    PAR ELEC 2006: INTERNATIONAL SYMPOSIUM ON PARALLEL COMPUTING IN ELECTRICAL ENGINEERING, PROCEEDINGS, 2006, : 68 - +
  • [23] A composite algorithm for multiprocessor scheduling
    Paletta, Giuseppe
    Vocaturo, Francesca
    JOURNAL OF HEURISTICS, 2011, 17 (03) : 281 - 301
  • [24] PROCESSOR SCHEDULING IN MULTIPROCESSOR SYSTEMS
    TRIPATHI, SK
    SERAZZI, G
    GHOSAL, D
    LECTURE NOTES IN COMPUTER SCIENCE, 1992, 591 : 208 - 225
  • [25] Multiprocessor scheduling in a genetic paradigm
    Kuwait Univ, Safat, Kuwait
    Parallel Comput, 3 (395-406):
  • [26] Implementing multiprocessor scheduling disciplines
    Parsons, EW
    Sevcik, KC
    JOB SCHEDULING STRATEGIES FOR PARALLEL PROCESSING, 1997, 1291 : 166 - 192
  • [27] Online Randomized Multiprocessor Scheduling
    S. S. Seiden
    Algorithmica, 2000, 28 : 173 - 216
  • [28] SCHEDULING MULTIPIPELINE AND MULTIPROCESSOR COMPUTERS
    SAHNI, S
    IEEE TRANSACTIONS ON COMPUTERS, 1984, 33 (07) : 637 - 645
  • [29] Multiprocessor Synchronization and Hierarchical Scheduling
    Nemati, Farhang
    Behnam, Moris
    Nolte, Thomas
    2009 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING WORKSHOPS (ICPPW 2009), 2009, : 58 - 64
  • [30] Multiprocessor scheduling in a genetic paradigm
    Ahmad, I
    Dhodhi, MK
    PARALLEL COMPUTING, 1996, 22 (03) : 395 - 406
12345