An algorithm for scheduling jobs in hypercube systems

被引：8
作者：
Kwon, OH
Chwa, KY
机构：
[1] Pukyong Natl Univ, Dept Comp Engn, Nam Gu, Pusan 608737, South Korea
[2] KAIST, Dept Comp Sci, Yusong Gu, Taejon 305701, South Korea
来源：
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1998年 / 9卷 / 09期
关键词：
hypercube systems; job scheduling; subcube allocation; approximation algorithm; absolute performance ratio;
D O I：
10.1109/71.722219
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, we consider the problem of nonpreemptively scheduling independent jobs so as to minimize overall finish time on an m-dimensional hypercube system. This problem is NP-hard. We propose a polynomial time approximation algorithm and prove that the absolute performance ratio of the algorithm does not exceed 1.875. This is the first algorithm achieving an absolute performance ratio less than two by a constant.
引用
收藏
页码：856 / 860
页数：5
相关论文
共 50 条
  • [41] Scheduling Supercomputer Jobs under Existing Power Consumption Constraints
    E. A. Kiselev
    A. V. Yarovoy
    P. N. Telegin
    A. V. Baranov
    Lobachevskii Journal of Mathematics, 2024, 45 (10) : 5082 - 5091
  • [42] Approximation algorithms for energy-efficient scheduling of parallel jobs
    Kononov, Alexander
    Kovalenko, Yulia
    JOURNAL OF SCHEDULING, 2020, 23 (06) : 693 - 709
  • [43] Scheduling parallel jobs on multicore clusters using CPU oversubscription
    Gladys Utrera
    Julita Corbalan
    Jesús Labarta
    The Journal of Supercomputing, 2014, 68 : 1113 - 1140
  • [44] Salamander: a Holistic Scheduling of MapReduce Jobs on Ephemeral Cloud Resources
    Handaoui, Mohamed
    Dartois, Jean-Emile
    Lemarchand, Laurent
    Boukhobza, Jalil
    2020 20TH IEEE/ACM INTERNATIONAL SYMPOSIUM ON CLUSTER, CLOUD AND INTERNET COMPUTING (CCGRID 2020), 2020, : 320 - 329
  • [45] Holistic Slowdown Driven Scheduling and Resource Management for Malleable Jobs
    D'Amico, Marco
    Jokanovic, Ana
    Corbalan, Julita
    PROCEEDINGS OF THE 48TH INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING (ICPP 2019), 2019,
  • [46] Job scheduling to minimize the weighted waiting time variance of jobs
    Li, Xueping
    Ye, Nong
    Liu, Tieming
    Sun, Yang
    COMPUTERS & INDUSTRIAL ENGINEERING, 2007, 52 (01) : 41 - 56
  • [47] Scheduling jobs under increasing linear machine maintenance time
    Xu, Dehua
    Yin, Yunqiang
    Li, Hongxing
    JOURNAL OF SCHEDULING, 2010, 13 (04) : 443 - 449
  • [48] Scheduling parallel jobs on multicore clusters using CPU oversubscription
    Utrera, Gladys
    Corbalan, Julita
    Labarta, Jesus
    JOURNAL OF SUPERCOMPUTING, 2014, 68 (03) : 1113 - 1140
  • [49] Improved approximation algorithms for scheduling parallel jobs on identical clusters
    Bougeret, Marin
    Dutot, Pierre-Francois
    Trystram, Denis
    Jansen, Klaus
    Robenek, Christina
    THEORETICAL COMPUTER SCIENCE, 2015, 600 : 70 - 85
  • [50] Scheduling Jobs on Batch Machines Based on Ant Colony Algorithms
    Huang, XiaBao
    APPLIED MECHANICS, MATERIALS AND MANUFACTURING IV, 2014, 670-671 : 1522 - 1525
12345