Abstract
Grid computing is a distributed paradigm that coordinates heterogeneous resources using decentralized control. Grid computing is commonly used by scientists for executing experiments. Scheduling jobs within Grid environments is a challenging task. Scientists often need to ensure not only a successful execution for their experiments but also they have to satisfy constraints such as deadlines or budgets. Both of these constraints, execution time and cost, are not trivial to satisfy, as they are conflict with each other, eg cheaper resources are usually slower than expensive ones. Hence, a multi-objective scheduling optimization is a more challenging task in Grid infrastructures. This chapter presents a new multi-objective approach, MOGSA (Multi-Objective Gravitational Search Algorithm), based on the gravitational search behaviour in order to optimize both objectives, execution time and cost, with the same importance and also at the same time. Two studies are carried out in order to evaluate the quality of this new approach for grid scheduling. Firstly, MOGSA is compared with the multiobjective standard and well-known NSGA-II (Non-Dominated Sorting Genetic Algorithm II) to prove the multi-objective optimization suitability of the proposed algorithm. Secondly two real grid schedulers (WMS and DBC) are also compared with MOGSA. TheWMS (WorkloadManagement System) is considered because of it is part of the most used European grid middleware - gLite - and also the DBC (Deadline Budget Constraint) algorithm from Nimrod-G participates in this evaluation due to its good performance kee** the deadline and budget per job. Results point out the superiority of MOGSA in all the studies carried out. MOGSA offers more quality solutions than NSGA-II and also better performance than current real schedulers.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amorim, P., Günther, H.O., Almada-Lobo, B.: Multi-objective integrated production and distribution planning of perishable products. International Journal of Production Economics 138(1), 89–101 (2012)
Buyya, R., Murshed, M.: Gridsim: a toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing. Concurrency and Computation: Practice and Experience 14(13), 1175–1220 (2002)
Buyya, R., Murshed, M., Abramson, D.: A deadline and budget constrained cost-time optimisation algorithm for scheduling task farming applications on global grids. In: Int. Conf. on Parallel and Distributed Processing Techniques and Applications, Las Vegas, Nevada, USA, pp. 2183–2189 (2002)
Castro, C., Crawford, B., Monfroy, E.: A genetic local search algorithm for the multiple optimisation of the balanced academic curriculum problem. In: Shi, Y., Wang, S., Peng, Y., Li, J., Zeng, Y. (eds.) MCDM 2009. CCIS, vol. 35, pp. 824–832. Springer, Heidelberg (2009)
Coello, C., Van Veldhuizen, D., Lamont, G.: Evolutionary Algorithms for Solving Multi-Objective Problems. In: Genetic Algorithms and Evolutionary Computation. Kluwer (2002)
Côté, P., Wong, T., Sabourin, R.: Application of a hybrid multi-objective evolutionary algorithm to the uncapacitated exam proximity problem. In: Proceedings of the 5th International Conference on Practice and Theory of Automated Timetabling, pp. 151–167 (2004)
Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons (2001)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast elitist multi-objective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation 6(2), 182–197 (2002)
Foster, I., Kesselman, C., Tuecke, S.: The anatomy of the grid. In: Grid Computing-Making the Global Infrastructure a Reality. John Wiley Sons (2010)
Hamta, N., Ghomi, S.F., Jolai, F., Shirazi, M.A.: A hybrid pso algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect. International Journal of Production Economics (2012)
Ismayilova, N.A., Sagir, M., Gasimov, R.N.: A multiobjective faculty-course-time slot assignment problem with preferences. Mathematical and Computer Modelling 46(7-8), 1017–1029 (2007)
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948 (1995)
Fonseca, C.M., Fleming, P.J., Zitzler, E., Deb, K., Thiele, L. (eds.): EMO 2003. LNCS, vol. 2632. Springer, Heidelberg (2003)
Lei, D.: Multi-objective production scheduling: a survey. The International Journal of Advanced Manufacturing Technology 43(9-10), 926–938 (2009)
Li, J., Burke, E.K., Curtois, T., Petrovic, S., Qu, R.: The falling tide algorithm: A new multi-objective approach for complex workforce scheduling. Omega 40(3), 283–293 (2012)
Loukil, T., Teghem, J., Fortemps, P.: A multi-objective production scheduling case study solved by simulated annealing. European Journal of Operational Research 179(3), 709–722 (2007)
Mansouri, S.A., Gallear, D., Askariazad, M.H.: Decision support for build-to-order supply chain management through multiobjective optimization. International Journal of Production Economics 135(1), 24–36 (2012)
Mobasher, A.: Nurse scheduling optimization in a general clinic and an operating suite. PhD thesis, University of Houston (2012)
El Moudani, W., Cosenza, C.A.N., de Coligny, M., Mora-Camino, F.: A bi-criterion approach for the airlines crew rostering problem. In: Zitzler, E., Deb, K., Thiele, L., Coello Coello, C.A., Corne, D.W. (eds.) EMO 2001. LNCS, vol. 1993, pp. 486–500. Springer, Heidelberg (2001)
Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems, 4th edn. Prentice-Hall (2012)
Rashedi, E., Nezamabadi-Pour, H., Saryazdi, S.: Gsa: A gravitational search algorithm. Information Sciences 179(13), 2232–2248 (2009)
Silva, A., Burke, E.K.: A tutorial on multiobjective metaheuristics for scheduling and timetabling. In: Multiple Objective Meta-Heuristics. LNEMS. Springer (2004)
Silva, A., Burke, E.K., Petrovic, S.: An introduction to multiobjective metaheuristics for scheduling and timetabling. In: Grandibleux, X., Sevaux, M., Sörensen, K., T’Kindt, V. (eds.) Metaheuristic for Multiobjective Optimisation. LNEMS, vol. 535, pp. 91–129. Springer, Heidelberg (2004)
Sulistio, A., Poduval, G., Buyya, R., Tham, C.: On incorporating differentiated levels of network service into gridsim. Future Gener. Comput. Syst. 23(4), 606–615 (2007)
Talukder, A.K.A., Kirley, M., Buyya, R.: Multiobjective differential evolution for workflow execution on grids. In: MGC 2007: Proceedings of the 5th International Workshop on Middleware for Grid Computing, pp. 1–6. ACM, New York (2007)
Talukder, A.K.A., Kirley, M., Buyya, R.: Multiobjective differential evolution for scheduling workflow applications on global grids. Concurr. Comput. Pract. Exper. 21(13), 1742–1756 (2009)
Tsuchiya, T., Osada, T., Kikuno, T.: Genetics-based multiprocessor scheduling using task duplication. Microprocessors and Microsystems 22(3-4), 197–207 (1998)
**ong, J., **ng, L., Chen, Y.: Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns. International Journal of Production Economics (2012)
Yannibelli, V., Amandi, A.: Project scheduling: A multi-objective evolutionary algorithm that optimizes the effectiveness of human resources and the project makespan. Engineering Optimization, 1–21 (2012)
Ye, G., Rao, R., Li, M.: A multiobjective resources scheduling approach based on genetic algorithms in grid environment. In: International Conference on Grid and Cooperative Computing Workshops, pp. 504–509 (2006)
Yu, J., Kirley, M., Buyya, R.: Multi-objective planning for workflow execution on grids. In: GRID 2007: Proceedings of the 8th IEEE/ACM International Conference on Grid Computing, pp. 10–17. IEEE Computer Society, Washington, DC (2007)
Zeng, B., Wei, J., Wang, W., Wang, P.: Cooperative grid jobs scheduling with multi-objective genetic algorithm. In: Stojmenovic, I., Thulasiram, R.K., Yang, L.T., Jia, W., Guo, M., de Mello, R.F. (eds.) ISPA 2007. LNCS, vol. 4742, pp. 545–555. Springer, Heidelberg (2007)
Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms - a comparative case study. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 292–304. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Arsuaga-Ríos, M., Vega-Rodríguez, M.A. (2013). Multi-objective Grid Scheduling. In: Uyar, A., Ozcan, E., Urquhart, N. (eds) Automated Scheduling and Planning. Studies in Computational Intelligence, vol 505. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39304-4_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-39304-4_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39303-7
Online ISBN: 978-3-642-39304-4
eBook Packages: EngineeringEngineering (R0)