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 条
  • [21] Scalability-aware Scheduling Optimization Algorithm for Multi-Objective Cloud Task Scheduling Problem
    Gabi, Danlami
    Ismail, Abdul Samad
    Zainal, Anazida
    Zakaria, Zalmiyah
    2017 6TH ICT INTERNATIONAL STUDENT PROJECT CONFERENCE (ICT-ISPC), 2017,
  • [22] A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar
    Zhang, Haowei
    Xie, Junwei
    Ge, Jiaang
    Zhang, Zhaojian
    Zong, Binfeng
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2019, 272 (03) : 868 - 878
  • [23] A gradient-based optimization approach for task scheduling problem in cloud computing
    Huang, Xingwang
    Lin, Yangbin
    Zhang, Zongliang
    Guo, Xiaoxi
    Su, Shubin
    CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS, 2022, 25 (05): : 3481 - 3497
  • [24] Multiprocessor task scheduling problem using hybrid discrete particle swarm optimization
    Vairam, T.
    Sarathambekai, S.
    Umamaheswari, K.
    SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES, 2018, 43 (12):
  • [25] Multiprocessor task scheduling problem using hybrid discrete particle swarm optimization
    T Vairam
    S Sarathambekai
    K Umamaheswari
    Sādhanā, 2018, 43
  • [26] Multiobjective evolutionary computation algorithms for solving task scheduling problem on heterogeneous systems
    Chitra, P.
    Venkatesh, P.
    INTERNATIONAL JOURNAL OF KNOWLEDGE-BASED AND INTELLIGENT ENGINEERING SYSTEMS, 2010, 14 (01) : 21 - 30
  • [27] A gradient-based optimization approach for task scheduling problem in cloud computing
    Xingwang Huang
    Yangbin Lin
    Zongliang Zhang
    Xiaoxi Guo
    Shubin Su
    Cluster Computing, 2022, 25 : 3481 - 3497
  • [28] A Parallel Memetic Algorithm on GPU to Solve the Task Scheduling Problem in Heterogeneous Environments
    Mirsoleimani, Sayyed Ali
    Karami, Ali
    Khunjush, Farshad
    GECCO'13: PROCEEDINGS OF THE 2013 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2013, : 1181 - 1188
  • [29] Quality of service task scheduling algorithm for time-cost trade off scheduling problem in cloud computing environment
    Gabi D.
    Ismail A.S.
    Zainal A.
    Zakaria Z.
    International Journal of Intelligent Systems Technologies and Applications, 2019, 18 (05) : 448 - 469
  • [30] Whale Optimization Algorithm (WOA) for Task Scheduling Problem in Multi-processors Environment
    Suliman, Saiful Izwan
    Khalish, Mohammad Nur
    Yusof, Yuslinda Wati Mohamad
    Rahman, Farah Yasmin Abdul
    2024 IEEE SYMPOSIUM ON INDUSTRIAL ELECTRONICS AND APPLICATIONS, ISIEA 2024, 2024,
12345