PCP-B2: Partial critical path budget balanced scheduling algorithms for scientific workflow applications

• We model the service-oriented computing system and define budget constrained workflow scheduling problem.
• We proposed a heuristic budget constrained workflow scheduling algorithm of time complexity O(log|RT||T|3)O(log|RT||T|3).
• We make comprehensively comparison with 5 state-of-the-art algorithms using 5 well-known scientific workflow applications.
• Our proposed algorithm performs better than the other algorithms on average. The advantages of related algorithms are also analyzed.

Service-oriented computing becomes an attractive environment for executing scientific workflow applications. It enables these applications to use resources in a pay-as-you-go model. However, it also challenges traditional best-effort workflow scheduling strategies, that only focus on minimizing schedule length. One of the most challenging problem is to optimize workflow execution time under QoS constraint of budget. To solve this problem, we propose a heuristic algorithm of PCP-B22. A PCP-wise budget distribution mechanism is proposed to balance budget among partial critical paths according to their sequential or parallel structure nature. The budget distribution mechanism is implemented using binary search method. Moreover, a partially rescheduling mechanism is designed to further tune budget distribution. Simulation experiments using five well-known scientific workflow applications show that PCP-B22 algorithm is efficient in scheduling pipeline structured workflows, and performs better than other budget constrained scheduling algorithms on average. The time complexity of PCP-B22 is O(log|RT||T|3)O(log|RT||T|3), where |RT||RT| denotes the number of resource type, and |T||T| denotes the total number of workflow task. This time complexity ensures that the proposed algorithm is able to schedule large scale workflows quickly.