Cloud workflow scheduling with hybrid resource provisioning

Abstract

Resource provisioning strategies are crucial for workflow scheduling problems which are widespread in cloud computing. The main challenge lies in determining the amounts of reserved and on-demand resources to meet users’ requirements. In this paper, we consider the cloud workflow scheduling problem with hybrid resource provisioning to minimize the total renting cost, which is NP-hard and has not been studied yet. An iterative population-based meta-heuristic is developed. According to the shift vectors obtained during the search procedure, timetables are computed quickly. The appropriate amounts of reserved and on-demand resources are determined by an incremental optimization method. The utilization of each resource is balanced in a swaying way, in terms of which the probabilistic matrix is updated for the next iteration. The proposed algorithm is compared with modified existing algorithms for similar problems. Experimental results demonstrate effectiveness and efficiency of the proposed algorithm.

1 Introduction

Cloud computing is a new resources provision model in which resources more flexible than in distributed computing and grid computing. Users can access resources anywhere and anytime. Providers manage large amounts of resources (server, network, storage, platform, software, etc.). Users rent resources from providers when they require such services. Users’ requests are commonly represented by workflows, which could describe a wide range of complex applications in distributed systems [13]. Generally workflow applications are supervised and executed in distributed or cloud systems, such as Pegasus [12], Askalon [33], Google MapReduce [10] and Amazon EC2 [20].

In cloud computing, the IaaS (infrastructure as a service) center usually provides three resource renting manners to the users: reserved, on-demand and spot [3]. The reserved manner is a long-term strategy which enables users to make a low, one-time payment for each demanded resource. Once the resource is reserved, it is owned during the entire period, i.e., the resource is not returned to the IaaS center until the due date. Users receive a significant discount for the resource renting, and the average cost could be reduced greatly. However, the rented resources are not fully used during the renting period which leads to poor resource utilization. On the contrary, the on-demand manner enables users to pay for computing capacity by hours without long-term commitments. The pay-on-demand leads to higher resource utilization. On-demand is the mostly adopted manner for workflow scheduling problems in cloud computing [2, 6, 9]. The spot manner enables users to bid for free resource capacity, e.g., the Amazon EC2 spot manner. Users bid for unused capacity. Instances are charged using the spot price, which is set by the provider and fluctuates periodically in terms of the supply and demand for resource capacity. Users’ requests are met if the bid price is higher than the spot price. Instances are kept by the current user until new users come and make the spot price higher than the current bid price.

In this paper, we consider the workflow scheduling problems in cloud computing. Tasks are assumed to be non-preemptive and have long processing times, e.g., academic workflows. A non-preemptive task cannot be terminated until the execution of the task is finished. Tasks are constrained by complex precedence, and tasks are executed in parallel or sequentially. Therefore, the resource requirements are variable. The combination of the three provisioning manners can meet the variable requirements. The reserved manner decreases the cost greatly by the discount while the idle time intervals will be resulted. The on-demand manner saves cost by providing short-term resources for peak demands, whereas no discount is received. The spot manner [29] has the risk of failure (or out-of-bid) which is not allowed in the considered workflows. Therefore, we consider rent resources for variable requirements with both reserved and on-demand manners in this paper. To the best of our knowledge, there are only few papers about resource renting with both reserved and on-demand manners for the problem under study. Since the Resource Availability Cost Problem (RACP) adopting only the reserved manner, which is a special case of the considered problem, is NP-hard [23], it is not hard to prove that the considered problem is NP-hard. To determine the appropriate amounts of reserved and on-demand resources to meet variable requirements for the total renting cost minimization, we establish the integer programming model for the considered problem. Based on the Estimation of Distribution Algorithm (EDA) [24], which is commonly used population-based meta-heuristic for combinatorial optimization, an Adaptive Probabilistic Algorithm (APA) is developed.

The rest of the paper is organized as follows. Related works are described in Sect. 2. Section 3 establishes the mathematical model for workflow scheduling with hybrid resource provisioning. In Sect. 4, the proposed APA is described. Computational results are shown in Sect. 5, followed by conclusions in Sect. 6.

2 Related works

Scheduling workflow applications have been studied for many years. Workflow scheduling can be described as mapping tasks to suitable resources to satisfy some performance criterion. In the traditional distributed computing environments (e.g., utility Grids), resources are usually clusters geographically dispersed and encapsulated as services. Several services are candidates for each task of the workflow. Services are used exclusively, i.e., they are not shared by different tasks. There are two common objectives: cost optimization under deadline constraints or execution time optimization under budget constraints [35]. Common methods for time optimization include dynamic programming [16], branch and bound [17], decomposition-based methods [19], list scheduling algorithm [30], critical path-based allocation [25], greedy randomized adaptive search [4] and ant colony optimization approach [11]. The methods for cost optimization include the Deadline-MDP algorithm [36], Deadline Early Tree (DET) algorithm [37], Partial Critical Paths (PCP) algorithm [1] and the Critical Path-based Iterative (CPI) heuristic [8].

However, only a few papers have focused on scheduling workflow applications in cloud computing, in which resources (virtual machines) are usually geographically concentrated. Byun et al. [5] proposed a Balanced Time Scheduling (BTS) algorithm for allocating homogeneous resources to a workflow within a user-specified finish time. The on-demand manner is usually adopted in existing literature with the short-term resources provisioning for workflow applications. In the follow-up work of Byun et al. [6], a Partitioned Balanced Time Scheduling (PBTS) algorithm was proposed for scheduling the on-demand homogeneous resources to the workflow application. PBTS considers time partitions in the algorithm and minimizes the amount of resources for each time partition. Abrishami et al. [1] proposed a QoS-based Partial Critical Paths (PCP) workflow scheduling algorithm on utility grids, and the PCP algorithm was modified for the on-demand cases [2] in cloud computing. The two proposed algorithms in [2], IC-PCP and IC-PCPD2, are different from PCP in three aspects: on-demand resource provisioning, homogeneous networks and the pay-as-you-go pricing model. Cai et al. [7] considered the workflow scheduling problem with heterogeneous resources and on-demand resource provisioning. The problem was divided into two subproblems: service mapping and task tabling on sharable resources. Two heuristics Critical Path-based Iterative heuristic with Shortest services (CPIS) and List-based Heuristic considering Cost minimization and Mach degree maximization (LHCM) were developed for the subproblems, respectively. The on-demand manner is usually adopted for workflow applications in the existing literature.

Few papers concerned long-term resources provisioning in cloud computing which provide resources in the reserved manner. Workflow scheduling with reserved resources is similar to the Resource Availability Cost Problem (RACP) [14], a traditional project scheduling problem with scare time and unlimited amount of resources. RACP is an extension to the Resource-Constrained Project Scheduling Problem. The schedule of RACP determines the start time of each precedence-constrained task in the project to minimize the maximum resource amount during the whole project period. Common methods for RACP are exact algorithms [14, 23, 27] and meta-heuristics (e.g., Scatter Search [34], genetic algorithm [28] and path relinking [26]). RACP only considers resources provisioning with the reserved manner.

There are several studies on both the reserved and on-demand resource provisioning manners. From the cloud provider’s viewpoint, Mazzucco et al. [22] attempted to maximize the net revenue of the cloud provider. Two resource provisioning manners were offered to different users: premium users with reserved instances and basic users with on-demand instances. The number of different instance types was determined by a queuing model. Chaisiri et al. [9] proposed an optimal cloud resource provisioning algorithm to get a balanced manner between the reserved and the on-demand. A stochastic programming model was formulated. The demand distribution of resources at each decision stage was supposed to be known in advance. Polynomial heuristics were proposed by Khatua et al. [22] for the hybrid resource provisioning problem. Van den Bossche et al. [32] presented a purchase management algorithm for the procurement decision on reserved contracts in the contexts of providers. However, these studies focused on independent task scheduling actually. These studies focused on independent task scheduling or virtual machine placement. To the best of our knowledge, no existing work exists on hybrid resource provisioning for workflow scheduling in which tasks are constrained by precedence.

3 Problem description

In this paper, we consider the workflow scheduling problems in cloud computing with long processing time and non-preemptive tasks. Tasks are fulfilled in parallel on multiple virtual machines, i.e., each task can be executed concurrently on several virtual machines. Resources are also shared by different tasks, i.e., a resource can be used by another task if the current task finishes during its resource renting period. Different types of resources (e.g., general-purpose, compute-optimized, GPU Instances, or memory-optimized virtual machine instances) are required by the tasks. Resources are provisioned with both reserved and on-demand manners.

A workflow application is usually denoted by an acyclic task-on-node network $G=(V,E)$. There are n nodes in $V=\{v_{1},\ldots ,v_{n}\}$. Each node $v_{j} \in V$ represents a task in the workflow, in which $v_{1}$ and $v_{n}$ are the dummy source and sink tasks. Each edge $(v_{i},v_{j}) \in E$ represents the precedence between task $v_{i}$ and $v_{j}$. Heterogeneous virtual machines $R=\{R_{1},\ldots ,R_{m}\}$ are provided by the IaaS center and rent by consumers. Tasks are regarded as malleable tasks which can be executed on several machines in parallel. We suppose that the task $v_{j}$ requires $r_{jk}$ units of virtual machine $R_{k}$, and the processing time of $v_{j}$ with these resources are $d_{j}$. All the processing time $d_{j}$ (in hours) are supposed to be integer since virtual machines are charged by hour in this paper. There are two resources renting manners for users. Let the unit cost of virtual machine $R_{k}$ ($k=1,\ldots , m$) with the on-demand manner be $c_{k}$. Let the discount of virtual machines with the reserved manner be $\varphi$. The unit cost of $R_{k}$ with the reserved manner is $c_{k}\times \varphi$. Let the deadline of the workflow be D. The objective is to determine the minimum amount of reserved and on-demand virtual machines for the workflow with the deadline satisfied.

Fig. 1

An example of the considered problem

Fig. 2

An example and the schedule of the considered problem

An example of the workflow application with 7 tasks and 1 type of resource is shown in Fig. 1. Nodes 1 and 7 are dummy tasks. The deadline of the workflow application is supposed to be 10 days. Let the unit cost of the on-demand resource be 5 and the discount of the reserved resource be 0.8. The required units of resource and the corresponding processing time are shown on the right of each task. Task 2 requires 3 units of resource with the processing time 2 days. Figure 2 shows a schedule for the workflow application, in which r is the number of virtual machines, D is the deadline of the workflow and t is the time (with the unit 1 day).

If all the 4 virtual machines are reserved, the total renting cost is $C=4\times 10\times 0.8\times 5=160$. If all the 4 virtual machines are on-demand, the total renting cost is $C=(4+4+4+3+2+2+2+2+3+3)\times 5=145$. If only virtual machines 2 and 3 are reserved, the other virtual machines are rented with the on-demand manner, the required on-demand resources are 2, 2, 2, 1, 0, 0, 0, 0, 1, 1 for each start time, respectively. The resource renting cost $C=2\,\times \,10\,\times \,0.8\,\times \,5\,+\,(2\,+\,2\,+\,2\,+\,1\,+\,1\,+\,1)\times \,5=125$. The hybrid resource provisioning manner saves the cost as compared to the only on-demand or reserved cases.

To determine the amount of resources for the workflow, the most important thing is to obtain the timetable $S=\{s_{1},\ldots ,s_{n}\}$ for the tasks, in which $s_{j}$ is the actual start time of task $v_{j}$. Related parameters of $v_{j}$ are shown in Table 1. Let the actual finish time of task $v_{j}$ be $f_{j}$, i.e., $f_{j}=s_{j}+d_{j}$. Let $est_{j}$ and $lst_{j}$ be the earliest and latest start times of task $v_{j}$. $\mathcal {P}_{j}$ and $\mathcal {O}_{j}$ denote the immediate predecessor and immediate successor sets of $v_{j}$, i.e., $\mathcal {P}_{j}=\{v_{i}|(v_{i},v_{j})\in E)\}$, $\mathcal {O}_{j}=\{v_{k}|(v_{j},v_{k})\in E)\}$. By the critical path-based Forward and Backward Pass Calculations [15], parameters $est_{j}$, $lst_{j}$ along with $\mathcal {P}_{j}$ and $\mathcal {O}_{j}$ of $v_{j}~(v_{j}\in V)$ can be obtained in O(|E|). The available earliest start time (i.e., the earliest start time of an unscheduled task, given the start times of the scheduled activities) of task $v_{j}$ is defined as $aest_{j}=\max _{v_{i}\in \mathcal {P}_{j}}\{f_{i}\}$. The available latest start time of task $v_{j}$ is defined as $alst_{j}=\min _{v_{k}\in \mathcal {O}_{j}}\{s_{k}-d_{j}\}$. The shift $h_{j}$ of task $v_{j} (j=1,\ldots ,n)$ represents the difference between $s_{j}$ and $aest_{j}$, i.e., $h_{j}=s_{j}-aest_{j}$. Similarly, the compensate shift $\bar{h}_{j}$ is $\bar{h}_{j}=alst_{j}-s_{j}$. Let the slack time $\ell _{j}$ of $v_{j}$ be $\ell _{j}=lst_{j}-est_{j}$. The available slack time $\hat{\ell _{j}}$ is defined as $\hat{\ell _{j}}=lst_{j}-aest_{j}$. Therefore, $0\le h_{j}\le \hat{\ell _{j}}\le \ell _{j}$. Relationships of the temporal parameters of $v_{j}$ are illustrated in Fig. 3.

Table 1 Related parameters of $v_{j}$

Fig. 3

Temporal parameters of $v_{j}$

Taking the task $v_{5}$ in Fig. 1 for example, the execution time $d_{5}$ is 5. Before allocating any tasks, the earliest and latest start time of $v_{5}$ are obtained with $est_{5}=3$ and $lst_{5}=5$. According to the schedule in Fig. 2, $s_{5}=3$ and $f_{5}=8$. The available earliest and latest start times can be calculated by $aest_{5}=\max _{v_{i}\in \mathcal {P}_{5}}\{f_{i}\}=f_{2}=2$ and $alst_{5}=\min _{v_{k}\in \mathcal {O}_{5}}\{s_{k}-d_{5}\}=s_{7}-5=5$. According to these parameters, we obtain $h_{5}=s_{5}-aest_{5}=3-2=1$, $\bar{h}_{5}=alst_{5}-s_{5}=5-3=2$, $\ell _{5}=lst_{5}-est_{5}=5-2=3$ and $\hat{\ell _{5}}=lst_{5}-aest_{5}=5-3=2$, respectively.

Let $\pi$ be a schedule of the considered problem. $A_{k}$ is the amounts of $R_{k}$ allocated to the workflow application with the reserved manner. $A_{kt}^{\prime }$ is the amounts of $R_{k}$ allocated to the workflow application with the on-demand manner at time t. The total resource renting cost is calculated by $C(\pi )=\sum _{k=1}^{m}( f_{n}\times A_{k}\times c_{k}\times \varphi +\sum _{t=0}^{f_{n}}{A_{kt}^{\prime }\times c_{k}})$, in which $f_{n}$ is the finish time of the dummy sink task. $x_{jt}$ is a binary variable, which is 1 only if task $v_{j}$ ($j\in \{1,\ldots ,n\}$) starts at time t ($t\in \{0,\ldots ,T\}$). Using the integer programming, workflow scheduling with hybrid resource provisioning is modeled as follows:

$$\begin{aligned} \min \sum _{k=1}^{m}\left( f_{n}\times A_{k}\times c_{k}\times \varphi +\sum _{t=0}^{f_{n}}{A_{kt}^{\prime }\times c_{k}}\right) \end{aligned}$$

(1)

s.t.

$$\begin{aligned}&x_{jt}\in \{0,1\}, ~ \forall j \in \{1,\ldots ,n\},~\forall t \in \{0,\ldots ,D\} \end{aligned}$$

(2)

$$\begin{aligned}&A_{k}\geqslant 0, ~\forall k\in \{1,\ldots ,m\} \end{aligned}$$

(3)

$$\begin{aligned}&A_{kt}^{\prime }\geqslant 0, ~\forall k\in \{1,\ldots ,m\},~\forall t \in \{0,\ldots ,D\} \end{aligned}$$

(4)

$$\begin{aligned}&\sum _{t=0}^{D}x_{jt}=1, ~\forall j \in \{1,\ldots ,n\} \end{aligned}$$

(5)

$$\begin{aligned}&\sum _{t=0}^{D}x_{it}t+d_{i}\leqslant \sum _{t=0}^{D}x_{jt}t, ~\forall j \in \{1,\ldots ,n\} \nonumber \\&\quad \forall i \in \{1,\ldots ,n\}~ i\ne j, ~ ~\forall (v_{i},v_{j})\in E \end{aligned}$$

(6)

$$\begin{aligned}&\sum _{t=0}^{D}x_{nt}t+d_{n} \leqslant D, \end{aligned}$$

(7)

$$\begin{aligned}&A_{k}+A_{kt}^{\prime }\geqslant \sum _{j=1}^{n}r_{jk}\sum ^{t+d_{j}-1}_{\tau =t}x_{j\tau },\nonumber \\&\quad \forall k\in \{1,\ldots ,m\},~\forall t\in \{0,\ldots ,D\} \end{aligned}$$

(8)

Equation (2) denotes the binary variables for each task. $x_{jt}$ equals to 1 if and only if the task $v_{j}$ starts at time t. Formulas (3) and (4) ensure that the reserved or on-demand units of virtual machine $R_{k}$ are nonnegative. Formula (5) ensures that each task starts exactly at one time. Precedence constraints of the tasks are denoted by Formula (6) with deadline constraints given in Formula (7). The resource availability constraints are established in Formula (8), in which $\textstyle \sum ^{t+d_{j}-1}_{\tau =t}x_{j\tau }$ is the task being processed at time t and $A_{k}+A_{kt}^{\prime }$ is the amount of $R_{k}$ available at time t.

4 Resource allocation with balanced scheme

The Adaptive Probabilistic Algorithm (APA) is proposed for the considered problem in this paper. APA is based on the Estimation of Distribution Algorithm (EDA) [24]. Unlike other evolutionary computing algorithms (e.g., genetic algorithm) producing new generations with explicit recombination operators, APA generates new populations implicitly, which makes APA different from usual recombination operators in EC. According to the probabilistic model of promising solutions, a solution distribution over the search space is estimated. A new generation is produced by sampling the search space using the estimated distribution. And vice versa, the estimated distribution is updated by the new generation.

There are five components in APA: shift vector generation scheme (SVGS), Shift Vector-based Timetabling (SVT), Incremental Renting Plan Decision (IRPD), Swaying Improvement Heuristic (SIH) and Weighted Voting-based Updating Mechanism. The flow chart of the proposed APA is shown in Fig. 4. By initializing all probabilities identical for the possible shift of each task, the initial probability distribution matrix $\mathbf {P}$ is obtained. In terms of the shift probability distribution matrix $\mathbf {P}$, the shift vectors for population Pop are generated by SVGS. SVT is adopted to generate timetable for the schedules quickly. The amounts of reserved and on-demand resources are determined by IRPD. Some elites are selected from Pop and appended to the elite set $\mathcal {E}$. The selected elites are improved by the swaying heuristic SIH. WVUM estimates the probability distribution of the elites among the search space using a voting mechanism. $\mathbf {P}$ is updated by a learning rate-based mechanism. The next population is generated according to the updated $\mathbf {P}$. The procedure is repeated until the termination criterion is satisfied. Let $\pi ^{*}$ be the best result of workflow scheduling with hybrid resource provisioning. Details of the four components of APA are given in Algorithm 1.

Fig. 4

Flow chart of APA

4.1 Shift vector generation scheme

The shift probability distribution matrix $\mathbf {P}=(\mathbf {p}_{1},\ldots ,\mathbf {p}_{n})$ is the foundation for generating shift vectors. According to the probability distribution matrix $\mathbf {P}=(\mathbf {p}_{1},\ldots ,\mathbf {p}_{n})$ (see Fig.  5), shift vectors $\mathcal {H}$ are generated by the Shift Vector Generation Scheme (SVGS). For each task $v_{j}$, the shift $h_{j}$ has at most $\ell _{j}$ states. Let $p_{ji}~(j=1,\ldots ,n)$ be the probability that $h_{j}$ takes the state $i~(i=0,\ldots ,\ell _{j})$. Each element of the probability vector $\mathbf {p}_{j}~(j=1,\ldots ,n)$ represents the probability of task $v_{j}$.

Theoretically, $v_{j}$ could start at any time from the earliest start time $est_{j}$ to the latest start time $lst_{j}$ if there were no precedence between activities. However, $v_{j}$ can start only after its predecessors have finished, i.e., $s_{j}$ is located somewhere between $aest_{j}$ and $lst_{j}$ because of the precedence constraints. In other words, to guarantee the feasibility of a schedule, $h_{j}$ satisfies $h_{j}\in [0,\hat{\ell _{j}}]$ ($\hat{\ell _{j}}$ see Fig. 3) and $p_{ji}$ is set as 0 for all $i=\hat{\ell _{j}}+1,\ldots ,\ell _{j}$. Initially, all probability vectors are uniformly distributed, i.e., $\forall v_{j}\in V$, the probability is determined by $p_{ji}=\frac{1}{{\ell _{j}}+1}$. Starting from $h_{1}$, the shift vector $\mathcal {H}$ is iteratively generated by $\mathbf {P}$. $h_{1}$ takes a random number uniformly from $[0,\ell _{1}]$ and $s_{1}=h_{1}$. Obviously, $f_{1}=s_{1}$ because $v_{1}$ is the dummy source node without any predecessor. Let $\mathcal {F}$ be the set of calculated tasks and $\mathcal {Q}$ be the list of ready ones, i.e., each element is an uncalculated task and all of its immediate predecessors have been processed. Initially, $\mathcal {F}$ is set as $\emptyset$ and $\mathcal {Q}$ is $(v_{1})$. The first element $v_{j}$ is removed from $\mathcal {Q}$ and appended to $\mathcal {F}$. The new probability $p^{\prime }_{ji}$ of $v_{j}$ is determined as follows.

$$\begin{aligned} p_{ji}^{\prime }= {\left\{ \begin{array}{ll} \frac{p_{ji}}{\sum _{i=0}^{\hat{\ell _{j}}}p_{ji}}, &{} \text {if}~~i=0,\ldots ,\hat{\ell _{j}}\\ 0, &{} \text {if}~~i=\hat{\ell _{j}}+1,\ldots ,\ell _{j} \end{array}\right. } \end{aligned}$$

Takes task $v_{5}$ in Figs. 1 and 2 for example, $\ell _{5}=3$ and $\hat{\ell _{5}}=2$. Initially, $\mathbf {p}_{5}=(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4})$, to make a feasible schedule, the new probability vector is set as $\mathbf {p}_{5}=(\frac{1}{3},\frac{1}{3},\frac{1}{3},0)$. Bigger deadline results in bigger slack time, and bigger shift vector of $v_{j}$. $h_{j}$ takes a random number from $[0,\hat{\ell _{j}}]$ with probability $p_{ji}^{\prime }$. For each immediate successor $v_{k}$ of $v_{j}$, i.e., $(v_j,v_k) \in E$, $v_{k}$ is appended to $\mathcal {Q}$ only when all of its immediate predecessors are included in $\mathcal {F}$. The process is repeated until there is no element in $\mathcal {Q}$. By this iterative procedure, the shift vector of the schedule is obtained. A feasible schedule is generated. SVGS is formally described in Algorithm 2.

Fig. 5

Shift probability distribution matrix $\mathbf {P}$

4.2 Shift Vector-based Timetabling

Once a shift vector $\mathcal {H}=(h_1,\ldots ,h_n)$ of a schedule is obtained from $\mathbf {P}$, the start times of all tasks can be calculated by the following Shift Vector-based Timetabling (SVT) procedure. Let $h_{j}$ be the shift of task $v_{j}$, $\mathcal {F}$ be the set of finished tasks. $\mathcal {X}$ is the list of a topological order of tasks $V=\{v_{1},\ldots ,v_{n}\}$, i.e., $v_{i}$ is in front of $v_{j}$ in $\mathcal {X}$ if $v_{i}$ is a predecessor of $v_{j}$. For any schedule, $s_{1}=0$. In the schedule, the shift of a task is a delay that the task starts after all of its immediate predecessors finish. That is, the task does not start immediately. Initially, $\mathcal {F}$ is set as $\emptyset$. The first element $v_{j}$ is removed from $\mathcal {X}$ and appended to $\mathcal {F}$. $s_{j}$ is calculated by $aest_{j}+h_{j}$. The process is repeated until there is no element in $\mathcal {X}$. The timetable of the schedule $S=\{s_{1},\ldots ,s_{n}\}$ is obtained. Take Fig. 1 for example, if the shift vector is $\mathcal {H}=(0,0,2,0,1,4,0)$ and the topological order is $\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}$, we can get the timetable $S=\{0,0,2,0,3,8,8\}$ directly with SVT without scheduling each task. SVT is formally described in Algorithm 3. In fact, different topological orders $\mathcal {X}$ produce the same timetable in SVT, which is guaranteed by the following theorem.

Theorem 1

SVT produces the same timetable for any topological order $\mathcal {X}$ of tasks $V=\{v_{1},\ldots ,v_{n}\}$.

Proof

For simplicity, we suppose two topological orders $\mathcal {X}^{1}=(v_{1},\ldots , v_{i},\ldots , v_{k},\ldots ,v_{n})$ and $\mathcal {X}^{2}=(v_{1},\ldots ,v_{k},\ldots ,v_{i},\ldots ,v_{n})$, they are different only on the positions of $v_{i}$ and $v_{k}$. Let the timetable of $\mathcal {X}^{1}$ generated by SVT be $S^{1}=\{s_{1}^{1},\ldots ,s_{n}^{1}\}$ and that of $\mathcal {X}^{2}$ be $S^{2}=\{s_{1}^{2},\ldots ,s_{n}^{2}\}$.

For the tasks $v_{i}$ and $v_{k}$ (take $v_{k}$ for example) $s_{k}^{1}=aest_{k}^{1}+h_{k}$, $s_{k}^{2}=aest_{k}^{2}+h_{k}$. Since $h_{k}$ is given, it does not change during the calculation. So $s_{k}$ is determined only by the start times of its predecessors. The fact that $\mathcal {X}^{2}$ is derived from $\mathcal {X}^{1}$ by just exchanging the positions of $v_{i}$ and $v_{k}$, which means that there are no predecessors and successors of them between the position $v_{i}$ and $v_{k}$. i.e., $v_{i}$ ($v_{k}$) is not a predecessor or a successor of $v_{k}$ ($v_{i}$). In other words, their start times are irrelevant to each other, i.e., $s_{k}^{1}=s_{k}^{2}$, $s_{i}^{1}=s_{i}^{2}$.

• (1) For any task $v_{j_{1}}$ before $v_{i}$ in $\mathcal {X}^{1}$ (or before $v_{k}$ in $\mathcal {X}^{2}$), $v_{k}$ and $v_{i}$ are not predecessors of $v_{j_{1}}$ since $\mathcal {X}^{1}$ and $\mathcal {X}^{2}$ are topological orders. So $s_{j_{1}}^{1}=s_{j_{1}}^{2}$.

• (2) For any task $v_{j_{2}}$ between $v_{i}$ and $v_{k}$ in $\mathcal {X}^{1}$ (or between $v_{k}$ and $v_{i}$ in $\mathcal {X}^{2}$), $v_{k}$ and $v_{i}$ are not predecessors of $v_{j_{2}}$ according to the above analysis, i.e., $s_{j_{2}}^{1}=s_{j_{2}}^{2}$.

• (3) For any task $v_{j_{3}}$ behind $v_{k}$ in $\mathcal {X}^{1}$ (or behind $v_{i}$ in $\mathcal {X}^{2}$), there are three cases. (i) Both $v_{k}$ and $v_{i}$ are not predecessors of $v_{j_{3}}$. It is obvious that $s_{j_{3}}^{1}=s_{j_{3}}^{2}$. (ii) Either $v_{k}$ or $v_{i}$ is a predecessor of $v_{j_{3}}$, e.g., $v_{k}$ is a predecessor of $v_{j_{3}}$. $s_{k}$ is the same in both topological orders. If $v_{k}$ is an immediate predecessor of $v_{j_{3}}$, its start time exerts no influence on those of the other immediate predecessors of $v_{j_{3}}$, hence $s_{j_{3}}^{1}=s_{j_{3}}^{2}$. If $v_{k}$ is not an immediate predecessor of $v_{j_{3}}$, $v_{k}$ exerts no influence on the start times of nodes which are the immediate predecessors of $v_{j_{3}}$ and are not successors of $v_{k}$. For immediate predecessors of $v_{j_{3}}$ which are successors of $v_{k}$, we can obtain that the start time of $v_{j_{3}}$ is not influenced by $v_{k}$ with an iterative process, i.e., $s_{j_{3}}^{1}=s_{j_{3}}^{2}$. (iii) Both $v_{k}$ and $v_{i}$ are predecessors of $v_{j_{3}}$. Since $s_{k}$ and $s_{i}$ are not changed, the start times of all the successors of $v_{k}$ and $v_{i}$ keep the same. Therefore, $s_{j_{3}}^{1}=s_{j_{3}}^{2}$.

For task at any position of the topological order $\mathcal {X}^{1}$ and $\mathcal {X}^{2}$, $s_{j}^{1}=s_{j}^{2}$. Thus, the timetable $S^{1}=S^{2}$. Any other topological orders could be generated by exchanging positions of tasks in $\mathcal {X}^{1}$.

From the above discussion, therefore, it follows that SVT produces the same timetable for any topological order $\mathcal {X}$. $\square$

Theorem 1 implies that for a given shift vector $\mathcal {H}$, no matter what topological order $\mathcal {X}$ has been used, the corresponding timetable S is unique. Obviously, the time complexity of SVT is O(n). In comparison with the existing task sequence-based schedule representation methods ($O(n^{2})$), this shift vector-based representation method is more intuitive without considering the complex precedence constraints.

Theorem 2

A shift vector generated by SVGS is a feasible schedule.

Proof

Let $S=\{s_{1},\ldots ,s_{n}\}$ be the timetable generated by SVT in terms of $\mathcal {H}=(h_1,\ldots ,h_n)$, a shift vector generated by SVGS. A schedule is impracticable if either the precedence constraints or the reserved deadline is not satisfied. However, (i) in Step 9 of SVGS, $s_{j}=aest_{j}+h_{j}$, $aest_{j}=\max _{v_{i}\in \mathcal {P}_{j}}\{f_{i}\}$ and $h_{j}\ge 0$, so $s_{j}\ge s_{i}+d_{i},~~\forall (v_{i},v_{j}) \in E$. The precedence constraints is satisfied. (ii) $h_{n}\le \hat{\ell _{n}}$, so $s_{n}=aest_{n}+h_{n}\le aest_{n}+\hat{\ell _{n}}$, and $s_{n}\le lst_{n} \le D$. The reserved deadline is satisfied. According to THEOREM 1, S is unique. In other words, for any task $v_{j}\in V=\{v_{1},\ldots ,v_{n}\}$, the start time $s_{j}$ calculated by SVGS and that generated by SVT are the same. Therefore, a feasible schedule could be produced by a shift vector using SVGS. $\square$

Theorem 2 illustrates that the feasible populations, Pop can be generated by the SVGS.

4.3 Incremental Renting Plan Decision

Resource renting plan is decided after SVT. The resource usage matrix $U=(u_{kt})_{m\times D}$ is calculated according to the timetable generated by SVT. Each element $u_{kt}\in U$ represents that $u_{kt}$ units of virtual machine $R_{k}$ are occupied at time t. For a timetable S, the corresponding matrix U is calculated as Algorithm 4. First, each element in U is set as 0, for each task $v_{j}$, if a virtual machine $R_{k}$ is occupied, $u_{kt}$ is updated by $u_{kt}+r_{jk}$ for the whole processing time of $v_{j}$.

According to the resource usage matrix U, the amounts of reserved and on-demand resources are determined. Obviously, too many reserved resources lead to a low resource usage rate, which makes the total renting cost high, and too little reserved resources does not take the advantage of the discount in the long-term reserved resources, which also makes a high renting cost. To get a balance between the reserved and on-demand resources, the lower bounds are calculated first. The lower bounds for a virtual machine $R_{i}$ are denoted as the minimal resource requirements in U, i.e., $Low_{i}=\min (u_{ij}),\forall j\in \{0,\ldots ,D\}$. IRPD starts with $A_{i}=Low_{i}$, and $u_{ij}^{\prime }$ is set as $u_{ij}-A_{i}$. In the matrix $u_{ij}^{\prime }(j\in \{0,\ldots ,D\})$, the elements equal to 0 are called free time slots for virtual machine $R_{i}$. Let the total number of free time slots for virtual machine $R_{i}$ be $\zeta$. If the reserved amount $A_{i}$ is increased by 1, some old free time slots $\zeta$ and on-demand resources $D-\zeta$ are calculated with the reserved way. The $\zeta$ free time slots increases the total renting cost by $\delta ^{+}=1\times \zeta \times c_{i}\times \varphi$ while the on-demand resources decrease the cost by $\delta ^{-}=1\times c_{i}\times (D-\zeta )-1\times \varphi \times c_{i}\times (D-\zeta )$. If $\delta ^{+}<\delta ^{-}$, the increase in the reserved resource reduces the total renting cost, $A_{i}$ is updated by $A_{i}+1$. The procedure is repeated until $\varphi >(D-\zeta )/D$. The on-demand units for resource $R_{i}$ is calculated by $A_{ij}^{\prime }=u_{ij}-A_{i}$ for each time j. After getting the resource renting plan for each virtual machine, the total renting cost is calculated by Formula (1).

Figure 6 shows an example of IRPD. The matrix $u_{1j}$ equals to (4, 4, 4, 3, 2, 2, 2, 2, 3, 3). $A_{i}$ is set to be 2 first. $u_{1j}^{\prime }$ = (2, 2, 2, 1, 0, 0, 0, 0, 1, 1). $\zeta$ and $D-\zeta$ are equal to 4 and 6, respectively. Suppose the discount $\varphi$ be 0.8, i.e., $\varphi >(D-\zeta )/D$. Therefore, the procedure stops. $A_{1}=2$ and $A_{1j}^{\prime }$ is set to be (2,2,2,1,0,0,0,0,1,1), respectively.

Fig. 6

An example of IRPD

4.4 Swaying Improvement Heuristic

All individuals in Pop are sorted in non-decreasing order of the resource renting cost. The first $|\mathcal {E}|$ schedules are selected. Usually, resources are always allocated in an unbalanced way in the initial schedule in terms of the probability-based methods. To balance the resource utilization, the swaying heuristic is developed. Different from traditional EDAs [24], the selected elites are improved by SIH before they are evaluated.

There are two procedures in SIH: Backward Moving and Forward Moving. Similar to $h_{j}$, there is a gap $\bar{h}_{j}$ between $s_{j}$ and $alst_{j}$ of task $v_{j}$ ($alst_{j}$ see Fig. 3). In the Backward Moving (BM), all tasks are sorted in the non-increasing order of the finish times of the current schedule and kept in the priority list $\mathcal {L}_{B}$. The head task $\mathcal {L}_{B}^{[1]}$ (the current task with the biggest finish time) denoted as $v_{[1]}$ is removed from $\mathcal {L}_{B}$ (the second one becomes the head task $\mathcal {L}_{B}^{[1]}$ now). There are $\bar{h}_{[1]}+1$ feasible start points for $v_{[1]}$ (from the current point $s_{[1]}$ to $alst_{[1]}$ ). Therefore, the new shift $h'_{[1]}$ is increased one by one from $h_{[1]}$ to $h_{[1]}+alst_{[1]}-s_{[1]}$. The corresponding resource renting costs of the possible schedules (only change the shift of $v_{[1]}$ while keeping the others unchanged) are calculated by IRPD. The shift vector (ties are broken by the larger shift) with the minimum cost is set as the new one. And the current $v_{[1]}$ is removed from $\mathcal {L}_{B}$. The procedure is repeated until $\mathcal {L}_{B}$ becomes empty. According to $\mathcal {L}_{B}$, all successors of $v_{[1]}$ have been calculated before the calculation of $v_{[1]}$. In other words, no immediate successor checking is needed. Forward Moving (FM) performs in an opposite way to BM. The priority list $\mathcal {L}_{F}$ is built according to the non-decreasing order of all the start times of the schedule obtained by BM. And the decreasing strategy of shift vector is similar to the increasing one in BM, where the new shift $h'_{[1]}$ is decreased one by one from $s_{[1]}-aest_{[1]}$ to 0. The shift vector (ties are broken by the smaller shift) with the minimum cost is set as the new one. SIH starts from a schedule in $\mathcal {E}$ and iteratively conducts the BM and FM until no better resource renting cost can be found.

Let $\pi ^\text {{best}}$ be the best schedule found so far and $\pi ^{c}$ be the best solution of the current generation. For each schedule $\pi \in \mathcal {E}$, $BFMI(\pi )$ is described in Algorithm 5.

4.5 Weighted Voting-based Updating Mechanism

The distribution estimation and the probability vector updating are crucial for APA to find good building blocks. The proposed WVUM estimates the probability distribution of the elites in the search space using a weighted voting mechanism. The probability vector $\mathbf {P}$ is updated by a learning rate-based mechanism.

Suppose $\pi ^\text {{worst}}$ is the worst solution in $\mathcal {E}$ and $\pi ^\text {{best}}$ is the best solution obtained so far. For each solution $\pi$ with the resource renting cost $C(\pi )$ in $\mathcal {E}$, the weight $w(\pi )$ is denoted as

$$\begin{aligned} w(\pi )= \frac{C(\pi ^\text {{worst}})-C(\pi )}{C(\pi ^\text {{best}})} \end{aligned}$$

(9)

A binary variable is defined as

$$\begin{aligned} x_{jik}= {\left\{ \begin{array}{ll} 1, &{} \text {if}~~i=h_{j}~~\text {in}~~\text {schedule}~~\pi _{k}\\ 0, &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

Since better schedule always implies better promising solution, the weight $w(\pi _{k})$ is adopted to update the probability vector. Since the current probability exerts great influence on the performance of the algorithm, the probability $p_{ji}^{t}$ in the t th generation is updated by

$$\begin{aligned} p_{ji}^{t+1} = (1-\beta )p_{ji}^{t} + \beta \frac{\sum _{\pi _{k}\in \mathcal {E}}x_{jik}\cdot w(\pi _{k})}{\sum _{i=0}^{\ell _{j}}\sum _{\pi _{k}\in \mathcal {E}}x_{jik}\cdot w(\pi _{k})} \end{aligned}$$

(10)

where $\beta$ is a learning rate, indicating the speed of the probability vector learned from the elite set $\mathcal {E}$. It seriously affects the convergence of APA. If $\beta$ is close to 0, APA becomes a random sampling method. If $\beta$ is too large, elements of the probability vector becomes constants quickly which traps the algorithm into local optimal.

For example, there are five elites in $\mathcal {E}$ with the resource renting costs $C=(20, 20, 25, 30, 40)$ and the cost of the global best solution $C(\pi ^\text {{best}})$ being 15. According to Eq. (9), the weights of the elites are $w=(1.33, 1.33, 1, 0.67, 0)$. If the slack time $\ell _{3}$ of task $v_{3}$ is 4, the possible shift states of $v_{3}$ would be $\{0,1,2,3,4\}$. Suppose the probability vector of $v_{3}$ is $\mathbf {p}_{3}=(0.4, 0.4, 0.1, 0.05, 0.05)$ and the shift of task $v_{3}$ in each elite is (0, 0, 1, 2, 3). The weighted number of states of $v_{3}$ in $\mathcal {E}$ is calculated by $\sum _{\pi _{k}\in \mathcal {E}}x_{jik}\cdot w(\pi _{k})$, i.e., $(1.33\,+\,1.33, 1, 0.67, 0, 0)=(2.66, 1, 0.67, 0, 0)$ for each shift states. Assume the learning rate $\beta$ is 0.5, the probability vector $\mathbf {p}_{3}$ of $v_{3}$ is updated by Eq. (10). For instance, $p_{30}=0.5\times 0.4 + 0.5\times \frac{2.66}{2.66\,+\,1\,+\,0.67\,+\,0\,+\,0}=0.507$. By this way, the new probability vector is obtained with $\mathbf {p}_{3}=$ (0.507, 0.315, 0.127, 0.025, 0.025).

5 Computational experiments

To the best of our knowledge, there is no existing problem exactly the same as the considered problem. Workflow scheduling with hybrid resource provisioning is similar to the Resource Availability Cost Problem (RACP), a traditional single project scheduling problem [14]. For RACP, the typical meta-heuristics include the scatter search (SS) [34], the genetic algorithm (GA) [28] and the path relinking algorithm (PR) [26]. The algorithm SS [34] adopted the resource capacity list to generate a schedule, while the algorithm GA [28] used the combination of an activity list and a resource capacity list to produce a schedule. They both transformed the problem into a series of resource-constrained scheduling problems and adjust the resource capacity to satisfy the deadline of the problem. The algorithm PR [26] generated a schedule directly according to the priority list of activities. In our algorithm APA, we use the shift vector scheme to generate a schedule directly. Comparing with APA and PR, SS and GA are much time-consuming. In addition, the three algorithms for RACP only consider reserved resources for scheduling workflows. For full evaluation, the three meta-heuristics are modified by adding IRPD to the schedule of each algorithm. The modified MSS, MGA and MPR are compared with the proposed APA. All algorithms are coded in Java and performed on the virtual machine (1000 MIPS processor with 1 G RAM and 10 GB of storage).

Different testing beds are adopted to calibrate the involved parameters and compare the algorithms. Problem sets with different sizes and deadlines are randomly generated by RanGen according to [31] to calibrate parameters. To compare the algorithms, project scheduling benchmarks from the well-known PSPLIB [21] are adapted for the considered problem. As well, RanGen is used to generate random instances with more type of resources and deadline factors DF to further compare the algorithms. Deadline factors DF are defined as $D=\text {DF}\times est_{n}$, where $est_{n}$ is the critical path of the current test workflow.

Since the schedule representation scheme and the computation of the improved heuristic are distinct in different methods, it is not impartial to use the number of iterations or CPU times as the terminal criterion. To fairly compare the involved algorithms, the maximum number of generated schedules is adopted in this paper. In MSS, every evaluated resource set is regarded as a schedule. In MGA and MPR, each evaluated feasible task sequence is regarded as a schedule. In the proposed APA, each evaluation of a shift vector is regarded as a schedule.

RDI (Relative Deviation Index) is adopted to measure the performance of the algorithms. Let $\pi ^\text {{best}}$ and $\pi ^\text {{worst}}$ be the best and worst schedules obtained by all the compared algorithms, respectively. $\pi$ is the schedule obtained by the evaluated algorithm. RDI of an algorithm with resource renting cost $C(\pi )$ is defined as

$$\begin{aligned} RDI= {\left\{ \begin{array}{ll} 0&{} \text {if}~~\pi ^\text {{worst}}=\pi ^\text {{best}} \\ \frac{C(\pi )-C(\pi ^\text {{best}})}{C(\pi ^\text {{worst}})-C(\pi ^\text {{best}})}\times 100\% &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

The closer to 0 the index, the better the algorithm. Note that if the worst and the best solutions are the same, all the combinations would provide the best solution and hence the index value would be 0 (the best index value).

Fig. 7

Interactions between |Pop|, $|\mathcal {E}|$ and task numbers with 95% Tukey HSD confidence intervals on RDI

5.1 Parameter calibration

In the proposed APA, there are three parameters to be calibrated: the population size |Pop|, the elite size $|\mathcal {E}|$, the learning rate $\beta$, which are restricted to {50, 100, 150, 250}, {1, 3, 5, 7}, {0, 0.01, 0.03, 0.05}, respectively. The termination criterion (TC) takes value from {1000, 5000, 10000} according to [34]. Instances with 30, 60, 90 and 120 tasks (which are called as J30, J60, J90 and J120), and 4 types of resources are randomly generated by RanGen according to [31]. The order strength (OS), an index of the network complexity, is set as {0.25, 0.50, 0.75}. The resource factor (RF) indicates the density of the different resource types needed by a task equals to {0.25, 0.50, 0.75, 1}. For each combination of OS and RF, 5 instances are generated frp fair comparison. The deadline factor (DF) takes value from {1.1, 1.2, 1.3, 1.4, 1.5}, e.g., the deadline of the workflow application is defined as $D=1.2\times est_{n} \cdot c_{k}$ of resource $R_{k}$ is a uniform random number in [1,10]. The discount $\varphi$ is set to be 0.8 as an example. Totally, we test $4\times 3\times 4\times 5\times 5=1200$ different instances. For different combinations of parameters, there are $4\times 4\times 4\times 3\times 1200=230400$ tests.

The multifactor analysis of variance (ANOVA) technique is used to calibrate the three parameters. Let the response variable be RDI. First, the three main hypotheses (normality, homoscedasticity and independence of the residuals) are checked from the residuals. All three hypotheses are acceptable. Since all the p values in the experiments are close to zero, they are not given in this paper. Interactions between (or among) any two (or more than two) factors are not considered because the observed F-Ratios are small in comparison.

Interactions between |Pop|, $|\mathcal {E}|$ and task numbers with 95% Tukey HSD confidence intervals are depicted in Fig. 7. When $|Pop|=100$, APA achieves the best performance for different problem size (n = 30, 60, 90 or 120). For the elite set size $|\mathcal {E}|$, except J30, the performances between different $|\mathcal {E}|$ are not so big. $|\mathcal {E}|=3$ is the best one for all the problem size. The learning rate $\beta$ exerts great influence on APA for different problem size, and APA obtains the best RDI when $\beta =0.01$. Interactions between $\beta$, TC and task numbers with 95% Tukey HSD confidence intervals are depicted in Fig. 8. For the termination criterion TC, the performances improve a lot for all the problem size when TC increases from 1000 to 5000, which improves a little when TC increases from 5000 to 10000. In the following comparison, |Pop| is set at 100, $|\mathcal {E}|=3$, $\beta =0.01$ for APA, and the maximum number of schedules is set at 5000 for all the compared algorithms as it is the most common termination criterion for project scheduling problems [18].

Fig. 8

Interactions between $\beta$, TC and task numbers with 95% Tukey HSD confidence intervals on RDI

Fig. 9

Interactions between algorithms and task numbers with 95% Tukey HSD confidence intervals on RDI

5.2 Performance comparison on PSPLIB

Test beds with 30, 60, 90 and 120 tasks scheduling on one system with 4 types of resources chosen from PSPLIB are adapted for performance comparison of different meta-heuristics, in which $\text {NC} \in \{1.5, 1.8, 2.1\}$ reflects the average number of immediate successors of a task and $\text {RF} \in \{0.25, 0.5, 0.75, 1\}$ determines the average number of resources requested by a task. For each combination of NC and RF, 5 instances are selected. The deadline factor DF is set as 1.2 according to [34] and [26]. In total, $4\times 1\times 3\times 4\times 5\times 1=240$ instances are taken from PSPLIB for the comparison.

Based on the calibrated parameters, RDI of the compared algorithms is shown in Fig. 9. From Fig. 9, it can be observed that the proposed APA outperforms the other three adapted algorithms on all four sizes of instances. For J30, the average RDI of APA is close to 5%, while those of MSS, MGA and MPR are close to 15, 80 and 80%, respectively. The average RDI of APA and that of MSS decrease with the instance size, while this is not true for MGA and MPR. MGA and MPR get the worst average RDI on J90 and J120, whereas APA and MSS obtain the worst average RDI on J30 (about 5 and 15%, respectively), which implies that APA and MSS are more suitable for large instances than MGA and MPR.

The above experimental results over benchmarks reveal that APA gets a better performance comparing to the three adapted algorithms with the increase in the instance size. The reason lies in that the proposed SVT (Shift Vector-based Timetabling) scheme generates schedules directly. With the increase in the instance size, the adapted three algorithms require more steps and computation times to generate schedules as compared to APA.

5.3 Performance comparison on random sets

To further investigate the influence of resource types and deadlines on performances of the involved algorithms, instances with 30 tasks and 2, 4, 6, 8, 10 types of resources are randomly generated by RanGen. The deadline factor DF takes value from {1.1, 1.2, 1.3, 1.4, 1.5}. The order strength (OS) is set as {0.25, 0.50, 0.75}. And the resource factor (RF) belongs to {0.25, 0.50, 0.75, 1}. For each combination of OS and RF, 5 instances are generated. Totally, $3\times 3\times 4\times 5\times 5=900$ different instances are generated and tested.

Comparison results of all the test beds are shown in Table 2. Table 2 shows that the proposed APA outperforms the other three adapted algorithms in both effectiveness and efficiency on average. The average RDI of APA is only 2.15%, which is much less than those of the other three algorithms. APA spends just 15.70 s, while the average CPU time of MGA, MPR and MSS is 17.98.10, 16.33 and 33.84 s, respectively.

Table 2 RDI (%) and CPU time (s) of the algorithms on random sets

The means plot with 95% Tukey HSD confidence intervals for the compared algorithms is shown in Fig. 10. The average RDI of APA is about $5\%$, while that for MSS, MRP and MGA are about 45, 75 and $80\%$. Figure 10 indicates that APA can save more cost than MSS, MPR and MGA. Therefore, APA outperforms the other three methods both on benchmark and on random instances.

Fig. 10

Means plot with 95% Tukey HSD confidence intervals for the compared algorithms on RDI

Interactions between algorithms and deadline factors with 95% Tukey HSD confidence intervals are shown in Fig. 11. Figure 11 illustrates that the proposed APA is better than the other three adapted algorithms on all the instances with different deadlines. Performance of MGA is the worst among the compared algorithms. The average RDI of APA is close to 0 while that of MGA is almost up to $80\%$ for the test beds with different DF. The average RDIs of APA and MSS decrease with deadlines. However, this is not true for MGA and MPR. For example, APA saves about $55\%$ of cost comparing with MGA, MPR and MSS when DF $=$ 1.1, whereas the differences between APA and MSS, MPR, MGA become around 30, 80 and $80\%$, respectively, when DF $=$ 1.5. The increase in the deadline factor leads to a better performance of APA. The reason is that a large deadline factor results in a large size of the shift probability distribution matrix and the diversification of APA is increased. However, APA takes more time to obtain schedules as the shift vector generation scheme (SVGS) is time-interval based. With the increase in the deadline factor, the performance of APA would become worse because more time is required to find a solution in the search space.

Fig. 11

Interactions between algorithms and deadline factors with 95% Tukey HSD confidence intervals on RDI (%)

Figure 12 demonstrates effectiveness of the compared algorithms with different numbers of resource types. APA is the best, while MGA is the worst for instances with different number of resource types. The average RDI of APA decreases with the number of resource types. However, the tendencies of MSS, MGA and MPR are non-monotonous. For example, APA saves about $5\%$ of cost comparing with MSS, while it saves about $40\%$ of cost comparing with MPR and MGA when $m=2$. When $m=6$, APA gets the best performance while the differences between APA and MSS, MPR, MGA become about 65, 85 and $87\%$, respectively. The above phenomena indicate that the traditional methods are less effective as the number of resource type increases in cloud computing. The reason lies in that the adapted algorithms generate schedules using resource capacity lists or priority lists of activities, and with the increase in the resource type, the adapted three algorithms also require more steps and computation times to generate schedules.

Fig. 12

Interactions between algorithms and resources types with 95% Tukey HSD confidence intervals on RDI (%)

Finally, comparing results on test beds with different OS and RF are shown in Fig. 13. Figure 13 indicates that APA outperforms all the other algorithms. The average RDI of each algorithm has no monotonous trend when OS and RF increase.

Fig. 13

Interactions between algorithms and instances on RDI (%) with 95% Tukey HSD confidence intervals for test beds with $m=2$ and $DF=1.2$

6 Conclusions and future work

We have considered the cloud workflow scheduling problem with hybrid resources provision which combination of the reserved and on-demand manners. The probability-based APA algorithm was proposed for the considered problem. APA mainly consisted of a new schedule generation scheme and an improvement procedure. The improvement procedure found good building blocks and the schedule generation scheme kept the good blocks to the next generation. Experimental results demonstrated that APA outperforms the other three adapted algorithms over both adapted benchmarks and random generated test beds. For the adapted benchmarks, APA improves MSS about $10\%$, MPR $85\%$ and MGA $85\%$ on average. For the random generated test beds, APA improves MSS about $40\%$, MPR about $75\%$ and MGA $80\%$ on average. With the deadline factor increased, the scale of the shift probability distribution matrix became larger which made APA more effective and efficient. Furthermore, the efficiency of APA decreased at a slower rate than the other algorithms as the number of resource types increased because the proposed schedule generation scheme produced timetables directly. The results indicated that APA is more suitable for resource allocation in cloud computing.

However, the proposed approach cannot be implemented in currently existent systems because many real constraints have not been considered in the problem under study, such as communication costs between tasks, setup times of virtual machines, uncertainties during executions. These constraints make the problem much harder. The proposed APA can be modified for those problems with newly designed heuristics incorporating characteristics of the harder problems. These topics would be promising in the future.