Research On Multi-objective Optimization Of Multiple Concurrent Deadline-constrained Workflows Scheduling

With the increase in large-scale scientific computing problems of many areas,scheduling the scientific workflows on distributed resources to achieve multi-objective optimization is increasingly important.In particular,the current paid use of computing resources has become an inevitable trend.For scheduling workflows on utility-based resources,it is necessary to consider not only the execution time of the workflow,but also the cost of execution,as well as throughput,fairness,and reliability.It is a very important NP-hard problem to achieve multi-objective comprehensive performance optimization.In recent years,it become one of the hotspots to study concurrent scheduling multiple workflows sharing a group of resources,which can make full use of the time slots in tasks and is also used in some practical application requirements.With regard to scheduling multi-workflow,there have been some achievements in improving resource utilization,average completion rate and fairness.There are still many problems that need to be further improved and solved for multiple optimization goals.Based on the analysis of the existing workflow scheduling works,for scheduling multiple workflows sharing a set of heterogeneous resources,research is carried out in calculating the task sub-deadline fairly,maximizing DAG throughput,minimizing waste time slots,optimizing the cost and other issues from balancing multi-objective optimization relationship.It is of great theoretical and practical significance to improve the resource utilization of multi-user workflow applications in distributed resources such as grid,cluster or cloud,and to reduce the cost of users and the cost of resource providers on the basis of meeting the constraint.The main content and innovations of this research are as follows:(1)Aiming at the scheduling of a single DAG on a fixed set of resources,RHEFT method is proposed based on reverse scheduling.After obtaining the earliest start time and the earliest finish time of the reverse task,the sub-deadline and the latest start time of each task are calculated easily.This process is not only concerned with the length of part critical path,but also the effect of DAG parallelism.Each task mapping can still ensure that the remaining tasks have sufficient time for mapping to the resource in sub-deadline constraints.(2)A throughput maximization algorithm with low complexity is proposed to scheduling multiple DAGs with deadline-constrain sharing finite resources.First,based on the latest start time of each task gotten by RHEFT,the new metic of the relative leniency measured is calculated for the highest priority task from each DAG.By comparison,the most urgent task is chosen and mapped to the resource time slot with the earliest finish time.The supersaturation is determined quickly according to the sub-deadline during the mapping process.Some DAG is discarded reasonably and need expansion of additional resources.The experimental results show that the algorithm has better performances in multi-DAG throughput,wasted time slots and fairness than other three strategies,and lower time complexity in similar performance.(3)Aiming at the problem of scheduling multiple deadline-constrain DAGs sharing finite resources,a scheduling strategy of waste time slot minimization is proposed by the elastic slot backfill.Multi-DAGs acquire scheduling order by comparing time slot ratios or duration urgency.Each task is mapped to the resource according to the earliest finish time priority strategy.If the earlier time slot is too small,the backfill will be achieved by slot extension.It can make full use of the earliest time slots that do not meet the mapping task requirements in the existing algorithm.At the same time,when selected resources are lack,some DAG is also discarded to achieve maximization scheduling DAG success rate.Experiments show that the task elastic slot backfilled algorithm can cause waste time slots minimization.It has the characteristics of time slots shift backward,and is especially suitable for the situation of co-scheduling dynamic multi-DAGs.(4)Aiming at the problem of scheduling multiple deadline-constrain DAGs sharing finite resources,MRHEFT method is proposed for fair sub-deadline by improving RHEFT.It gives the different start time for each reverse DAG based on deadline.The DAG with the maximum deadline is first mapped reversely.When the next deadline is reached,the other DAG joins for reverse scheduling.By comparing the reverse weights,the task is fairly chosen and mapped.After the earliest start time and the earliest finish time is gotten,calculate sub-deadline and the latest start time.According to whether the latest start time is negative,identify whether multi-DAGs can be concurrent scheduled meeting the deadline.(5)Aiming at the problem of scheduling multiple DAGs with deadline constrain sharing finite resources,a cost-optimal strategy is proposed based on relative relaxation.First,obtain the latest start time of each task with MRHEFT scheduling method and determine whether there is DAG supersaturation problem quickly.If the DAGs are supersaturated,they are selectively abandoned to ensure that all remaining DAG can be completed within the deadline.And then the urgent task is chosen from the first one in each DAG according to the loose degree.It is mapped to the cheapest appropriate resources meeting the sub-deadline constraints.Until all tasks are mapped to achieve the optimal scheduling costs.