a PM/VM both are a few tens or fewer, thus the selection of a PM or VM and the decision of an assignment are $O(P)$ and $O(T)$, respectively, in time complexity. Therefore, assigning tasks to PMs is $O(T\cdot(P+T))$ in time complexity. We assume that there are $N_{RV}$ VMs leased from public cloud for completing the tasks within their respective deadlines. Assigning tasks to a VM is $O(T)$ in time complexity. Thus, Assigning tasks to the rented VMs is $O(T\cdot N_{RV})$ in time complexity. Hence, the algorithm is $O(T\cdot(P+T+N_{RV}))$ in time complexity, overall.

Performance Evaluation {#ERA}
======================

In this section, we introduce our testbed and experiment design, and then discuss the experimental results.

Testbed and Experiments Design {#TED}
------------------------------

![image](Table2)

We use a 3-month trace collected from the University of Luxemburg *Gaia* cluster system and a 2-month trance collected from NASA Ames iPSC/860, i.e., *UniLu Gaia log* and *NASA iPSC log* in Parallel Workloads Archive [@PWA], to evaluate the performance of our algorithm. We assume that the trace data are the information of tasks running on 1 GHz cores. We set the deadline of each job as $ \alpha $ (1, 2, 3, or 4) times of its run time on 