Near-optimal dynamic priority scheduling strategy for instance-intensive business workflows in cloud computing

Utilization of cloud computing resources has made a fast growth in e-business. Business and government agencies often need to handle large volume of service requests, the so-called instance-intensive business processes in a constrained period. On-time completion for instance-intensive business processes within the constrained time is a very important issue. In the past few years, traditional optimal task scheduling has been well researched and proven to be a nondeterministic polynomial (NP) time–complete problem. So many heuristic and metaheuristic algorithms are put forward to solve the issue with near-optimal solutions. However, most of them just treat a single workflow instance as a multistep task without considering that steps within a task can be different types of activities. To explain multistep features of business workflows, a typical motivating instance-intensive business example of security exchange and a multistep scheduling model for business workflows are introduced in this paper. Then our near-optimal dynamic priority scheduling (DPS) strategy is proposed on the basis of the idea of Min-Min heuristic algorithm and greedy philosophy. Compared to the first come first served and constrained Min-Min by makespan and standard deviation, DPS can make a more optimized choice in each round of scheduling towards overall outcome. To show the effectiveness of DPS, theoretical minimum execution time (MET_theory) is used as a benchmark for evaluation based on simulation. The results show that the ratios between MET_theory and DPS are more than 98.5% by scheduling different orders of magnitude tasks from 1000 to 1 000 000. In particular, the ratio between MET_theory and DPS is nearly 99.9% with 1 000 000 tasks, which means that our DPS can get the near-optimal result when scheduling large number of tasks.