Near-optimal dynamic priority scheduling strategy for instance-intensive business workflows in cloud computing
| Autor: | Yun Yang, Rongbin Xu, Wei Huang, Ying Xie, Yeguo Wang, Dong Yuan |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Rate-monotonic scheduling
Earliest deadline first scheduling Computer Networks and Communications Computer science Heuristic (computer science) Distributed computing Cloud computing 02 engineering and technology Dynamic priority scheduling Fair-share scheduling Theoretical Computer Science Scheduling (computing) Fixed-priority pre-emptive scheduling 0202 electrical engineering electronic engineering information engineering Job shop scheduling business.industry Heuristic 020206 networking & telecommunications Deadline-monotonic scheduling Computer Science Applications Workflow Computational Theory and Mathematics Two-level scheduling 020201 artificial intelligence & image processing business Software |
| Zdroj: | Concurrency and Computation: Practice and Experience. 29:e4167 |
| ISSN: | 1532-0626 |
| DOI: | 10.1002/cpe.4167 |
| Popis: | Summary 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 1 000 000. In particular, the ratio between METtheory 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text