Workflow Scheduling in the Cloud With Weighted Upward-Rank Priority Scheme Using Random Walk and Uniform Spare Budget Splitting
We study a difficult problem of how to schedule complex workflows with precedence constraints under a limited budget in the cloud environment. We first formulate the scheduling problem as an integer programming problem, which can be optimized and used as the baseline of performance. We then consider...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8695176/ |
| _version_ | 1819179480719032320 |
|---|---|
| author | Hang Zhang Xiaoying Zheng Ye Xia Mingqi Li |
| author_facet | Hang Zhang Xiaoying Zheng Ye Xia Mingqi Li |
| author_sort | Hang Zhang |
| collection | DOAJ |
| description | We study a difficult problem of how to schedule complex workflows with precedence constraints under a limited budget in the cloud environment. We first formulate the scheduling problem as an integer programming problem, which can be optimized and used as the baseline of performance. We then consider the traditional approach of scheduling jobs in a prioritized order based on the upward-rank of each job. For those jobs with no precedence constraints among themselves, the plain upward-rank priority scheme assigns priorities in an arbitrary way. We propose a job prioritization scheme that uses the Markovian chain stationary probabilities as a measure of the importance of jobs. The scheme keeps the precedence order for the jobs that have precedence constraints between each other and assigns priorities according to the jobs' importance for the jobs without precedence constraints. We finally design a uniform spare budget-splitting strategy that splits the spare budget uniformly across all the jobs. We test our algorithms on a variety of workflows, including the Fast Fourier transform (FFT), the Gaussian elimination, typical scientific workflows, randomly generated workflows, and workflows from an in-production cluster of an online streaming service company. We compare our algorithms with state-of-the-art algorithms. The empirical results show that the uniform spare budget splitting scheme outperforms the splitting scheme in proportion to extra demand on average for most cases, and the Markovian-based prioritization further improves the workflow makespan. |
| first_indexed | 2024-12-22T21:59:07Z |
| format | Article |
| id | doaj.art-a81aa2ce432749c2aa611e66b709f90c |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-22T21:59:07Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-a81aa2ce432749c2aa611e66b709f90c2022-12-21T18:11:10ZengIEEEIEEE Access2169-35362019-01-017603596037510.1109/ACCESS.2019.29126528695176Workflow Scheduling in the Cloud With Weighted Upward-Rank Priority Scheme Using Random Walk and Uniform Spare Budget SplittingHang Zhang0https://orcid.org/0000-0002-8270-0179Xiaoying Zheng1Ye Xia2Mingqi Li3School of Computer Engineering and Science, Shanghai University, Shanghai, ChinaChinese Academy of Sciences, Shanghai Advanced Research Institute, Shanghai, ChinaDepartment of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, USAChinese Academy of Sciences, Shanghai Advanced Research Institute, Shanghai, ChinaWe study a difficult problem of how to schedule complex workflows with precedence constraints under a limited budget in the cloud environment. We first formulate the scheduling problem as an integer programming problem, which can be optimized and used as the baseline of performance. We then consider the traditional approach of scheduling jobs in a prioritized order based on the upward-rank of each job. For those jobs with no precedence constraints among themselves, the plain upward-rank priority scheme assigns priorities in an arbitrary way. We propose a job prioritization scheme that uses the Markovian chain stationary probabilities as a measure of the importance of jobs. The scheme keeps the precedence order for the jobs that have precedence constraints between each other and assigns priorities according to the jobs' importance for the jobs without precedence constraints. We finally design a uniform spare budget-splitting strategy that splits the spare budget uniformly across all the jobs. We test our algorithms on a variety of workflows, including the Fast Fourier transform (FFT), the Gaussian elimination, typical scientific workflows, randomly generated workflows, and workflows from an in-production cluster of an online streaming service company. We compare our algorithms with state-of-the-art algorithms. The empirical results show that the uniform spare budget splitting scheme outperforms the splitting scheme in proportion to extra demand on average for most cases, and the Markovian-based prioritization further improves the workflow makespan.https://ieeexplore.ieee.org/document/8695176/Workflow schedulingheterogeneous cloudsbudget constraintsprecedence constraintsschedule length |
| spellingShingle | Hang Zhang Xiaoying Zheng Ye Xia Mingqi Li Workflow Scheduling in the Cloud With Weighted Upward-Rank Priority Scheme Using Random Walk and Uniform Spare Budget Splitting IEEE Access Workflow scheduling heterogeneous clouds budget constraints precedence constraints schedule length |
| title | Workflow Scheduling in the Cloud With Weighted Upward-Rank Priority Scheme Using Random Walk and Uniform Spare Budget Splitting |
| title_full | Workflow Scheduling in the Cloud With Weighted Upward-Rank Priority Scheme Using Random Walk and Uniform Spare Budget Splitting |
| title_fullStr | Workflow Scheduling in the Cloud With Weighted Upward-Rank Priority Scheme Using Random Walk and Uniform Spare Budget Splitting |
| title_full_unstemmed | Workflow Scheduling in the Cloud With Weighted Upward-Rank Priority Scheme Using Random Walk and Uniform Spare Budget Splitting |
| title_short | Workflow Scheduling in the Cloud With Weighted Upward-Rank Priority Scheme Using Random Walk and Uniform Spare Budget Splitting |
| title_sort | workflow scheduling in the cloud with weighted upward rank priority scheme using random walk and uniform spare budget splitting |
| topic | Workflow scheduling heterogeneous clouds budget constraints precedence constraints schedule length |
| url | https://ieeexplore.ieee.org/document/8695176/ |
| work_keys_str_mv | AT hangzhang workflowschedulinginthecloudwithweightedupwardrankpriorityschemeusingrandomwalkanduniformsparebudgetsplitting AT xiaoyingzheng workflowschedulinginthecloudwithweightedupwardrankpriorityschemeusingrandomwalkanduniformsparebudgetsplitting AT yexia workflowschedulinginthecloudwithweightedupwardrankpriorityschemeusingrandomwalkanduniformsparebudgetsplitting AT mingqili workflowschedulinginthecloudwithweightedupwardrankpriorityschemeusingrandomwalkanduniformsparebudgetsplitting |