  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 Markovian chain
stationary probabilities as a measure of 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, which splits the spare budget uniformly across all the
jobs. We test our algorithms on a variety of workflows, including FFT, 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 the-state-of-art algorithms. The empirical
results show that the uniform spare budget splitting scheme outperforms the
splitting scheme in proportion to extra demand in average for most cases, and
the Markovian based prioritization further improves the workflow makespan.
