Thursday 30
Cloud and cluster computing
B. Dorronsoro
› 12:10 - 12:30 (20min)
A Hybrid Meta-heuristics approach for Workflow Scheduling in Cloud Computing
Anis Allal  1, *@  , Sidi-Mohamed Benslimane  2, *@  
1 : École Nationale Supérieure d'Informatique  (ESI)  -  Website
Alger -  Algeria
2 : University Djillali Liabes
Sidi-Bel-Abbes -  Algeria
* : Corresponding author

Cloud computing is a paradigm that has emerged with the development of several disciplines such as computing, distributed parallel processing and computer networks. This is a new type of shared infrastructure able to offer a variety of resources, through the Internet, as services to meet users needs paying only for the resources they use (pay- per-use model). Cloud Computing aims to become the solution of tomorrow in the actual economic environment where we seek to maximize the return on investment and minimize the ecological footprint (Green IT).

Managing the quality of service (QoS) in the Cloud Computing attracts more and more effort from the research community. This is mainly due to the following reasons: First, the environment of cloud computing is very dynamic and uncertain, therefore, it is difficult to get a quality service without an efficient strategy for managing the QoS, the second reason is that the Cloud Computing is a market-oriented and service contracts model. A high quality of service is necessary to improve customer satisfaction and avoid penalties for breach of contract services. In general, the quality of service refers to the non-functional requirements for web services such as performance, reliability, availability, security and so on. The management of quality of service relates to a set of strategies dedicated to providing QoS requirements targeted.

Resource demands of the users can generally be divided into a number of tasks composing a workflow. Therefore, optimization of scheduling is required to meet these demands efficiently and with a good quality of service. In workflow scheduling, different sub tasks of a bigger task are allocated resources in such a way that some pre-defined objective criteria is met. For the “pay-per-use” service Cloud, the scheduling decision during workflow scheduling must be guided by users' QoS constraints[1]. There are various problems where a set of sub tasks is executed in a particular sequence in order to carry out a bigger task. In general, a workflow application requires series of steps to be executed in a particular fashion. These steps have parent child relationship.

Running a Workflow in a Cloud Computing is the assignment of each task to a virtual machine. While most cloud environments offer an unlimited number of virtual machines, a good ordering of these tasks allow it to meet user requirements better as non-functional quality of services such as cost, the execution time, reliability, availability, etc. There are currently no optimal solutions for this problem, and this is the reason for which the use of meta- heuristic is an increasingly explored way. These are ideal for the resolution of this kind of NP-complete problem. 

To solve the problem of optimization of scheduling, several solutions have been proposed in the literature to carry out the optimization of workflow scheduling, there are many approaches, some are based on meta- heuristics. [1], [2] introduce some algorithms for scheduling workflow in a Grid environment. In our work, we are interested in workflow scheduling in Cloud environment. We focus on the approaches that use meta-heuristics. Some of these approaches are based on Genetic Algorithms (GA) [3], [4]. There is also works in which Particle Swarm Optimization (PSO) are used for the scheduling of workflow in Cloud environment [5], [6]. Recently, researches show that Ant Colony Optimization (ACO) is one of the best meta-heuristic for scheduling workflow in Cloud computing [7]. Most of these researches focus only on one or two optimization objective, but there is not researches on multiple QoS requirements. The QoS constraints treated by the works are most often cost or time.

The objective of our work is to propose a multiple QoS constrains scheduling strategy to tackle workflow scheduling problem. We focus on non-functional properties to improve the quality of service offered to users. A new approach based on hybrid meta-heuristic algorithms for scheduling workflows in Cloud computing is introduced. In our approach, we propose ACO-GA that combine ACO and GA to enhance resolving discrete problem. Crossover and mutation operators of GA are embedded into ACO to improve scheduling strategy. The experimental results show that the performance of ACO-GA based scheduling algorithm is better than other approaches. 

References

[1] J. Yu, R. Buyya, and C. K. Tham (2005). QoS-based Scheduling of Workflow Applications on Service Grids. presented at the IEEE International Conference on e-Science and Grid Computing (e-Science'05), University of Melbourne, Australia.

[2] F. Tao, D. Zhao, Y. Hu, and Z. Zhou (2008). Resource Service Composition and Its Optimal Selection Based on Particle Swarm Optimization in Manufacturing Grid System. IEEE Transactions on Industrial Informatics, 4, 315 - 327.

[3] H. Zhong, K. Tao, and X. Zhang (2010). An Approach to Optimized Resource Scheduling Algorithm for Open-source Cloud Systems. presented at the Fifth Annual China Grid Conference, Guangzhou.

[4] S. Kaur and A. Verma (2012). An Efficient Approach to Genetic Algorithm for Task Scheduling in Cloud Computing Environment. International Journal of Information Technology and Computer Science(IJITCS), 4, 74 - 79.

[5] L. Guo, S. Zhao, S. Shen, and C. Jiang (2012). Task Scheduling Optimization in Cloud Computing Based on Heuristic Algorithm. journal of Networks, 7, 547-553.

[6] Z. Wu, Z. Ni, L. Gu, and X. Liu (2010). A Revised Discrete Particle Swarm Optimization for Cloud Workflow Scheduling. presented at the International Conference on Computational Intelligence and Security, Nanning.

[7] Z. Wu, X. Liu, Z. Ni, D. Yuan, and Y. Yang (2013). A market-oriented hierarchical scheduling strategy in cloud workflow systems. The Journal of Supercomputing, 63, 256-293.

 

 

 


Online user: 2 RSS Feed