Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (2): 312-320.doi: 10.11896/jsjkx.201000102

• Computer Network • Previous Articles     Next Articles

Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment

LIN Chao-wei1,2, LIN Bing2,3, CHEN Xing1,2   

  1. 1 College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China
    2 Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing,Fuzhou 350108,China
    3 College of Physics and Energy,Fujian Normal University,Fuzhou 350117,China
  • Received:2020-10-20 Revised:2021-03-05 Online:2022-02-15 Published:2022-02-23
  • About author:LIN Chao-wei,born in 1998,postgra-duate.His main research interests include workflow scheduling,computational intelligence and its applications,and fuzzy theory.
    LIN Bing,born in 1986,Ph.D,lecturer,postgraduate supervisor,is a member of China Computer Federation.His main research interests include parallel and distributed computing,computational intelligence and its applications,and fuzzy theory.
  • Supported by:
    National Key R & D Program of China(2018YFB1004800) and Natural Science Foundation of Fujian Province for Distinguished Young Scholars(2020J06014).

PDF (PC)

597

Abstract: As a novel computing paradigm,edge computing has become a significant approach to solve large-scale scientific applications.Aiming at scientific workflow scheduling under edge environment,task computation time and data transmission time are uncertain due to the fluctuation of server processing performance and bandwidth,respectively.In order to help capture and reflect the uncertainty during workflow execution,task computation time and data transmission time are represented as triangular fuzzy numbers (TFN),based on fuzzy theory.Simultaneously,an adaptive discrete fuzzy GA-based particle swarm optimization (ADFGA-PSO) is proposed to minimize fuzzy execution cost of workflow while satisfying deadline constraint.Besides,two-point crossover operator,neighborhood mutation and adaptive multipoint mutation operator of genetic algorithm (GA) are introduced to avoid particles being trapped in local optimum.Experimental results show that,compared with others,scheduling strategy based on ADFGA-PSO can more effectively reduce fuzzy execution cost in regard to deadline-constrained scientific workflow scheduling under edge environment.

Key words: Edge computing, Genetic operators, Triangular fuzzy numbers, Uncertainty, Workflow scheduling

CLC Number: 

  • TP338
[1]NASCIMENTO A,OLIMPIO V,SILVA V,et al.A Reinforcement Learning Scheduling Strategy for Parallel Cloud-Based Workflows[C]//2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW).2019:817-824.
[2]HAN P,DU C,CHEN J,et al.Cost and Makespan Scheduling ofWorkflows in Clouds Using List Multiobjective Optimization Technique[J/OL].Journal of Systems Architecture.https://www.sciencedirect.com/science/article/abs/pii/S1383762120301296.
[3]LI Y,LUO J,JIN J,et al.An Effective Model for Edge-Side Collaborative Storage in Data-Intensive Edge Computing[C]//2018 IEEE 22nd International Conference on Computer Supported Cooperative Work in Design (CSCWD).2018:92-97.
[4]KO H,LEE J,PACK S.Spatial and Temporal Computation Offloading Decision Algorithm in Edge Cloud-Enabled Heteroge-neous Networks[J].IEEE Access,2018,6:18920-18932.
[5]ZHANG L X,ZHOU L Q,WEN H,et al.Energy EfficientScheduling Algorithm of Workflows with Cost Constraint in Heterogeneous Cloud Computing Systems[J].Computer Science,2020,47(8):112-118.
[6]MA Y Y,ZHENG W B,MA Y,et al.Multi-workflow Offloading Method Based on Deep Reinforcement Learning and Probabilistic Performance-aware in Edge Computing Environment[J].Computer Science,2021,48(1):40-48.
[7]LI J,ZHANG Y P,PANG L,et al.Joint Resource Allocationand Task Scheduling in Mobile Edge Computing[J].Journal of Chongqing University of Technology(Natural Science),2020,34(11):156-163.
[8]SUN L,LIN L,GEN M,et al.A Hybrid Cooperative Coevolution Algorithm for Fuzzy Flexible Job Shop Scheduling[J].IEEE Transactions on Fuzzy Systems,2019,27(5):1008-1022.
[9]GAO D,WANG G,PEDRYCZ W.Solving Fuzzy Job-shopScheduling Problem Using DE Algorithm Improved by a Selection Mechanism[J].IEEE Transactions on Fuzzy Systems,2020,28(12):3265-3275.
[10]SAHNI J,VIDYARTHI D P.A Cost-Effective Deadline-Con-strained Dynamic Scheduling Algorithm for Scientific Workflows in a Cloud Environment[J].IEEE Transactions on Cloud Computing,2018,6(1):2-18.
[11]SHI W,ZHANG X.Edge Computing:State-of-the-Art and Future Directions[J].Journal of Computer Research & Development,2019,56(1):69-89.
[12]XIE Y,ZHU Y,WANG Y,et al.A novel directional and non-local-convergent particle swarm optimization based workflow scheduling in cloud-edge environment[J].Future Generation Computer Systems,2019,97(AUG.):361-378.
[13]HUANG B,LI Z,TANG P,et al.Security modeling and efficientcomputation offloading for service workflow in mobile edge computing[J].Future Generation Computer Systems,2019,97(AUG.):755-774.
[14]PENG Q,JIANG H,CHEN M,et al.Reliability-aware andDeadline-constrained workflow scheduling in Mobile Edge Computing[C]//2019 IEEE 16th International Conference on Networking,Sensing and Control (ICNSC).2019:236-241.
[15]LIN K,LIN B,CHEN X,et al.A Time-Driven Workflow Sche-duling Strategy for Reasoning Tasks of Autonomous Driving in Edge Environment[C]//2019 IEEE Intl Conf on Parallel & Distributed Processing with Applications,Big Data & Cloud Computing,Sustainable Computing & Communications,Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom).2019:124-131.
[16]LEI D.Fuzzy job shop scheduling problem with availability constraints[J].Computers Industrial Engineering,2010,58(4):610-617.
[17]FORTEMPS P.Jobshop scheduling with imprecise durations:a fuzzy approach[J].IEEE Transactions on Fuzzy Systems,1997,5(4):557-569.
[18]MATTES A,TAVERA F,OPHEY A,et al.Parallel and serial task processing in the PRP paradigm:a drift-diffusion model approach[J].Psychological Research,2021(85):1529-1552.
[19]ZADEH L A.Fuzzy Sets[J].Information Control,1965,8(3):338-353.
[20]PALACIOS J J,GONZÑLEZ-RODRÍGUEZ I,VELA C R,et al.Coevolutionary makespan optimisation through different ranking methods for the fuzzy flexible job shop[J].Fuzzy Sets and Systems,2015,278:81-97.
[21]LEE E S,LI R J.Comparison of fuzzy numbers based on theprobability measure of fuzzy events[J].Computers & Mathe-matics with Applications,1988,15(10):887-896.
[22]PALACIOS J J,GONZÑLEZ M A,VELA C R,et al.Genetictabu search for the fuzzy flexible job shop problem[J].Compu-ters & Operations Research,2015,54:74-89.
[23]SAKAWA M,KUBOTA R.Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms[J].European Journal of Operational Research,2000,120(2):393-407.
[24]KENNEDY J,EBERHART R.Particle swarm optimization[C]//ICNN95-International Conference on Neural Networks.1995.
[25]RODRIGUEZ M A,BUYYA R.Deadline Based Resource Pro-visioning and Scheduling Algorithm for Scientific Workflows on Clouds[J].IEEE Transactions on Cloud Computing,2014,2(2):222-235.
[26]LI H,YANG D,SU W,et al.An Overall Distribution Particle Swarm Optimization MPPT Algorithm for Photovoltaic System Under Partial Shading[J].IEEE Transactions on Industrial Electronics,2019,66(1):265-275.
[27]LI X,GAO L.An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J].International Journal of Production Economics,2016,174(Apr.):93-110.
[28]SHI Y.A Modified Particle Swarm Optimizer[C]//Proceedings of IEEE ICEC Conference.1998.
[29]BHARATHI S,CHERVENAK A,DEELMAN E,et al.Characterization of scientific workflows[C]//Workflows in Support of Large-Scale Science.2008.
[30]TOPCUOGLU H,HARIRI S,WU M Y.Performance effectiveand low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.
[31]CUI L,ZHANG J,YUE L,et al.A Genetic Algorithm BasedData Replica Placement Strategy for Scientific Applications in Clouds[J].IEEE Transactions on Services Computing,2018,11(4):727-739.
[32]ZHOU B,XIE S S,WANG F,et al.Multi-step predictive compensated intelligent control for aero-engine wireless networked system with random scheduling[J].Journal of the Franklin Institute-Engineering and Applied Mathematics,2020,357(10):6154-6174.
[1] SUN Hui-ting, FAN Yan-fang, MA Meng-xiao, CHEN Ruo-yu, CAI Ying. Dynamic Pricing-based Vehicle Collaborative Computation Offloading Scheme in VEC [J]. Computer Science, 2022, 49(9): 242-248.
[2] YU Bin, LI Xue-hua, PAN Chun-yu, LI Na. Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning [J]. Computer Science, 2022, 49(7): 248-253.
[3] LI Meng-fei, MAO Ying-chi, TU Zi-jian, WANG Xuan, XU Shu-fang. Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient [J]. Computer Science, 2022, 49(7): 271-279.
[4] YUAN Hao-nan, WANG Rui-jin, ZHENG Bo-wen, WU Bang-yan. Design and Implementation of Cross-chain Trusted EMR Sharing System Based on Fabric [J]. Computer Science, 2022, 49(6A): 490-495.
[5] FANG Tao, YANG Yang, CHEN Jia-xin. Optimization of Offloading Decisions in D2D-assisted MEC Networks [J]. Computer Science, 2022, 49(6A): 601-605.
[6] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[7] XIE Wan-cheng, LI Bin, DAI Yue-yue. PPO Based Task Offloading Scheme in Aerial Reconfigurable Intelligent Surface-assisted Edge Computing [J]. Computer Science, 2022, 49(6): 3-11.
[8] ZHANG Hai-bo, ZHANG Yi-feng, LIU Kai-jian. Task Offloading,Migration and Caching Strategy in Internet of Vehicles Based on NOMA-MEC [J]. Computer Science, 2022, 49(2): 304-311.
[9] LIANG Jun-bin, ZHANG Hai-han, JIANG Chan, WANG Tian-shu. Research Progress of Task Offloading Based on Deep Reinforcement Learning in Mobile Edge Computing [J]. Computer Science, 2021, 48(7): 316-323.
[10] QIAN Ji-de, XIONG Ren-he, WANG Qian-lei, DU Dong, WANG Zai-jun, QIAN Ji-ye. Application of Edge Computing in Flight Training [J]. Computer Science, 2021, 48(6A): 603-607.
[11] XUE Yan-fen, GAO Ji-mei, FAN Gui-sheng, YU Hui-qun, XU Ya-jie. Energy-aware Fault-tolerant Collaborative Task Execution Algorithm in Edge Computing [J]. Computer Science, 2021, 48(6A): 374-382.
[12] SONG Hai-ning, JIAO Jian, LIU Yong. Research on Mobile Edge Computing in Expressway [J]. Computer Science, 2021, 48(6A): 383-386.
[13] QIAN Tian-tian, ZHANG Fan. Emotion Recognition System Based on Distributed Edge Computing [J]. Computer Science, 2021, 48(6A): 638-643.
[14] FAN Yan-fang, YUAN Shuang, CAI Ying, CHEN Ruo-yu. Deep Reinforcement Learning-based Collaborative Computation Offloading Scheme in VehicularEdge Computing [J]. Computer Science, 2021, 48(5): 270-276.
[15] ZHANG Kai-qiang, JIANG Cong-feng, CHENG Xiao-lan, JIA Gang-yong, ZHANG Ji-lin, WAN Jian. Resource-aware Based Adaptive-scaling Image Target Detection Under Multi-resolution Scenario [J]. Computer Science, 2021, 48(4): 180-186.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.