Smart DAG Tasks Scheduling between Trusted and Untrusted Entities Using the MCTS Method

Yuxia Cheng, Zhiwei Wu, Kui Liu, Qing Wu and Yu Wang
Additional contact information
Yuxia Cheng: School of Computer Science and Technology, Hangzhou Dianzi University, 1158 Baiyang No. 2 Street, Hangzhou 310018, China
Zhiwei Wu: School of Computer Science and Technology, Hangzhou Dianzi University, 1158 Baiyang No. 2 Street, Hangzhou 310018, China
Kui Liu: School of Computer Science and Technology, Hangzhou Dianzi University, 1158 Baiyang No. 2 Street, Hangzhou 310018, China
Qing Wu: School of Computer Science and Technology, Hangzhou Dianzi University, 1158 Baiyang No. 2 Street, Hangzhou 310018, China
Yu Wang: School of Computer Science, Guangzhou University, 230 Wai Huan Xi Road, Guangzhou Higher Education Mega Center, Guangzhou 510006, China

Sustainability, 2019, vol. 11, issue 7, 1-16

Abstract: Task scheduling is critical for improving system performance in the distributed heterogeneous computing environment. The Directed Acyclic Graph (DAG) tasks scheduling problem is NP-complete and it is hard to find an optimal schedule. Due to its key importance, the DAG tasks scheduling problem has been extensively studied in the literature. However, many previously proposed traditional heuristic algorithms are usually based on greedy methods and also lack the consideration of scheduling tasks between trusted and untrusted entities, which makes the problem more complicated, but there still exists a large optimization space to be explored. In this paper, we propose a trust-aware adaptive DAG tasks scheduling algorithm using the reinforcement learning and Monte Carlo Tree Search (MCTS) methods. The scheduling problem is defined using the reinforcement learning model. Efficient scheduling state space, action space and reward function are designed to train the policy gradient-based REINFORCE agent. The MCTS method is proposed to determine actual scheduling policies when DAG tasks are simultaneously executed in trusted and untrusted entities. Leveraging the algorithm’s capability of exploring long term reward, the proposed algorithm could achieve good scheduling policies while guaranteeing trusted tasks scheduled within trusted entities. Experimental results showed the effectiveness of the proposed algorithm compared with the classic HEFT/CPOP algorithms.

Keywords: DAG scheduling; trusted entities; heterogeneous; MCTS (search for similar items in EconPapers)
JEL-codes: O13 Q Q0 Q2 Q3 Q5 Q56 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2071-1050/11/7/1826/pdf (application/pdf)
https://www.mdpi.com/2071-1050/11/7/1826/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jsusta:v:11:y:2019:i:7:p:1826-:d:217419

Access Statistics for this article

Sustainability is currently edited by Ms. Alexandra Wu

More articles in Sustainability from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().