  Outsourcing jobs to a public cloud is a cost-effective way to address the
problem of satisfying the peak resource demand when the local cloud has
insufficient resources. In this paper, we study on managing
deadline-constrained bag-of-tasks jobs on hybrid clouds. We present a binary
nonlinear programming (BNP) problem to model the hybrid cloud management where
the utilization of physical machines (PMs) in the local cloud/cluster is
maximized when the local resources are enough to satisfy the deadline
constraints of jobs, while when not, the rent cost from the public cloud is
minimized. To solve this BNP problem in polynomial time, we proposed a
heuristic algorithm. Its main idea is assigning the task closest to its
deadline to current core until the core cannot finish any task within its
deadline. When there is no available core, the algorithm adds an available PM
with most capacity or rents a new VM with highest cost-performance ratio.
Extensive experimental results show that our heuristic algorithm saves
16.2%-76% rent cost and improves 47.3%-182.8% resource utilizations satisfying
deadline constraints, compared with first fit decreasing algorithm.
