تکنیک های زمانبندی فرا ابتکاری در محاسبات ابر A review of metaheuristic scheduling techniques in cloud computing

1. Introduction Scheduling allows optimal allocation of resources among given tasks in a finite time to achieve desired quality of service. Formally, scheduling problem involves tasks that must be scheduled on resources subject to some constraints to optimize some objective function. The aim is to build a schedule that specifies when and on which resource each task will be executed [1]. It has remained a topic of research in various fields for decades, may it be scheduling of processes or threads in an operating system, job shop, flow shop or open shop scheduling in production environment, printed circuit board assembly scheduling or scheduling of tasks in distributed computing systems such as cluster, grid or cloud. In recent years, distributed computing paradigm has gained much attention due to high scalability, reliability, information sharing and low-cost than single processor machines. Cloud computing has emerged as the most popular distributed computing paradigm out of all others in the current scenario. It provides on-demand access to shared pool of resources in a self-service, dynamically scalable and metered manner with guaranteed Quality of service to users. To provide guaranteed Quality of Service (QoS) to users, it is necessary that jobs should be efficiently mapped to given resources. If the desired performance is not achieved, the users will hesitate to pay. Therefore scheduling is considered as a central theme in cloud computing systems. In general, the problem of mapping tasks on apparently unlimited computing resources in cloud computing belongs to a category of problems known as NP-hard problems. There are no algorithms which may produce optimal solution within polynomial time for such kind of problems. Solutions based on exhaustive search are not feasible as the operating cost of generating schedules is very high [2]. Metaheuristic based techniques [3] deal with these problems by providing near optimal solutions within reasonable time. Metaheuristics have gained huge popularity in the past years due to its efficiency and effectiveness to solve large and complex problems. In this paper, we present an extensive review of various scheduling algorithms based on five metaheuristic techniques namely Ant Colony Optimization (ACO), Genetic Algorithm (GA), Particle Swarm Optimization (PSO), League Championship Algorithm (LCA) and BAT algorithm. Fig. 1 demonstrates a general framework of the paper.