A feasible mathematical algorithm for workflow scheduling

A Directed Acyclic Graph (DAG) is commonly used to model a workflow, where graph nodes represent computational tasks, and edges reflect task dependencies. However, workflow scheduling, which involves assigning suitable virtual machines to workflow tasks based on constraints such as time and cost, is a well-known NP-complete problem. In cite{nad2022}, we proposed GuRMiC as a heuristic algorithm for this problem with a cost objective function based on mathematical concepts while satisfying the predefined deadline. To this end, the workflow paths are scheduled based on a totally ordered set, $(T^{exe}({ P}), preccurlyeq),$ which is formed by considering an algebraic structure for a given workflow, where $T^{exe}({ P})$ is the set of path execution times. In this paper, we prove the feasibility of GuRMiC by demonstrating the possibility of (I) scheduling all workflow paths on the virtual machine selected for the critical path, (II) scheduling all sub-paths after changing the machine selected for a given path to a slower one, and (III) scheduling paths after updating the virtual machines based on the extra times. Hence, GuRMiC provides an efficient solution for workflow scheduling with a cost objective function.