Dynamic Multi-DAG Schedule Based On Attachment Composition Priority

DAG schedule problem is that,there are nodes connecting with each other by some data transaction,the nodes can form a directed acyclic graph to schedule, we should give a strategy to execute the nodes as fast as possible considering the data dependence between every two nodes.Dynamic multi-DAG schedule problem is that,there are n DAGs coming at different time,we want to give a strategy to schedule all of the nodes belonging to the DAGs,in order to make the average makespan of all the DAGs as fast as possible.lt is belongs to the NP-hard problems,so we should give an approximate algoorithm to solve it.Plaiiner-guided algorithm is an algorithm to solve the multi-DAG schedule problem,but the algorithm has its old disadvantagees, such as the lack of fairness among a single DAG and the possibility to delay the children nodes.In this paper,we studied the dynamic mxilti-DAGs schedule problem and proposed an improved algorithm on priority based on the framework of planner-guided algorithm.When a new DAG arrives, we attach the remnant tasks onto the new coming DAG by using the maximum EFT value of the remnant tasks and the EST values of the new tasks.The key point to the problem is the strategy to calculate the priorities of the tasks. Then when we distribute the node onto a machine,we use tiie strategy that we calculate the effect on it,s child nodes. Compared witii tiie planner-guided algorithm, we can get lower makespans and higher utilization ratios of the resources.