# A Hybrid Metaheuristic for Multi-Objective Scientific Workflow Scheduling in a Cloud Environment
## 3 Problem Description for the Proposed Methodology
### System Model  
The cloud data center used in this study is represented by a set of heterogeneous \(k\) VMs, \(M=\{m_{1},m_{2},m_{3},\ldots m_{k}\}\) where \(m_{r}\in M\) such that \(1\leq r\leq k\), as shown in Figure 1. Each VM has its own processing speed measured in Millions of Instruction Per Second (MIPS), memory in Megabytes (MB), storage space in MB, bandwidth in Megabits per second (Mbps), and cost per unit of time. Tasks of scientific workflow applications can be represented by a DAG, \(W=(V,E)\), where \(V=\{v_{1},v_{2},v_{3},\ldots,v_{n}\}\) is the set of vertices representing \(n\) different tasks of the workflow, and \(E\) is the set of directed edges between the vertices representing dependencies and precedence constraints. An edge \(e_{ij}\in E\) between the tasks \(v_{i}\) and \(v_{j}\), indicates the precedence constraint that the task \(v_{j}\) cannot start its execution before \(v_{i}\) finishes and sends all the needed output data to task \(v_{j}\). In this case, \begin{table}
\begin{tabular}{l l} \hline \hline
**Notation** & **Description** \\ \hline \(d\) & Number of objective functions \\ \(f\) & Fitness function, including \(f_{1},\ldots,\)\(f_{d}\) \\ \(f_{1}\) & Makespan \\ \(f_{2}\) & Cost \\ \(f_{3}\) & Degree of imbalance of VMs \\ \(nf\) & Normalized fitness evaluation function of the solution \(x\) across the objectives \\ \(y_{ir}\) & Binary variable, if task \(v_{i}\) is executed on VM \(m_{r},y_{ir}=1\); otherwise \(y_{ir}=0\) \\ \(WL_{i}\) & Workload (i.e., service length) of task \(v_{i}\) measured by Millions of Instructions (MI) \\ \(CC_{r}\) & Central Processing Unit (CPU) computing capacity of VM \(m_{r}\) measured by Millions of Instruction Per Second (MIPS) \\ \(DS_{ij}\) & Data transfer size from task \(v_{i}\) to \(v_{j}\) \\ \(BW_{r}\) & Bandwidth of VM \(m_{r}\) \\ \(ST_{ir}\) & Start time of task \(v_{i}\) executed on VM \(m_{r}\) \\ \(ET_{ir}\) & Execution time of task \(v_{i}\) running on VM \(m_{r}\) \\ \(CT_{ij}\) & Communication time between task \(v_{i}\) and \(v_{j}\); if the tasks are executed on same VM, \\ \(CT_{ij}=0\) & \(CT_{ij}=0\) \\ \(FT_{ir}\) & Finish time of task \(v_{i}\) executed on VM \(m_{r}\) \\ \(AT_{r}\) & Available time of VM \(m_{r}\) for the execution of task \(v_{i}\) \\ \(FT_{exit}\) & Finish time of last task \\ \(CI_{r}\) & Cost per interval unit of VM type \(m_{r}\) \\ \(BI_{r}\) & Billing interval of VM type \(m_{r}\) \\ \(EC_{ir}\) & Execution cost of task \(v_{i}\) on VM \(m_{r}\) \\ \(TC_{r}\) & Data transfer cost per time unit for VM \(m_{r}\) \\ \(PV_{r}\) & VM performance variability \\ \(MK\) & Execution makespan of workflow \\ \(DI\) & Degree of imbalance among VMs \\ UR & Utilization rate of VM \\ \hline \hline \end{tabular}
\end{table} 
Table 1: _Cont._  
Figure 1: Block diagram of proposed workflow scheduling model. task \(v_{i}\) is considered one of the immediate predecessors of task \(v_{j}\), and task \(v_{j}\) is considered one of the immediate successors of task \(v_{i}\). Task \(v_{i}\) can have multiple predecessor and multiple successor tasks, denoted as \(pred(v_{i})\) and \(succ(v_{i})\) of \(v_{i}\), respectively. A task is considered as a ready task when all its predecessors have finished execution. Each task \(v_{i}\) is assumed to have a workload, denoted by \(WL_{i}\), which is the runtime of the task on a specific VM type. Also, each edge \(e_{ij}\) has a weight that indicates the data transfer size of the output data from \(v_{i}\) to \(v_{j}\), denoted by \(DS_{i}\). Any task without a predecessor task is called the entry task \(v_{entry}\), and a task with no successor task is called the exit task \(v_{exit}\), i.e., \(pred\big{(}v_{entry}\big{)}=\varnothing\) and \(succ(v_{exit})=\varnothing\), respectively. In this work, we assume that the given workflow has single \(v_{entry}\) and \(v_{exit}\).