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

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-B-2. 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-B2 algorithm is efficient in scheduling pipeline structured workflows, and performs better than other budget constrained scheduling algorithms on average. The time complexity of PCP-B-2 is Omicron(log vertical bar RT vertical bar vertical bar T vertical bar(3)), where vertical bar RT vertical bar denotes the number of resource type, and vertical bar T vertical bar denotes the total number of workflow task. This time complexity ensures that the proposed algorithm is able to schedule large scale workflows quickly. (C) 2016 Elsevier B.V. All rights reserved.