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 条
  • [31] A column generation approach for the integrated shift and task scheduling problem of logistics assistants in hospitals
    Volland, Jonas
    Fuegener, Andreas
    Brunner, Jens O.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2017, 260 (01) : 316 - 334
  • [32] Evolutionary Algorithmic approaches for solving three objectives task scheduling Problem on Heterogeneous systems
    Chitra, P.
    Revathi, S.
    Venkatesh, P.
    Rajaram, R.
    2010 IEEE 2ND INTERNATIONAL ADVANCE COMPUTING CONFERENCE, 2010, : 38 - 43
  • [33] Solving Task Scheduling Problem in the Cloud Using a Hybrid Particle Swarm Optimization Approach
    Cheikh, Salmi
    Walker, Jessie J.
    INTERNATIONAL JOURNAL OF APPLIED METAHEURISTIC COMPUTING, 2022, 13 (01)
  • [34] Modeling Multi-constrained Fog-cloud Environment for Task Scheduling Problem
    Thang Nguyen
    Khiem Doan
    Nguyen, Giang
    Binh Minh Nguyen
    2020 IEEE 19TH INTERNATIONAL SYMPOSIUM ON NETWORK COMPUTING AND APPLICATIONS (NCA), 2020,
  • [35] Artificial Immune System (AIS) for Task Scheduling Problem in Multi-processors Environment
    Nazri, Muhamad Firdaus Mohd
    Suliman, Saiful Izwan
    Yusoff, Yuslinda Wati Mohd
    Harun, Afdallyna Fathiyah
    PROCEEDINGS OF 2019 8TH INTERNATIONAL CONFERENCE ON INDUSTRIAL TECHNOLOGY AND MANAGEMENT (ICITM 2019), 2019, : 348 - 352
  • [36] An Evolutionary Algorithm for Solving Task Scheduling Problem in Cloud-Fog Computing Environment
    Huynh Thi Thanh Binh
    Tran The Anh
    Do Bao Son
    Pham Anh Duc
    Binh Minh Nguyen
    PROCEEDINGS OF THE NINTH INTERNATIONAL SYMPOSIUM ON INFORMATION AND COMMUNICATION TECHNOLOGY (SOICT 2018), 2018, : 397 - 404
  • [37] A complex task scheduling scheme for big data platforms based on Boolean Satisfiability Problem
    Hong, Huang
    Khan, Latifur
    Ayoade, Gbadebo G.
    Zhou Shaohua
    Wei Yong
    2018 IEEE INTERNATIONAL CONFERENCE ON INFORMATION REUSE AND INTEGRATION (IRI), 2018, : 170 - 177
  • [38] RAS: A Task Scheduling Algorithm Based on Resource Attribute Selection in a Task Scheduling Framework
    Zhao, Yong
    Chen, Liang
    Li, Youfu
    Liu, Peng
    Li, Xiaolong
    Zhu, Chenchen
    INTERNET AND DISTRIBUTED COMPUTING SYSTEMS, IDCS 2013, 2013, 8223 : 106 - 119
  • [39] Approximation Schemes for Machine Scheduling
    Maack, Marten
    OPERATIONS RESEARCH PROCEEDINGS 2021, 2022, : 21 - 26
  • [40] An approximation algorithm for the three-machine scheduling problem with the routes given by the same partial order
    Quibell, Richard
    Strusevich, Vitaly A.
    COMPUTERS & INDUSTRIAL ENGINEERING, 2014, 76 : 347 - 359
12345