On approximation of the bulk synchronous task scheduling problem

被引：0
|
作者：
Fujimoto, N [1 ]
Hagihara, K [1 ]
机构：
[1] Osaka Univ, Grad Sch Informat Sci & Technol, Toyonaka, Osaka 5608531, Japan
来源：
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 2003年 / 14卷 / 11期
基金：
日本学术振兴会;
关键词：
task scheduling; distributed memory; fine grain; software overhead; message packaging; bulk synchronous schedule; NP-complete; approximation; nonapproximability;
D O I：
10.1109/TPDS.2003.1247678
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The bulk synchronous task scheduling problem (BSSPO) is known as an effective task scheduling problem for distributed-memory machines. This paper presents a proof of NP-completeness of the decision counterpart of BSSPO, even in the case of makespan of at most five. This implies nonapproximability of BSSPO, meaning that there is no approximation algorithm with performance guarantee smaller than 6/5 unless P = NP. This paper also gives an approximation algorithm, with a performance guarantee of two for BSSPO in several restricted cases.
引用
收藏
页码：1191 / 1199
页数：9
相关论文
共 50 条
  • [1] Complexity and approximation for scheduling problem for a torpedo
    Giroudeau, R.
    Koenig, J. C.
    Simonin, G.
    CIE: 2009 INTERNATIONAL CONFERENCE ON COMPUTERS AND INDUSTRIAL ENGINEERING, VOLS 1-3, 2009, : 300 - 304
  • [2] Complexity and approximation for scheduling problem for a torpedo
    Simonin, G.
    Giroudeau, R.
    Koenig, J. C.
    COMPUTERS & INDUSTRIAL ENGINEERING, 2011, 61 (02) : 352 - 356
  • [3] Task schedulable problem and maximum scheduling problem in a multi-agent system
    Li B.
    Zhang X.
    Wu J.
    Zhu J.
    Journal of Software, 2011, 6 (11 SPEC. ISSUE) : 2225 - 2231
  • [4] A Stochastic Approximation Approach for Foresighted Task Scheduling in Cloud Computing
    Mostafavi, Seyedakbar
    Hakami, Vesal
    WIRELESS PERSONAL COMMUNICATIONS, 2020, 114 (01) : 901 - 925
  • [5] A Stochastic Approximation Approach for Foresighted Task Scheduling in Cloud Computing
    Seyedakbar Mostafavi
    Vesal Hakami
    Wireless Personal Communications, 2020, 114 : 901 - 925
  • [6] Research of task scheduling problem in product data management
    Luo, Xinggang
    Wang, Dingwei
    Tang, Jiafu
    Tu, Yiliu
    WCICA 2006: SIXTH WORLD CONGRESS ON INTELLIGENT CONTROL AND AUTOMATION, VOLS 1-12, CONFERENCE PROCEEDINGS, 2006, : 7018 - 7022
  • [7] Task scheduling for power optimisation of multi frequency synchronous data flow graphs
    Knerr, B
    Holzer, M
    Rupp, M
    SBCCI 2005: 18TH SYMPOSIUM ON INTEGRATED CIRCUITS AND SYSTEMS DESIGN, PROCEEDINGS, 2005, : 50 - 55
  • [8] Approximation of the parallel machine scheduling problem with additional unit resources
    Hebrard, Emmanuel
    Huguet, Marie-Jose
    Jozefowiez, Nicolas
    Maillard, Adrien
    Pralet, Cedric
    Verfaillie, Gerard
    DISCRETE APPLIED MATHEMATICS, 2016, 215 : 126 - 135
  • [9] Synchronous Cellular Automata Scheduler with Construction Heuristic to Static Task Scheduling in Multiprocessors
    Carneiro, Murillo G.
    Oliveira, Gina M. B.
    PROCEEDINGS OF THE FOURTEENTH INTERNATIONAL CONFERENCE ON GENETIC AND EVOLUTIONARY COMPUTATION COMPANION (GECCO'12), 2012, : 1433 - 1434
  • [10] Approximation of the Objective Function of Single-Machine Scheduling Problem
    Lazarev, Alexander
    Pravdivets, Nikolay
    Barashov, Egor
    MATHEMATICS, 2024, 12 (05)
12345