$$\textrm{Minimize}\ \ -\varepsilon\cdot\sum_{k=1}^Pu_k + \sum_{k=P+1}^{P+V}c_k, \label{objective}$$

subject to: $$\begin{aligned}
&& \sum_{k=1}^{P+V}\sum_{l=1}^{N_k}x_{i,j,k,l} = 1,\  \forall j=1,...,T_i,\ \forall i=1,...,J,\label{st0}\\
\nonumber &&\textrm{Inequalities~(\ref{deadline})},\\
\nonumber && \textrm{Equations~(\ref{cost})},\\
\nonumber && \textrm{Equations~(\ref{uti})}, \label{st2}\\
\nonumber && x_{i,j,k,l}\in \{0, 1\},\  \forall j=1,...,T_i,\ \forall i=1,...,J,\\
&&\hspace{0.8in} \forall l=1,...,N_k,\ \forall k=1,...,P+V,\label{st3}
$$ The decision variables are $x_{i,j,k,l}$ ($j=1,...,T_i$, $i=1,...,J$, $l=1,...,N_k$, $k=1,...,P+V$). In the objective function (\[objective\]), $\varepsilon$ is a small constant such that $0<\varepsilon<p_k/P, \forall k=P+1,...,P+V$, which guarantees that the value of the objective function is negative if there is no VM leased from public cloud while positive if there is at least one rented VM. Therefore, the objective of this model is maximizing the local resource utilization when the resources of the local cloud are enough to complete jobs within respective deadlines while minimizing the cost ($\sum_{k=P+1}^{P+V}c_k$) of rented VMs when the local resources are insufficient. Constraints (\[st0\]) ensure that each task must be assigned to only one core. Constraints (\[st3\]) represent the binary requirements for the decision variables. After solving this model, we achieve the task assignments, $x_{i,j,k,l}$ ($i=1,...,J$, $j=1,...,T_i$, $k=1,...,P+V$, $l=1,...,N_k$), and the renting time for each VM, $c_k/p_k$ ($k=P+1,...,P+V$).

The Heuristic Algorithm
-----------------------

As BNP is NP-hard [@NIP], we propose a heuristic algorithm to solve the model 