# A Hybrid Metaheuristic for Multi-Objective Scientific Workflow Scheduling in a Cloud Environment
## 3 Problem Description for the Proposed Methodology
### Problem Formulation  
The objectives of the proposed work are to minimize the makespan, cost, and degree of imbalance among the VMs. In the workflow scheduling problem, the fitness of a solution is the trade-off between the three objectives. The cloud workflow scheduling problem can be formulated as follows:  
\[\min f=(f_{1},\ f_{2},\ f_{3}) \tag{3}\]  
\[f_{1}=MK \tag{4}\]  
\[f_{2}=\sum_{v_{i}\in V}\sum_{m_{r}\in M}y_{ir}\times EC_{ir} \tag{5}\]  
\[f_{3}=DI \tag{6}\]  
subject to  
\[MK=FT_{exit} \tag{7}\]  
\[ET_{ir}=\frac{WL_{i}}{CC_{r}\times(1-PV_{r})} \tag{8}\]  
\[CT_{ji}=\left\{ \begin{array}{ll}0,&r=s\\ \frac{DS_{ji}}{\min(BW_{r},BW_{s})},&r\
eq s\end{array} \right. \tag{9}\]  
\[ST_{ir}=\left\{ \begin{array}{ll}\max(AT_{r}),&i=entry\\ \max\left\{AT_{r},\max_{v_{i}\in pred(v_{i})}\left(FT_{j}+CT_{ji}\right)\right\},&i\
eqentry\end{array} \right. \tag{10}\]  
\[FT_{ir}=ST_{ir}+ET_{ir} \tag{11}\]  
\[EC_{ir}=\left(\frac{ET_{ir}\times CI_{r}}{BI_{r}}\right)+\left(CT_{ij}\times TC _{r}\right) \tag{12}\]  
\[FT_{i}+CT_{i}\leq ST_{j}\ \ \text{where}\ v_{j}=succ(v_{i}) \tag{13}\]  
\[DI=\sum_{i=1}^{n}\sqrt{\sum_{q=1}^{k}\left(1-UR\left(x_{i_{q}}\right)\right)^ {2}} \tag{14}\]  
\[\forall v_{i}\in V,\forall m_{r}\in M,\ \forall x_{i,q}\in X_{i},\ i\in[1,n]:\ UR \left(x_{i,q}\right)=\frac{\sum_{\forall x_{i,q}=m_{r}}ET_{i}}{\max(FT_{i})- \min(ST_{i})} \tag{15}\]  
\[\forall v_{i}\in V,\ \forall m_{r}\in M:\ \sum_{i=1}^{n}\sum_{r=1}^{k}y_{ir}=1 \tag{16}\]  
\[y_{ir}=0\ \text{or}\ 1. \tag{17}\]  
The fitness function \(f\) is defined by Equations (3)-(6), where \(f_{1}\), \(f_{2}\), and \(f_{3}\) indicate minimizing the three objectives, namely makespan, cost, and degree of imbalance among the VMs, respectively. Equation (7) indicates that the makespan of a workflow depends on the finish time of the exit task. Equation (8) defines the execution time of task \(v_{i}\) on VM \(m_{r}\) considering the VM's performance variability which represent the potential uncertainties, variation, or degradation in CPU performance and network resources due to the multi-tenant, heterogeneous, shared, and virtualized nature of real cloud environments. In other words, it is the amount by which the speed of a VM may degrade. Ultimately, it may result in a degradation in execution time of tasks. Equation (9) calculates the communication time between the tasks \(v_{i}\) and \(v_{j}\), which represents the ratio of data transfer size from task \(v_{i}\) to \(v_{j}\) to the smallest bandwidth between the VMs \(m_{r}\) and \(m_{s}\). \(m_{r}\) and \(m_{s}\) are VMs on which \(v_{i}\) and \(v_{j}\) are executed, respectively. When successive tasks execute on the same VM, \(CT_{ij}=0\). Equation (10) represents the start time (\(ST_{ir}\)) of task \(v_{i}\) to be executed on VM \(m_{r}\). It is computed based on the available time of the VM (\(AT_{r}\)) for the execution of the task, the maximum value of the sum of the finish time of all its predecessors, and the communication time between its predecessors and itself. After \(v_{i}\) is decided to run on \(m_{r}\), \(AT_{r}\) will be updated as the finish time of the immediate predecessor task that has been executed on the same VM. Specifically, when \(v_{i}\) is the entry task of the application, the start time can be computed as the available time of VM \(m_{r}\) where \(v_{i}\) is mapped during resource allocation. The finish time (\(FT_{ir}\)) of task \(v_{i}\) executed on VM \(m_{r}\) is defined by Equation (11). The total execution cost for the workflow is defined in Equation (12). Equation (13) ensures the precedence constraint that a task can only start execution after its predecessor task has finished and all the required input data is received. Equation (14) measures the degree of imbalance of all leased VMs based on the Euclidean distance. Obviously, minimizing this value will result in higher utilization of VMs. Equation (15) defines the utilization rate of VM \(m_{r}\). Equation (16) ensures that a task can be assigned to exactly one VM and can be executed only once.