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 条
  • [21] Energy-Efficient Location and Activity-Aware On-Demand Mobile Distributed Sensing Platform for Sensing as a Service in IoT Clouds
    Perera, Charith
    Talagala, Dumidu S.
    Liu, Chi Harold
    Estrella, Julio C.
    [J]. IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS, 2015, 2 (04) : 171 - 181
  • [22] Task Scheduling on Adaptive Multi-Core
    Pricopi, Mihai
    Mitra, Tulika
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 2014, 63 (10) : 2590 - 2603
  • [23] A taxonomy of flexible flow line scheduling procedures
    Quadt, Daniel
    Kuhn, Heinrich
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 178 (03) : 686 - 698
  • [24] A Bin Packing Heuristic for On-Line Service Placement and Performance Control
    Reynolds, M. Brent
    Hulce, Don R.
    Hopkinson, Kenneth M.
    Oxley, Mark E.
    Mullins, Barry E.
    [J]. IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, 2013, 10 (03): : 326 - 339
  • [25] The hybrid flow shop scheduling problem
    Ruiz, Ruben
    Antonio Vazquez-Rodriguez, Jose
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 205 (01) : 1 - 18
  • [26] Supporting HPC Analytics Applications with Access Patterns Using Data Restructuring and Data-Centric Scheduling Techniques in MapReduce
    Sehrish, Saba
    Mackey, Grant
    Shang, Pengju
    Wang, Jun
    Bent, John
    [J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2013, 24 (01) : 158 - 169
  • [27] Energy and Makespan Tradeoffs in Heterogeneous Computing Systems using Efficient Linear Programming Techniques
    Tarplee, Kyle M.
    Friese, Ryan
    Maciejewski, Anthony A.
    Siegel, Howard Jay
    Chong, Edwin K. P.
    [J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2016, 27 (06) : 1633 - 1646
  • [28] A Hyper-Heuristic Scheduling Algorithm for Cloud
    Tsai, Chun-Wei
    Huang, Wei-Cheng
    Chiang, Meng-Hsiu
    Chiang, Ming-Chao
    Yang, Chu-Sing
    [J]. IEEE TRANSACTIONS ON CLOUD COMPUTING, 2014, 2 (02) : 236 - 250
  • [29] Orchestrating an Ensemble of MapReduce Jobs for Minimizing Their Makespan
    Verma, Abhishek
    Cherkasova, Ludmila
    Campbell, Roy H.
    [J]. IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, 2013, 10 (05) : 314 - 327
  • [30] Scheduling two-stage hybrid flow shops with parallel batch, release time, and machine eligibility constraints
    Wang, I. -Lin
    Yang, Taho
    Chang, Yu-Bang
    [J]. JOURNAL OF INTELLIGENT MANUFACTURING, 2012, 23 (06) : 2271 - 2280
1234