Kahina Bessai
email: kahina.bessai@gmail.com

Samir Youcef

Ammar Oulamara

Claude Godart

Selmin Nurcan
email: nurcan@univ-paris1.fr

Resources allocation and scheduling approaches for business process applications in Cloud contexts

come

I. INTRODUCTION

During the last decades software sales model dominated market. This model requires from customers managing continuously software deployment, including transitioning between different versions. Therefore, customers need technical expertise and expensive initial investment for acquiring and using them. Furthermore, they also need to pay for upgrades as annual maintenance fee. With the advent of Cloud computing paradigm, IT organizations need to think in terms of managing services rather than managing devices. Cloud service providers tent to offer services that can be classified in three categories [START_REF] Buyya | Cloudbus toolkit for marketoriented cloud computing[END_REF][5]: i) Software as a Service (SaaS), ii) Platform as a Service (PaaS) and iii) Infrastructure as a Service (IaaS).

Therefore, the Cloud computing has quickly changed the way that compute resources can be used and allow users to access computing resources on the fly according to the application's need. For instance, to run any desired software, Amazon's EC2 [START_REF] Juve | Scientific workflow applications on Amazon EC2[END_REF] provides a Web service through which users can boot an Amazon Machine Image. However, despite the proven benefits of using Cloud to execute business processes, users lack guidance for choosing between different offering while taking into account several objectives often conflicting.

Moreover, most existing workflow matching and scheduling algorithms consider only an environment in which the number of resources is assumed to be bounded. However, in distributed systems such as Cloud computing this assumption is in opposition to the usefulness of such systems. Indeed, the "illusion of infinite resources" is the most important feature of Clouds [START_REF]Workflow Management Coalition: Terminology & Glossary[END_REF] [START_REF] Buyya | Cloudbus toolkit for marketoriented cloud computing[END_REF], which means that users can request, and are likely to obtain, sufficient resources for their need at any time. Additionally to this characteristic, a Cloud computing environment can provide several advantages that are distinct from other computing environments: i) computing resources can be elastically scaled on demand (i.e. the number of resources used to execute a given workflow can be changed at runtime), ii) computing resources are exposed as services and thereby a standardization interface is provided. In this paper, we are interested to business processes where in opposition to scientific workflows it is difficult to automate all the tasks. Especially, certain tasks, that cannot be automated, require validation as subject to human intervention.

Furthermore, although there are efficient algorithms in the literature for workflow tasks allocation and scheduling for heterogeneous resources such as those proposed in grid computing context [START_REF] Tordsson | Cloud brokering mechanisms for optimized placement of virtual machines across multiple providers[END_REF] [START_REF] Breitgand | Policy-driven service placement optimization in federated clouds[END_REF] [21] [START_REF] Van Den Bossche | Cost-Efficient Scheduling Heuristics for Deadline Constrained Workloads on Hybrid Clouds[END_REF], they do not consider the human dimension. In addition, they apply to a bounded number of resources. As a consequence, they are not appropriate for business processes matching and scheduling.

To overcome the limitations of existing approaches, we propose new approaches which are distinct from the related works as they mainly take into account Clouds elasticity feature and human resource dimension. Moreover, our approaches consider the overall completion time and the execution cost together.

To summarize, in this paper we make the following contributions:

1) We formalize a model for workflow tasks allocation and scheduling in Cloud environment taking into account the human dimension. 2) We propose a first approach for workflow tasks allocation and scheduling based on minimizing the execution cost incurred by using a set of resources. 3) We propose a second approach based on the overall completion time. 4) We present a third approach combining the above objectives. The remainder of the paper is organized as follows. In the next section, we introduce our workflow matching and scheduling model. Section III introduces the bi-criterion optimization approach. In Section IV, we present our matching and scheduling algorithms (the cost-driven approach, the timedriven approach and the cost-time-driven approach). Experimental results are presented in Section V. Section VI presents related works and compare them with our proposition. Finally, we draw conclusions and give some future works in Section VII.

II. PROBLEM FORMULATION AND OBJECTIVE FUNCTIONS

Recall that the main scope of this paper is to deal with the workflow tasks allocation and scheduling problem in the Cloud environment. In the following, we start by refining the problem definitions and then present the cost and the time objective functions that we consider in this work. More precisely, we give a model comprising resources, role, tasks and business process applications definitions and the relationship between them.

A. Problem formulation

Before giving the problem statement, lets start with some definitions to facilitate the understanding of our approaches.

Definition 1 (Resource): A resource r represents an available unit that is required for executing a task. As mentioned earlier, a resource can be human resource or virtual machine. The set of available resources is denoted R Definition 2 (Role): A role ro refers a class of resources that own the same capabilities. The set of available roles is denoted Ro.

Definition 3 (Task): A task t i is a logical unit of work that is executed by a resource which can be human resource (if the task cannot be automated) or machine (if the task can be automated).

Definition 4 (Business process): A business process application is represented as a directed acyclic graph (DAG). Formally, a workflow application is a DAG represented by G = (T, E), where:

1) T = {t 1 , ..., t n } is a finite set of tasks.

2) E represents the set of directed edges. An edge (t i , t j ) of graph G corresponds to the data dependencies between these tasks (the data generated by t i is consumed by t j ). 3) Task t i is called the immediate parent of t j which is the immediate child task of t i . Note that the child task cannot be executed until all of its parents tasks are completed. In a given graph, a task without any precedents is called an input task, denoted t input and a task without successors is called an exit task, denoted t exit .

Definition 5 (Data): Let Data be a n×n matrix of communication data, where data[i, j] is the amount of data required to be transmitted from task t i to task t j .

Most of the workflow tasks allocation and scheduling algorithms require single input (t input ) and single exit (t exit ) task graphs. So, if there is more than one input (exit) task, they are connected to a zero-cost (-time) pseudo-input (-exit) task with zero communication cost and time, which does not affect the allocation and the schedule.

Moreover, a task is an indivisible unit of work and is nonpreemptive. Figure 1 (left side) shows an example of workflow application defined by ten tasks, which are represented as nodes. The dependencies between tasks are represented as arrows. The initial task may have an input file denoted (input.file) and the exit task produces an output file (output.file).

To execute a given workflow application (DAG), a set of resources (human resources and virtual machines) can be used on-demand.

Definition 6 (Resource graph): The resources are represented as a directed graph denoted RG. Formally, a resources graph is represented by RG = (R, V ), where:

1) R = {V M 1 , ..., V M m , HR 1 , ..., HR m } is a finite set of virtual machines types and human resources. 2) V represents the set of directed edges. Each edge is denoted (V M i , V M j ) corresponding to the link between these virtual machines. However, unlike the number of human resources which is assumed to be finite, we consider that there is enough virtual machines for each type. Thus, a user can request and obtain sufficient virtual machines at any time. This assumption is reasonable in Cloud computing environment because it gives for user an "illusion of infinite resources". When there is no ambiguity, we omit the term type and use virtual machine instead virtual machine type.

Definition 7 (Bandwidth ): Let B be a m × m matrix, in which B[i, j] is the bandwidth between virtual machine types V M i and V M j , where B[i, i] -→ ∞ means that there is no transfer data. Remark It is important to note that data are transmitted only through the used virtual machines. In others words, if a given task is performed by a human resource, it uses a virtual machine, once finished executing this task, to transmit the generated data to any other resources that will execute the next tasks.

Figure 1 (right side) shows an example of resources graph with real-life measurement of data transfer speeds (bandwidth) between different data centers of the Cloud provider Amazon. To simplify the example, we assume that data[i, j] = data[i].

Definition 8 (Transfer time): Let r(t j ) denotes the resource (virtual machine or human resource) that executes task t j . The transfer time T T (r(t i ), r(t j )), which is for transferring data from task t i (executed by r(t i )) to task t j (executed by r(t j )) is defined by: T T (r

(t i ), r(t j )) = data[i, j] B[r(t i ), r(t j )]
Definition 9 (Execution time matrix): Let ET be a n × m execution time matrix in which ET (t i , r j ) gives the execution time estimation to complete task t i by resource r j .

Definition 10 (Unit execution cost vector): Let U EC be a (m + m )-dimensional unit execution cost vector, where U EC(r j ) represents the cost per time unit incurred by using the resource r j . Let EC be a n × (m + m ) execution cost matrix in which EC(t i , r j ) gives the execution cost to complete task t i by resource r j defined by:

EC(t i , r j ) = ET (t i , r j ) × U EC(r j )
Definition 11 (Transfer cost): The data transfer cost T C(r(t i ), r(t j )), which is the cost incurred due to the transfer of data from task t i (executed by r(t i )) to task t j (executed by r(t j )), is defined by:

T C(r(t i ), r(t j )) = data[i, j] × (C out (r(t i )) + C in (r(t j )))
where C out (r(t i )) and C in (r(t j )) represent respectively the cost of transferring data from r(t i ) and the cost of receiving data on r(t j ). The transferring data cost is determined by mutual agreement between the consumer and the provider in the SLA (e.g Amazon CloudFront).

B. Objective functions

In the following, we give the formal definition of the considered objective functions in this paper (i.e. the overall execution time and the cost incurred using a set of resources). Before giving the objective functions considered in our study, we start by the the following definition.

Definition 12 (Human ressource availability): The availability of resource r j , denoted avail[j], is the earliest time at which the resource r j is ready for task execution.

1) a. Time objective function: Let EST (earliest start time) and EF T (earliest finish time) attributes that characterize the set of resources (virtual machine types and human resources). These attributes are derived from a given partial allocation and scheduling (i.e. a task t i is assigned to virtual machine V M (t i ) or human resource HM (t i )). The partial schedule refers to the fact that for each task the earliest start time and the earliest finish time values are obtained using only the tasks that must be performed before it. EST (t i , r j ) and EF T (t i , r j ) are the earliest execution start time and the earliest execution finish time of task t i on resource r j , respectively. For the input task t input , the earliest execution start time and the earliest execution finish time are given by Equation 1 and Equation 2, respectively:

EST (t input , r j ) = 0 (1) EF T (t input , r j ) = ET (t i , r j ) (2)
For the other tasks in the graph, the EST and the EF T values are computed recursively, starting from the initial task, as shown in Equation 3 and Equation 4. In order to compute the EF T of a task t j , all immediate predecessor tasks of t j must have been assigned and scheduled with the consideration of the transfer time.

EF T

(t i , r j ) = EST (t i , r j ) + ET (t i , r j ) (3)
EST (ti, rj) = max avail[j], max tp∈pred(t j ) [AF T (tp) + T T (r(tp), r(ti))] (4)
where pred(t i ) is the set of immediate predecessors of task t i and avail[j] is the earliest time at which resource r j is ready for task execution. As the number of virtual machines is assumed to be infinite, then avail[j] = 0 where r j is a virtual machine. In other words, if task t i is performed by resource r j which is a virtual machine then EST (t i , r j ) is computed as follows:

EST (t i , r j ) = max tp∈pred(tj ) {AF T (t p ) + T T (r(t p ), r(t i ))}
(5) However, as the number of human resources is assumed to be finite, then if task is performed by human resource the earliest time at which this resource is ready should be taking into account (i.e. avail[j]). Therefore, if t i is the last assigned task on resource r j , then avail[j] is the time that resource r j completed the execution of the task t i and it is ready to execute another task. The inner max block in the EST equation returns the ready time, i.e. the time when all required data by t i has arrived at resource r j .

After a task t i is scheduled on a resource r j , the earliest start time and the earliest finish time of t i on resource r j is equal to the actual start time, denoted AST (t i ), and the actual finish time, denoted AF T (t i ), of task t i , respectively.

After all tasks in a graph are scheduled, the schedule length (i.e., the overall completion time) will be the actual finish time of the exit task (i.e. AF T (t exit )). The schedule length, also called makespan, is defined as:

makespan = AF T (t exit ) (6)
Therefore, the time objective function is to determinate the assignment of tasks of a given workflow application to resources (virtual machines and human resources) such that its schedule length is minimized. Predictive heuristic for human resource availabilities The actual finish time as computed previously does not take into account the fact that human resources can perform other tasks that do not belong to the same process. More precisely, the work list of a given human resource may contain work items of different processes. The realism of this assumption can be disputed as human resources are "shared" by more than one process. Thus, it is might be desirable to design a procedure which tries to predict the humane resource availabilities. Concretely, we propose to estimate the availability values of human resources taking into account the previous observations. Let availability[j] k+1 the estimation of resource j availability and t i the next task that can be performed by this resource. Instead of simply adapting to the computed availability using equation 4, one can try to forecast and estimate what availability[j] k+1 will be using the historical data. In our experiment results we used a double exponential smoothing to estimate the availability of a given resource. Formally, the model is represented by the following equation:

Avail[j] k+1 = (1 -α) k m=0 (1 -α)avail[j] k-m , 0 < α < 1 (7)
Intuitively, Equation 7 produces a prediction of resource availabilities that weights historical data based on exponential decay according to the time distance in the past. The parameters α is computed from the data using auto-correlation analysis.

2) b. Cost objective function: In the following, we focus on the cost objective function which is the total expense for workflow tasks execution including (i) the tasks execution cost and (ii) the data transfer cost between the used virtual machines.

The cost function is a structure independent criterion defined as the sum of the costs of executing all workflow tasks, given by:

cost = n j=1    EC(r(t j )) + p∈pred(tj ) T C(r(t p ), r(t j ))    (8)
Thus, the cost objective function is to determinate the assignment of tasks of a given workflow application such that its overall execution cost is minimized. Problem statement Suppose a business process together with its given task set T , resource set R, role set Ro, a mapping from resources to role, i.e. R → Ro, and from role to tasks, i.e. Ro → T . The objective is to find a set of resources to execute workflow applications while minimizing the overall execution time and the cost function simultaneously. Formally, this problem is defined as follows:

min {AF T (t exit )} and min n j=1 EC(r(t j )) + p∈pred(t j ) T C(r(t j ), r(tp))    respect the tasks -precedence requirement (DAG)
given a set of resources (R)

III. BI-CRITERIA APPROACH

The optimization problem defined above can be approached in several ways. Indeed, to deal with bi-criterion allocation and scheduling problems mainly three streams are considered [START_REF] Hoogeveen | Multicriteria scheduling[END_REF] [15] [START_REF] Billaut | Multicriteria Scheduling. theory, models and algorithms[END_REF]: i) aggregation approach, ii) -approach and iii) Pareto approach. By studying the possible transformation of the addressed problem into a mono-criteria one, we remarked that no criterion is dominant. Therefore, the Pareto approach seems us the most appropriate for addressing our problem. A multi-objective problem can be defined as:

min f (x) = (f 1 (x), ..., f n (x))
where x ∈ X; X is a set of feasible solutions (or decision space). A feasible solution x ∈ X is a Pareto solution (or efficient solution) if there does not exist any x ∈ X such that: ∀i ∈ {1, ..., n}, fi(x ) ≤ fi(x) ∧ ∃j ∈ {1, ..., n}, fj(x ) < fj(x)

Figure 2 shows solutions for the minimization problem of two conflicting objectives f 1 (x) and f 2 (x). The solution x 4 dominates x 1 , because both objective values of x 4 are lower than those of x 1 (i.e. f 1 (x 4 ) < f 1 (x 1 ) and f 2 (x 4 ) < f 2 (x 1 )). However, x 2 does not dominate x 4 , since f 1 (x 2 ) > f 1 (x 4 ). We say that x 4 and x 2 are non-dominated solutions (Pareto solutions). The set of non-dominated solutions forms a nondominated front, denoted P S ⊆ X (see Figure 2).

IV. APPROACHES FOR TASKS ALLOCATION AND

SCHEDULING IN CLOUD CONTEXTS In the following, we detail the three proposed complementary approaches. The first one is based on the minimization of the overall execution time, while the second one aims to minimize the cost incurred using a set of resources. The third approach allows to select only the Pareto solutions obtained by the two approaches.

A. The cost-based approach

In the cost-based approach, we focus only on minimizing the execution and communication costs of using a set of resources incurred by the execution of a given process. However, for each obtained feasible solution by using an allocation strategy the overall corresponding completion time is computed. Recall that the objective is to assign tasks to resources respecting the precedence constraints. The cost-based approach is an application allocation and scheduling algorithm for an unbounded number of virtual machines and a bounded number of human resources. As mentioned previously, users can request and obtain sufficient virtual machine at any time, while a human resource cannot execute more than one task at any time (i.e. human resources cannot execute tasks in parallel). The approach proposed has three major phases, namely: i) tasks sorting phase, ii) resource allocation phase and iii) Pareto selection phase. An overview of the cost-based approach is shown by Algorithm 1.

1) Tasks sorting phase: In order to group the tasks that are independent of each other, the given business process (DAG) is traversed in a top-down fashion to sort tasks at each level. As a result, tasks belonging to the same level do not exchange data and can be executed in parallel (because they are not related by precedence constraints). Given a DAG G = (T, E), the level 1 and the last level contains respectively the input t input task and the exist t exit task. Level k, denoted l k , consists of all tasks t j such that for all edges (t i , t j ), task t i is in a level k < k and there exists at least one edge (t i , t j ) such that t i is in level k -1. Let L be the number of levels of a given process.

For instance, for the tasks graph given in Figure 1, there are five levels (i.e. L = 5): level l 1 consists of task t 1 (initial task), level l 2 consists of task t 2 , t 3 , t 4 , level l 3 consists of tasks t 5 , t 6 , level l 4 consists of task t 7 , t 8 , t 9 and the level five l 5 contains task t 10 (exit task). The line 2 of Algorithm 1 corresponds to the tasks sorting phase.

2) Resource allocation phase: In this phase the selection of an "optimal" resources for each task is decided. In other words, the resource which gives minimum execution and communication costs for a task is selected and the task is assigned to that resources. More precisely, given the labeling of tasks in the graph levels, the allocation process explores the graph by starting the allocation tasks of level k, where the value of k is given by the following strategies: i) top-down, iii) bottom-up and iii) mixed exploration and strategy.

3) The top-down: strategy consists of starting by the allocation of the initial task (level l 1 ) to the resource which gives minimum execution cost. After this assignment, the graph is traversed in a top-down fashion from level 2 to level L. At level k, the task is assigned to the resource which gives minimum of execution and communication costs as follows:

∀t i ∈ l k , r(t i ) = r s such that:

EC(t i , r s ) + t h ∈pred(ti) T C(r(t h ), r(t i )) = min rj    EC(t i , r j ) + t h ∈pred(ti) T C(r(t h ), r(t i ))    (9)
where pred(t i ) is the set of immediate predecessors of task t i .

The lines 3 (with k = 1) to 10 of Algorithm 1 corresponds to the top-dow strategy.

4) The bottom-up: strategy consists on starting by the allocation of the finish task (the last level). After this allocation, the graph is traversed in a bottom-up fashion from level L -1 to level 1. At level k, the task is assigned to the resource which gives minimum of execution and communication costs as follows:

∀t i ∈ l k , r(t i ) = r s such that: EC(t i , r s ) + t h ∈succ(ti) T C(r(t i ), r(t h )) = min rj    EC(t i , r j ) + t h ∈succ(ti) T C (r(t i ), r(t h ))    ( 10
)
where succ(t i ) is the set of immediate successors of task t i .

The lines 11 (with k = L) to 15 of Algorithm 1 corresponds to the bottom-up strategy.

5) The mixed: strategy starts by assigning the tasks belonging to the intermediate level, i.e. k ∈ {2, ..., L -1}. Given starting level k, therefore the assignment of the tasks belonging to this level is only based on the execution cost EC(t i , r j ), given by the following equation:

∀t i ∈ l k , r(t i ) = r k such that: EC(t i , r k ) = min rj EC(t i , r j ) (11)
For the tasks belonging to the level k < k and k > k, the assignment of a task t i is impacted by the previous assignments by taking into account the both costs (execution and communication costs), using bottomp-up and top-down strategy respectively. Equation 9 and 10 are recursively applied until all the tasks are assigned using the mixed strategy for all k ∈ {2, ..., L -1}. In the case of k ∈ {1, L}, we use the top-down and bottom-up strategy respectively. Note that, equations 9 and 10 have respectively one variable (r(t i )) because r(t h ) is computed in the previous iteration.

The lines 4-17 (k ∈ {2, ..., L -1}) of Algorithm 1 corresponds to the mixed strategy.

Hence, for the mixed strategy we obtain L -2 solutions (each of them consists on the assignment of all tasks) and one solution respectively for top-down and bottom-up strategy.

6) Pareto selection phase: Recall that at the end of the previous phase a L (the number of levels of a given process) assignment of all tasks is obtained. In this phase, we first compute the overall completion time (using Equation 2, 3 and 4) corresponding to each assignment and then only nondominated solutions are maintained. The lines 18 and 19 of Algorithm 1 corresponds to the Pareto selection phase.

Algorithm 1 Cost-based approach

1: read the DAG, the RG and associated attributes values; 2: sort tasks at each level by traversing the DAG in a top-down fashion; // let L be the set of levels and l k the tasks // belonging to the level k 3: k ← 1; // first level 4: while (k ≤ L) do 5: for all tasks ti ∈ l k , compute r(ti) using equation 11// assign task ti to the resource r(ti) // that minimizes the execution cost mincost[k, ti] ← r(ti); // mincost is a L × m matrix // where line k corresponds to the assignment of all tasks // obtained starting by the tasks assignement belonging to // this level 6: h ← k + 1; // compute r(ti) for all tasks that belong to levels h > k 7: while (h ≤ L) do 8: for all tasks ti ∈ l h , compute r(ti) using equation 9 mincost[k, ti] ← r(ti); 9: h ← h + 1 10: end while 11: h ← k -1; // compute r(ti) for all tasks that belong // to levels h < k 12: while (h ≥ 1) do 13: for all tasks ti ∈ l h , compute r(ti) using equation 10 mincost[k, ti] ← r(ti);

B. The time-based approach

While the previous approach is based on minimizing the cost function, the time-based approach, detailed in the following, is based on the makespan criterion. More precisely, the timebased approach attempts to minimize the overall completion time (i.e. execution and communication time). As the costbased approach, the time-based approach is an application matching and scheduling algorithm for an "unbounded" number of virtual machines and bounded number of human resources, which has three major phases, namely: a tasks sorting phase i), ii) an allocation phase and iii) Pareto selection phase. This approach contains the same steps as the previous approach. The Equations 11, 9 and 10 are replaced by Equations 12, 13 and 14 respectively.

1) Tasks sorting phase: This phase is the same as for the cost-based algorithm. Recall that this phase allows to group the workflow application tasks that are independent of each other.

2) Resource allocation phase: The cost-based and the timebased approaches differ mainly at resource allocation phase. Indeed, the first one approach focus on minimizing the cost function while the second approach attempts to minimize the time function. The objective of the resource allocation phase of the time-based approach is to choose the resource that minimizes the actual finish time of each task and the task is assigned to that resource. The three allocation strategies, detailed above, are also applied to explore the given graph (DAG). Therefore, the obtained solutions number is equal to the number of graph levels (i.e. L). So, If the resource allocation phase starts at the level k, therefore the assignment of the tasks belonging to this level is only based on the execution time ET (t i , r j ), given by the following equation: ∀t i ∈ l, r(t i ) = r k such that:

ET (t i , r k ) = min rj ET (t i , r j ) (12)
For the tasks belonging to the level l k+1 and l k-1 , the allocation decision of a task t i are recursively defined by respectively the following equations until all the tasks are assigned:

∀t i ∈ l k+1 , r(t i ) = r k such that: ET (t i , r k ) + t h ∈pred(ti) T T (r(t h ), r(t i )) = min rj    ET (t i , r j ) + t h ∈pred(ti) T T (r(t h ), r(t i ))    ( 13
)
∀t i ∈ l k-1 , r(t i ) = r k such that: ET (t i , r k ) + t h ∈succ(ti) T C(r(t i ), r(t h )) = min rj    ET (t i , r j ) + t h ∈succ(ti) T C (r(t i ), r(t h ))    (14)
3) Pareto selection phase: Recall that at the end of the previous phase L assignment of all tasks is obtained. In this phase, we first compute the overall execution cost (using

V LB V Opt V algo
δ Opt -algo δ LB-algo Fig. 3. Gap between the obtained solutions, the optimal and the lower solutions Equation 8) corresponding to each assignment and then only non-dominated solutions are maintained.

C. Cost-time-based approach

The cost-time-based approach objective is to offer a guidance for choosing between different offering in order to complete the workflow application considering the two criterion together. It is composed by two phases. The first one consists to execute both algorithms (cost-based and time-based algorithms). The second one allows to select only the non-dominated solutions.

V. EXPERIMENTAL RESULTS AND DISCUSSION

In order to assess the quality of the obtained solutions by our algorithms, we need to compare the obtained solutions with an optimal solution of the problem. But as the problem is NP-hard, the optimal solution cannot be obtained in polynomial time, thus a relaxation of the original problem is needed to obtain a lower bound of the optimal solution in polynomial time. Then instead to compare our solutions with optimal solution of the original problem, we compare it with the lower bound. As showed in Figure 3, δ LB-algo is the gap between the solution of our algorithm (V algo ) and the lower bound (V LB), whereas δ Opt-algo is the effective gap between the optimal solution (V opt ) and the solution obtained by our algorithm.

A. Lower bounds

For time criterion, a lower bound LB t is obtained by the execution of the t exit task in the critical path of the relaxed problem for the workflow G = (T, E), in which each task t j is executed on the resource r(t j ) with the minimal execution time, i.e., ET (t j , r j ) = min r k ET (t j , r k ) and each edge (t i , t j ) of G is valued with a lower bound of the transfer time between t i and t j . The transfer time T T (i, j) is defined by the following formula:

T T (t i , t j ) = min    ET (t j , r(t i )) -ET (t j , r(t j )) (1) ET (t i , r(t j )) -ET (t i , r(t i )) (2) ET (t i , t j , r k ) ( 3
)
where ET (t i , t j , r k ) = min r l {ET (t i , r l (t j )) -ET (t i , r(t i )) + ET (t j , r l (t j )) -ET (t j , r(t j ))}. In the formula of T T (t i , t j ), the first term (1) represents the additional execution time of task t i if it is executed on resource r(t j ) instead of r(t i ), the second term (2) represents the additional execution time of task t j if it is executed on resource r(t i ) instead of r(t j ), and the last term (3) represents the additional execution times of tasks t i and t j if they are executed on resource r k (t i ) instead of r(t i ), and on resource r k (t j ) instead of V r(t j ), respectively.

B. Data setting

In our experiment, we simulate a Cloud computing environment in which five families of instances are randomly generated. A family is associated on tasks n ∈ {50, 100, 300, 600, 1000}. Each family of instances is subdivided into three series S, M and L with small, medium and large density of precedence constraints, respectively. For each pair (t i , t j ) of tasks it is decided with a certain probability p that t i precedes t j , such that G is acyclic. For the series S, M , and L the corresponding probabilities are p S = 0.2, p M = 0.4 and p L = 0.6. We consider the number of virtual machines types m as a function of the number of tasks, i.e., m = n/10. Also, the number of human resources is m = n/10. As mentioned previously, for the real resource availability we use exponential smoothing. We assume that each task can be executed on all virtual machines types. For all families of instances, processing times of tasks on virtual machines are generated according to an uniform distribution, varying in [START_REF]Workflow Management Coalition: Terminology & Glossary[END_REF][START_REF] Deelman | Workflows and e-Science: An overview of workflow system features and capabilities[END_REF]. The unit execution cost on each virtual machine type is uniformly generated in interval [0.1, 0.9]. The bandwidth matrix between virtual machines is uniformly generated, in the interval [START_REF]Workflow Management Coalition: Terminology & Glossary[END_REF][START_REF] Mladen | Cloud Computing -Issues, Research and Implementations[END_REF] and the transfer data matrix D is also uniformly generated in interval [START_REF] Deelman | Workflows and e-Science: An overview of workflow system features and capabilities[END_REF]90]. Finally the transfer C out and the receiving cost C in of virtual machines are uniformly generated in the interval [START_REF]Workflow Management Coalition: Terminology & Glossary[END_REF][START_REF] Mladen | Cloud Computing -Issues, Research and Implementations[END_REF]. Each series consists of 1000 instances.

C. Summary of results and discussion

The obtained Pareto solutions divided by the number of the overall obtained solutions is considered as the ratio of each approach. Figure's 4 histograms indicate two things. First, in most cases the ratio increases with the density of precedence constraints (i.e p), which is mainly due to the importance of time and cost communications. So, It is interesting to consider not all levels of the graph, but only those where the obtained solution is very likely a Pareto solution. Second, the ratio of Pareto solutions obtained by the cost-time based approach is almost equal to the sum of the ratios of the costbased and the time-based approach divided by two, which means that no criterion dominates the other one. Therefore, the Pareto approach is the most appropriate one to deal with the allocation and scheduling workflow tasks in Cloud computing environment.

The result of the quality of the obtained solutions by our approaches is given in Figure 5, plotting the minimum D min , the average D average and the maximum D max performance criterion. The D min , D average and D max are obtained by dividing the minimum value, the average value and the maximum value among all obtained Pareto solutions and the lower bound, respectively, by considering the two criteria (i.e. cost and time). These results show that in average the considered performance criterion do not exceed 2.9, which means that the obtained Pareto solutions are less than to 2.9 times the lower bound. Note that this observation is the same in three proposed approaches.

VI. RELATED WORK AND DISCUSSION

Due to its importance on performance, the workflow tasks allocation and scheduling problem on heterogeneous computing environment such as grid has been intensively explored. Beside, the tasks allocation to compute resources is an NP-complete problem in the general form [START_REF] Gary | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. So, past works have proposed heuristic driven approaches for scheduling workflow applications [START_REF] Topcuoglu | Performance effective and lowcomplexity task scheduling for heterogeneous computing[END_REF] [START_REF] Ilavarasan | Low complexity performance effective task scheduling algorithm for heterogeneous computing environments[END_REF]. These heuristics cannot be applied in Clouds computing environments because they require a bounded number of resources.

Therefore, allocation and scheduling workflow tasks in Cloud has gained popularity in recent times and few algorithms are proposed to deal with this problem [19] [20] [21] [START_REF] Van Den Bossche | Cost-Efficient Scheduling Heuristics for Deadline Constrained Workloads on Hybrid Clouds[END_REF]. In [START_REF] Tordsson | Cloud brokering mechanisms for optimized placement of virtual machines across multiple providers[END_REF], the authors developed a model that uses particle swarm optimization (PSO) for task-resource mapping to minimize the overall cost of execution such that it completes within deadline that user specifies. To tackle the problem of choosing resource among different cloud providers, a binary integer program is proposed in [START_REF] Tordsson | Cloud brokering mechanisms for optimized placement of virtual machines across multiple providers[END_REF], where the objective is to minimize the total infrastructure capacity under budget and load balancing constraints. In [START_REF] Breitgand | Policy-driven service placement optimization in federated clouds[END_REF], the authors presented a model for formulation of the generalized federated placement problem and application of this problem to load balancing and consolidation within a cloud, where one cloud can subcontract workloads to partnering clouds to meet peaks in demand. They used an Integer Program formulation of the placement program and provide a 2-approximation algorithm. In [START_REF] Den Bossche | Cost-optimal scheduling in hybrid iaas clouds for deadline constrained workloads[END_REF], the authors a binary integer program formulation for cost-optimal scheduling in hybrid IaaS clouds for deadline constrained workloads. In [START_REF] Van Den Bossche | Cost-Efficient Scheduling Heuristics for Deadline Constrained Workloads on Hybrid Clouds[END_REF], the authors proposed a set of heuristics to cost-efficiently schedule deadline-constrained computational applications on both public cloud providers and private infrastructure. Although, most of these studies consider unbounded number of resources, however, they convert the initial problem (bi-cretiria) to theconstraints problem.

To overcome these limitations, we propose new approaches which are distinct from the related work as they take into account Clouds elasticity feature, which means that users can rent and release resources according to the need of its applications. Moreover, our approaches consider the overall completion time and the execution cost together, where the problem of tasks allocation and scheduling problem has not been converted neither to mono-criterion nor to -constraints problem. Therefore, the matching and scheduling problem described here does not appear to have been studied before. The work presented in this paper is an extension of our previous works [START_REF] Bessai | Bi-criteria workflow tasks allocation and scheduling in Cloud computing environments[END_REF] [START_REF] Bessai | Multi-objective Resources Allocation Approaches for Workflow Applications in Cloud Environments[END_REF].

VII. CONCLUSION

This paper deals with the allocation and scheduling workflow tasks in Cloud contexts. More precisely, as the problem is computational hard we have proposed three approaches based respectively on the overall execution time, on the cost incurred using a set of resources (i.e. virtual machines and human resources) and on the both criterion. The obtained results are very encouraging but one the same time open new and interesting questions. We focus on several perspectives. First, we interested in applying the proposed approaches on realworld applications. Then, we want to compare the obtained results with the obtained ones in the case of average-analysis. Finally, we interested to extend the proposed approach to take into account more complex workflow patterns.

Fig. 1 .

 1 Fig. 1. An illustrative business process application and a set of resources (virtual machines and human resources)

Fig. 2 .

 2 Fig. 2. Four non-dominated solutionand four dominated solutions

Fig. 4 .Fig. 5 .

 45 Fig. 4. Scheduling 1000 randomly generated workflows versus the ratio of the obtained Pareto solutions for each proposed approach

  14: h ← h -1 15: end while 16: k ← k + 1 17: endwhile 18: for each assignment, compute AF T (texit) using equations 2, 3 and 4; 19: select the Pareto solutions among L solutions;


Kahina Bessai

Samir Youcef

Ammar Oulamara

Claude Godart

Selmin Nurcan

Bi-criteria workflow tasks allocation and scheduling in Cloud computing environments

Although there are few efficient algorithms in the literature for scientific workflow tasks allocation and scheduling for heterogeneous resources such as those proposed in grid computing context, they usually require a bounded number of computer resources that cannot be applied in Cloud computing environment. Indeed, unlike grid, elastic computing, such as Amazon's EC2, allows users to allocate and release compute resources on-demand and pay only for what they use. Therefore, it is reasonable to assume that the number of resources is infinite. This feature of Clouds has been called "illusion of infinite resources". However, despite the proven benefits of using Cloud to run scientific workflows, users lack guidance for choosing between multiple offering while taking into account several objectives which are often conflicting.

On the other side, the workflow tasks allocation and scheduling have been shown to be NP-complete problems. Thus, it is convenient to use heuristic rather than deterministic algorithm. The objective of this paper is to design an allocation strategy for Cloud computing platform. More precisely, we propose three complementary bi-criteria approaches for scheduling workflows on distributed Cloud resources, taking into account the overall execution time and the cost incurred by using a set of resources.

I. INTRODUCTION

Cloud computing is based on resources virtualization and its business model is based on the concept of paying only for what customers use, which overcome the limitations of the traditional software sales model. In this context, IT organizations need to think in terms of managing services rather than managing devices.

In practice, Cloud service providers offer services that can be classified in three categories, [START_REF] Mell | The NIST Definition of Cloud Computing[END_REF] [START_REF] Buyya | Cloudbus toolkit for marketoriented cloud computing[END_REF] namely:

• Software as a service (SaaS) is a software distribution model in which applications are hosted by a service provider delivered as a service to consumer but without controlling the host environment. Examples of this model are the Google Apps (http://www.google.com/apps/) and Salesforce (http://www.salesforce.com/). • Platform as a Service (PaaS) allows customers to rent virtualized servers for using existing applications or developing and testing new ones. Examples of this model are the Google App Engine (http://www.code. google.com/in1/en/appengine/) and Amazon Web Services (http://www.aws.amazon.com/) .

• Infrastructure as a Service (IaaS) allows customers to use computing resources such as storage and processing power, and they pay on a per-use basis. Amazon Elastic Compute Cloud (http://aws.amazon.com/ec2) is an example of this model. As a result, the Cloud computing has quickly changed the way that compute resources can be used and allows users to access computer on the fly, according to the application's needs. For instance, currently Amazon's EC2 provide a Web service through which user can boot an Amazon Machine Image for creating a virtual machine that can run any desired software.

Furthermore, unlike grids, Could platforms give the illusion that the available computing resources are unlimited. This means that users can request, and are likely to obtain, sufficient resources for their need at any time. This feature of Clouds has been called "illusion of infinite resources" [START_REF] Juve | Scientific workflow applications on Amazon EC2[END_REF] [START_REF] Juve | Scientific Workflows in the Cloud[END_REF]. The elasticity is one of the most important feature of Clouds which means that users can release resources on-demand. In addition for provisioning on-demand and the elasticity characteristics, unlike grids, Cloud platforms allow to users to directly allocate resources as required to schedule their computations. Due to these characteristics and the Cloud model's proven benefits, such as flexibility, scalability and cost-effectiveness, it has been rapidly gaining interest for distributing many enterprise software such as banking, e-commerce business software [START_REF] Deelman | Workflows and e-Science: An overview of workflow system features and capabilities[END_REF].

Generally, two most important types of workflow are distinguished, namely: i) business process workflows and ii) scientific workflows. In this paper, we focus only on the second type of workflows. The extension to the first category is under investigation. In fact, Cloud computing paradigm has also naturally and rapidly gained interest in the scientific community for workflow simulation, image processing, data analysis, etc., in many scientific disciplines, such that astronomy and bioinformatic domains [START_REF] Mladen | Cloud Computing -Issues, Research and Implementations[END_REF]. Indeed, workflows are able to be used, in many situations, to express different types of scientific analysis.

Scientific workflow tasks are commonly represented as a directed acyclic graph (DAG) in which nodes represent application tasks and edges represent dependencies between these tasks [START_REF] Topcuoglu | Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing[END_REF]. One well-known challenge for executing workflow applications on Cloud is tasks allocation and schedul-ing, that is, making decisions for mapping computations to resource in order to optimize some performance metric, such that completion time and execution cost, and so that tasksprecedence requirement are satisfied. The tasks matching and scheduling is NP-complete in the general case [START_REF] Gary | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], as well as some restricted cases [START_REF] Ullman | NP-Complete Scheduling Problems[END_REF] [START_REF] Topcuoglu | Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing[END_REF]. Therefore, it is convenient to use heuristic rather than an exact algorithm to deal with this problem.

The objective of this paper is to design allocation and scheduling strategies for Cloud computing platforms. More precisely, we consider the bi-criteria approach for the allocation and scheduling of workflow applications on Cloud. The objectives are: i) minimizing the workflow application completion time and ii) minimizing the amount cost incurred by using resources.

Before summarizing the contributions of this paper, we start by giving an overview on the approaches used to deal with bi-criterion allocation and scheduling problems that are extensively considered in the literature. Mainly three streams are considered [10] [11] [12]:

• Aggregation approach: both criteria f 1 and f 2 are aggregated into one composite function F(f 1 (π), f 2 (π)) for some given F , usually an additive function, where π is the schedule. In this approach the bi-criteria problem is transformed into a mono-criterion problem. • -approach: in this approach the criterion f 2 is minimized under the additional constraint f 1 ≤ , where is a given value fixed by decision maker. This approach is also viewed as a lexicographical approach in which the more important criterion f 1 is minimized and let f * 1 the obtained optimal value, and then the second criterion f 2 is minimized under the additional constraint f 1 ≤ f * 1 , here = f * 1 .

• Pareto approach: this approach is applied when no criterion is dominant, in that case no-dominant solutions are computed, also called Pareto solutions, that will be introduced in Section IV. By studying the possible transformation of the addressed problem in this paper into mono-criteria one, we remarked that no criterion is dominant. Therefore, the Pareto approach seems us the most appropriate for addressing our problem.

To summarize, in this paper we make the following contributions:

1) We formalize a model for workflow tasks matching and scheduling in Cloud environment. 2) We propose a first approach for workflow tasks matching and scheduling based on minimizing the cost execution incurred by using a set of resources. 3) We propose a second approach based on the overall completion time. 4) Finally, we present a third approach combining the above objectives. The remainder of the paper is organized as follows. Section II presents related works and compare them with our proposition. Section III describes our system model and the objective functions. In Section IV, we detail the proposed approaches for workflow tasks matching and scheduling. Experimental results are presented in Section V. Section VI summarizes the contributions and outlines areas for future research.

II. RELATED WORK

Due to its importance on performance, the workflow tasks allocation and scheduling problem on heterogeneous computing environment such as grid has been intensively explored. Beside, the tasks allocation to compute resources is an NPcomplete problem in the general form [START_REF] Gary | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. So, past works have proposed heuristic driven approaches for scheduling workflow applications [START_REF] Topcuoglu | Performance effective and lowcomplexity task scheduling for heterogeneous computing[END_REF] [START_REF] Ilavarasan | Low complexity performance effective task scheduling algorithm for heterogeneous computing environments[END_REF]. These heuristics cannot be applied in Clouds computing environments because they require a bounded number of resources.

Therefore, allocation and scheduling workflow tasks in Cloud has gained popularity in recent times and few algorithms are proposed to deal with this problem [START_REF] Tordsson | Cloud brokering mechanisms for optimized placement of virtual machines across multiple providers[END_REF] [16] [17] [18]. In [START_REF] Tordsson | Cloud brokering mechanisms for optimized placement of virtual machines across multiple providers[END_REF], the authors developed a model that uses particle swarm optimization (PSO) for task-resource mapping to minimize the overall cost of execution such that it completes within deadline that user specifies. To tackle the problem of choosing resource among different cloud providers, a binary integer program is proposed in [START_REF] Tordsson | Cloud brokering mechanisms for optimized placement of virtual machines across multiple providers[END_REF], where the objective is to minimize the total infrastructure capacity under budget and load balancing constraints. In [START_REF] Breitgand | Policy-driven service placement optimization in federated clouds[END_REF], the authors presented a model for formulation of the generalized federated placement problem and application of this problem to load balancing and consolidation within a cloud, where one cloud can subcontract workloads to partnering clouds to meet peaks in demand. They used an Integer Program formulation of the placement program and provide a 2-approximation algorithm. In [START_REF] Den Bossche | Cost-optimal scheduling in hybrid iaas clouds for deadline constrained workloads[END_REF], the authors proposed a binary integer program formulation for cost-optimal scheduling in hybrid IaaS clouds for deadline constrained workloads. In [START_REF] Van Den Bossche | Cost-Efficient Scheduling Heuristics for Deadline Constrained Workloads on Hybrid Clouds[END_REF], the authors proposed a set of heuristics to cost-efficiently schedule deadline-constrained computational applications on both public cloud providers and private infrastructure. Although, most of these studies consider unbounded number of resources, however, they convert the initial problem (bi-cretiria) to theconstraints problem.

To overcome these limitations, we propose new approaches which are distinct from the related work as they take into account Clouds elasticity feature, which means that users can rent and release resources according to the need of its applications. Moreover, our approaches consider the overall completion time and the execution cost together, where the problem of tasks allocation and scheduling problem has not been converted neither to mono-criterion nor to -constraints problem. Therefore, the matching and scheduling problem described here does not appear to have been studied before.

III. WORKFLOW TASKS ALLOCATION AND SCHEDULING PROBLEMS FORMULATION IN CLOUD COMPUTING

In the following, we start by refining the problem definition and then present the cost and time objective functions that we consider in this work.

Recall that the main scope of this paper is to deal with the workflow tasks allocation and scheduling problem in the Cloud environment. Scientific workflow applications are commonly represented as a directed acyclic graph (DAG). Formally, a workflow application is a DAG represented by G = (T, E), where T = {t 1 , ..., t n } is a finite set of tasks. E represents the set of directed edges. An edge (t i , t j ) of graph G corresponds to the data dependencies between these tasks (the data generated by t i is consumed by t j ). Task t i is called the immediate parent of t j which is the immediate child task of t i . Note that the child task cannot be executed until all of its parents tasks are completed. In a given graph, a task without any precedents is called an input task, denoted t input and a task without successors is called an exit task, denoted t exit . Let Data be a n × n matrix of communication data, where data[i, j] is the amount of data required to be transmitted from task t i to task t j .

Most of the workflow tasks allocation and scheduling algorithms require single input (t input ) and single exit (t exit ) task graphs. So, if there is more than one input (exit) task, they are connected to a zero-cost (and zero-time) pseudo-input (-exit) task with zero communication cost and time, which does not affect the allocation and the schedule. This modification allows to obtain a DAG with only one input and one exit tasks.

Moreover, a task is an indivisible unit of work and is nonpreemptive. Figure 1 (left side) shows an example of workflow application defined by ten tasks, which are represented as nodes. The dependencies between tasks are represented as arrows. The initial task may have an input file denoted (input.file) and the exit task produces an output file (output.file).

To execute a given workflow application (DAG), an infinite set of resources (virtual machine) can be used on-demand. The latters are represented as a directed graph denoted RG. Formally, a resources graph is represented by RG = (V M, V ), where V M = {V M 1 , ..., V M m } is a finite set of virtual machines types that define a virtual machine images and a data center locations. However, we consider that there is enough virtual machines for each type. Thus, a costumer can request and obtain sufficient virtual machines at any time. This assumption is reasonable in rather Cloud computing environment because it gives for user an "illusion of infinite resources". When there is no ambiguity, we omit term type and use virtual machine instead virtual machine type. V represents the set of directed edges. Each edge is denoted (V M i , V M j ) corresponding to the link between these virtual machines. Let B be a m × m matrix, in which B[i, j] is the bandwidth between virtual machines V M i and V M j , where B[i, i] -→ ∞ means that there is no transfer data. Figure 1 (right side) shows an example of resources graph with real-life measurement of data transfer speeds (bandwidth) between different data centers of the Cloud provider Amazon.

Let V M (t j ) denotes the virtual machine that executes task t j . The transfer time T T (V M (t i ), V M (t j )), which is for transferring data from task t i (executed on V M (t i )) to task t j (executed on V M (t j )) is defined by:

T T (V M (t i ), V M (t j )) = data[i,j] B[V M (ti),V M (tj )]
Let ET be a n × m execution time matrix in which ET (t i , V M j ) gives the execution time estimation to complete task t i on virtual machine V M j . The real execution of a given task depends on the amount of input generated data.

Let U EC be a m-dimensional unit execution cost vector, where U EC(V M j ) represents the cost per time unit incurred by using the virtual machine V M j . Let EC be a n × m execution cost matrix in which EC(t i , V M j ) gives the execution cost to complete task t i on virtual machine V M j defined by:

EC(t i , V M j ) = ET (t i , V M j ) × U EC(V M j ) We assume that the data transfer cost T C(V M (t i ), V M (t j ))
, which is the cost incurred due to the transfer of data from task t i (executed on V M (t i )) to task t j (executed on V M (t j )), is defined by:

T C(V M (ti), V M (tj)) = data[i, j] × (Cout(V M (ti)) + Cin(V M (tj)))
where C out (V M (t i )) and C in (V M (t j )) represent respectively the cost of transferring data from V M (t i ) and the cost of receiving data on V M (t j ). The transferring data cost is determined by mutual agreement between the consumer and the provider in the Service Level Agreement (SLA) [START_REF] Mell | The NIST Definition of Cloud Computing[END_REF].

A. Time objective function

Before presenting the time objective function, it is necessary to define the ST and F T attributes, which are derived from a given partial allocation and scheduling of tasks to virtual machines (i.e. a task t i is assigned to virtual machine V M (t i )). The partial allocation and scheduling refers to the fact that for each task the ST and FT values are computed using only the tasks that must be performed before it as shown in the following. More precisely, ST (t j ) and F T (t j ) are the earliest start execution time and the earliest finish execution time of task t j . For the input task t input :

ST (t input ) = 0, F T (t input ) = ST (T input ) + ET (t input , V M (t input )) (1)
For the other tasks in the graph, the ST and the F T values are computed recursively, starting from the initial task, as shown in Equation 2 and Equation 3. In order to compute the F T of a task t j , all immediate predecessor tasks of t j must have been assigned and scheduled with the consideration of the transfer time:

F T (t j ) = ST (t j ) + ET (t j , V M (t j )) (2)
ST (t j ) = max tp∈pred(tj ) {F T (t p ) + T T (V M (t p ), V M (t j ))}
(3) where pred(t j ) is the set of immediate predecessors of task t j .

After all tasks in a graph are scheduled, the schedule length (i.e., the overall completion time) will be the finish time of the exit task. The schedule length, also called makespan, is defined as:

makespan = F T (t exit ) (4)
Therefore, the time objective function is to determine the assignment of tasks of a given workflow application to virtual machines such that its schedule length is minimized. Fig. 1. A workflow application and a set of virtual machines

B. Cost objective function

In the following, we focus on the cost objective function which is the total expense for workflow tasks execution including i) the tasks execution cost and ii) the data transfer cost between the used virtual machines. The cost function is a structure independent criterion defined as the sum of the costs of executing all workflow tasks, given by:

cost = n j=1    EC(V M (tj)) + p∈pred(t j ) T C(V M (tj), V M (tp))    (5)
Thus, the cost objective function is to determinate the assignment of tasks of a given workflow application such that its overall execution cost is minimized.

The problem addressed in this work deals with the tasks workflow application allocation and scheduling while simultaneously minimizing the makespan and the overall cost execution.

As mentioned previously, this problem can be approached in several ways. In our work, we have opted for the effective solutions (Pareto solutions) computation. To achieve this objective, we propose in the following three multi-objective approaches. The first one is based on the overall cost execution function while the second one is conducted by the makespan function. Finally, we propose an approach taking into account the two functions together.

IV. WORKFLOW TASKS ALLOCATION AND SCHEDULING APPROACHES IN CLOUD COMPUTING CONTEXT

As mentioned above, we propose in the following three algorithms for allocation and scheduling workflow application in Cloud computing environment. More precisely, the first algorithm aims to minimize the execution and communication costs (cost-based approach) using several allocation strategies. For each obtained solution the overall completion time corresponding is computed. The second algorithm proceeds similarly as the first one by attempting to minimize the execution and the communication times (time-based approach) and for each obtained solution the overall computation cost corresponding is computed. Finally, we propose a third algorithm, called costtime-based approach, based on the obtained Pareto solutions by the two first algorithms. In other words, using the solutions produced by the cost-based and the time-based approaches only the non-dominated solutions are selected. A multi-objective problem can be defined as: min f (x) = (f 1 (x), ..., f n (x)) where x ∈ X; X is a set of feasible solutions (or decision space). A feasible solution x ∈ X is a Pareto solution (or efficient solution) if there does not exist any x ∈ X such that ∀i ∈ {1, ..., n}, f i (x ) ≤ f i (x) ∧ ∃j ∈ {1, ..., n}, f j (x ) < f j (x)

Figure 2 shows solutions for the minimization problem of two conflicting objectives f 1 (x) and f 2 (x). The solution x 4 dominates x 1 , because both objective values of x 4 are lower than those of x 1 (i.e. f 1 (x 4 ) < f 1 (x 1 ) and f 2 (x 4 ) < f 2 (x 1 )). However, x 2 does not dominate x 4 , since f 1 (x 2 ) > f 1 (x 4 ). We say that x 4 and x 2 are non-dominated solutions (Pareto solutions). The set of non-dominated solutions forms a nondominated front.

Cost-based approach

In the cost-based approach, we focus only on minimizing the execution and communication costs of using a set of virtual machines incurred by the execution of a given workflow. However, for each obtained feasible solution by using an allocation strategy the overall completion time corresponding is computed. Recall that the objective is to assign tasks to virtual machines respecting the precedence constraints. The cost-based approach is an application allocation and scheduling algorithm for an unbounded number of virtual machines. As mentioned previously, users can request and obtain sufficient resources at any time. The approach proposed has three major phases, namely: i) tasks sorting phase, ii) resource allocation phase and iii) Pareto selection phase. An overview of the cost-based approach is shown by Algorithm 1. Tasks sorting phase In order to group the tasks that are independent of each other, the given workflow (DAG) is traversed in a top-down fashion to sort tasks at each level. As a result, tasks belonging to the same level do not exchange data and can be executed in parallel (because they are not related by precedence constraints). Given a DAG G = (T, E), the level 1 and the last level contains respectively the input t input task and the exist t exit task. Level k, denoted l k , consists of all tasks t j such that for all edges (t i , t j ), task t i is in a level k < k and there exists at least one edge (t i , t j ) such that t i is in level k -1. Let L the number of levels of a given workflow.

For instance, for the tasks graph given in Figure 1, there are five levels (i.e. L = 5): level l 1 consists of task t 1 (initial task), level l 2 consists of task t 2 , t 3 , t 4 , level l 3 consists of tasks t 5 , t 6 , level l 4 consists of task t 7 , t 8 , t 9 and the level five l 5 contains task t 10 (exit task). The line 2 of Algorithm 1 corresponds to the tasks sorting phase. Resource allocation phase In this phase the selection of an "optimal" virtual machine for each task is decided. In other words, the virtual machine which gives minimum execution and communication costs for a task is selected and the task is assigned to that virtual machine. More precisely, given the labeling of tasks in the graph levels, the allocation process explores the graph by starting the allocation tasks of level k, where the value of k is given by the following strategies: i) topdown, iii) bottom-up and iii) mixed exploration and allocation strategy. The top-down strategy consists of starting by the allocation of the initial task (level l 1 ) to the virtual machine which gives minimum execution cost. After this assignment, the graph is traversed in a top-down fashion from level 2 to level L. At level k, the task is assigned to the virtual machine which gives minimum of execution and communication costs as follows:

∀t i ∈ l k , V M (t i ) = V M s such that: EC(t i , V M s ) + t h ∈pred(ti) T C(V M (t h ), V M (t i )) = min V Mj    EC(t i , V M j ) + t h ∈pred(ti) T C(V M (t h ), V M (t i ))  (6)
where pred(t i ) is the set of immediate predecessors of task t i .

The lines 3 (with k = 1) to 10 of Algorithm 1 corresponds to the top-dow strategy. The bottom-up strategy consists on starting by the allocation of the finish task (the last level). After this allocation, the graph is traversed in a bottom-up fashion from level L -1 to level 1. At level k, the task is assigned to the virtual machine which gives minimum of execution and communication costs as follows:

∀t i ∈ l k , V M (t i ) = V M s such that: EC(t i , V M s ) + t h ∈succ(ti) T C(V M (t i ), V M (t h )) = min V Mj    EC(t i , V M j ) + t h ∈succ(ti) T C (V M (t i ), V M (t h ))    (7)
where succ(t i ) is the set of immediate successors of task t i .

The lines 11 (with k = L) to 15 of Algorithm 1 corresponds to the bottom-up strategy. The mixed strategy starts by assigning the tasks belonging to the intermediate level, i.e. k ∈ {2, ..., L -1}. Given starting level k, therefore the assignment of the tasks belonging to this level is only based on the execution cost (EC(t i ), V M j ), given by the following equation:

∀t i ∈ l k , V M (t i ) = V M k such that: EC(t i , V M k ) = min V Mj EC(t i , V M j ) (8)
For the tasks belonging to the level k < k and k > k, the assignment of a task t i is impacted by the previous assignments by taking into account the both costs (execution and communication costs), using bottomp-up and top-down strategy respectively. Equation 6 and 7 are recursively applied until all the tasks are assigned using the mixed strategy for all k ∈ {2, ..., L -1}. In the case of k ∈ {1, L}, we use the top-down and bottom-up strategy respectively. Note that, equations 6 and 7 have respectively one variable (V M (t i )) because V M (t h ) is computed in the previous iteration.

The lines 4-17 (k ∈ {2, ..., L -1}) of Algorithm 1 corresponds to the mixed strategy.

Hence, for the mixed strategy we obtain L -2 solutions (each of them consists on the assignment of all tasks) and one solution respectively for top-down and bottom-up strategy. Pareto selection phase Recall that at the end of the previous phase a L assignment of all tasks is obtained. In this phase, we first compute the overall completion time (using Equation 1, 2 and 3) corresponding to each assignment and then only nondominated solutions are maintained. The lines 18 and 19 of Algorithm 1 corresponds to the Pareto selection phase.

B. Time-based approach

While the previous approach is based on minimizing the cost function, the time-based approach, detailed in the following, is based on the makespan criterion. More precisely, the time-based approach attempts to minimize the overall completion time (i.e. execution and communication time). As the cost-based approach, the time-based approach is an application matching and scheduling algorithm for an "unbounded" number of virtual machines, which has three major phases, namely: a tasks sorting phase i), ii) an allocation phase and iii) Pareto selection phase. An overview of this approach is given by Algorithm 2. Tasks sorting phase This phase is the same as for the costbased algorithm. Recall that this phase allows to group the workflow application tasks that are independent of each other. Resource allocation phase The cost-based and the time-based approaches differ mainly at resource allocation phase. Indeed, the first one approach focus on minimizing the cost function Algorithm 1 Cost-based approach 1: read the DAG, the RG and associated attributes values; 2: sort tasks at each level by traversing the DAG in a top-down fashion; // let L be the set of levels and l k the tasks // belonging to the level k 3: k ← 1; // first level 4: while (k ≤ L) do 5: for all tasks ti ∈ l k , compute V M (ti) using equation 8 // assign task ti to the virtual machine V M (ti) // that minimizes the execution cost mincost[k, ti] ← V M (ti); // mincost is a L × m matrix // where line k corresponds to the assignment of all tasks // obtained starting by the tasks assignement belonging to // this level 6: h ← k + 1; // compute V M (ti) for all tasks that belong // to levels h > k 7: while (h ≤ L) do 8: for all tasks ti ∈ l h , compute V M (ti) using equation 6 mincost[k, ti] ← V M (ti); 9: h ← h + 1 10: end while 11: h ← k -1; // compute V M (ti) for all tasks that belong // to levels h < k 12: while (h ≥ 1) do 13: for all tasks ti ∈ l h , compute V M (ti) using equation 7mincost[k, ti] ← V M (ti); while the second approach attempts to minimize the time function. The objective of the resource allocation phase of the time-based approach is to choose the virtual machine that minimizes the finish time of each task and the task is assigned to that virtual machine. The three allocation strategies, detailed above, are also applied to explore the given graph (DAG). The lines 3 (with k = 1) to 10 of Algorithm 2 corresponds to the top-dow strategy. The lines 11 (with k = L) to 15 of Algorithm 2 corresponds to the bottomp-up strategy. The lines 4-17 (k ∈ {2, ..., L -1}) of Algorithm 2 corresponds to the mixed strategy. Therefore, the obtained solutions number is equal to the number of graph levels (i.e. L). So, If the resource allocation phase starts at the level k, therefore the assignment of the tasks belonging to this level is only based on the execution time (ET (t i ), V M j ), given by the following equation:

∀t i ∈ l, V M (t i ) = V M k such that: ET (t i , V M k ) = min V Mj ET (t i , V M j ) (9)
For the tasks belonging to the level l k+1 and l k-1 , the allocation decision of a task t i are recursively defined by respectively the following equations until all the tasks are assigned:

∀t i ∈ l k+1 , V M (t i ) = V M k such that: ET (t i , V M k ) + t h ∈pred(ti) T T (V M (t h ), V M (t i )) = min V Mj    ET (t i , V M j ) + t h ∈pred(ti) T T (V M (t h ), V M (t i ))    (10) ∀t i ∈ l k-1 , V M (t i ) = V M k such that: ET (t i , V M k ) + t h ∈succ(ti) T C(V M (t i ), V M (t h )) = min V Mj    ET (t i , V M j ) + t h ∈succ(ti) T C (V M (t i ), V M (t h ))    (11)
Algorithm 2 Time-based approach 1: read the DAG, the RG and associated attributes values; 2: sort tasks at each level by traversing the DAG in a top-down fashion; // let L be the set of levels and l k the tasks // belonging to the level k 3: k ← 1; // first level 4: while (k ≤ L) do 5: for all tasks ti ∈ l k , compute V M (ti) using equation 9 // assign task t k to the virtual machine V M (ti) //that minimizes the execution time mintime[k, ti] ← V M (ti); // mincost is a L × m matrix // where line k corresponds to the assignment of all tasks // obtained starting by the tasks assignement belonging to // this level 6: h ← k + 1; // compute V M (ti) for all tasks that belong // to levels h > k 7: while (h ≤ L) do 8: for all tasks ti ∈ l h , compute V M (ti) using equation 10 mintime[k, ti] ← V M (ti); 9: h ← h + 1 10: end while 11: h ← k -1; // compute V M (ti) for all tasks that belong // to levels h < k 12: while (h ≥ 1) do 13: for all tasks ti ∈ l h , compute V M (ti) using equation 11 mintime[k, ti] ← V M (ti); Pareto selection phase Recall that at the end of the previous phase L assignment of all tasks is obtained. In this phase, we first compute the overall completion time (using Equation 5) corresponding to each assignment and then only non-dominated solutions are maintained. The lines 18 and 19 of Algorithm 2 corresponds to the Pareto selection phase.

C. Cost-time-based approach

The cost-time-based approach objective is to offer a guidance for choosing between different offering in order to complete the workflow application considering the two criterion together. It is composed by two phases. The first one consists to execute Algorithm 1 and 2. The second one allows to select only the non-dominated solutions.

D. Lower bounds

In order to assess the quality of the obtained solutions by our algorithms with experiments, we need to know the value of an optimal solution of each criterion. But as the problem is NP-Hard, we are thus looking for good lower bounds.

For time criterion, a lower bound LB t is obtained by the execution of the t exit task in the critical path of the relaxed problem for the workflow G = (T, E), in which each task t j is executed on the virtual machine V M * (t j ) with the minimal execution time, i.e., ET (t j , V M * (t j )) = min V M k ET (t j , V M k ) and each edge (t i , t j ) of G is valued with a lower bound of

8 Fig. 2 .

 82 Fig.2. Four non-dominated solution (x 2 -x 5 ) and four dominated solutions (x 1 , x 6 -x 8 ) for two objectives cost and time

14 :

 14 h ← h -1 15: end while 16: k ← k + 1 17: endwhile 18: for each assignment, compute cost using equation 5; 19: select the Pareto solutions among L solutions;

  VM 2 VM 3 VM 4 VM 5 VM 6

	Input.file	t 1			VM
						Task	VM 1
						t 1	13	19	18	11	8	16
	t 2		t 3		t 4	t 2 t 3	24 24	14 8	13 14	19 17 18 21	10 11
						t 4	21	70	16	18	21	19
	t 7	t 5	t 8	t 6	t 9	t 5 t 6 t 7 t 8 t 9 t 10	8 18 7 8 12 25	5 12 15 17 13 11	14 11 11 9 21 25	10 20 21 14 6 11	18 18 20 13 18 13	6 10 19 24 14 8
	Output.file	t 10

  14: h ← h -1 15: end while 16: k ← k + 1 17: endwhile 18: for each assignment, compute F T (texit) using equations 1, 2 and 3; 19: select the Pareto solutions among L solutions;

where ET (t i , t j , V M k ) = min V M l {ET (t i , V M l (t j )) -ET (t i , V M * (t i )) + ET (t j , V M l (t j )) -ET (t j , V M * (t j ))}.

In the formula of T T (t i , t j ), the first term [START_REF] Mell | The NIST Definition of Cloud Computing[END_REF] represents the additional execution time of task t i if it is executed on virtual machine V M * (t j ) instead of V M * (t i ), the second term [START_REF] Buyya | Cloudbus toolkit for marketoriented cloud computing[END_REF] represents the additional execution time of task t j if it is executed on virtual machine V M * (t i ) instead of V M * (t j ), and the last term (3) represents the additional execution times of tasks t i and t j if they are executed on virtual machine V M k (t i ) instead of V M * (t i ), and on virtual machine V M k (t j ) instead of V M * (t j ), respectively.

Concerning the cost criterion, we use the same relaxation than for the computation of the LB t , but on the execution cost instead the execution time. Then the lowed bound LB c for the cost criterion is calculated as the total execution cost of the tasks of the relaxed valued graph, in which each the task t j is executed on the virtual machine V M * (t j ) with minimal execution cost, i.e., EC(t j , V M * (t j )) = min V M k EC(t j , V M k (t j )) and each edge (t i , t j ) of G is valued with a lower bound of the transfer cost between t i and t j , then T C(t i , t j ) is given by the following formula:

where

In the formula of T C(t i , t j ), the term (1) represents the additional execution cost of task t i if it is executed on virtual machine V M * (t j ) instead of V M * (t i ), the second term (2) represents the additional execution cost of task t j if it is executed on virtual machine V M * (t i ) instead of V M * (t j ), and the last term (3) represents the additional execution costs of tasks t i and t j if they are executed on virtual machine V M k (t i ) instead of V M * (t i ), and on virtual machine V M k (t j ) instead of V M * (t j ), respectively.

V. EXPERIMENTAL RESULTS AND DISCUSSION

We perform an empirical study of the heuristics discussed in Section IV. In the next subsection, we describe how we generate the data. Finally, we report the results and analysis in Section V-B.

A. Data setting

In our experiment, we simulate a Cloud computing environment in which five families of instances are randomly generated. A family is associated on tasks n ∈ {50, 100, 300, 600, 1000}. Each family of instances is subdivided into three series S, M and L with small, medium and large density of precedence constraints, respectively. For each pair (t i , t j ) of tasks it is decided with a certain probability p that t i precedes t j , such that G is acyclic. For the series S, M , and L the corresponding probabilities are p S = 0.2, p M = 0.4 and p L = 0.6. We consider the number of virtual machines types m as a function of the number of tasks, i.e., m = n/10. We assume that each task can be executed on all virtual machines types. For all families of instances, processing times of tasks on virtual machines are generated according to an uniform distribution, varying in [START_REF] Mell | The NIST Definition of Cloud Computing[END_REF][START_REF] Hoogeveen | Multicriteria scheduling[END_REF]. The unit execution cost on each virtual machine type is uniformly generated in interval [0.1, 0.9]. The bandwidth matrix between virtual machines B is uniformly generated, in the interval [START_REF] Mell | The NIST Definition of Cloud Computing[END_REF][START_REF] Gary | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] and the transfer data matrix D is also uniformly generated in interval [START_REF] Hoogeveen | Multicriteria scheduling[END_REF]90]. Finally the transfer C out and the receiving cost C in of virtual machines are uniformly generated in the interval [START_REF] Mell | The NIST Definition of Cloud Computing[END_REF][START_REF] Gary | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Each series consists of 1000 instances.

B. Summary of results and discussion

The obtained Pareto solutions divided by the number of the overall obtained solutions is considered as the ratio of each approach. Figure's 3 histograms indicate two things. First, in most cases the ratio increases with the density of precedence constraints (i.e p), which is mainly due to the importance of time and cost communications. So, It is interesting to consider not all levels of the graph, but only those where the obtained solution is very likely a Pareto solution. Second, the ratio of Pareto solutions obtained by the cost-time based approach is almost equal to the sum of the ratios of the costbased and the time-based approach divided by two, which means that no criterion dominates the other one. Therefore, the Pareto approach is the most appropriate one to deal with the allocation and scheduling workflow tasks in Cloud computing environment.

The result of the quality of the obtained solutions by our approaches is given in Figure 4, plotting the minimum D min , the average D average and the maximum D max performance criterion. The D min , D average and D max are obtained by dividing the minimum value, the average value and the maximum value among all obtained Pareto solutions and the lower bound, respectively, by considering the two criteria (i.e. cost and time). These results show that in average the considered performance criterion do not exceed 2.9, which means that the obtained Pareto solutions are less than to 2.9 times the lower bound. Note that this observation is the same in three proposed approaches.

VI. CONCLUSION

In this paper, we have proposed three bi-criteria complementary approaches to tackle the allocation and scheduling workflow problems in Cloud environments. Moreover, in order to assess the quality of obtained solutions by our approaches we have proposed two lower bounds for each considered criterion. Unlike existing works, these approaches take into account two conflicting criteria simultaneously: i) execution cost and ii) execution time. Moreover, they offer more flexibility to consumer to estimate their preferences and choose a desired schedule from the obtained efficient solutions. More precisely, the first one focused on the cost incurred by using a set of resources, while the second approach attempts to minimize the Results presented in this paper are very encouraging but they in the same time open up new and interesting questions. Therefore, we focus on several perspectives for this work. Currently, we are extending the proposed approaches for business process workflows considering workflow patterns and compositions. Moreover, we plan to extend the proposed work to take into account others criteria like carbon emission and energy cost. In addition, it is interesting to adapt the proposed approaches to the case where a task cannot be executed on all virtual machine types.


Kahina Bessai
email: kahina.bessai@malix.univ-paris1.fr

Samir Youcef
email: youcef@loria.fr

Ammar Oulamara
email: oulamara@loria.fr

Claude Godart
email: godart@loria.fr

Selmin Nurcan
email: selmin.nurcan@malix.univ-paris1.fr

Multi-objective resources allocation approaches for workflow applications in Cloud environments

Introduction

The Cloud computing has quickly changed the way that compute resources can be used and allow users to access compute on the fly according to the application's need. For example, to run any desired software Amazon's EC2 provide a Web service through which users can boot an Amazon Machine Image. However, despite the proven benefits of using Cloud to execute business processes, users lack guidance for choosing between different offering while taking into account several objectives often conflicting.

Moreover, most existing workflow matching and scheduling algorithms consider only an environment in which the number of resources is assumed to be bounded. However, in distributed systems such as Cloud computing this assumption is in opposition to the usefulness of such systems. Indeed, the "illusion of infinite resources" is the most important feature of Clouds [START_REF]Workflow Management Coalition: Terminology & Glossary[END_REF] [START_REF] Buyya | Cloudbus toolkit for market-oriented cloud computing[END_REF], which means that users can request, and are likely to obtain, sufficient resources for their need at any time. Additionally to this characteristic, a Cloud computing environment can provide several advantages that are distinct from other computing environments [START_REF] Buyya | Cloudbus toolkit for market-oriented cloud computing[END_REF]. Moreover, unlike scientific workflows, where generally their processing are fully automated, when executing workflow processes it is difficult to automate all theirs tasks. Indeed, certain tasks require validations that cannot be automated because they are subject to human intervention.

To overcome the limitations of existing approaches for workflow process optimization, we propose an extension of our recent study [START_REF] Bessai | Nurcan Bi-criteria workflow tasks allocation and scheduling in Cloud computing environments[END_REF].

Problem formulation

Definition 1 (Business process). A business process application is represented as a directed acyclic graph (DAG) denoted G = (T, E), where:

1. T = {t 1 , ..., t n } is a finite set of tasks.

2. E represents the set of directed edges. An edge (t i , t j ) of graph G corresponds to the data dependencies between these tasks (the data generated by t i is consumed by t j ). 3. Task t i is called the immediate parent of t j which is the immediate child task of t i .

Let Data be a n × n matrix of communication data, where data[i, j] is the amount of data required to be transmitted from task t i to task t j .

Definition 2 (Resource graph). The resources are represented as a directed graph denoted RG. Formally, a resources graph is represented by RG = (R, V ), where:

1. R = {V M 1 , ..., V M m , HR 1 , ..., HR m } is a finite set of virtual machines
types and human resources. 2. V represents the set of directed edges. Each edge is denoted

(V M i , V M j )
corresponding to the link between these virtual machines.

Let B be a m × m matrix, in which B[i, j] is the bandwidth between virtual machine types V M i and V M j , where B[i, i] -→ ∞ means that there is no transfer data.

Let r(t j ) denotes the resource (virtual machine or human resource) that executes task t j . The transfer time T T (r(t i ), r(t j )), which is for transferring data from task t i (executed by r(t i )) to task t j (executed by r(t j )) is defined by:

T T (r(t i ), r(t j )) = data[i, j] B[r(t i ), r(t j )]
Let ET be a n × m execution time matrix in which ET (t i , r j ) gives the execution time estimation to complete task t i by resource r j .

Let U EC be a (m + m )-dimensional unit execution cost vector, where U EC(r j ) represents the cost per time unit incurred by using the resource r j . Let EC be a n × m + m execution cost matrix in which EC(t i , r j ) gives the execution cost to complete task t i by resource r j defined by:

EC(t i , r j ) = ET (t i , r j ) × U EC(r j )
The data transfer cost T C(r(t i ), r(t j )), which is the cost incurred due to the transfer of data from task t i (executed by r(t i )) to task t j (executed by r(t j )), is defined by: T C(r

(t i ), r(t j )) = data[i, j] × (C out (r(t i )) + C in (r(t j )))
where C out (r(t i )) and C in (r(t j )) represent respectively the cost of transferring data from r(t i ) and the cost of receiving data on r(t j ).

3 The objective functions a. Time objective function Let EST (earliest start time) and EF T (earliest finish time) attributes that characterize the set of resources (virtual machine types and human resources). These attributes are derived from a given partial matching and scheduling (i.e. a task t i is assigned to virtual machine V M (t i ) or human resource HM (t i )). The partial schedule refers to the fact that for each task the earliest start time and the earliest finish time values are obtained using only the tasks that must be performed before it. EST (t i , r j ) and EF T (t i , r j ) are the earliest execution start time and the earliest execution finish time of task t i on resource r j , respectively. For the input task input , the earliest execution start time and the earliest execution finish time are given by Equation 1and Equation 2, respectively:

EST (t input , r j ) = 0 (1) EF T (t input , r j ) = ET (t i , r j ) (2)
For the other tasks in the graph, the EST and the EF T values are computed recursively, starting from the initial task, as shown in Equation 3 and Equation 4. In order to compute the EF T of a task t j , all immediate predecessor tasks of t j must have been assigned and scheduled with the consideration of the transfer time.

EF T (t i , r j ) = EST (t i , r j ) + ET (t i , r j ) ( 3)

EST (t i , r j ) = max avail[j], max tp∈pred(tj ) [AF T (t p ) + T T (r(t p ), r(t i ))] (4)
where pred(t i ) is the set of immediate predecessors of task t i . avail[j] is the earliest time at which resource r j is ready for task execution. As the number of virtual machines is assumed to be infinite, then avail[j] = 0 for all the used virtual machines. In other words, if task t i is performed by resource r j which is a virtual machine then EST (t i , r j ) is computed as follows:

EST (t i , r j ) = max tp∈pred(tj ) {AF T (t p ) + T T (r(t p ), r(t i ))} (5)
The avail[j] is the time that resource r j completed the execution of the task t i and it is ready to execute another task. The inner max block in the EST equation returns the ready time, i.e. the time when all required data by t i has arrived at resource r j .

After a task t i is scheduled on a resource r j , the earliest start time and the earliest finish time of t i on resource r j is equal to the actual start time, denoted AST (t i ), and the actual finish time, denoted AF T (t i ), of task t i , respectively.

After all tasks in a graph are scheduled, the schedule length (i.e., the overall completion time) will be the actual finish time of the exit task (i.e. AF T (t exit )). The schedule length, also called makespan, is defined as:

makespan = AF T (t exit ) (6)
Predictive heuristic for human resource availabilities The actual finish time as computed previously does not take into account the fact that human resources can perform other tasks that do not belong to the same process. More precisely, the work list of a given human resource may contain work items of different processes. The realism of this assumption can be disputed as a human resources are "shared" by more than one process. Thus, it is might be desirable to design a procedure in order to predict the human resources availabilities. Concretely, we propose to estimate this availability values taking into account the previous observation. Let availability[j] k+1 is the estimation of resource j availability and t i the next task that can be performed by this resource. Instead of simply adapting to the computed availability using equation 4, one can try to forecast and estimate what availability[j] k+1 will be using the historical data.

b. Cost objective function The cost function is a structure independent criterion defined as the sum of the costs of executing all workflow tasks, given by:

cost = n j=1    EC(r(t j )) + p∈pred(tj ) T C(r(t j ), r(t p ))    (7)
Thus, the cost objective function is to determinate the assignment of tasks of a given workflow application such that its overall execution cost is minimized.

To take into account these objectives simultaneously, we propose to use the proposed approaches in our study [START_REF] Bessai | Nurcan Bi-criteria workflow tasks allocation and scheduling in Cloud computing environments[END_REF] by replacing the execution time and the execution cost by respectively Equations 4 and 7.

Conclusion

In this paper, we have proposed a model for business processes execution in Cloud computing environments. The proposed approaches extend our previous algorithms. More precisely, three complementary approaches are designed to deal with the problem of matching and scheduling business process tasks in Cloud context taking into account two objectives (execution time and cost incurred using a set of resources). We plan to extend the proposed work to take into account others criteria like carbon emission and energy cost.