Improved Dynamic Johnson Sequencing Algorithm (DJS) in Cloud Computing Environment for Efficient Resource Scheduling for Distributed Overloading

Abstract

This study introduces an innovative approach to optimize cloud computing job distribution using the Improved Dynamic Johnson Sequencing Algorithm (DJS). Emphasizing on-demand resource sharing, typical to Cloud Service Providers (CSPs), the research focuses on minimizing job completion delays through efficient task allocation. Utilizing Johnson’s rule from operations research, the study addresses the challenge of resource availability post-task completion. It advocates for queuing models with multiple servers and finite capacity to improve job scheduling models, subsequently reducing wait times and queue lengths. The Dynamic Johnson Sequencing Algorithm and the M/M/c/K queuing model are applied to optimize task sequences, showcasing their efficacy through comparative analysis. The research evaluates the impact of makespan calculation on data file transfer times and assesses vital performance indicators, ultimately positioning the proposed technique as superior to existing approaches, offering a robust framework for enhanced task scheduling and resource allocation in cloud computing.

Keywords

First come first served (FCFS) scheduling / round robin / task scheduling / queuing model / Johnson scheduling algorithm

References

[1] Alkhashai H M, Omara F A. An enhanced task scheduling algorithm on cloud computing environment. International Journal of Grid and Distributed Computing, 2016, 9(7): 91-100.

[2] Banerjee P, Roy S, Sinha A, Hassan M M, Burje S, Agrawal A, ⋯, El-Shafai W (2023). MTD-DHJS: Makespanoptimizedtaskschedulingalgorithmforcloudcomput-ing with dynamic computational time prediction. IEEE Access: 105578–105618.

[3] Baranwal G, Vidyarthi D P. A fair multi-attribute combinatorial double auction model for resource allocation in cloud computing. Journal of Systems and Software, 2015, 108: 60-76.

[4] Barrett E, Howley E, Duggan J (2011). A learning architecture for scheduling workflow applications in the cloud. 2011 IEEE Ninth European Conference on Web Services. Lugano, Switzerland, September 14–16, 2011.

[5] Calheiros R N, Buyya R. Meeting deadlines of scientific workflows in public clouds with tasks replication. IEEE Transactions on Parallel and Distributed Systems, 2013, 25(7): 1787-179.

[6] Cheng C, Li J, Wang Y. An energy-saving task scheduling strategy based on vacation queuing theory in cloud computing. Tsinghua Science and Technology, 2015, 20(1): 28-39.

[7] Delavar A G, Javanmard M, Shabestari M B, Talebi M K. RSDC (reliable scheduling distributed in cloud computing). International Journal of Computer Science, Engineering and Applications, 2012, 2(3): 1.

[8] Ding J, Zhang Z, Ma R T, Yang Y. Auction-based cloud service differentiation with service level objectives. Computer Networks, 2016, 94: 231-249.

[9] El-kenawy E S T, El-Desoky A I, Al-rahamawy M F. Extended max-min scheduling using petri net and load balancing. International Journal Soft Computing Engineering (IJSCE), 2012, 2(4): 198-203.

[10] Gan G N, Huang T L, Gao S (2010). Genetic simulated annealing algorithm for task scheduling based on cloud computing environment. International Conference on Intelligent Computing and Integrated Systems. Guilin, China, October 22–24, 2010.

[11] Ge J W, Yuan Y S. Research of cloud computing task scheduling algorithm based on improved genetic algorithm. Applied Mechanics and Materials, 2013, 347: 2426-2429.

[12] Gu J, Hu J, Zhao T, Sun G. A new resource scheduling strategy based on genetic algorithm in cloud computing environment. Journal of Computers, 2012, 7(1): 42-52.

[13] Himthani P, Saxena A, Manoria M (2015). Comparative analysis of VM scheduling algorithms in cloud environment. International Journal of Computer Applications 120(6).

[14] Hines M R, Gopalan K (2009). Post-copy based live virtual machine migration using adaptive pre-paging and dynamic self-ballooning. Proceedings of the 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments. Washington DC, USA, March 11–13, 2009.

[15] Jansen R, Brenner P R (2011). Energy efficient virtual machine allocation in the cloud. 2011 International Green Computing Conferenceand Workshops. Orlando, USA, July 25–28, 2011.

[16] Kalra M, Singh S. A review of metaheuristic scheduling techniques in cloud computing. Egyptian Informatics Journal, 2015, 16(3): 275-295.

[17] Karthick A V, Ramaraj E, Subramanian R G (2014). An efficient multi queue job scheduling for cloud computing. 2014 World Congress on Computing and Communication Technologies. Trichirappalli, India, February 27–March 01, 2014.

[18] Khazaei H, Misic J, Misic V B (2011). Modelling of cloud computing centers using M/G/m queues. 2011 31st International Conference on Distributed Computing Systems Workshops. Minneapolis, USA, June 20–24, 2011.

[19] Khazaei H, Misic J, Misic V B. Performance analysis of cloud computing centers using M/G/m/m + r queuing systems. IEEE Transactions on Parallel and Distributed Systems, 2011, 23(5): 936-943.

[20] Kumar K, Hans A, Sharma A, Singh N (2015). A review on scheduling issues in cloud computing. International Journal of Computer Applications.

[21] Kuo R J, Cheng W C. Hybrid meta-heuristic algorithm for job shop scheduling with due date time window and release time. The International Journal of Advanced Manufacturing Technology, 2013, 67: 59-71.

[22] Lee C, Wang P, Niyato D. A real-time group auction system for efficient allocation of cloud internet applications. IEEE Transactions on Services Computing, 2013, 8(2): 251-268.

[23] Lin C C, Liu P, Wu J J (2011). Energy-efficient virtual machine provision algorithms for cloud systems. 2011 Fourth IEEE International Conference on Utility and Cloud Computing, Melbourne, Australia, December 05–08, 2011

[24] Liu H, Jin H, Liao X, Hu L, Yu C (2009). Live migration of virtual machine based on full system trace and replay. Proceedings of the 18th ACM International Symposium on High Performance Distributed Computing. Garching, Germany, June 11–13, 2009.

[25] Mangla N, Singh M, Rana S K. Resource scheduling in cloud environmet: A survey. Advances in Science and Technology Research Journal, 2016, 10(30): 38-50.

[26] Mishra R K, Kumar S, Naik B S (2014). Priority based round-robin service broker algorithm for cloud-analyst. 2014 IEEE International Advance Computing Conference (IACC). Gurgaon, India, February 21–22, 2014.

[27] Nejad M M, Mashayekhy L, Grosu D. Truthful greedy mechanisms for dynamic virtual machine provisioning and allocation in clouds. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(2): 594-603.

[28] Pal S, Le D N, Pattnaik P K (2022). Classification of Virtualization Environment. Cloud ComputingSolutions: Architecture, Data Storage, Implementation and Security: 77–90.

[29] Pal S, Pattnaik P K. Efficient architectural framework for cloud computing. International Journal of Cloud Computingand Services Science, 2012, 1(2): 66

[30] Poola D, Ramamohanarao K, Buyya R. Fault-tolerant workflow scheduling using spot instances on clouds. Procedia Computer Science, 2014, 29: 523-533.

[31] Salot P. A survey of various scheduling algorithm in cloud computing environment. International Journal of Research in Engineeringand Technology, 2013, 2(2): 131-135.

[32] Sarathy V, Narayan P, Mikkilineni R (2010). Next generation cloud computing architecture: Enabling real-time dynamism for shared distributed physical infrastructure. 2010 19th IEEE International Workshops on Enabling Technologies: Infrastructures for Collaborative Enterprises. Larissa, Greece, June 28–30, 2010.

[33] Schmidt M, Fallenbeck N, Smith M, Freisleben, B (2010). Efficient distribution of virtual machines for cloud computing. 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing. Pisa, Italy, February 17–19, 2010.

[34] Shaikh F B, Haider S (2011). Security threats in cloud computing. 2011 International Conference for Internet Technology and Secured Transactions. Abu Dhabi, United Arab Emirates, December 11–14, 2011.

[35] Singh S, Chana I. A survey on resource scheduling in cloud computing: Issues and challenges. Journal of Grid Computing, 2016, 14: 217-264.

[36] Sowjanya T S, Praveen D, Satish K, Rahiman A (2011). The queueing theory in cloud computing to reduce the waiting time. International Journal of Computer Science EngineeringTechnology 1(3).

[37] Sundareswaran S, Squicciarini A, Lin D (2012). A brokerage-based approach for cloud service selection. 2012 IEEE Fifth International Conference on Cloud Computing. Honolulu, USA, June 24–29, 2012.

[38] Szabo C, Kroeger T (2012). Evolving multi-objective strategies for task allocation of scientific workflows on public clouds. In 2012 IEEE Congress on Evolutionary Computation. Brisbane, Australia, June 10–15, 2012.

[39] Talukder A K A, Kirley M, Buyya R. Multiobjective differential evolution for scheduling workflow applications on global grids. Concurrency and Computation: Practice and Experience, 2009, 21(13): 1742-1756.

[40] Topcuoglu H, Hariri S, Wu M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.

[41] Xiao Z, Song W, Chen Q. Dynamic resource allocation using virtual machines for cloud computing environment. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(6): 1107-1117.

[42] Yang S, Kwon D, Yi H, Cho Y, Kwon Y, Paek Y. Techniques to minimize state transfer costs for dynamic execution offloading in mobile cloud computing. IEEE Transactions on Mobile Computing, 2014, 13(11): 2648-2660.

[43] Yassein M O B, Khamayseh Y M, Hatamleh A M. Intelligent randomize round Robin for cloud computing. International Journal of Cloud Applications and Computing, 2013, 3(1): 27-33.

[44] Ye K, Jiang X, Ye D, Huang D (2010). Two optimization mechanisms to improve the isolation property of server consolidation in virtualized multi-core server. 2010 IEEE 12th International Conference on High Performance Computing and Communications (HPCC). Melbourne, Australia, September 01–03, 2010.

[45] Yu J, Kirley M, Buyya R (2007). Multi-objective planning for workflow execution on grids. 2007 8th IEEE/ACM International Conference on Grid Computing. Austin, USA, September 19–21, 2007.

[46] Zhang Y, Li B, Huang Z, Wang J, Zhu J. SGAM: strategy-proof group buying-based auction mechanism for virtual machine allocation in clouds. Concurrency and Computation: Practice and Experience, 2015, 27(18): 5577-5589.

[47] Zhao W, Stankovic J A (1989). Performance analysis of FCFS and improved FCFS scheduling algorithms for dynamic real-time computer systems. 1989 Real-Time Systems Symposium. Santa Monica, USA, December 05–07, 1989.

[48] Zheng M, Sanán D, Sun J, Liu Y, Dong J S, Gu Y. Giacobazzi R, Berdine J, Mastroeni I. State space reduction for sensor networks using two-level partial order reduction. Verification, Model Checking, and Abstract Interpretation, 2013, Berlin, Heidelberg: Springer vol 7737

[49] Zhu Z, Zhang G, Li M, Liu X. Evolutionary multi-objective workflow scheduling in cloud. IEEE Transactions on Parallel and Distributed Systems, 2015, 27(5): 1344-1357.