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 条
  • [1] Approximation algorithm for scheduling independent multiprocessor jobs
    Huang J.-G.
    Li R.-H.
    Ruan Jian Xue Bao/Journal of Software, 2010, 21 (12): : 3211 - 3219
  • [2] Scheduling Jobs on Cloud Computing using Firefly Algorithm
    Esa, Demyana Izzat
    Yousif, Adil
    INTERNATIONAL JOURNAL OF GRID AND DISTRIBUTED COMPUTING, 2016, 9 (07): : 149 - 158
  • [3] An adaptive algorithm for scheduling parallel jobs in meteorological Cloud
    Hao, Yongsheng
    Wang, Lina
    Zheng, Mai
    KNOWLEDGE-BASED SYSTEMS, 2016, 98 : 226 - 240
  • [4] ON JOB SCHEDULING ON A HYPERCUBE
    ZHU, YH
    AHUJA, M
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1993, 4 (01) : 62 - 69
  • [5] TABU SEARCH ALGORITHM FOR SCHEDULING INDEPENDENT JOBS IN COMPUTATIONAL GRIDS
    Xhafa, Fatos
    Carretero, Javier
    Dorronsoro, Bernabe
    Alba, Enrique
    COMPUTING AND INFORMATICS, 2009, 28 (02) : 237 - 250
  • [6] Scheduling jobs on computational grid using Differential Evolution algorithm
    Selvi, S.
    Manimegalai, D.
    RECENT ADVANCES IN NETWORKING, VLSI AND SIGNAL PROCESSING, 2010, : 118 - +
  • [7] An Approximation Algorithm for Preemptive Speed Scaling Scheduling of Parallel Jobs with Migration
    Kononov, Alexander
    Kovalenko, Yulia
    LEARNING AND INTELLIGENT OPTIMIZATION (LION 11 2017), 2017, 10556 : 351 - 357
  • [8] Cooperative grid jobs scheduling with multi-objective genetic algorithm
    Zeng, Bin
    Wei, Jun
    Wang, Wei
    Wang, Pu
    PARALLEL AND DISTRIBUTED PROCESSING AND APPLICATIONS, PROCEEDINGS, 2007, 4742 : 545 - 555
  • [9] An online algorithm for scheduling big data analysis jobs in cloud environments
    Kang, Youyou
    Pan, Li
    Liu, Shijun
    KNOWLEDGE-BASED SYSTEMS, 2022, 245
  • [10] HEURISTIC SUBCUBE ALLOCATION IN HYPERCUBE SYSTEMS
    KANG, OH
    YOON, SY
    YOON, HS
    CHO, JW
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1992, E75D (04) : 517 - 526
12345