# Cost and Time Economical Planning Algorithm for Scientific Workflows in Cloud Computing
## 4 Proposed Algorithm
### Deadline and Budget Computation  
The user-defined deadline is given as  
\[D_{user}=low_{time}+K_{d}*(high_{time}-low_{time}) \tag{13}\]  
where \(low_{time}\) is the lowest time to execute and \(high_{time}\) is the highest time to execute the application.  
\[low_{time}=\sum\limits_{t_{k}\in CP}CT_{min}\ (t_{k})+\overline{TC}_{(t_{j} \to t_{i})}\]  
where \(t_{j}\) is the parent task of \(t_{i}\) in the critical path. \(K_{d}\) is the deadline ratio between \([0\dots 1]\). CP is the critical path of a DAG from tstart to end.  
\(high_{time}\) is the highest time to execute the application.  
\[high_{time}=\sum\limits_{t_{k}\in CP}CT_{max}\ (t_{k})+\overline{TC}_{(t_{j} \to t_{i})}\]  
\(CT_{min}\ (t_{k})\) is the minimum time required to execute on the fastest processor and \(CT_{max}\ (t_{k})\) is the maximum time to execute on the slowest processor.  
\(CT_{least}=\sum\limits_{t_{k}\in T}CT\) represents the lowest computation time to execute on the fastest processor. Where \(CT_{least}\) is the summation of computation time of all the task on the fastest processor.  
\(B_{user}\) represents the budget defined by the user, and it is given by  
\[D_{user}=low_{time}+K_{d}*(high_{time}-low_{time}) \tag{14}\]  
where \(K_{b}\) is the budget ratio between \([0\dots 1]\), \(low_{cost}\) is the lowest cost to execute and the, which is the summation of the cost to execute a task on the critical path, and \(high_{cost}\) is the highest time to execute the application on the fastest processor, which is the summation of the cost to execute a task on the critical path.  
\[low_{cost}=\sum\limits_{t_{k}\in CP}CT_{min}\ (t_{k})\]  
\[high_{cost}=\sum\limits_{t_{k}\in CP}CT_{max}\ (t_{k})\]  
\(C_{cheap}\) is the cheapest cost involved in the execution of the application.  
The critical path of Figure (a)a is calculated as \(1\to 4\to 8\to 10\) which is 88.  
\(C_{cheap}=\sum\limits_{t_{k}\in T}C_{low}\) is the lowest execution cost of the task \(t_{i}\) amid all the processors.  
Figure 3: (a) Sample DAG with the transfer cost of \(10\) tasks. (b) Computation cost of \(10\) tasks and \(3\) processors.  
method is explained as follows: consider the scheduling of task T1 and task T3: for the task T1, P2 is the resource that gives the least EFT, and for the task T3, P2 is the resource that gives the least EFT. Thus, T1 is scheduled to P2 and T2 is scheduled to P3. Moreover, for the entire DAG, the anticipated EFT is reduced. The makespan obtained from the proposed forecast-based algorithm is 114, the makespan obtained for the same DAG1 using PEFT is 134, and the makespan based on HEFT using the same DAG is 145. Thus, the obtained makespan using HEFT, PEFT, and POTC for the DAG1 is 145, 134, and 114.  
The time complexity of the proposed method is calculated based on the rank computation and the task to resource mapping, Given the workflow \(G(T,E)\) with the number of tasks represented as 'n' and the dependencies represented as 'e'. The first phase of the algorithm computes the rank of all the tasks which process the entire tasks and the edges. The time complexity of this step is given as \((n+e)\approx O\big{(}n^{2}22\big{)}\). In the selection phase, the outer loop is for 'n' tasks and the inner loop is for 'r' resources. The time complexity for this phase is given as \(O(n.r)\). Thus, the final time complexity is given as \(O\big{(}n^{2}22\big{)}\). Thus, the time complexity of the proposed method is similar to PEFT, MOPT, and BDHEFT.