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 条
  • [21] A NEW DISTRIBUTED JOB SCHEDULING ALGORITHM FOR GRID SYSTEMS
    Torkestani, Javad Akbari
    CYBERNETICS AND SYSTEMS, 2013, 44 (01) : 77 - 93
  • [22] Cuckoo Search Algorithm for Job Scheduling in Cloud Systems
    Amtade, Supacheep
    Miyamoto, Toshiyuki
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2015, E98A (02) : 645 - 649
  • [23] MIN-Max-Min: A Heuristic Scheduling Algorithm for Jobs Across Geo-distributed Datacenters
    Li, Yan
    Zhu, Chunge
    Wang, Yong
    2018 IEEE 38TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS (ICDCS), 2018, : 1573 - 1574
  • [24] On Speed Scaling Scheduling of Parallel Jobs with Preemption
    Kononov, Alexander
    Kovalenko, Yulia
    DISCRETE OPTIMIZATION AND OPERATIONS RESEARCH, DOOR 2016, 2016, 9869 : 309 - 321
  • [25] Resource Aware Scheduling for EDA Regression Jobs
    Nanda, Saurav
    Parthasarathy, Ganapathy
    Choudhary, Parivesh
    Venkatachar, Arun
    EURO-PAR 2019: PARALLEL PROCESSING WORKSHOPS, 2020, 11997 : 639 - 651
  • [26] Associate Scheduling of Mixed Jobs in Cloud Computing
    Komarasamy, Dinesh
    Muthuswamy, Vijayalakshmi
    PROCEEDINGS OF THE 3RD INTERNATIONAL SYMPOSIUM ON BIG DATA AND CLOUD COMPUTING CHALLENGES (ISBCC - 16'), 2016, 49 : 133 - 142
  • [27] Scheduling with Calibrations for Multi-Interval Jobs
    Chau, Vincent
    Damerius, Christoph
    Kling, Peter
    Li, Minming
    Schneider, Florian
    Zhang, Ruilong
    INFORMS JOURNAL ON COMPUTING, 2025,
  • [28] Scheduling jobs on a single machine with inventory operations
    Fan, Bao-Qiang
    Tang, Guo-Chun
    Zhang, Shu-Xia
    OPERATIONS RESEARCH AND ITS APPLICATIONS, PROCEEDINGS, 2008, 8 : 344 - +
  • [29] Scheduling unrelated machines with two types of jobs
    Vakhania, Nodari
    Alberto Hernandez, Jose
    Werner, Frank
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2014, 52 (13) : 3793 - 3801
  • [30] AN APPROXIMATION ALGORITHM FOR PREEMPTIVE SCHEDULING ON PARALLEL-TASK SYSTEMS
    KRISHNAMURTI, R
    NARAHARI, B
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1995, 8 (04) : 661 - 669
12345