Real-time DAG scheduling method based on deadline of tasks

被引：0

作者：

Xu R. ^{[1
,2
]}

Liu X. ^{[1
]}

Yang Z. ^{[1
]}

Guo X. ^{[1
,2
]}

Xie Y. ^{[3
]}

Wu J. ^{[1
]}

机构：

[1] School of Computer Science and Technology, Anhui University, Hefei

[2] Co-Innovation Center for Information Supply & Assurance Technology, Anhui University, Hefei

[3] Computer Studies Department, Anhui University, Hefei

来源：

Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS | 2016年 / 22卷 / 02期

基金：

中国国家自然科学基金;

关键词：

Directed acyclic graph; Execution deadline; Parallel scheduling; Real-time scheduling; Stretch scheduling; Valid main path;

D O I：

10.13196/j.cims.2016.02.018

中图分类号：

学科分类号：

摘要：

To map tasks into multiple resources for improving the execution efficiency, and to manage a business process effectively, a novel Directed Acyclic Graph (DAG) model was given based on the traditional DAG model, which divided the tasks into serial and parallel scheduling parts. A valid main path for task scheduling was extracted to make the task be expanded into parallel mode based on the novel DAG model. Based on completion time and deadline of the task, a stretch scheduling strategy was put forward to meet the deadline of tasks and reduce the occupation of resources, which made other tasks could be scheduled effectively. A simulation example was provided to prove the excellent feasibility of the proposed method. © 2016, CIMS. All right reserved.

引用

页码：455 / 464

页数：9

共 19 条

[1]

Liu X., Wang D., Yuan D., Et al., Throughput based temporal verification for monitoring large batch of parallel processes, Proceedings of the 2014 International Conference on Software and System Process, (2014)

[2]

Hande P.V., Ghosh D., A comparative study on factors shaping buying behaviour on B2B and B2C E-commerce platforms in India, EXCEL International Journal of Multidisciplinary Management Studies, 5, 3, pp. 1-10, (2015)

[3]

Liu X., Yuan D., Zhang G., Et al., Workflow systems in the cloud, The Design of Cloud Workflow Systems, pp. 1-11, (2012)

[4]

van Den B.J., Belien J., de Bruecker P., Et al., Personnel scheduling: A literature review, European Journal of Operational Research, 226, 3, pp. 367-385, (2013)

[5]

Liu K., Jin H., Chen J., Et al., A compromised-time-cost scheduling algorithm in SwinDeW-C for instance-intensive cost-constrained workflows on cloud computing platform, International Journal of High Performance Computing Applications, 24, 4, pp. 445-456, (2010)

[6]

Kong Y., Zhang M., Ye D., A negotiation-based method for task allocation with time constraints in open grid environments, Concurrency and Computation: Practice and Experience, 27, 3, pp. 735-761, (2015)

[7]

Vasilecas O., Savickas T., Lebedys E., Directed acyclic graph extraction from event logs, Information and Software Technology, pp. 172-181, (2014)

[8]

Fernandez-Baca D., Allocating modules to processors in a distributed system, IEEE Transactions on Software Engineering, 15, 11, pp. 1427-1436, (1989)

[9]

Bokhari S.H., A shortest tree algorithm for optimal assignments across space and time in a distributed processor system, IEEE Transactions on Software Engineering, 7, 6, pp. 583-589, (1981)

[10]

Chen H., Wang R., A grid DAG scheduling algorithm for cost-time optimization, Chinese Journal of Electronics, 33, 8, pp. 1375-1380, (2005)

← 1 2 →