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.
Although some cloud providers look at the hybrid cloud as blasphemy, there are strong reasons for them to adopt it. Hybrid clouds offer the cost and scale benefits of public clouds while also offering the security and control of private clouds. Task scheduling, one of the most famous combinational optimization problems, plays a key role in the hybrid cloud environment. We propose a graph-based task scheduling algorithm. In order to achieve minimum cost, our algorithm takes into account not only the private resources but also the public resources. This paper also presents an extensive evaluation study and demonstrates that our proposed algorithms minimize the user's cost in a hybrid cloud environment. We reduce the problem of finding an augmenting path in a general graph to a reachability problem and show that a slight modification of depth-first search leads to an algorithm for finding such paths. As a consequence, we obtain a straightforward algorithm for maximum matching in general graphs of time complexity O(√nm), where n is the number of nodes and m is the number of edges in the graph.