Multi-level parallel scheduling of dependent-tasks using graph-partitioning and hybrid approaches over edge-cloud

• Published in: Soft Computing
• Main Author: Kaur M.; Kadam S.; Hannoon N.
• Format: Article
• Language: English
• Published: Springer Science and Business Media Deutschland GmbH 2022
• Online Access: https://www.scopus.com/inward/record.uri?eid=2-s2.0-85127804420&doi=10.1007%2fs00500-022-07048-1&partnerID=40&md5=b98fb5897c01b8d735112fab96e02625

An efficient scheduling of dependent-tasks over edge-cloud is the key for achieving better utilization of computational resources and timely completion of interdependent tasks for scientific as well as defence-oriented applications. Many applications comprise several tasks that are dependent in nature and are required to be executed in a specific sequence within a minimum span of time. To handle the execution of such dependent-tasks on distributed computational resources is a challenging problem; as the number of tasks increase, the solution space comprising different task-resource mapping sequences also increase exponentially and it is very difficult to find the near optimal solutions in the search space. In this paper, we focus on two strategies for obtaining optimal solutions for scheduling the multiple dependent-tasks with the specified sequence in a parallel and distributed environment. In the first approach, a hybrid mechanism is proposed to efficiently search the scheduling solution space for multiple dependent tasks. The idea is to first find a schedule by heuristic algorithms and use these as initial solutions in the search space to obtain better solutions using unsupervised machine learning methods. In the second approach, each task-graph is partitioned into different clusters of sub-tasks, where each partitioned cluster is mapped onto the same resource. This strategy reduces the idle times on the resources, wherever possible, in comparison with the first approach. The innovative part of the proposed approaches is to schedule the multiple dependent-tasks in a parallel fashion rather than scheduling in sequential manner. The results show that the schedules obtained by our proposed approaches minimize the total execution time (TET) significantly as compared to other approaches considered in our research study. © 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.