Task assignment in grid computing, where both processing and bandwidth constraints at multiple heterogeneous devices need to be considered, is a challenging problem. Moreover, targeting the optimization of multiple objectives makes it even more challenging. This paper presents a task assignment strategy based on genetic algorithms in which multiple and conflicting objectives are simultaneously optimized. Specifically, we maximize task execution quality while minimizing energy and bandwidth consumption. Moreover, in our video processing scenario; we consider transcoding to lower spatial/temporal resolutions to tradeoff between video quality; processing, and bandwidth demands. The task execution quality is then determined by the number of successfully processed streams and the spatial-temporal resolution at which they are processed. The results show that the proposed algorithm offers a range of Pareto optimal solutions that outperforms all other reference strategies. 1. Introduction Nowadays multimedia applications such as multicamera surveillance or multipoint videoconferencing, are increasingly demanding both in processing power, and bandwidth requirements. In addition, there is a tendency towards thin client applications where the processing capacities of the client device are reduced and the tasks are migrated to more powerful devices in the network. In this respect, grid computing can integrate and make use of these heterogeneous computing resources which are connected through networks, overcoming the limited processing capabilities at a client’s device. In the context of distributed media processing we can think of scenarios such as video control rooms where multiple video streams are processed and simultaneously displayed. One way to downscale the processing and bandwidth requirements at the displaying device is by transcoding the video streams at the servers to lower temporal or spatial resolutions. This is done, however, at the cost of a degraded perceived video quality and an increased processing cost at the server. Therefore, in grid computing we may need to optimize and trade off multiple objectives, targeting for instance quality maximization of the stream execution and minimization of the energy consumption on the client/servers simultaneously. In this respect, implementing a suitable strategy for task assignment/scheduling becomes crucial for achieving a good performance in grid computing. This subject has been thoroughly studied in literature, and various heuristic approaches have been widely used for scheduling. In particular, Genetic
References
[1]
Y.-W. Zhong and J.-G. Yang, “A hybrid genetic algorithm with Lamarckian individual learning for tasks scheduling,” in Proceedings of the IEEE International Conference on Systems, Man and Cybernetics (SMC '04), pp. 3343–3348, October 2004.
[2]
K. Dahal, A. Hossain, B. Varghese, A. Abraham, F. Xhafa, and A. Daradoumis, “Scheduling in multiprocessor system using genetic algorithms,” in Proceedings of the 7th IEEE Computer Information Systems and Industrial Management Applications (CISIM '08), pp. 281–286, June 2008.
[3]
M. R. Miryani and M. Naghibzadeh, “Hard real-time multiobjective scheduling in heterogeneous systems using genetic algorithms,” in Proceedings of the 14th International CSI Computer Conference (CSICC '09), pp. 437–445, October 2009.
[4]
J. Carretero, F. Xhafa, and A. Abraham, “Genetic algorithm based schedulers for grid computing systems,” International Journal of Innovative Computing, Information and Control, vol. 3, no. 6, pp. 1053–1071, 2007.
[5]
R. Entezari-Maleki and A. Movaghar, “A genetic algorithm to increase the throughput of the computational grids,” International Journal of Grid and Distributed Computing, vol. 4, no. 2, 2011.
[6]
J. Liu, L. Chen, Y. Dun, L. Liu, and G. Dong, “The research of ant colony and genetic algorithm in grid Task scheduling,” in Proceedings of the International Conference on MultiMedia and Information Technology, (MMIT '08), pp. 47–49, December 2008.
[7]
A. Folling, C. Grimme, J. Lepping, and A. Papaspyrou, “Robust load delegation in service grid environments,” IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 9, pp. 1304–1316, 2010.
[8]
K.-M. Yu and C.-K. Chen, “An evolution-based dynamic scheduling algorithm in grid computing environment,” in Proceedings of the 8th International Conference on Intelligent Systems Design and Applications (ISDA '08), pp. 450–455, November 2008.
[9]
A. Michalas and M. Louta, “Adaptive task scheduling in grid computing environments,” in Proceedings of the 4th International Workshop on Semantic Media Adaptation and Personalization (SMAP '09), pp. 115–120, December 2009.
[10]
X. Yang, J. Zeng, and J. Liang, “Apply MGA to multi-objective flexible job shop scheduling problem,” in Proceedings of the International Conference on Information Management, Innovation Management and Industrial Engineering (ICIII '09), pp. 436–439, December 2009.
[11]
M. Basseur, F. Seynhaeve, and E.-G. Talbi, “Path relinking in Pareto multi-objective genetic algorithms,” in Proceedings of the 3rd International Conference on Evolutionary Multi-Criterion Optimization (EMO '05), pp. 120–134, March 2005.
[12]
P. Chitra, S. Revathi, P. Venkatesh, and R. Rajaram, “Evolutionary algorithmic approaches for solving three objectives task scheduling problem on heterogeneous systems,” in Proceedings of the IEEE 2nd International Advance Computing Conference (IACC '10), pp. 38–43, February 2010.
[13]
R. P. Dick and N. K. Jha, “MOGAC: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, no. 10, pp. 920–935, 1998.
[14]
M. Camelo, Y. Donoso, and H. Castro, “MAGS—an approach using multi-objective evolutionary algorithms for grid task scheduling,” International Journal of Applied Mathematics and Informatics, vol. 5, no. 2, 2011.
[15]
F. S. Kazemi and R. Tavakkoli-Moghaddam, “Soving a multi-objective multi-mode resource-constrained project scheduling problem with particle swarm optimization,” International Journal of Academic Research, vol. 3, no. 1, 2011.
[16]
Y. Hu and B. Gong, “Multi-objective optimization approaches using a CE-ACO inspired strategy to improve grid jobs scheduling,” in Proceedings of the 4th ChinaGrid Annual Conference (ChinaGrid '09), pp. 53–58, August 2009.
[17]
M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. Freund, “Dynamic mapping of a class of independent tasks onto heterogeneous computing systems,” in Proceedings of the 8th IEEE Heterogeneous Computing Workshop (HCW '99), pp. 30–44, San Juan, Puerto Rico, April 1999.
[18]
N. Srinivas and K. Deb, “Multi-objective optimization using non-dominated sorting in genetic algorithms,” Evolution Computing, vol. 2, no. 3, pp. 221–248, 1994.
[19]
E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach,” IEEE Transactions on Evolutionary Computation, vol. 3, no. 4, pp. 257–271, 1999.
[20]
Y. Iosifidis, A. Mallik, S. Mamagkakis et al., “A framework for automatic parallelization, static and dynamic memory optimization in MPSoC platforms,” in Proceedings of the 47th Design Automation Conference, (DAC '10), pp. 549–554, June 2010.
[21]
A. Y. Zomaya, C. Ward, and B. Macey, “Genetic scheduling for parallel processor systems: Comparative studies and performance issues,” IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 8, pp. 795–812, 1999.
[22]
S. H. Hou, N. Ansari, and H. Ren, “Genetic algorithm for multiprocessor scheduling,” IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 2, pp. 113–120, 1994.
