# Cost and Time Economical Planning Algorithm for Scientific Workflows in Cloud Computing
## 3 Task Scheduling Problem  
### Application Model  
The two methods of task scheduling are the static method and the dynamic method. When the task and the system parameters are unknown at compile time, a dynamic scheduling strategy is suitable. For the dynamic scheduling, strategy decisions have to be made at runtime, and this leads to an added overhead. The program, the heterogeneous cloud environment, and the performance measure are the three components of the scheduling model. The program, which is the initial step of a scheduling model, is characterized by a direct acyclic graph (DAG), where the DAG is represented by G = (T, E) and T represents the group of m tasks \(\{t_{1},\ t_{2},\ \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots  
Thus, with both the task and the system parameters available at compile-time, this static approach has no or zero overhead during runtime and so is more suitable. Moreover, in this model, we take into account the processors which are connected to each other using a fully connected topology. For each processor, the communication of tasks with other processors and the execution of tasks can be attained instantaneously and without contention. Furthermore, the task execution is said to be non-preemptive. Our heterogeneous system is considered to be an infrastructure with a single site, with a set of GPUs and CPUs that assures parallel communications between various pairs of devices and that are linked together with a switched network. The reason behind the heterogeneity is that the system consists of dissimilar devices, such as GPUs and microprocessors, with various types, specifications, and dissimilar generations. The same site may have multiple clusters, and selecting resources from these clusters requires another type of machine. A heterogeneous machine is nothing but a set of processors selected from a homogeneous cluster to execute a DAG. Differences that are caused because of CPU latency in a heterogeneous machine can vary and are insignificant. For lower Communication to Computation Ratios (CCRs) [22] the communications between tasks are considered to be negligible, but for the cause of higher Communication to Computation Ratios (CCRs), network bandwidth is considered to be a major feature, and that is why we consider network bandwidth to be similar throughout the whole network. Then, we extended certain collective attributes that are used in scheduling the task. This shall be discussed in the following sections. Each and every task has a dissimilar cost and time in different virtual machines in a heterogeneous system. Each task \(t_{i}\in T\) is associated with the instructions and is implemented on the processor. Furthermore, \(CT(i,j)\) is the predicted computation time on processor \(P_{i}\) for each task \(t_{i}\). For a task \(t_{i}\), the computation time is defined by  
\[CT_{t_{i}}^{VM_{i}}=\frac{ST_{i}}{PCvm_{i}} \tag{1}\]  
where \(ST_{i}\) is the size of the task \(t_{i}\), \(CT_{ti}^{VMi}\) is the time taken for the computation of the task \(t_{i}\). \(VM_{i}\) represents the virtual machine \(VM_{i}\). \(PCvm_{i}\) is the processing capacity on \(VM_{i}\). The average computation time is given by  
\[\overline{CTi}=\left(\sum_{j=1}^{n}CT(i,j)\right)/P \tag{2}\]  
where the number of processors is denoted by \(P\). The computation cost is denoted by \(CC_{i,p}\) and is given by  
\[CC_{i,p}=\mu_{p}*CT_{i,p} \tag{3}\]  
where the unit price for using the hardware resource \(\
u\) is represented by \(\mu_{p}\) for each time interval, and the further storage cost is presumed to be zero. For the period that is needed to transfer the data, independent tasks are mapped to the same resources, but other tasks are mapped to different resources. For the task \(t_{i}\) in a DAG, the set of immediate predecessors is given by \(\text{pred}(t_{i})\). The entry task is the task with no predecessors [23]. In a DAG, \(\text{succ}(t_{i})\) represents the group of immediate successors for the task \(t_{i}\). If the task has no successors, then it is named the exit task.