This paper aims at scheduling bag-of-tasks (BoT) applications under budget constraints on hybrid clouds for minimizing the makespan. To solve this NP-hard problem, we propose a novel firefly algorithm (NFA) in which the evaluation of a firefly consists of two steps: (1) mapping a firefly to a scheduling solution (a task sequence); (2) calculating the solution’s objective (its corresponding makespan). In the first step, different from the well-known ranked-order value (ROV) rule, we propose a distancebased mapping operator that relies on the distance between a firefly and the brightest one to determine the mapping relationship between a firefly and a solution. We use a probability model in which solutions corresponding to fireflies closer to the brightest one would have higher probabilities to inherit tasks from the current best solution. In this manner, these solutions can inherit more ‘‘good genes’’ hidden inside the current best solution to evolve into more high-quality solutions. In the second step, we employ an effective heuristic to evaluate solution objectives. We further develop a composite heuristic to generate the initial best solution, providing the proposed NFA with a good start. We also establish a new movement scheme such that fireflies distant from the brightest one can explore a wide range in the search space, whereas fireflies nearby the brightest one can search in a small neighborhood. Experimental results show that, by employing the above-mentioned strategies, NFA outperforms the standard firefly algorithm and the existing best algorithm, in terms of scheduling effectiveness and computational efficiency. Specifically, the distance-based mapping operator is verified to be both more effective and more efficient than the ROV rule. The composite heuristic is capable of generating a good initial solution, leading to the high quality of the final schedule. The movement scheme can further reduce the makespan of BoT applications.

Introduction

Cloud computing is a popular distributed computing paradigm that can deliver a massive amount of computing resources in a pay-as-you-go manner. In other words, users only need to pay what they have actually used. As a result, users can temporally use computing resources of public clouds while the private cloud cannot provide sufficient resources. In order to achieve this target, cloud vendors offer hybrid cloud solutions that integrates a private cloud with public clouds seamlessly. As illustrated in Figure 1, with the aid of hybrid cloud solutions, administrators or programs of the private cloud can manage the computing resources of the hybrid cloud (i.e., the private cloud and public clouds) via unified interfaces. For example, in case that the available computing resources of the private cloud cannot afford an instance of a ‘‘large’’ virtual machine (VM) type for processing a specific task, an instance of the same VM type can be created on a public cloud to tackle this task. In addition, many cloud providers now can deliver and charge VM instances in seconds (e.g., QingCloud1 and TecentCloud2 ) instead of in hours. This new charging mechanism makes hybrid clouds more popular for cloud customers, since they would not waste a certain fraction of the last hour that has to be paid entirely in traditional charging mechanisms.