An Improved Budget-Deadline Constrained Workflow Scheduling Algorithm on Heterogeneous Resources

摘要

In recent years, there are many scheduling algorithms for execution of workflow applications using Quality of Service (QoS) parameters. In this paper, we improve a scheduling workflow algorithm considering the time and cost constraints on heterogeneous resources, which is called Budget-Deadline constrained using Sub-Deadline scheduling (BDSD). With the deadline and budget constraints required by the user, we use the BDSD algorithm to find a scheduling which satisfy with the both constraints. We use the planning successful rate (PSR) to show the effectiveness of our algorithm. In the simulation experiment, we use the random workflow applications and real workflow applications to experiment. The simulation results show that compared with other algorithms, our BDSD algorithm has a high PSR and low-time complexity of O(n2m) for n tasks and m processors.