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

Wei Liang; Chunhua Hu; Min Wu; Qun Jin

doi:10.1016/j.jcss.2017.01.005

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

Wei Liang, Chunhua Hu^*, Min Wu, Qun Jin

^*この研究の対応する著者

人間科学部

研究成果: Article › 査読

3 被引用数 (Scopus)

抄録

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.

本文言語	English
ページ（範囲）	64-79
ページ数	16
ジャーナル	Journal of Computer and System Sciences
巻	89
DOI	https://doi.org/10.1016/j.jcss.2017.01.005
出版ステータス	Published - 2017 11月

ASJC Scopus subject areas

理論的コンピュータサイエンス
コンピュータサイエンス（全般）
コンピュータネットワークおよび通信
計算理論と計算数学
応用数学

文献へのアクセス

10.1016/j.jcss.2017.01.005

他のファイルとリンク

引用スタイル

@article{838dc5845a804633af5fdcdb671882ca,

title = "A data intensive heuristic approach to the two-stage streaming scheduling problem",

abstract = "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.",

keywords = "Data intensive computing, Makespan, NP-hard, Scheduling",

author = "Wei Liang and Chunhua Hu and Min Wu and Qun Jin",

note = "Funding Information: This work was jointly supported by the National Nature Science Foundation of China under Grant No. 61273232 and No. 71210003, the Program for New Century Excellent Talents in University under NCET-13-0785, the Key Laboratory of Hunan Province for Mobile Business Intelligence under Grant No. 2015TP1002, and Mobile E-business 2011 Collaborative Innovation Center of Hunan Province. Publisher Copyright: {\textcopyright} 2017 Elsevier Inc.",

year = "2017",

month = nov,

doi = "10.1016/j.jcss.2017.01.005",

language = "English",

volume = "89",

pages = "64--79",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

}

TY - JOUR

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

AU - Liang, Wei

AU - Hu, Chunhua

AU - Wu, Min

AU - Jin, Qun

N1 - Funding Information: This work was jointly supported by the National Nature Science Foundation of China under Grant No. 61273232 and No. 71210003, the Program for New Century Excellent Talents in University under NCET-13-0785, the Key Laboratory of Hunan Province for Mobile Business Intelligence under Grant No. 2015TP1002, and Mobile E-business 2011 Collaborative Innovation Center of Hunan Province. Publisher Copyright: © 2017 Elsevier Inc.

PY - 2017/11

Y1 - 2017/11

N2 - 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.

AB - 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.

KW - Data intensive computing

KW - Makespan

KW - NP-hard

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=85012868497&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85012868497&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2017.01.005

DO - 10.1016/j.jcss.2017.01.005

M3 - Article

AN - SCOPUS:85012868497

SN - 0022-0000

VL - 89

SP - 64

EP - 79

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -

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

抄録

ASJC Scopus subject areas

文献へのアクセス

他のファイルとリンク

フィンガープリント

引用スタイル