Scheduling techniques play a prominent role in parallel computing environment to reduce the waiting time of users. Parallel computing provides an incredible amount of resources for user’s on-demand. Therefore, it has become more challenging to schedule the resources in an efficient manner. It has been observed that scheduling is NP-Hard in nature so in order to solve this, meta-heuristic techniques are used for optimal solution. This paper has exhibited a comprehensive review on different scheduling algorithms in the perspective of scheduling metrics such as Execution cost, response time, Makespan, Energy Consumption, Resource utilization are presented. Additionally, classification of meta-heuristic techniques such as GA, PSO, ACO, DA etc. and various constraints designed for parallel computing environment have also been discussed.

ParallelComputing,Scheduling,Meta-heuristics,Deadline,ReliabilityConstraint

[1] S.H. Roosta, “Parallel Processing and Parallel Algorithms: Theory and Computation”, Springer Publication, 2000.
[2] [2] A. A Chandio , K Bilal ,N.Tziritas • Z. Yu ,Q. Jiang ,S.U. Khan ,C.Z. "A comparative study of job scheduling strategies in large-scale parallel computational systems." In Trust, Security and Privacy in Computing and Communications (TrustCom), 2013 12th IEEE International Conference on, pp. 949-957. IEEE, 2013.
[3] D. Agarwal, S. Jain, et al., “Efficient optimal algorithm of task scheduling in cloud computing environment," arXiv preprint arXiv:1404.2076, 2014.
[4] D. E Goldberg,"Genetic algorithms in Search, Optimization and Machine Leaning", Pearson Education India, 2006.
[5] R. Eberhart and J. Kennedy. “A New Optimizer Using Particle Swarm Theory”. In International Symposium on Micro Machine and Human Science, pages 3943. IEEE, 10, 14,1995.
[6] X. S Yang, and S. Deb, “Cuckoo search via Levy flights, “In: Proc. of World Congress on Nature & Biologically Inspired Computing (NaBic 2009), India, IEEE Publications, USA, pp. 210–214,2009.
[7] Yaseen, S. Ghaleb, and Nada MA Al-Slamy. "Ant colony optimization." IJCSNS 8.6: 351,2008.
[8] S. Mirjalili, “Dragonfly algorithm: a new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems," Neural Computing and Applications, vol. 27, no. 4, pp. 1053,1073, 2016.
[9] R.Abbas ,Haidri, C.P.katti, P.C Saxena, “Cost Effective Deadline Aware Scheduling Strategy for Workflow Applications on Virtual Machines in Cloud Computing”, Journal of King Saud University – Computer and Information Sciences 2017.
[10] Xiao, Xiongren, G. Xie, C. Xu, C.Fan, R.Li, and K. Li. "Maximizing reliability of energy constrained parallel applications on heterogeneous distributed systems." Journal of Computational Science (2017).
[11] Zhang, Y. Wen, H.Z. Zhang, and C .Wang "Reliability-aware low energy scheduling in real time systems with shared resources." Microprocessors and Microsystems 52: 312-324,2017.
[12] E. Hyytiä, R. Righter, O. Bilenne, and W. Xiaohu. "Dispatching fixed-sized jobs with multiple deadlines to parallel heterogeneous servers." Performance Evaluation (2017)
[13] J. Zhou, K. Cao, P. Cong, T .Wei,M. Chen, G.Zhang, J. Yan, and “Reliability and temperature constrained task scheduling for Makespan minimization on heterogeneous multi-core platforms”. Journal of Systems and Software, 133, pp.1-16(2017).
[14] Haque, Mohammad, H. Aydin, and D. Zhu. "On Reliability Management of Energy-Aware Real-Time Systems Through Task Replication." IEEE Transactions on Parallel and Distributed Systems 28, no. 3: 813-825,2017.
[15] A. Verma, and S. Kaushal. "A hybrid multi-objective Particle Swarm Optimization for scientific workflow scheduling." Parallel Computing 62 (2017): 1-19.
[16] Seddik, Yasmina, and Z. Hanzálek. "Match-up scheduling of mixed-criticality jobs: Maximizing the probability of jobs execution." European Journal of Operational Research262, no. 1 (2017): 46-59.
[17] Liu, Li, M. Zhang, R. Buyya, and Q Fan. "Deadline‐constrained coevolutionary genetic algorithm for scientific workflow scheduling in cloud computing." Concurrency and Computation: Practice and Experience 29, no. 5 ,2017.
[18] Ghasemzadeh, Mozhgan, H.Arabnejad, and J.G. Barbosa. "Deadline-Budget constrained Scheduling Algorithm for Scientific Workflows in a Cloud Environment." In LIPIcs-Leibniz International Proceedings in Informatics, vol. 70. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
[19] Wang, Shuli, L .Kenli, M. Jing, X. Guoqing and L .Keqin. "A Reliability-aware Task Scheduling Algorithm Based on Replication on Heterogeneous Computing Systems." Journal of Grid Computing 15, no. 1: 23-39.2017.
[20] Xie, Guoqi, G Zeng, C Yuekun , Y Bai, Z Zhou, L Renfa , and L Keqin . "Minimizing redundancy to satisfy reliability requirement for a parallel application on heterogeneous service-oriented systems." IEEE Transactions on Services Computing (2017).
[21] Zhang, Longxin, L.Kenli , L.Changyun , and L.Keqin . "Bi-objective workflow scheduling of the energy consumption and reliability in heterogeneous computing systems." Information Sciences 379: 241-256,2017
[22] Deldari, Arash, M Naghibzadeh, and S Abrishami. "CCA: a deadline-constrained workflow scheduling algorithm for multicore resources on the cloud." The journal of Supercomputing 73, no. 2: 756-781,2017.
[23] Wu, Quanwang, F.Ishikawa, Z.Qingsheng, X.Yunni, and J.Wen. "Deadline-constrained Cost Optimization Approaches for Workflow Scheduling in Clouds." IEEE Transactions on Parallel and Distributed Systems (2017).
[24] G Kaur, and M Kalra. "Deadline constrained scheduling of scientific workflows on cloud using hybrid genetic algorithm." In Cloud Computing, Data Science & Engineering-Confluence, 2017 7th International Conference on, pp. 276-280. IEEE, 2017.
[25] Xie, Guoqi, Y Chen, X. Xiao, C Xu, Li Renfa , and Li Keqin . "Energy-efficient Fault-tolerant Scheduling of Reliable Parallel Applications on Heterogeneous Distributed Embedded Systems." IEEE Transactions on Sustainable Computing (2017).
[26] P Kaur, and S.Mehta. "Resource provisioning and work flow scheduling in clouds using augmented Shuffled Frog Leaping Algorithm." Journal of Parallel and Distributed Computing 101: 41-50,2017.
[27] Gedik, Ridvan, C. Rainwater, H. Nachtmann, and Ed A. Pohl. "Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals." European Journal of Operational Research 251, no. 2: 640-6.50,2016.
[28] Hao, Yongsheng, LWang, and M Zheng. "An adaptive algorithm for scheduling parallel jobs in meteorological Cloud." Knowledge-Based Systems 98: 226-240,2016.
[29] N Kaur, and S Singh. "A Budget-constrained Time and Reliability Optimization BAT Algorithm for Scheduling Workflow Applications in Clouds." Procedia Computer Science 98: 199-204,2016.
[30] S, Jiyuan, L Junzhou, F Dong, J Zhang, and J. Zhang. "Elastic resource provisioning for scientific workflow scheduling in cloud under budget and deadline constraints." Cluster Computing 19, no. 1: 167-182,2016.
[31] T.Kaur, and I Chana. "Energy aware scheduling of deadline constrained tasks in cloud computing." Cluster Computing 19, no.2 : 679-698,2016.
[32] Zhang, Longxin, Li Kenli, Xu Yuming , M Jing F Zhang, and Li Keqin . "Maximizing reliability with energy conservation for parallel task scheduling in a heterogeneous cluster." Information Sciences 319: 113-131,2015.
[33] Chen, Z. Gan, K Du, Z. Zhan, and Jun Zhang. "Deadline constrained cloud computing resources scheduling for cost optimization based on dynamic objective genetic algorithm." In Evolutionary Computation (CEC), 2015 IEEE Congress on, pp. 708-714. IEEE, 2015.
[34] A. Verma and S. Kaushal, “Cost Minimized PSO based Workflow Scheduling Plan for Cloud Computing”, I.J. Information Technology and Computer Science, vol.08, 37-43, 2015 Published Online July 2015 in MECS (http://www.mecs-press.org/) DOI: 10.5815/ijitcs.2015.08.06.
[35] L. zuo, L.shu, S. dong, C.zhu, (Student Member, IEEE), AND T. hara4, (Senior Member, IEEE) “A Multi-Objective Optimization Scheduling Method Based on the Ant Colony Algorithm in Cloud Computing”, IEEE Transaction clod computing, Vol-3, December 23, 2015.
[36] Liu, Guoquan, Y. Zeng, Dong Li, and Y. Chen. "Schedule length and reliability-oriented multi-objective scheduling for distributed computing." Soft Computing 19, no. 6 (2015): 1727-1737.
[37] Abudhagir, U. Syed, and S. Shanmugavel. "A novel dynamic reliability optimized resource scheduling algorithm for grid computing system." Arabian Journal for Science and Engineering 39, no. 10 (2014): 7087-7096.
[38] A. Verma, and S. Kaushal. "Deadline constraint heuristic-based genetic algorithm for workflow scheduling in cloud." International Journal of Grid and Utility Computing 5, no. 2: 96-106,2014.