A data intensive heuristic approach to the two-stage streaming scheduling problem

被引：4
作者：
Liang, Wei [1 ,2 ]
Hu, Chunhua [1 ,2 ]
Wu, Min [3 ]
Jin, Qun [4 ]
机构：
[1] Hunan Univ Commerce, Key Lab Hunan Prov Mobile Business Intelligence, Changsha, Hunan, Peoples R China
[2] Hunan Univ Commerce, Mobile E Busines Collaborat Innovat Ctr Hunan Pro, Changsha, Hunan, Peoples R China
[3] China Univ Geosci, Sch Automat, Wuhan, Hubei, Peoples R China
[4] Waseda Univ, Fac Human Sci, Tokorozawa, Saitama, Japan
来源：
JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2017年 / 89卷
关键词：
Data intensive computing; Scheduling; Makespan; NP-hard; HYBRID FLOW-SHOPS; MANAGEMENT; ALGORITHM; SYSTEMS;
D O I：
10.1016/j.jcss.2017.01.005
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Data intensive computing (DIC) provides a high performance computing approach to process large volume of data. In this study, a new formalization is introduced to present the two-stage DIC task execution in a stream manner. A novel heuristic algorithm is proposed for the scheduling problem due to the NP complexity. The theoretical approximation ratio bounds for the heuristic are analyzed and confirmed by the experimental evaluation. Overall, we observe that the proposed method conducts average 1.2 times makespan than the theoretic bound of the optimal solution. Besides, the proposed method outperforms the GA and FIFO scheduling schemes with overall improvements. (C) 2017 Elsevier Inc. All rights reserved.
引用
收藏
页码：64 / 79
页数：16
相关论文
共 35 条
  • [1] Energy-Aware Scheduling of Distributed Systems
    Agrawal, Pragati
    Rao, Shrisha
    [J]. IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2014, 11 (04) : 1163 - 1175
  • [2] Heuristics for a two-stage assembly flowshop with bicriteria of maximum lateness and makespan
    Al-Anzi, Fawaz S.
    Allahverdi, Ali
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (09) : 2682 - 2689
  • [3] List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table
    Arabnejad, Hamid
    Barbosa, Jorge G.
    [J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2014, 25 (03) : 682 - 694
  • [4] Archana GK, 2015, PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON COMPUTING AND COMMUNICATIONS TECHNOLOGIES (ICCCT 15), P368, DOI 10.1109/ICCCT2.2015.7292777
  • [5] A Two-Stage Margin-Based Algorithm for Optimal Plug-in Electric Vehicles Scheduling
    Baccino, Francesco
    Grillo, Samuele
    Massucco, Stefano
    Silvestro, Federico
    [J]. IEEE TRANSACTIONS ON SMART GRID, 2015, 6 (02) : 759 - 766
  • [6] Optimization of Resource Provisioning Cost in Cloud Computing
    Chaisiri, Sivadon
    Lee, Bu-Sung
    Niyato, Dusit
    [J]. IEEE TRANSACTIONS ON SERVICES COMPUTING, 2012, 5 (02) : 164 - 177
  • [7] Job Scheduling With Uncertain Local Generation in Smart Buildings: Two-Stage Robust Approach
    Danandeh, Anna
    Zhao, Long
    Zeng, Bo
    [J]. IEEE TRANSACTIONS ON SMART GRID, 2014, 5 (05) : 2273 - 2282
  • [8] BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES
    GRAHAM, RL
    [J]. BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09): : 1563 - +
  • [9] Large-Scale Cognitive Cellular Systems: Resource Management Overview
    Guizani, Mohsen
    Khalfi, Bassem
    Ben Ghorbel, Mahdi
    Hamdaoui, Bechir
    [J]. IEEE COMMUNICATIONS MAGAZINE, 2015, 53 (05) : 44 - 51
  • [10] Performance Analysis of Cloud Computing Services for Many-Tasks Scientific Computing
    Iosup, Alexandru
    Ostermann, Simon
    Yigitbasi, M. Nezih
    Prodan, Radu
    Fahringer, Thomas
    Epema, Dick H. J.
    [J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2011, 22 (06) : 931 - 945
1234