Description
To optimize the cost of business process enriched with a set of nonfunctional requirements (time, RAM, vCPU, penalty), we propose an approach to optimally schedule business
process activities without violating temporal constraints and capacity requirements. In this manner, an enterprise can minimize its expenditure by deciding process activities execution
timing in order to overlap with the temporal interval of the cheapest pricing strategy.
Basically, our contributions include:
 A formal specification of Cloud resource pricing strategies
 A Mixed Integer Program (MIP) that:
 Selects for each activity the Cloud resource that has the required capacities
 Selects the suitable Cloud pricing strategies for each Cloud resource
 Defines the start and end times of each business process activity to overlap with the less expensive pricing strategies temporal constraints
 Experiments to demonstrate the feasability and performance of our approach
Cloud pricing strategies description
The common pricing strategy between all Cloud providers is ondemand where instances are purchased at a fixed cost per hour. Whereas, some providers offer instances in cheaper cost for a specific period of time. For example, a perminute billing strategy is proposed by Google. Otherwise, Microsoft instances are billed in prepaid subscriptions. However, Amazon proposes two pricing strategies based on temporal perspective which are reserved and spot strategies.
Mathematical formulation of the linear program
We formulate the activity assignment and scheduling problem for
resources proposed by Cloud providers in various pricing strategies as a Mixed
Integer Programming (MIP) model. The latter is defined through an objective function and a set of constraints.
The objective function (1) minimizes the Cloud resources cost to run the business process by assigning for each
activity the suitable Cloud resource, the cheapest Cloud pricing strategy and the best time to start and to finish.
This function is subject to a set of constraints (216) that should be respected. For instance, equations (25) are used to ensure the respect
of process temporal constraints. Whearas, we use equations (67) to guarantee that the resource's
capacities in processing and memory satisfy the activity requirements. However, equations (8) and (9) are used to restrict the time span allowed to use a
resource R_i. But, to guarantee that an activity a_q should be performed when its required resource R_i is available, we define equations (10) and (11).
When the instance has an interruption risk and the activity has a penalty cost so this quantity should be added (equation(12)).
Equation (13) ensures that each instance type,
Cloud provider and pricing strategy is used by an only and one activity. Moreover, equation (14) is used to guarantee that each task
uses an only one instance type, Cloud provider and pricing strategy. However, equations (15) and (16) impose that the decision
variables X_ijkq and V_q should be either 0 or 1 (binary variables).
The MIP formulation:
Evaluation
To evaluate our approach, we implemented our MIP using IBMILOG Cplex Optimization Studio V12.6.3 on a laptop with a 64bit Intel Core 2.3 GHz CPU, 8 Go RAM and Windows 10 as OS.
Example Scenario
We demonstrate the feasability of our proposed MIP for scheduling process activities by using it with a specific process.
In fact, we apply our method to the process of service supervision model presented in Figure 1. The MIP inputs are
presented in the file Scenario inputs.xlsx. We consider that d_q=MaxD_q and the process does not
have inflexible temporal constraints.
The optimal resource allocation and computed scheduling are visualized respectively in Figure 2 and Figure 3. In figure 2, we note that
the whole process cost is 2.915$. Moreover, in Figure 3 the execution periods are depicted as green
rectangles with a tag on it defining activity name. Moreover, the allocated resource is mentioned in red colour.
Performance
To evaluate the performance of our MIP, we study the impact of varying the process structure on the cost. Next, we analyze the scheduler performance while varying the number of process activities, the maximum number of Cloud resources proposed by each Cloud provider in different pricing strategies. Moreover, we study the effect of inflexible temporal constraints and evaluate the impact of deadline constraint (equation (5)). For our experimental evaluation, we present in Dataset.xlsx file the set of data that are generated randomly.
AND Split/Join Constraints
The process structure is one of the factors that can have impacts on the scheduling execution plan and then on the process deployment cost. In our work, we consider that BP models have only the AND split/join branching. So, we vary the number of this branching on the process models. The results are shown in Figure 4 and given in file AND_Evaluation.xlsx.
Temporal Flexibility Constraint
The research space of our MIP can be limited if the process have some inflexible temporal constraints. For that, in a first experiment we evaluate the Cplex time and objective function when all the temporal constraints are flexible, and when the rate of temporal constraints is about 50% while varying the number of process activities and the maximum number of Cloud resources proposed by each Cloud provider in different pricing strategies. We present the experimental results in file Performance.xlsx. In the second experiment, we apply our method to the busniness process example (see Figure 1) and we vary the rate of inflexible temporal constraints. Figure 5 shows the total process cost values and the results are given in file Inflexible_Variation.xlsx.
Deadline Constraint
In our MIP, we use a deadline constraint that limits the end times of activities (in equation (5)). Thus, we investigate the Cplex time and objective function values when this constraint is removed. As presented in Performance.xlsx, without deadline constraint, we can notice that the objective function is higher and the CPLEXs computational time is considered as a good indicator of the importance of equation (5).
Comparison with other Approaches
We compare our approach against two resource allocation methods. The first one is our previous work and the second is a priority based
scheduling algorithm ("Priority+FCFS").
The experimental results are given in files Comparison.xlsx.
Contributors
 Rania Ben Halima
 Slim Kallel
 Walid Gaaloul
 Mohamed Jmaiel
Contact

Rania Ben Halima
Telecom SudParis
Computer Science Departement
9 rue Charles Fourier
91011 EVRY Cedex, France
email: rania.ben_halima@telecomsudparis.eu