## 3 Task Scheduling Problem
### Problem Formulation  
When requests from BoT applications are sent to the Fog layer, they are decomposed into small and independent tasks to be processed over the Cloud-Fog computing infrastructure. Each task has the following properties: number of instructions, memory required, size of input and output files. Assuming that \(T_{k}\) indicates the \(k\)th task, at each time, there is a set of \(n\) independent tasks sent to the system, as follows:  
\[T=\left\{T_{1},T_{2},T_{3},...,T_{n}\right\}. \tag{1}\]  
The Cloud-Fog computing infrastructure consists of processors, i.e., Cloud nodes and Fog nodes, which have the same attributes such as CPU rate, CPU usage fee, memory usage fee, and bandwidth usage fee. However, Cloud nodes are typically more powerful than the Fog nodes, but the cost of using them is greater. The set of \(m\) processors including \(c\) Cloud nodes and \(f\) Fog nodes in the system \((N=N_{cloud}\cup N_{Fog})\) is expressed as:  
\[N=\left\{N_{1},N_{2},N_{3},...,N_{m}\right\}, \tag{2}\]  
where \(N_{i}\) presents the \(i\)th processing node. Each task \(T_{k}(T_{k}\in\textit{Tasks})\) is assigned to the processor \(N_{i}(N_{i}\in\textit{Nodes})\), which is represented as \(T_{k}^{i}\). One processor can be assigned to process a set of one or more tasks:  
\[N_{i}\textit{Tasks}=\left\{T_{x^{\prime}}^{i},T_{y^{\prime}}^{i}...,T_{z}^{i}\right\} \tag{3}\]  
The task scheduling problem in Cloud-Fog computing environment could be formulated as searching of a set:  
\[\textit{NodeTasks}=\left\{T_{1}^{a},T_{2}^{b},T_{3}^{c},...,T_{n}^{p}\right\} \tag{4}\]  
For a set of tasks \(N_{i}\textit{Tasks}\), the execution time \((EXT)\) that node \(N_{i}\) needs to complete all tasks assigned is:  
\[EXT\left(N_{i}\right)=\sum_{T_{i}\in N_{i}\textit{Tasks}}\textit{ExecTime}(T _{k}^{i})=\frac{\sum_{T_{k}^{i}\in N_{i}\textit{Tasks}}\textit{length}(T_{k })}{CPUrate(N_{i})} \tag{5}\]  
where \(\textit{ExecTime}(T_{k}^{i})\) is the execution time of \(T_{k}\) processed in node \(N_{i}\), which is calculated by:  
\[\textit{ExecTime}(T_{k}^{i})=\frac{length(T_{k}^{i})}{CPUrate(N_{i})} \tag{6}\]  
Figure 1: The operation of Cloud–Fog system. with \(length(T_{k})\) the number of instructions of task \(T_{k}\) and \(CPUrate(N_{i})\) the CPU rate of node \(N_{i}\), which is determined based on clock rate, number of cores, instruction level parallelism, etc. _Makespan_ is the total time for the system to complete all tasks, defined from the time when the request is received to the time that the last task is completed, or the time when the last machine finishes. _Makespan_ is determined by the formula:  
\[Makespan=\underset{1\leq i\leq m}{Max}\left[EXT\left(N_{i}\right)\right] \tag{7}\]  
Let \(MinMakespan\) be the lower bound of _Makespan_, i.e., the shortest time that the system needs to complete all tasks. Ideally, when all nodes finish all tasks assigned at the same time, \(MinMakespan\) will be obtained and calculated by:  
\[MinMakespan=EXT\left(N_{1}\right)=...=EXT\left(N_{m}\right)\]  
thus,  
\[MinMakespan=\frac{\sum_{1\leq k\leq n}length(T_{k})}{\sum_{1\leq i\leq n}CPUrate (N_{i})} \tag{8}\]  
When one task is executed in Cloud-Fog system, a monetary amount must be paid for processing cost, memory usage cost, and bandwidth usage cost. The cost estimated when node \(N_{i}\) processes the task \(T_{k}\) is expressed as:  
\[N=\left\{N_{1},N_{2},N_{3},...,N_{m}\right\}, \tag{2}\]0  
In Equation (5), each cost is calculated as follows. Processing cost is defined as:  
\[N=\left\{N_{1},N_{2},N_{3},...,N_{m}\right\}, \tag{2}\]1  
where \(c_{1}\) is the CPU usage cost per time unit in node \(N_{i}\), and \(ExeTime(T_{k}^{i})\) is defined as Equation (6). Letting \(c_{2}\) be the memory usage cost per data unit in node \(N_{i}\) and \(Mem(T_{k})\) the memory required by task \(T_{k}\), the memory usage cost is:  
\[N=\left\{N_{1},N_{2},N_{3},...,N_{m}\right\}, \tag{2}\]2  
Task \(T_{k}\) processed in node \(N_{i}\) needs an amount of bandwidth \(Bw(T_{k})\), which is the sum of input and output file size.