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

作者：Xu, Rongbin; Wang, Yeguo; Huang, Wei; Yuan, Dong; Xie, Ying^*; Yang, Yun

来源：Concurrency and Computation: Practice and Experience (CCPE) , 2017, 29(18): e4167.

DOI：10.1002/cpe.4167

• business workflow
• cloud computing
• dynamic scheduling
• multistep task
• on-time completion
• parallel processes

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 (METtheory) is used as a benchmark for evaluation based on simulation. The results show that the ratios between METtheory and DPS are more than 98.5% by scheduling different orders of magnitude tasks from 1000 to 1000000. In particular, the ratio between METtheory and DPS is nearly 99.9% with 1000000 tasks, which means that our DPS can get the near-optimal result when scheduling large number of tasks.

• 出版日期2017-9-25
• 单位安徽大学