## 3 The Multiple Workflows Allocation Model
### Problem Formulation and Parameter Estimation
The tasks in each partition can be executed in parallel. Each partition is sorted in descending order as per their rank computed in Equation (7), and tasks are selected for assignment in the order in which they appear in the sorted partitions. The complete batch is assigned in accordance with the level-wise partitions starting from the first level partition to the last one. Level-wise allocation ensures not only the preservation of precedence constraints but also that all parents are getting executed before their children. This will improve the overall execution cost. Here, our motivation is to exploit the inherent parallelism available in the independent tasks in the batch efficiently. The sum of the earliest start time (EST\({}_{\text{ijk}}\)) and execution time for T\({}_{\text{ij}}\) is used to estimate the earliest finish time (EFT\({}_{\text{ijk}}\)), which can be expressed as  
\[EFT_{ijk}=E_{ijk}+EST_{ijk} \tag{8}\]  
The EST\({}_{\text{ijk}}\) is the time at which task T\({}_{\text{ij}}\) can begin its execution as early as possible, which is the minimum of the start time of T\({}_{\text{ij}}\) on the set of all VMs and can be written as  
\[EST_{ijk}=\max\left(AET_{k},\quad\underbrace{max}_{T_{ip}\in pred(T_{ij})} \big{(}AFT\big{(}T_{ip}+C_{ipj}\big{)}\big{)}\right) \tag{9}\]  
The actual execution time (AET\({}_{\text{k}}\)) on the virtual machine VM\({}_{\text{k}}\) is initialized with the ready time (RT\({}_{\text{k}}\)) values on that virtual machine. After computation of the EFT\({}_{\text{ijk}}\) and EST\({}_{\text{ijk}}\), the task selected is assigned to the VM having the EST and EFT. After the allocation of tasks, the EST\({}_{\text{ijk}}\) and EFT\({}_{\text{ijk}}\) become the actual start time (AST\({}_{\text{ij}}\)) and actual finish time (AFT\({}_{\text{ij}}\)) of task T\({}_{\text{ij}}\). As soon as a task is assigned to the virtual machine VM\({}_{\text{k}}\), the (AET\({}_{\text{k}}\)) of that virtual machine is updated with the AET of the assigned task \(T_{ij}\), which is the difference between the AFT and AST of that task as shown in Equation (10):  
\[AET_{k}=AET_{k}+(AFT_{kij}-AST_{ij}) \tag{10}\]  
In the same way, all tasks from the batch are assigned as per the algorithm given in Section 4. The time from submission to completion is known as the makespan (MS) of W. Now, the MS is calculated by adding the overall completion time of W and the estimated queuing time (QT) together as follows  
\[MS=QT+AFT_{exit} \tag{11}\]  
In the context of workflow allocation, the queuing time (QT) refers to the time that tasks spend waiting in a queue before they can be executed. Workflow allocation involves distributing tasks among available VMs in a system. Equation (12) is used to calculate the QT, which is defined as the global queue's average waiting time for W.  
\[QT=\left\{ \begin{array}{c}\frac{1}{H-\lambda}ifB\leq Q_{u}\\ \frac{1}{H-\lambda}\Big{(}\frac{B}{Q_{u}}\Big{)}ifB\geq Q_{u}\end{array} \right. \tag{12}\]  
where \(B\) and \(Q_{u}\) are the total size of \(W\) and the queue unit. In the context of workflow allocation, average utilization (U\({}_{s}\)) refers to the average level of workload on the available VMs over a certain period of time. It is a crucial metric for evaluating how effectively the resources are being utilized and whether the system is operating efficiently. The U\({}_{s}\) of the cloud resources of W can be estimated by using Equation (13)  
\[U_{s}=\frac{\sum_{k=1}^{k=K}AET_{k}}{K*\max\ (AET_{k})} \tag{13}\]  
Average flowtime (FT) refers to the average time it takes for a task to go through the entire workflow process, from submission to completion. It is a key performance metric that provides insights into the efficiency and responsiveness of the system in processing tasks. The FT of W can be estimated by using Equation (14) as  
\[FT=\frac{\sum_{k=1}^{k=K}AET_{k}}{k} \tag{14}\]  
For cloud computing to provide the best possible quality of service (QoS), multiple workflow allocation must be performed effectively.