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 条
  • [31] Approximation algorithms for scheduling jobs with chain precedence constraints
    Jansen, K
    Solis-Oba, R
    PARALLEL PROCESSING AND APPLIED MATHEMATICS, 2004, 3019 : 105 - 112
  • [32] Customer order scheduling to minimize the number of late jobs
    Lin, B. M. T.
    Kononov, A. V.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 183 (02) : 944 - 948
  • [33] Scheduling of Jobs based on Hungarian Method in Cloud Computing
    Patel, Ronakkumar R.
    Desai, Tushar T.
    Patel, Swachilkumar J.
    PROCEEDINGS OF THE 2017 INTERNATIONAL CONFERENCE ON INVENTIVE COMMUNICATION AND COMPUTATIONAL TECHNOLOGIES (ICICCT), 2017, : 6 - 9
  • [34] Precedence-Constrained Scheduling of Malleable Jobs with Preemption
    Makarychev, Konstantin
    Panigrahi, Debmalya
    AUTOMATA, LANGUAGES, AND PROGRAMMING (ICALP 2014), PT I, 2014, 8572 : 823 - 834
  • [35] The Aggressive Oversubscribing Scheduling for Interactive Jobs on a Supercomputing System
    Minami, Shohei
    Endo, Toshio
    Nomura, Akihiro
    2023 IEEE HIGH PERFORMANCE EXTREME COMPUTING CONFERENCE, HPEC, 2023,
  • [36] APPROXIMATION SCHEMES FOR SCHEDULING JOBS WITH CHAIN PRECEDENCE CONSTRAINTS
    Jansen, Klaus
    Solis-Oba, Roberto
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2010, 21 (01) : 27 - 49
  • [37] The First Approximation Algorithm for the Maximin Latin Hypercube Design Problem
    Le Guiban, Kaourintin
    Rimmel, Arpad
    Weisser, Marc-Antoine
    Tomasik, Joanna
    OPERATIONS RESEARCH, 2018, 66 (01) : 253 - 266
  • [38] A New Approach for Scheduling Tasks and/or Jobs in Big Data Cluster
    Hadjar, Karim
    Jedidi, Ahmed
    2019 4TH MEC INTERNATIONAL CONFERENCE ON BIG DATA AND SMART CITY (ICBDSC), 2019, : 191 - 194
  • [39] Scheduling jobs under increasing linear machine maintenance time
    Dehua Xu
    Yunqiang Yin
    Hongxing Li
    Journal of Scheduling, 2010, 13 : 443 - 449
  • [40] Approximation algorithms for energy-efficient scheduling of parallel jobs
    Alexander Kononov
    Yulia Kovalenko
    Journal of Scheduling, 2020, 23 : 693 - 709
12345