World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

On Optimal Scheduling Algorithms for Well-Structured Workflows in the Cloud with Budget and Deadline Constraints

    In this paper, we consider optimal scheduling algorithms for scientific workows with two typical structures, fork&join and tree, on a set of provisioned (virtual) machines under budget and deadline constraints in cloud computing. First, given a total budget B, by leveraging a bi-step dynamic programming technique, we propose optimal algorithms in pseudo-polynomial time for both workows with minimum scheduling length as a goal. Our algorithms are efficient if the total budget B is polynomially bounded by the number of jobs in respective workows, which is usually the common case in practice. Second, we consider the dual of this optimization problem to minimize the cost when the deadline of the computation D is fixed. We change this problem into the standard multiple-choice knapsack problem via a parallel transformation.

    Communicated by K. Qiu