the mapping between the PMs or rented VMs and the tasks with minimal cost while fitting deadlines.

![Hybrid cloud environment. A task of jobs is assigned to either a PM in local cloud(s)/cluster(s) or a VM leased from public cloud(s).[]{data-label="arch"}](arch){width="2.4in"}

Problem Formulation {#PF}
-------------------

We consider a hybrid cloud consisted of a local cloud/cluster and a public cloud. Multiple public clouds in a hybrid cloud can be seen as one big public cloud including the resources provisioned by these public clouds. Table \[notations\] summarizes notations used in this paper.

   **Notations**  **Description**
  --------------- ----------------------------------------------------------------------------------------------------------------------
        $J$       The number of jobs running on the hybrid cloud.
       $T_i$      The number of tasks constituting job $i$.
        $T$       The number of tasks, $T = \sum_{i=1}^JT_i$.
     $t_{i,j}$    The $j$th task of job $i$.
       $d_i$      The deadline of job $i$.
     $r_{i,j}$    The resource amount needed to complete $t_{i,j}$.
        $P$       The number of PMs in the local cloud.
        $V$       The maximal number of VMs leased from the public cloud.
       $p_k$      The price per unit time of container $k$ representing a VM provisioned by the public cloud when $P+1\leq k\leq P+V$.
       $c_k$      The cost for renting container $k$ ($P+1\leq k\leq P+V$).
       $N_k$      The number of cores on container $k$.
       $r_k$      