Scheduling Independent Parallel Jobs in Cloud Computing: A Survey

Samaneh Abdolhosseini, Mohammad Taghi Kheirabadi

Abstract


The impressive and rapid development of the internet and wireless networks leads to growing of users in the last decade. Therefore, the limited resources of these systems are now more evident than in the past. Cloud computing is the latest technology to handle the limitation of resources for users. Type of jobs play the main role in the design of scheduling algorithms. A job can be run simultaneously by multi-processor called parallel job, while the job can run by a single processor called serial job. In addition, based on dependency of jobs to each other, the jobs can be divided into dependent and independent jobs. Scheduling the independent parallel jobs is one of important challenges in cloud computing. Hence, in this paper, we classified the existing algorithms of scheduling independent parallel jobs into two main categories including Non-Layer and Two-Layer. This division is performed based on the number of jobs running on a processor simultaneously. Furthermore, the existing scheduling algorithms belong to each categories are divided into two subcategories based on their solving techniques including heuristic and metaheuristic. Then, the algorithms belong to each category are described in detail. After that, these algorithms are compared to each other based on their different attributes. Our analysis show that the existing Two-Layer scheduling algorithms focus on cost parameter to increase the performance of scheduling algorithms by reducing the waste time of CPU through simultaneous assigning more than one job to each physical machine, while Non-Layer scheduling algorithms didn't pay attention to this issue and only employ techniques to manage the scheduling queue in order to improve the different parameters such as cost, energy, load balancing and deadline.

Keywords


Cloud Computing; Independent Jobs; Resource Allocation; Scheduling Parallel Job;

Full Text:

PDF

References


H., Luo, “A Distributed Management Method Based on the Artificial Fish-Swarm Model in Cloud Computing Environment, ” International Journal of Wireless Information Networks, 2018. 25(3): p. 289-295.

W. and A. van Moorsel, Wongthai, “Logging System Architectures for Infrastructure as a Service Cloud,” Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 2017. 9(2-4): p. 35-40.

S., Ab, M. Dogan, and E. Alqahtani, “A Survey On Resource Allocation In Cloud Computing, ” Vol. 6. 2016.

Z., Li, et al., “Bandwidth-Guaranteed Resource Allocation and Scheduling for Parallel Jobs in Cloud Data Center, ” Symmetry, 2018. 10(5): p. 134.

D., Komarasamy, and V. Muthuswamy, “Priority scheduling with consolidation based backfilling algorithm in cloud,” World Wide Web, 2018: p. 1-19.

Y., Zhu, and L. Zhou, “An Compression Technology for Effective Data on Cloud Platform,” International Journal of Wireless Information Networks, 2018. 25(3): p. 340-347.

H., Althumali , M. Hussin, and Z.M. Hanapi, “Cost Efficient Scheduling Through Auction Mechanism in Cloud Computing, ” Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 2017. 9(2-10): p. 65-69.

L.F., Bittencourt, et al., “Scheduling in distributed systems: A cloud computing perspective,” Computer Science Review, 2018. 30: p. 31- 54.

R. Tyagi, and S.K. Gupta, “A Survey on Scheduling Algorithms for Parallel and Distributed Systems, ” in Silicon Photonics & High Performance Computing. 2018, Springer. p. 51-64.

Yang, J. and Q. He, “Scheduling parallel computations by work stealing: a survey. International Journal of Parallel Programming, 2018. 46(2): p. 173-197.

P. Akilandeswari, and H. Srimathi, “Survey and analysis on Task scheduling in Cloud environment, ” Indian Journal of Science and Technology, 2016. 9(37).

Meriam, and N. Tabbane. “A Survey on Cloud Computing Scheduling Algorithms, ” In: 2016 Global Summit on Computer & Information Technology (GSCIT). 2016. IEEE.

E. Liu, Y., et al. “A Fuzzy-based Approach for MobilePeerDroid System Considering of Peer Communication Cost, ” in International Conference on P2P, Parallel, Grid, Cloud and Internet Computing. 2018. Springer. pp 180-191

Chrétienne, P. and A. Quilliot, “A polynomial algorithm for the homogeneously non-idling scheduling problem of unit-time independent jobs on identical parallel machines, ” Discrete Applied Mathematics, 2018. 243: p. 132-139.

P. Durgadevi, and S. Srinivasan, “Resource Allocation in Cloud Computing Using SFLA and Cuckoo Search Hybridization, ” International Journal of Parallel Programming, 2018: p. 1-17.

X. Zhang, , et al., “Securing elastic applications on mobile devices for cloud computing, ” in Proceedings of the 2009 ACM workshop on Cloud computing security. 2009, ACM: Chicago, Illinois, USA. p. 127-134.

Aggarwal, R., “Resource Provisioning and Resource Allocation in Cloud Computing Environment, ” Vol. 3 , no. 3, 2018. pp. 1040– 1049.

L. Huang, , H.-s. Chen, and T.-t. Hu, “Survey on Resource Allocation Policy and Job Scheduling Algorithms of Cloud Computing, ” 1. JSW, 2013. 8(2): p. 480-487.

J.-T. Tsai,., J.-C. Fang, and J.-H. Chou, “Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm, ” Computers & Operations Research, 2013. 40(12): p. 3045-3055.

S. Jayanthi, “Literature review: Dynamic resource allocation mechanism in cloud computing environment,” In: 2014 International Conference on Electronics, Communication and Computational Engineering (ICECCE). 2014. IEEE.

L. Shi, , Z. Zhang, and T. Robertazzi, “Energy-Aware Scheduling of Embarrassingly Parallel Jobs and Resource Allocation in Cloud, ” IEEE Transactions on Parallel and Distributed Systems, 2017. 28(6): p. 1607-1620.

A. Beloglazov , J. Abawajy, and R. Buyya, “Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing, ” Future generation computer systems, 2012. 28(5): p. 755-768.

A. Beloglazov, et al., “A taxonomy and survey of energy-efficient data centers and cloud computing systems,” Advances in computers, 2011. 82(2): p. 47-111.

S.T. Selvi, C. Valliyammai, and V.N. Dhatchayani. “Resource allocation issues and challenges in cloud computing, ” In 2014 International Conference on Recent Trends in Information Technology. 2014. IEEE.

T. Meng, , et al., “A secure and cost-efficient offloading policy for Mobile Cloud Computing against timing attacks, ” Pervasive and Mobile Computing, 2018. 45: p. 4-18.

M.H. Mohamaddiah , et al., “A survey on resource allocation and monitoring in cloud computing. International Journal of Machine Learning and Computing, 2014. 4(1): p. 31.

F. Capobianco, “5 Reasons To Care About Mobile Cloud Computing. International Free and Open Source Software Law Review, ” 2010. 1(2): p. 139-142.

N.R. Mohan, and E.B. Raj. “Resource Allocation Techniques in Cloud Computing--Research Challenges for Applications, ” In: 2012 Fourth International Conference on Computational Intelligence and Communication Networks (CICN). 2012. IEEE.

X. Liu, et al., “Scheduling parallel jobs with tentative runs and consolidation in the cloud, ” Journal of Systems and Software, 2015. 104: p. 141-151.

F. Villa, , E. Vallada, and L. Fanjul-Peyro, “Heuristic algorithms for the unrelated parallel machine scheduling problem with one scarce additional resource, ” Expert Systems with Applications, 2018. 93: p. 28-38.

A. Choudhary, , et al. “Workflow scheduling algorithms in cloud environment: A review, taxonomy, and challenges, ” In: 2016 Fourth International Conference on Parallel, Distributed and Grid Computing (PDGC). 2016. IEEE.

M. Abdullahi, and M.A. Ngadi, “Symbiotic Organism Search optimization based task scheduling in cloud computing environment, ” Future Generation Computer Systems, 2016. 56: p. 640-650.

L. Wu, , Y.J. Wang, and C.K. Yan. “Performance comparison of energy-aware task scheduling with GA and CRO algorithms in cloud environment, ” in Applied Mechanics and Materials. 2014. Trans Tech Publ.

S. Durga, , S. Mohan, and J.D. Peter, “A Two-Stage Queue Model for Context-Aware Task Scheduling in Mobile Multimedia Cloud Environments, ” in Advances in Big Data and Cloud Computing, 2018, Springer. p. 287-297.

K. Li, , “Scheduling parallel tasks with energy and time constraints on multiple Manycore processors In A cloud computing environment, ” Future Generation Computer Systems, 2017.

Y. Chen, Z. Yu, and B. Li. “Clockwork: Scheduling Cloud Requests in Mobile Applications, ” in 2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON). 2017.

F. Cao, M.M. Zhu, and C.Q. Wu. “Energy-efficient resource management for scientific workflows in clouds, ” In: 2014 IEEE World Congress on Services (SERVICES). 2014. IEEE.

Q. Zhang, , H. Liang, and Y. Xing, “A parallel task scheduling algorithm based on fuzzy clustering in cloud computing environment, ” International Journal of Machine Learning and Computing, 2014. 4(5): p. 437.

S.G. Domanal, and G.R.M. Reddy. “Load balancing in cloud computingusing modified throttled algorithm,” In: 2013 IEEE International Conference on Cloud Computing in Emerging Markets (CCEM). 2013. IEEE.

H.V .Raghu, S.K. Saurav, and B.S. Bapu. “PAAS: Power Aware Algorithm for Scheduling in High Performance Computing,” in 2013 IEEE/ACM 6th International Conference on Utility and Cloud Computing. 2013.

U. Bhoi, and P.N. Ramanuj, “Enhanced max-min task scheduling algorithm in cloud computing,” International Journal of Application or Innovation in Engineering and Management (IJAIEM), 2013. 2(4): p. 259-264.

W. Zhang, Y. Wen, and D.O. Wu. “Energy-efficient scheduling policy for collaborative execution in mobile cloud computing,” In 2013 Proceedings Ieee Infocom. 2013. IEEE.

H. Chen, et al. “User-priority guided Min-Min scheduling algorithm for load balancing in cloud computing,” In: 2013 National Conference on Parallel Computing Technologies (PARCOMPTECH). 2013. IEEE.

S. Koneru, V.R. Uddandi, and S. Kavuri, “Resource Allocation Method using Scheduling methods for Parallel Data Processing in Cloud, ” International Journal of Computer Science and Information Technologies [IJCSIT], 2012. 3(4): p. 4625-4628.

V.V. Kumar, and S. Palaniswami, “A dynamic resource allocation method for parallel dataprocessing in cloud computing, ” Journal of computer science, 2012. 8(5).

B. Fahimnia, H. Davarzani, and A. Eshragh, “Planning of complex supply chains: A performance comparison of three meta-heuristic algorithms,” Computers & Operations Research, 2018. 89: p. 241- 252.

B. Jana, M. Chakraborty, and T. Mandal, “A Task Scheduling Technique Based on Particle Swarm Optimization Algorithm in Cloud Environment,” in Soft Computing: Theories and Applications. 2019, Springer. p. 525-536.

A.S. Kumar, and M. Venkatesan, “Task scheduling in a cloud computing environment using HGPSO algorithm,” Cluster Computing, 2018: p. 1-7.

D. Laha, and J.N. Gupta, “An Improved Cuckoo Search Algorithm for Scheduling Jobs on Identical Parallel Machines,” Computers & Industrial Engineering, 2018.Vol. 126. p. 348-360

T. Wen, , Z. Zhang, and M. Wang. “A Parallel Bee Colony Algorithm for Resource Allocation Application in Cloud Computing Environment, ” In: 2015 IEEE International Conference on Data Science and Data Intensive Systems. 2015.

P. Phuoc Hung, and E.-N. Huh, “An Adaptive Procedure for Task Scheduling Optimization in Mobile Cloud Computing,” Mathematical Problems in Engineering, 2015.Vol. 2015: p. 13.

R. Lin, and Q. Li. “Task scheduling algorithm based on Pre-allocation strategy in cloud computing,” In: 2016 IEEE International Conference on Cloud Computing and Big Data Analysis (ICCCBDA). 2016. IEEE.

S. Zhan, and H. Huo, “Improved PSO-based task scheduling algorithm in cloud computing,” Journal of Information & Computational Science, 2012. 9(13): p. 3821-3829.

K. Li, et al. “Cloud Task Scheduling Based on Load Balancing Ant Colony Optimization,” In 2011 Sixth Annual Chinagrid Conference. 2011.

Y.-D. Lin, et al., “Two-tier project and job scheduling for SaaS cloud service providers,” Journal of Network and Computer Applications, 2015. 52: p. 26-36.

X. Liu, et al., “Priority-based consolidation of parallel workloads in the cloud. IEEE Transactions on Parallel and Distributed Systems, 2013. 24(9): p. 1874-1883.

X. Liu, et al., “Scheduling Parallel Jobs Using Migration and Consolidation in the Cloud,” Mathematical Problems in Engineering, 2012.Vol. 2012: p. 18.

M. Ashouraie, and N. Jafari Navimipour, “Priority-based task scheduling on heterogeneous resources in the Expert Cloud,” Kybernetes, 2015. 44(10): p. 1455-1471.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

ISSN: 2180-1843

eISSN: 2289-8131