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 条
  • [1] A Semi Greedy Soft Real-Time Multiprocessor Scheduling Algorithm
    Alhussian, Hitham
    Zakaria, Nordin
    Hussin, Fawnizu Azmadi
    Bahbouh, Hussein T.
    2014 INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION SCIENCES (ICCOINS), 2014,
  • [2] An iterated greedy heuristic for multistage hybrid flowshop scheduling problems with multiprocessor tasks
    Ying, K-C
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2009, 60 (06) : 810 - 817
  • [3] An unfair semi-greedy real-time multiprocessor scheduling algorithm
    Alhussian, Hitham
    Zakaria, Nordin
    Patel, Ahmed
    COMPUTERS & ELECTRICAL ENGINEERING, 2016, 50 : 143 - 165
  • [4] Multiprocessor task scheduling in multistage hybrid flow-shops: A parallel greedy algorithm approach
    Kahraman, Cengiz
    Engin, Orhan
    Kaya, Ihsan
    Ozturk, R. Elif
    APPLIED SOFT COMPUTING, 2010, 10 (04) : 1293 - 1300
  • [5] A greedy-but-safe dynamic scheduling strategy for an interactive video-on-demand server
    To, JPJ
    Hamidzadeh, B
    PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON MULTIMEDIA COMPUTING AND SYSTEMS, 1996, : 136 - 143
  • [6] Hybrid real-time task scheduling upon multiprocessor platforms using server techniques
    El-Kebbe, DA
    ISORC 2003: SIXTH IEEE INTERNATIONAL SYMPOSIUM ON OBJECT-ORIENTED REAL-TIME DISTRIBUTED COMPUTING, PROCEEDINGS, 2003, : 277 - 284
  • [7] A Greedy Algorithm for Jobs Allocation in a Multiprocessor System
    Khutoretskii, Alexandre
    Bredikhin, Sergei
    2019 15TH INTERNATIONAL ASIAN SCHOOL-SEMINAR OPTIMIZATION PROBLEMS OF COMPLEX SYSTEMS (OPCS 2019), 2019, : 82 - 85
  • [8] On multiprocessor system scheduling
    Deng, XT
    Dymond, P
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 1998, 1 (04) : 377 - 392
  • [9] Multiprocessor scheduling with rejection
    Bartal, Y
    Leonardi, S
    Marchetti-Spaccamela, A
    Sgall, J
    Stougie, L
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (01) : 64 - 78
  • [10] On Multiprocessor System Scheduling
    Xiaotie Deng
    Patrick Dymond
    Journal of Combinatorial Optimization, 1998, 1 : 377 - 392
12345