Minimizing Time in Scheduling of Independent Tasks Using Distance-Based Pareto Genetic Algorithm Based on MapReduce Model

Devarajan Rajeswari^*, Veerabadran Jawahar Senthilkumar

Department of Electronics and Communication Engineering, College of Engineering, Anna University, Chennai, India.

DOI: 10.4236/cs.2016.76063                

Abstract

Distributed Systems (DS) have a collection of heterogeneous computing resources to process user tasks. Task scheduling in DS has become prime research case, not only due of finding an optimal schedule, but also because of the time taken to find the optimal schedule. The users of Ds services are more attentive about time to complete their task. Several algorithms are implemented to find the optimal schedule. Evolutionary kind of algorithms is one of the best, but the time taken to find the optimal schedule is more. This paper presents a distance-based Pareto genetic algorithm (DPGA) with the Map Reduce model for scheduling independent tasks in a DS environment. In DS, most of the task scheduling problem is formulated as multi-objective optimization problem. This paper aims to develop the optimal schedules by minimizing makespan and flow time simultaneously. The algorithm is tested on a set of benchmark instances. MapReduce model is used to parallelize the execution of DPGA automatically. Experimental results show that DPGA with MapReduce model achieves a reduction in makespan, mean flow time and execution time by 12%, 14% and 13% than non-dominated sorting genetic algorithm (NSGA-II) with MapReduce model is also implemented in this paper.

Keywords

Distributed Systems, Multi-Objective, MapReduce, Optimization, DPGA, NSGA-II

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Braun, T.D., Siegel, H.J, Beck, N., Boloni, L.L., Maheswaran, M., Reuther, A.I., Robertson, J.P., Theys, M.D. and Yao, B. (2001) Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems. Journal of Parallel and Distributed Computing, 61, 810-837. http://dx.doi.org/10.1006/jpdc.2000.1714
[2]	Subashini, G. and Bhuvaneswari, M.C. (2011) Non Dominated Particle Swarm Optimization for Scheduling Independent Tasks on Heterogeneous Distributed Environments. International Journal of Advances in Soft Computing and Its Applications, 3, 1.
[3]	Kaiwartya, O., Prakash, S., Abdullah, A.H. and Hassan, A.N. (2015) Minimizing Energy Consumption in Scheduling of Dependent Tasks Using Genetic Algorithm in Computational Grid. KSII Transactions on Internet and Information Systems, 9, 8.
[4]	Abraham, A., Liu, H., Zhang, W. and Chang, T.G. (2006) Scheduling Jobs on Computational Grids Using Fuzzy Particle Swarm Algorithm. Springer-Verlag, Berlin, Heidelberg, 500-507. http://dx.doi.org/10.1007/11893004_65
[5]	Deb, K. (2002) Multi-Objective Optimization Using Evolutionary Algorithms. Wiley Publications.
[6]	Osycaka, A. and Kundu, S. (1995) A New Method to Solve Generalized Multicriteria Optimization Problems Using the Simple Genetic Algorithm. Structural Optimization, 10, 94-99. http://dx.doi.org/10.1007/BF01743536
[7]	Wang, F., Qiu, J., Yang, J., Dong, B., Li, X. and Li, Y. (2009) Hadoop High Availability through Metadata Replication. In: Cloud, D.B., Ed., Proceedings of the First International Workshop on Cloud Data Management. http://dx.doi.org/10.1145/1651263.1651271
[8]	Munir, E.U., Li, J.-Z., Shi, S.-F. and Rasool, Q. (2007) Performance Analysis of Task Scheduling Heuristics in Grid. ICMLC’07: Proceedings of the International Conference on Machine Learning and Cybernetics, 6, 3093-3098. http://dx.doi.org/10.1109/icmlc.2007.4370679
[9]	Maheswaran. M., Ali, S., Siegel, H.J., Hensgen, D. and Freund, R.F. (1999) Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems. Journal of Parallel and Distributed Computing, 59, 107-131. http://dx.doi.org/10.1006/jpdc.1999.1581
[10]	Freund, R.F., Gherrity, M., Ambrosius, S., Campbell, M., Halderman, M., Hensgen, D., Keith, T., Kussow, M., Lima, J.D., Mirabile, F., Moore, L., Rust, B. and Siegel, H.J. (1998) Scheduling Resources in Multiuser, Heterogeneous, Computing Environments with SmartNet. 7th IEEE Heterogeneous Computing Workshop, 184-199.
[11]	Abraham, A., Buyya, R. and Nath, B. (2000) Nature’s Heuristics for Scheduling Jobs on Computational Grids. The 8th IEEE International Conference on Advanced Computing and Communications (ADCOM 2000), India, 14-16.
[12]	Kang, Q.M. and He, H. (2011) A Novel Discrete Particle Swarm Optimization Algorithm for Meta-Task Assignment in Heterogeneous Computing Systems. Microprocessors and Microsystems, 35, 10-17. http://dx.doi.org/10.1016/j.micpro.2010.11.001
[13]	Pacini, E., Mateos, C. and Garino, C.G. (2015) Balancing Throughput and Response Time in Online Scientific Clouds via Ant Colony Optimization. Advances in Engineering Software, 84, 31-47. http://dx.doi.org/10.1016/j.advengsoft.2015.01.005
[14]	Hossein, S., Doulabi, H., Avazbeigi, M., Arab, S. and Davoudpour, H. (2012) An Effective Hybrid Simulated Annealing and Two Mixed Integer Linear Formulations for Just-in-Time Open Shop Scheduling Problem. The International Journal of Advanced Manufacturing Technology, 59, 1143-1155.
[15]	Izakian, H., Abraham, A. and Snasel, V. (2009) Comparison of Heuristics for Scheduling Independent Tasks on Heterogeneous Distributed Environments. IEEE Control Systems Magazine, 1, 8-12.
[16]	Abraham, A., Liu, H., Grosan, C. and Xhafa, F. (2008) Nature Inspired Meta-Heuristics for Grid Scheduling: Single and Multi-Objective Optimization Approaches. In: Xhafa, F. and Abraham, A., Eds., Metaheuristics for Scheduling in Distributed Computing Environments, Springer Verlog, Berlin, 247-272. http://dx.doi.org/10.1007/978-3-540-69277-5_9
[17]	Carretero, J., Xhafa, F. and Abraham, A. (2007) Genetic Algorithm Based Schedulers for Grid Computing Systems. International Journal of Innovative Computing, Information and Control, 3, 1-19.
[18]	Lim, D., Ong, Y.-S., Jin, Y., Sendhoff, B. and Lee, B.-S. (2007) Efficient Hierarchical Parallel Genetic Algorithms Using Grid Computing. Future Generation Computing Systems, 23, 658-670. http://dx.doi.org/10.1016/j.future.2006.10.008
[19]	Durillo, J.J., Nebro, A.J., Luna, F. and Alba, E. (2008) A Study of Master-Slave Approaches to Parallelize NSGA-II. IEEE International Symposium on Parallel and Distributed, Miami, 14-18 April 2008, 1-8. http://dx.doi.org/10.1109/IPDPS.2008.4536375
[20]	Subhashini, G. and Bhuvaneswari, M.C. (2010) A Fast and Elitist Bi-Objective Evolutionary Algorithm for Scheduling Independent Tasks on Heterogeneous Systems. ICTACT, Journal on Soft Computing, 1, 9-17.
[21]	Rajeswari, D. and Jawahar Senthilkumar, V. (2015) Multiprocessor Scheduling and Performance Evaluation Using Elitist Non-Dominated Sorting Genetic Algorithm for Independent Task. International Journal on Computational Science & Applications, 5, 49-59.
[22]	Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T. (2002) A Fast Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6, 182-197. http://dx.doi.org/10.1109/4235.996017
[23]	Rajeswari, D. and Jawahar Senthilkumar, V. (2015) Multiprocessor Scheduling and Performance Evaluation Using Distance-Based Pareto Genetic Algorithm for Independent Task. International Journal of Applied Engineering Research, 10, 33-38.
[24]	Dhole Poonam, B. and Gunjal Baisa, L. (2013) Survey Paper on Traditional Hadoop and Pipelined Map Reduce. International Journal of Computational Engineering Research, 3, 32-36.
[25]	http://hadoop.apache.org/docs/r1.2.1/mapred_tutorial.html
[26]	Niimura, T. and Nakashima, T. (2003) Multiobjective Tradeoff Analysis of Deregulated Electricity Transactions. International Journal of Electrical Power & Energy Systems, 25, 179-185. http://dx.doi.org/10.1016/S0142-0615(02)00076-5
[27]	Guzek, M., Pecero, J.E., Dorronsoro, B. and Bouvry, P. (2014) Multi-Objective Evolutionary Algorithms for Energy-Aware Scheduling on Distributed Computing Systems. Applied Soft Computing, 24, 432-446. http://dx.doi.org/10.1016/j.asoc.2014.07.010