A hybrid instance-intensive workflow scheduling method in private cloud environment

Springer Science and Business Media LLC - Tập 18 - Trang 735-746 - 2017
Xin Ye1, Jia Li1, Sihao Liu1, Jiwei Liang1, Yaochu Jin1,2
1Institute of Information and Decision Technology, Dalian University of Technology, Dalian, People’s Republic of China
2Department of Computer Science, University of Surrey, Guildford, UK

Tóm tắt

Aiming to solve the problem of instance-intensive workflow scheduling in private cloud environment, this paper first formulates a scheduling optimization model considering the communication time between tasks. The objective of this model is to minimize the execution time of all workflow instances. Then, a hybrid scheduling method based on the batch strategy and an improved genetic algorithm termed fragmentation based genetic algorithm is proposed according to the characters of instance-intensive cloud workflow, where task priority dispatching rules are also taken into account. Simulations are conducted to compare the proposed method with the canonical genetic algorithm and two heuristic algorithms. Our simulation results demonstrate that the proposed method can considerably enhance the search efficiency of the genetic algorithm and is able to considerably outperform the compared algorithms, in particular when the number of workflow instances is high and the computational resource available for optimization is limited.

Tài liệu tham khảo

Benoit A, Dobrila A, Nicod J-M, Philippe L (2013) Scheduling linear chain streaming applications on heterogeneous systems with failures. Future Gener Comput Syst 29:1140–1151 Byun EK, Kee YS, Kim JS, Maeng S (2011) Cost optimized provisioning of elastic resources for application workflows. Future Gener Comput Syst 27:1011–1026 Chen W, Da Silva RF, Deelman E, Sakellariou R (2014) Using imbalance metrics to optimize task clustering in scientific workflow executions. Future Gener Comput Syst 46:69–84 De Falco I, Scafuri U, Tarantino E (2014) Two new fast heuristics for mapping parallel applications on cloud computing. Future Gener Comput Syst 37:1–13 Du W (2009) Toward community-based personal cloud computing. In: Proceedings of world academy of science engineering and technology, p 901 Durillo JJ, Nae V, Prodan R (2014) Multi-objective energy-efficient workflow scheduling using list-based heuristics. Future Gener Comput Syst 36:221–236 Fard HM, Prodan R, Fahringer T (2014) Multi-objective list scheduling of workflow applications in distributed computing infrastructures. J Parallel Distrib Comput 74:2152–2165 Fu Z, Sun X, Liu Q, Zhou L, Shu J (2015) Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE Trans Commun 98(1):190–200 Ghorbannia Delavar A, Aryan Y (2014) HSGA: a hybrid heuristic algorithm for workflow scheduling in cloud systems. Clust Comput 17:129–137 Hassan M, Song B, Hossain MS, Alamri A (2014) Efficient resource scheduling for big data processing in cloud platform. In: Internet and distributed computing systems, (Lecture notes in computer science), vol 8729. Springer, pp 51–63 Huang KC, Tsai YL, Liu HC (2015) Task ranking and allocation in list-based workflow scheduling on parallel computing platform. J Supercomput 71:217–240 Huifang L, Siyuan G, Lu Z (2014) A QoS-based scheduling algorithm for instance-intensive workflows in cloud environment. In: The 26th Chinese control and decision conference (2014 CCDC), 31 May 2014–2 June 2014, pp 4094–4099 Li W (2010) A community cloud oriented workflow system framework and its scheduling strategy. In: Proceedings 2010 IEEE 2nd symposium on web society Lingfang Z, Veeravalli B, Xiaorong L (2012) ScaleStar: budget conscious scheduling precedence-constrained many-task workflow applications in cloud. In: IEEE 26th international conference on advanced information networking and applications (AINA), 26–29 March 2012, pp 534–541 Moattar EZ, Rahmani AM, Derakhshi MRF (2007) Job scheduling in multiprocessor architecture using genetic algorithm. In: 4th IEEE conference on innovations in information technology, pp 248–251 Mocanu EM, Florea M, Ionut M (2012) Cloud computing task scheduling based on genetic algorithm. In: System IEEE conference, pp 1–6 Nasonov D, Butakov N (2014) Hybrid scheduling algorithm in early warning systems. Procedia Comput Sci 29:1677–1687 Pandey S (2010) Scheduling and management of data intensive application workflows in grid and cloud computing environments. Ph.D. dissertation, Department of Computer Science and Software Engineering, University of Melbourne, Melbourne Pereira WF, Bittencourt LF, Da Fonseca NLS (2013) Scheduler for data-intensive workflows in public clouds. In: 2nd IEEE latin American conference on cloud computing and communications (LatinCloud), 9–10 Dec 2013, pp 41–46 Ren Y, Shen J, Wang J, Han J, Lee S (2015) Mutual verifiable provable data auditing in public cloud storage. J Internet Technol 16:317–323 Rodriguez MA, Buyya R (2014) Deadline based resource provisioningand scheduling algorithm for scientific workflows on clouds. IEEE Trans Cloud Comput 2:222–235 Safi Esfahani F, Azmi Murad MA, Sulaiman MNB, Udzir NI (2011) Adaptable decentralized service oriented architecture. J Syst Softw 84:1591–1617 Singh L, Singh S (2014) A genetic algorithm for scheduling workflow applications in unreliable cloud environment. In: Martínez Pérez G, Thampi S, Ko R, Shu L (eds) Recent trends in computer networks and distributed systems security, vol 420., Communications in computer and information scienceSpringer, Berlin, pp 139–150 Vijindra, Shenai S (2012) Survey on scheduling issues in cloud computing. Procedia Eng 38:2881–2888 Yu J, Buyya R, Ramamohanarao K (2008) Workflow scheduling algorithms for grid computing. In: Xhafa F, Abraham A (eds) Metaheuristics for scheduling in distributed computing environments, vol 146., Studies in computational intelligenceSpringer, Berlin, pp 173–214 Yu L, Zhao S, Zhang Y et al (2013) Application of cloud workflow technologies in business intelligence SaaS platform. Comput Intergr Manuf Syst 19:1738–1747 Yun-Chia L, Chen AHL, Yung-Hsiang N (2014) Artificial bee colony for workflow scheduling. In: 2014 IEEE congress on evolutionary computation (CEC), 6–11 July 2014, pp 558–564 Zeng L, Veeravalli B, Li X (2015) SABA: a security-aware and budget-aware workflow scheduling strategy in clouds. J Parallel Distrib Comput 75:141–151 Zhang F, Cao J, Li K, Khan SU, Hwang K (2014) Multi-objective scheduling of many tasks in cloud platforms. Future Gener Comput Syst 37:309–320 Zhuo T, Zhenzhen C, Kenli L, Keqin L (2014) An efficient energy scheduling algorithm for workflow tasks in hybrids and DVFS-enabled cloud environment. In: Sixth international symposium on parallel architectures, algorithms and programming (PAAP), 13–15 July 2014, pp 255–261