A Study of DAG Scheduling Algorithms for Distributed Systems

Workflow represents a directed acyclic graph (DAG) of computing tasks which are related to each other by data dependencies. Such applications commonly occur during automation of complex calculations and data processing. The problem of workflow scheduling is to construct an optimal schedule for processing tasks on a given system configuration. Optimal schedule is generally understood as either the cheapest or the fastest schedule possible. Such a problem is well-studied for systems consisting of a limited number of computing nodes. Cloud environments allow flexible configuration management by attaching/detaching new physical nodes and creating virtual containers. This advantage provides new degrees of freedom while optimizing workflow planning in such an environment. The goal of this work is to develop a scheduling algorithm. In related work existing approaches to solve this problem are examined and a new approach is proposed. Keywords: cloud computing, schedule creation, distributed systems, workflows, heuristic algorithms.