Description

To optimize the cost of business process enriched with a set of non-functional 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:

  1. A formal specification of Cloud resource pricing strategies
  2. 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
  3. Experiments to demonstrate the feasability and performance of our approach

Cloud pricing strategies description

The common pricing strategy between all Cloud providers is on-demand 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 per-minute billing strategy is proposed by Google. Otherwise, Microsoft instances are billed in pre-paid 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 (2-16) that should be respected. For instance, equations (2-5) are used to ensure the respect of process temporal constraints. Whearas, we use equations (6-7) 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 IBM-ILOG Cplex Optimization Studio V12.6.3 on a laptop with a 64-bit 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.


Figure 1. Service supervision process

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.



                                           Figure 2. MIP solution


                                           Figure 3. Gantt chart of the service supervision process

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.

Figure 4. AND Split/Join Variation

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.

Figure 5. Flexibility Evaluation

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").

    
Figure 6. Approaches Comparison


The experimental results are given in files Comparison.xlsx.

Contributors

Contact

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