Title | ||
---|---|---|
Near-optimal dynamic priority scheduling strategy for instance-intensive business workflows in cloud computing. |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1002/cpe.4167 | CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE |
Keywords | Field | DocType |
business workflow,cloud computing,dynamic scheduling,multistep task,on-time completion,parallel processes | Fixed-priority pre-emptive scheduling,Job shop scheduling,Fair-share scheduling,Computer science,Parallel computing,Deadline-monotonic scheduling,Two-level scheduling,Rate-monotonic scheduling,Earliest deadline first scheduling,Dynamic priority scheduling,Distributed computing | Journal |
Volume | Issue | ISSN |
29 | 18 | 1532-0626 |
Citations | PageRank | References |
5 | 0.43 | 17 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Rongbin Xu | 1 | 37 | 10.01 |
Yeguo Wang | 2 | 5 | 0.43 |
Wei Huang | 3 | 5 | 0.43 |
Dong Yuan | 4 | 33 | 6.68 |
Ying Xie | 5 | 47 | 14.48 |
Yun Yang | 6 | 2103 | 150.49 |