Computer Science ›› 2021, Vol. 48 ›› Issue (6A): 420-426.doi: 10.11896/jsjkx.201000023

• Network & Communication • Previous Articles     Next Articles

Cloud Task Scheduling Algorithm Based on Three-way Decisions

WANG Zheng, JIANG Chun-mao   

  1. School of Computer Science and Information Engineering,Harbin Normal University,Harbin 150025,China
  • Online:2021-06-10 Published:2021-06-17
  • About author:WANG Zheng,born in 1996,postgra-duate.His main research interests include cloud computing and granularity computing.
    JIANG Chun-mao,born in 1972,Ph.D,professor,is a member of China Computer Federation.His main research interests include cloud computing and big data,intelligent data decision making.
  • Supported by:
    Natural Science Foundation of Heilongjiang Province,China(JJ2020LH0473).

Abstract: As an essential component of the cloud computing system,task scheduling directly impacts resource utilization and service quality.To solve the problems existing in Min-Min and Max-Min algorithms in the current cloud platform,such as load imbalance,low comprehensive resource utilization,and sizeable overall task completion time due to task distribution,a task sche-duling optimization algorithm based on the three-way decision (CTSA-3WD) is proposed.First,the algorithm divides tasks into light-load and heavy-load tasks according to their execution time and computational resource requirements.Secondly,the algorithm divides the tasks into three categories according to the proportion of the task set's two types of tasks.It develops scheduling strategies for these three task sets.Specifically,the strategy uses the Max-Min algorithm for tasks with a high percentage of light load tasks and uses the Min-Min algorithm for a high proportion of heavily loaded tasks.An improved task scheduling algorithm based on Min-Min and Max-Min is used for the set,which has close numbers between light and heavy-duty tasks.Third,the critical resources in the allocated nodes are rescheduled.The algorithm selects the best matching tasks to be allocated to the light-load resources,subject to the overall completion time reduction.The experimental based on the CloudSim reveals that the CTSA-3WD algorithm can effectively improve the overall resource utilization and quality of service to users compared to Min-Min,Max-Min,selective scheduling algorithms.Moreover,it also makes the resources in the whole system reach a better load-balancing level.

Key words: Cloud computing, Load balancing, Multi-granularity, Task scheduling, Three-way decisions

CLC Number: 

  • TP301
[1] PANDA S K,JANA P K.An efficient task scheduling algorithm for heterogeneous multi-cloud environment[J].The Journal of Supercomputing,2015,71(4):1505-1533.
[2] GAVVALA S K,JATOTH C,GANGADHARAN G R,et al.QoS-aware cloud service composition using eagle strategy[J].Future Generation Computer Systems.2019,90:273-290.
[3] KAUR P,MEHTA S.Resource provisioning and work flowscheduling in clouds using augmented Shuffled Frog Leaping Algorithm[J].Journal of Parallel and Distributed Computing,2017,101:41-50.
[4] CHEN X,CHENG L,LIU C,et al.A WOA-Based Optimization Approach for Task Scheduling in Cloud Computing Systems[J].IEEE Systems Journal,2020,14(3):3117-3128.
[5] GE D,DING Z,JI H.A task scheduling strategy based onweighted round robin for distributed crawler[J].Concurrency &Computation Practice & Experience,2016,28(11):3202-3212.
[6] VERMA A,PEDROSA L,KORUPOLU M,et al.Large-scalecluster management at Google with Borg[C]//Proceedings of the Tenth European Conference on Computer Systems.2015:1-17.
[7] YAO Y.Three-way decision and granular computing[J].International Journal of Approximate Reasoning,2018,103:107-123.
[8] YAO Y.Set-theoretic models of three-way decision[J].Granular Computing,2021,6(1):133-148.
[9] JIANG C,GUO D,DUAN Y,et al.Strategy selection under entropy measures in movement-based three-way decision[J].International Journal of Approximate Reasoning,2020,119:280-291.
[10] YAO Y.Tri-level thinking:models of three-way decision[J].International Journal of Machine Learning & Cybernetics,2019:1-13.
[11] GUO D D,JIANG C M.Multi-stage Regional Transformation Strategy in Move-based Three-way Decisions Model [J]Compute Science,2019,46(10):279-285.
[12] BRAUN T D,SIEGEL H J,BECK N,et al.A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems[J].Journal of Parallel & Distributed Computing,2001,61(6):810-837.
[13] ETMINANI K,NAGHIBZADEH M.A Min-Min Max-Min selective algorithm for grid task scheduling[C]//2007 3rd IEEE/IFIP International Conference in Central Asia on Internet.IEEE,2007:1-7.
[14] REHMAN A,JAVED K,BABRI H A,et al.Selection of the most relevant terms based on a max-min ratio metric for text classification[J].Expert Systems with Applications,2018,114:78-96.
[15] ZHANG Y,XU B.Task Scheduling Algorithm based-on QoSConstrains in Cloud Computing[J].International Journal of Grid and Distributed Computing,2015,8(6):269-280..
[16] LI Z,SHEN H,MILES C.PageRankVM:A PageRank BasedAlgorithm with Anti-Collocation Constraints for Virtual Machine Placement in Cloud Datacenters[C]//2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS).IEEE,2018.
[17] BEY K B,BENHAMMADI F,BENAISSA R.Balancing heuristic for independent task scheduling in cloud compu[C]//International Symposium on Programming & Systems.IEEE,2015.
[18] WU J W,JIANG C M.Load-aware score scheduling of three-way clustering for cloud task[J].CAAI transactions on intelligentsystems,2019,14(2):316-322.
[19] JIANG C M,WANG K X.Real-time Cloud Tasks Schedule Algorithm for Saving Energy Based on Tri-queue System,2019,51(2):66-71.
[20] INGBO J,JU W,DALI W,et al.The research on meta-jobscheduling heuristics in heterogeneous environments[J].Journal of Intelligent & Fuzzy Systems,2018,34(2):1141-1151.
[1] QIN Qi-qi, ZHANG Yue-qin, WANG Run-ze, ZHANG Ze-hua. Hierarchical Granulation Recommendation Method Based on Knowledge Graph [J]. Computer Science, 2022, 49(8): 64-69.
[2] ZHANG Yuan, KANG Le, GONG Zhao-hui, ZHANG Zhi-hong. Related Transaction Behavior Detection in Futures Market Based on Bi-LSTM [J]. Computer Science, 2022, 49(7): 31-39.
[3] TIAN Zhen-zhen, JIANG Wei, ZHENG Bing-xu, MENG Li-min. Load Balancing Optimization Scheduling Algorithm Based on Server Cluster [J]. Computer Science, 2022, 49(6A): 639-644.
[4] GAO Jie, LIU Sha, HUANG Ze-qiang, ZHENG Tian-yu, LIU Xin, QI Feng-bin. Deep Neural Network Operator Acceleration Library Optimization Based on Domestic Many-core Processor [J]. Computer Science, 2022, 49(5): 355-362.
[5] YANG Fei-fei, SHEN Si-yu, SHEN De-rong, NIE Tie-zheng, KOU Yue. Method on Multi-granularity Data Provenance for Data Fusion [J]. Computer Science, 2022, 49(5): 120-128.
[6] GAO Shi-yao, CHEN Yan-li, XU Yu-lan. Expressive Attribute-based Searchable Encryption Scheme in Cloud Computing [J]. Computer Science, 2022, 49(3): 313-321.
[7] TAN Shuang-jie, LIN Bao-jun, LIU Ying-chun, ZHAO Shuai. Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning [J]. Computer Science, 2022, 49(2): 336-341.
[8] SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[9] XIA Zhong, XIANG Min, HUANG Chun-mei. Hierarchical Management Mechanism of P2P Video Surveillance Network Based on CHBL [J]. Computer Science, 2021, 48(9): 278-285.
[10] ZHANG Shi-peng, LI Yong-zhong. Intrusion Detection Method Based on Denoising Autoencoder and Three-way Decisions [J]. Computer Science, 2021, 48(9): 345-351.
[11] WANG Dong, ZHOU Da-ke, HUANG You-da , YANG Xin. Multi-scale Multi-granularity Feature for Pedestrian Re-identification [J]. Computer Science, 2021, 48(7): 238-244.
[12] SONG Hai-ning, JIAO Jian, LIU Yong. Research on Mobile Edge Computing in Expressway [J]. Computer Science, 2021, 48(6A): 383-386.
[13] LYU Le-bin, LIU Qun, PENG Lu, DENG Wei-bin , WANG Chong-yu. Text Matching Fusion Model Combining Multi-granularity Information [J]. Computer Science, 2021, 48(6): 196-201.
[14] ZHENG Zeng-qian, WANG Kun, ZHAO Tao, JIANG Wei, MENG Li-min. Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster [J]. Computer Science, 2021, 48(6): 261-267.
[15] DING Ling, XIANG Yang. Chinese Event Detection with Hierarchical and Multi-granularity Semantic Fusion [J]. Computer Science, 2021, 48(5): 202-208.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!