Hybrid Scheduling Deadline-Constrained Multi-DAGs Based on Reverse HEFT

Scheduling complex DAG (Directed Acyclic Graph) scientific workflow in the distributed heterogeneous system has attracted widespread attention. Recent researches about multiple DAG workflows in heterogeneous system have been making progress and have solved some problems, but fail to address and to solve some important problems of scheduling Deadline-Constrained multi-DAGs sharing a bounded number of machines in a heterogeneous system. In this work, we propose a reverse HEFT (Heterogeneous Earliest Finish Time) scheduling policy, which can quickly get the latest start time and sub-deadline for each task. Based on the latest start time of in highest priority tasks in each DAG, we define a new relative laxity degree metrics for them. By comparing these tasks' metrics, the current task to be scheduled is chosen and then mapped to the time slot with the earliest finish time in all resources. If the resources are not enough, oversaturation can be rapidly determined in accordance with sub-deadline, and some DAGs is reasonably discarded and other resources is chosen. This multi-DAGs scheduling policy select a relative urgency scheduling task only by a simple calculation without the remaining tasks pre-scheduling in each DAG scheduling. The experimental results show that it has a better performance than other three policies on throughput capacity, waste time slot ratio and fairness, and time complexity is much lower.