A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 8 Issue 5
May  2021

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2021  >  8(5): 1079-1094
Y. Wang and X. Q. Zuo, “An effective cloud workflow scheduling approach combining pso and idle time slot-aware rules,” IEEE/CAA J. Autom. Sinica, vol. 8, no. 5, pp. 1079–1094, May 2021. doi: 10.1109/JAS.2021.1003982
Citation: Y. Wang and X. Q. Zuo, “An effective cloud workflow scheduling approach combining pso and idle time slot-aware rules,” IEEE/CAA J. Autom. Sinica, vol. 8, no. 5, pp. 1079–1094, May 2021. doi: 10.1109/JAS.2021.1003982
shu

An Effective Cloud Workflow Scheduling Approach Combining PSO and Idle Time Slot-Aware Rules

doi: 10.1109/JAS.2021.1003982
  • 1.

    School of Computing Science, Beijing University of Posts and Telecommunications, Beijing 100876, China

  • 2.

    School of Information Engineering, Nanchang Institute of Technology, Nanchang 330099, China

  • 3.

    Key Laboratory of Trustworthy Distributed Computing and Service (BUPT), Ministry of Education, Beijing 100876, China

Funds:  This work was supported in part by the National Natural Science Foundation of China (61874204, 61663028, 61703199), in part by the Science and Technology Plan Project of Jiangxi Provincial Education Department (GJJ190959)
More Information
    Abstract
  • Workflow scheduling is a key issue and remains a challenging problem in cloud computing. Faced with the large number of virtual machine (VM) types offered by cloud providers, cloud users need to choose the most appropriate VM type for each task. Multiple task scheduling sequences exist in a workflow application. Different task scheduling sequences have a significant impact on the scheduling performance. It is not easy to determine the most appropriate set of VM types for tasks and the best task scheduling sequence. Besides, the idle time slots on VM instances should be used fully to increase resources’ utilization and save the execution cost of a workflow. This paper considers these three aspects simultaneously and proposes a cloud workflow scheduling approach which combines particle swarm optimization (PSO) and idle time slot-aware rules, to minimize the execution cost of a workflow application under a deadline constraint. A new particle encoding is devised to represent the VM type required by each task and the scheduling sequence of tasks. An idle time slot-aware decoding procedure is proposed to decode a particle into a scheduling solution. To handle tasks’ invalid priorities caused by the randomness of PSO, a repair method is used to repair those priorities to produce valid task scheduling sequences. The proposed approach is compared with state-of-the-art cloud workflow scheduling algorithms. Experiments show that the proposed approach outperforms the comparative algorithms in terms of both of the execution cost and the success rate in meeting the deadline.

     

    • FullText(HTML)
  • loading
    • 1 https://confluence.pegasus.isi.edu/display/pegasus/WorkflowHub
    References(49)
  • [1]
    E. Deelman, D. Gannon, M. Shields, and I. Taylor, “Workflows and e-Science: An overview of workflow system features and capabilities,” Futur. Gener. Comp. Syst., vol. 25, no. 5, pp. 528–540, May 2009. doi: 10.1016/j.future.2008.06.012
    [2]
    P. Mell and T. Grance, The NIST Definition of Cloud Computing, document SP 800–145, NIST, Gaithersburg, MD, USA, 2001.
    [3]
    F. Wu, Q. Wu, and Y. Tan, “Workflow scheduling in cloud: A survey,” J. Supercomput., vol. 71, no. 9, pp. 3373–3418, 2015. doi: 10.1007/s11227-015-1438-4
    [4]
    Amazon elastic compute cloud (Amazon EC2) [Online]. Available: http://aws.amazon.com/ec2/, Accessed on: Mar. 2020.
    [5]
    J. Sahni and D. P. Vidyarthi, “A cost-effective deadline-constrained dynamic scheduling algorithm for scientific workflows in a cloud environment,” IEEE Trans. Cloud Comput., vol. 6, no. 1, pp. 2–18, Jan.-Mar. 2018. doi: 10.1109/TCC.2015.2451649
    [6]
    Y. Xu, K. Li, J. Hu, and K. Li, “A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues,” Inf. Sci., vol. 270, pp. 255–287, Jun. 2014. doi: 10.1016/j.ins.2014.02.122
    [7]
    Ullman and D. Jeffrey, “NP-complete scheduling problems,” J. Comput. Syst. Sci., vol. 10, no. 3, pp. 384–393, 1975. doi: 10.1016/S0022-0000(75)80008-0
    [8]
    Z. H. Zhan, X. F. Liu, Y. J. Gong, J. Zhang, S.H. Chung, and Y. Li, “Cloud computing resource scheduling and a survey of its evolutionary approaches,” ACM Comput. Surv., vol. 47, no. 4, pp. 1–33, Jul. 2015.
    [9]
    Z. Zhu, G. Zhang, M. Li, and X. Liu, “Evolutionary multi-objective workflow scheduling in cloud,” IEEE Trans. Parallel Distrib. Syst., vol. 27, no. 5, pp. 1344–1357, May 2016. doi: 10.1109/TPDS.2015.2446459
    [10]
    Z. G. Chen , Z. H. Zhan, Y. Lin, Y. J. Gong, T. L. Gu, F. Zhao, H. Q. Yuan, X. Chen, Q. Li, and J. Zhang, “Multi-objective cloud workflow scheduling: a multiple populations ant colony system approach,” IEEE Trans. Cloud Comput., vol. 49, no. 8, pp. 2912–2926, Aug. 2019.
    [11]
    S. Pandey, L. Wu, S. M. Guru, and R. Buyya, “A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments,” in Proc. IEEE Int. Conf. Adv. Inf. Netw. Appl., Perth, WA, Australia, 2010, pp. 400–407.
    [12]
    H. Y. Hu, Z. J. Li, H. Hu, J. Chen, J. D. Ge, C. Y. Li, and V. Chang, “Multi-objective scheduling for scientific workflow in multicloud environment,” J. Netw. Comput. Appl., vol. 114, pp. 108–122, Jul. 2018. doi: 10.1016/j.jnca.2018.03.028
    [13]
    H. R. Faragardi, S. Dehnavi, T. Nolte, M. Kargahi, and T. Fahringer, “An energy-aware resource provisioning scheme for real-time applications in a cloud data center,” Softw.,Practice Experience, vol. 48, no. 10, pp. 1734–1757, 2018.
    [14]
    X. Xu, W. Dou, X. Zhang, and J. Chen, “EnReal: An energy-aware resource allocation method for scientific workflow executions in cloud environment,” IEEE Trans. Cloud Comput., vol. 4, no. 2, pp. 166–179, Apr.–Jun. 2016. doi: 10.1109/TCC.2015.2453966
    [15]
    M. S. Kumar, I. Gupta, and P. K. Jana, “Resource-aware energy efficient workflow scheduling in Cloud Infrastructure,” in Proc. IEEE Int. Conf. Adv. Comput., Commun. Inf., Bangalore, India, 2018, pp. 293–299.
    [16]
    H. R. Faragardi, M. R. Saleh Sedghpour, S. Fazliahmadi, T. Fahringer, and N. Rasouli, “GRP-HEFT: A budget-bonstrained resource provisioning scheme for workflow scheduling in IaaS clouds,” IEEE Trans. Parallel Distrib. Syst., vol. 31, no. 6, pp. 1239–1254, Jun. 2020. doi: 10.1109/TPDS.2019.2961098
    [17]
    V. Arabnejad, K. Bubendorfer, and B. Ng, “Budget and deadline aware e-science workflow scheduling in clouds,” IEEE Trans. Parallel Distrib. Syst., vol. 30, no. 1, pp. 29–44, Jan. 2019. doi: 10.1109/TPDS.2018.2849396
    [18]
    M. A. Rodriguez and R. Buyya, “Budget-driven scheduling of scientific workflows in IaaS clouds with fine-grained billing periods,” ACM Trans. Auton. Adapt. Syst., vol. 12, no. 2, pp. 1–22, May 2017.
    [19]
    H. Chen, X. Zhu, D. Qiu, L. Liu and Z. Du, “Scheduling for workflows with security-sensitive intermediate data by selective tasks duplication in clouds,” IEEE Trans. Parallel Distrib. Syst., vol. 28, no. 9, pp. 2674–2688, Sept. 2017. doi: 10.1109/TPDS.2017.2678507
    [20]
    Z. J. Li, J. D. Ge, H. J. Yang, L. G. Huang, H. Y. Hu, H. Hu, and B. Luo, “A security and cost aware scheduling algorithm for heterogeneous tasks of scientific workflow in clouds,” Futur. Gener. Comp. Syst., vol. 65, pp. 140–152, Dec. 2016. doi: 10.1016/j.future.2015.12.014
    [21]
    M. A. Rodriguez and R. Buyya, “Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds,” IEEE Trans. Cloud Comput., vol. 2, no. 2, pp. 222–235, Apr.–Jun. 2014. doi: 10.1109/TCC.2014.2314655
    [22]
    L. Liu, M. Zhang, R. Buyya, and Q. Fan, “Deadline-constrained coevolutionary genetic algorithm for scientific workflow scheduling in cloud computing,” Concurr. Comput.-Pract. Exp., vol. 20, no. 5, pp. 1–12, Mar. 2017.
    [23]
    Z. G. Chen, K. J. Du, Z. H. Zhan, and J. Zhang, “Deadline constrained cloud computing resources scheduling for cost optimization based on dynamic objective genetic algorithm,” in Proc. IEEE Congr. Evol. Comput., Sendai, Japan, 2015, pp. 708–714.
    [24]
    Z. G. Chen, Z. H. Zhan, H. H. Li, K. J. Du, J. H. Zhong, Y. W. Foo, Y. Li, and J. Zhang, “Deadline constrained cloud computing resources scheduling through an ant colony system approach,” in Proc. IEEE Int. Conf. Cloud Comput. Res. Innov., Singapore, 2015, pp. 112–119.
    [25]
    Y. H. Jia, W. N. Chen, H. Q. Yuan, T. L. Gu, H. X. Zhang, Y. Gao, and J. Zhang, “An intelligent cloud workflow scheduling system with time estimation and adaptive ant colony optimization,” IEEE Trans. Syst. Man Cybern.-Syst., to be published, DOI: 10.1109/TSMC.2018.2881018
    [26]
    P. Kaur and S. Mehta, “Resource provisioning and workflow scheduling in clouds using augmented Shuffled Frog Leaping Algorithm,” J. Parallel Distrib. Comput., vol. 101, pp. 41–50, 2017. doi: 10.1016/j.jpdc.2016.11.003
    [27]
    Z. Tong, H. J. Chen, X. M. Deng, K. L. Li, and K. Q. Li, “A novel task scheduling scheme in a cloud computing environment using hybrid biogeography-based optimization,” Soft Comput., vol. 23, pp. 11035–11054, 2019. doi: 10.1007/s00500-018-3657-0
    [28]
    X. Zuo, G. Zhang and W. Tan, “Self-adaptive learning PSO-based deadline constrained task scheduling for hybrid IaaS cloud,” IEEE Trans. Autom. Sci. Eng., vol. 11, no. 2, pp. 564–573, Apr. 2014. doi: 10.1109/TASE.2013.2272758
    [29]
    Q. Wu, F. Ishikawa, Q. Zhu, Y. Xia, and J. Wen, “Deadline-constrained cost optimization approaches for workflow scheduling in clouds,” IEEE Trans. Parallel Distrib. Syst., vol. 28, no. 12, pp. 3401–3412, Dec. 2017. doi: 10.1109/TPDS.2017.2735400
    [30]
    H. Yuan, J. Bi, W. Tan, M. Zhou, B. H. Li and J. Li, “TTSA: An effective scheduling approach for delay bounded tasks in hybrid clouds,” IEEE Trans. Cybern., vol. 47, no. 11, pp. 3658–3668, Nov. 2017. doi: 10.1109/TCYB.2016.2574766
    [31]
    H. Topcuoglu, S. Hariri, and M. Y. Wu, “Performance-effective and low-complexity task scheduling for heterogeneous computing,” IEEE Trans. Parallel Distrib. Syst., vol. 13, no. 3, pp. 260–274, 2002. doi: 10.1109/71.993206
    [32]
    S. Abrishami, M. Naghibzadeh, and D. H. Epema, “Deadline-constrained workflow scheduling algorithms for Infrastructure as a Service Clouds,” Futur. Gener. Comp. Syst., vol. 29, no. 1, pp. 158–169, Jan. 2013. doi: 10.1016/j.future.2012.05.004
    [33]
    V. Arabnejad, K. Bubendorfer, and B. Ng, “Scheduling deadline constrained scientific workflows on dynamically provisioned cloud resources,” Futur. Gener. Comp. Syst., vol. 75, pp. 348–364, Oct. 2017. doi: 10.1016/j.future.2017.01.002
    [34]
    R. Calheiros and R. Buyya, “Meeting deadlines of scientific workflows in public clouds with tasks replication,” IEEE Trans. Parallel Distrib. Syst., vol. 25, no. 7, pp. 1787–1796, Jul. 2014. doi: 10.1109/TPDS.2013.238
    [35]
    X. Li and Z. Cai, “Elastic resource provisioning for cloud workflow applications,” IEEE Trans. Autom. Sci. Eng., vol. 14, no. 2, pp. 1195–1210, April. 2017. doi: 10.1109/TASE.2015.2500574
    [36]
    H. Chen, X. Zhu, G. Liu, and W. Pedrycz, “Uncertainty-aware online scheduling for real-time workflows in cloud service environment,” IEEE Trans. Serv. Comput. to be published, DOI: 10.1109/TSC.2018.2866421.
    [37]
    X. M. Zhou, G. X. Zhang, J. Sun, J. L. Zhou, T. Q. Wei, and S. Y. Hu, “Multi-objective workflow scheduling in Amazon EC2,” Cluster Comput., vol. 17, pp. 169–189, 2014. doi: 10.1007/s10586-013-0325-0
    [38]
    X. M. Zhou, G. X. Zhang, J. Sun, J. L. Zhou, T. Q. Wei, and S. Y. Hu, “Minimizing cost and makespan for workflow scheduling in cloud using fuzzy dominance sort based HEFT,” Futur. Gener. Comp. Syst., vol. 93, pp. 278–289, 2019. doi: 10.1016/j.future.2018.10.046
    [39]
    Y. K. Kwok and I. Ahmad, “Static scheduling algorithms for allocating directed task graphs to multiprocessors,” ACM Comput. Surv., vol. 31, no. 4, pp. 406–471, Dec. 1999. doi: 10.1145/344588.344618
    [40]
    S. Ostermann, A. Iosup, N. Yigitbasi, R. Prodan, T. Fahringer, and D. Epema, et al., “A performance analysis of EC2 cloud computing services for scientific computing,” in Proc. Lect. Notes Inst. Comput. Sci. Soc. Informatics Telecommun. Eng., Berlin, Heidelberg, Germany, 2009, pp. 115–131.
    [41]
    Y. Shi and R. C. Eberhart, “Empirical study of particle swarm optimization”, in Proc. IEEE Congr. Evol. Comput., Washington DC, USA, 1999, pp.1945–1950.
    [42]
    L. Tang and X. Wang, “An Improved Particle Swarm Optimization Algorithm for the Hybrid Flowshop Scheduling to Minimize Total Weighted Completion Time in Process Industry,” IEEE Trans. Control Syst. Technol., vol. 18, no. 6, pp. 1303–1314, Nov. 2010.
    [43]
    J. Bi, H. Yuan, Y. Fan, W. Tan, and J. Zhang, “Dynamic fine-grained resource provisioning for heterogeneous applications in virtualized cloud data center,” in Proc. IEEE Int. Conf. on Cloud Computing, New York, NY, USA, 2015, pp. 429–436.
    [44]
    H. Yuan, J. Bi, B. H. Li, and W. Tan, “Cost-aware request routing in multi-geography cloud data centres using software-defined networking,” Enterp. Inf. Syst., vol. 11, no. 3, pp. 359–388, Mar. 2017. doi: 10.1080/17517575.2015.1048833
    [45]
    K. Deb, A. Pratap, S. Agarwal, and T. A. M. T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, Apr. 2002. doi: 10.1109/4235.996017
    [46]
    G. Juve, A. Chervenak, E. Deelman, S. Bharathi, G. Mehta, and K. Vahi, “Characterizing and profiling scientific workflows,” Futur. Gener. Comp. Syst., vol. 29, no. 3, pp. 682–692, Mar. 2013. doi: 10.1016/j.future.2012.08.015
    [47]
    R. N. Calheiros, R. Ranjan, A. Beloglazov, C. A. De Rose, and R. Buyya, “CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms,” Softw.: Practice Experience, vol. 41, no. 1, pp. 23–50, 2011. doi: 10.1002/spe.995
    [48]
    H. T. Yuan, J. Bi, M. C. Zhou, Q. Liu, and A. C. Ammari, “Biobjective task scheduling for distributed green data centers,” IEEE Trans. Autom. Sci. Eng., to be published, DOI: 10.1109/TASE.2019.2958979.
    [49]
    J. Bi, H. T. Yuan, W. Tan, M. C. Zhou, Y. S. Fan, J. Zhang, and J. Q. Li, “Application-Aware Dynamic Fine-Grained Resource Provisioning in a Virtualized Cloud Data Center,” IEEE Trans. Autom. Sci. Eng., vol. 14, no. 2, pp. 1172–1184, Apr. 2017. doi: 10.1109/TASE.2015.2503325
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(10)  / Tables(4)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1439) PDF downloads(70) Cited by()

    Highlights

    • The proposed cloud workflow scheduling algorithm combines PSO and idle time-aware rules, having the advantage of both meta-heuristics (PSO) and heuristic rules.
    • A new solution encoding is devised to represent simultaneously the VM type required by each task and the scheduling sequence of each task.
    • Idle time slot-aware heuristic scheduling rules are proposed to decode a particle (a solution encoding) to a scheduling solution.
    • A simple repairing method is suggested to repair invalid priorities of tasks because of the randomness of PSO.

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return