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 条
  • [41] Approximation Schemes for Machine Scheduling
    Maack, Marten
    OPERATIONS RESEARCH PROCEEDINGS 2021, 2022, : 21 - 26
  • [42] A chameleon and remora search optimization algorithm for handling task scheduling uncertainty problem in cloud computing
    Pabitha, P.
    Nivitha, K.
    Gunavathi, C.
    Panjavarnam, B.
    SUSTAINABLE COMPUTING-INFORMATICS & SYSTEMS, 2024, 41
  • [43] An Improved Ant Colony Optimization for Solving Task Scheduling Problem in Radar Signal Processing System
    Xu, Guowei
    Lin, Hui
    Cheng, Yi
    Li, Shuo
    JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY, 2023, 95 (2-3): : 333 - 350
  • [44] Orthogonal Taguchi-based cat algorithm for solving task scheduling problem in cloud computing
    Danlami Gabi
    Abdul Samad Ismail
    Anazida Zainal
    Zalmiyah Zakaria
    Ajith Abraham
    Neural Computing and Applications, 2018, 30 : 1845 - 1863
  • [45] An Improved Ant Colony Optimization for Solving Task Scheduling Problem in Radar Signal Processing System
    Guowei Xu
    Hui Lin
    Yi Cheng
    Shuo Li
    Journal of Signal Processing Systems, 2023, 95 : 333 - 350
  • [46] Orthogonal Taguchi-based cat algorithm for solving task scheduling problem in cloud computing
    Gabi, Danlami
    Ismail, Abdul Samad
    Zainal, Anazida
    Zakaria, Zalmiyah
    Abraham, Ajith
    NEURAL COMPUTING & APPLICATIONS, 2018, 30 (06) : 1845 - 1863
  • [47] Task Scheduling Problem of Double-Deep Multi-Tier Shuttle Warehousing Systems
    Zhan, Xiangnan
    Xu, Liyun
    Ling, Xufeng
    PROCESSES, 2021, 9 (01) : 1 - 21
  • [48] Task scheduling in virtual enterprise
    Gao, Y
    Jiang, ZB
    PROCEEDINGS OF THE 2005 INTERNATIONAL CONFERENCE ON MANAGEMENT SCIENCE & ENGINEERING (12TH), VOLS 1- 3, 2005, : 623 - 626
  • [49] Scheduling task graphs optimally with A*
    Shahul, Ahmed Zaki Semar
    Sinnen, Oliver
    JOURNAL OF SUPERCOMPUTING, 2010, 51 (03) : 310 - 332
  • [50] Correlation adaptive task scheduling
    Thanasis Moustakas
    Kostas Kolomvatsos
    Computing, 2023, 105 : 2459 - 2486
12345