local resources.

Conclusion {#CFW}
==========

In this paper, we study on the management of BoT jobs with deadline constraints on hybrid clouds. To minimize the cost of VMs leased from public cloud to complete jobs within their respective deadlines, respectively, we model the task schedule and resource provision into a BNP problem. As the BNP problem is NP-hard, we propose a heuristic algorithm to solve the problem in polynomial time. The main idea of the heuristic algorithm is assigning the task whose finish time is closest to and no later than its deadline if running on the current PM or rented VM. if there is no such assignment, the algorithm add a PM with maximum available capacity or a VM with best cost-performance ratio when there is no available PM. We conduct extensive experiments using two real work traces to investigate the effectiveness and efficiency of the proposed algorithm. The experiments results show that our heuristic algorithm saves 16.2%-76% cost for finishing jobs within their respective deadlines and improves 47.3%-182.8% resource utilizations, compared with first fit decreasing (FFD) algorithm, with good scalability.

ACKNOWLEDGMENT {#acknowledgment .unnumbered}
==============

The authors are grateful to the anonymous reviewers’ comments. This work was supported in 