计算机科学 ›› 2022, Vol. 49 ›› Issue (2): 312-320.doi: 10.11896/jsjkx.201000102
林潮伟1,2, 林兵2,3, 陈星1,2
LIN Chao-wei1,2, LIN Bing2,3, CHEN Xing1,2
摘要： 作为一种新型计算范式,边缘计算已成为解决大规模科学应用程序的重要途径。针对边缘环境下的科学工作流调度问题,考虑到任务计算过程中的服务器执行性能波动和数据传输过程中的带宽波动造成的不确定性,文中基于模糊理论,使用三角模糊数表示任务计算时间和数据传输时间,同时提出一种基于遗传算法算子的自适应离散模糊粒子群优化算法(Adaptive Discrete Fuzzy GA-based Particle Swarm Optimization,ADFGA-PSO),目的是在满足工作流截止日期约束的前提下,降低其模糊执行代价。该方法引入遗传算法的两点交叉算子以及关于任务优先级的邻域变异算子和关于服务器编号的自适应多点变异算子,避免粒子陷入局部最优,有效提高算法的搜索性能。实验结果表明,与其他调度策略相比,基于ADFGA-PSO的调度策略能够更加有效地降低边缘环境下带截止日期约束的科学工作流的模糊执行代价。
中图分类号:
| [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] | 孙慧婷, 范艳芳, 马孟晓, 陈若愚, 蔡英. VEC中基于动态定价的车辆协同计算卸载方案 Dynamic Pricing-based Vehicle Collaborative Computation Offloading Scheme in VEC 计算机科学, 2022, 49(9): 242-248. https://doi.org/10.11896/jsjkx.210700166 |
| [2] | 于滨, 李学华, 潘春雨, 李娜. 基于深度强化学习的边云协同资源分配算法 Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning 计算机科学, 2022, 49(7): 248-253. https://doi.org/10.11896/jsjkx.210400219 |
| [3] | 李梦菲, 毛莺池, 屠子健, 王瑄, 徐淑芳. 基于深度确定性策略梯度的服务器可靠性任务卸载策略 Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient 计算机科学, 2022, 49(7): 271-279. https://doi.org/10.11896/jsjkx.210600040 |
| [4] | 方韬, 杨旸, 陈佳馨. D2D辅助移动边缘计算下的卸载策略优化 Optimization of Offloading Decisions in D2D-assisted MEC Networks 计算机科学, 2022, 49(6A): 601-605. https://doi.org/10.11896/jsjkx.210200114 |
| [5] | 刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems 计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165 |
| [6] | 袁昊男, 王瑞锦, 郑博文, 吴邦彦. 基于Fabric的电子病历跨链可信共享系统设计与实现 Design and Implementation of Cross-chain Trusted EMR Sharing System Based on Fabric 计算机科学, 2022, 49(6A): 490-495. https://doi.org/10.11896/jsjkx.210500063 |
| [7] | 谢万城, 李斌, 代玥玥. 空中智能反射面辅助边缘计算中基于PPO的任务卸载方案 PPO Based Task Offloading Scheme in Aerial Reconfigurable Intelligent Surface-assisted Edge Computing 计算机科学, 2022, 49(6): 3-11. https://doi.org/10.11896/jsjkx.220100249 |
| [8] | 周天清, 岳亚莉. 超密集物联网络中多任务多步计算卸载算法研究 Multi-Task and Multi-Step Computation Offloading in Ultra-dense IoT Networks 计算机科学, 2022, 49(6): 12-18. https://doi.org/10.11896/jsjkx.211200147 |
| [9] | 彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中QoE和能量效率的公平联合优化 Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos 计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027 |
| [10] | 张海波, 张益峰, 刘开健. 基于NOMA-MEC的车联网任务卸载、迁移与缓存策略 Task Offloading,Migration and Caching Strategy in Internet of Vehicles Based on NOMA-MEC 计算机科学, 2022, 49(2): 304-311. https://doi.org/10.11896/jsjkx.210100157 |
| [11] | 梁俊斌, 张海涵, 蒋婵, 王天舒. 移动边缘计算中基于深度强化学习的任务卸载研究进展 Research Progress of Task Offloading Based on Deep Reinforcement Learning in Mobile Edge Computing 计算机科学, 2021, 48(7): 316-323. https://doi.org/10.11896/jsjkx.200800095 |
| [12] | 薛艳芬, 高继梅, 范贵生, 虞慧群, 许亚杰. 边缘计算中基于能耗感知的容错协同任务执行算法 Energy-aware Fault-tolerant Collaborative Task Execution Algorithm in Edge Computing 计算机科学, 2021, 48(6A): 374-382. https://doi.org/10.11896/jsjkx.200900027 |
| [13] | 宋海宁, 焦健, 刘永. 高速公路中的移动边缘计算研究 Research on Mobile Edge Computing in Expressway 计算机科学, 2021, 48(6A): 383-386. https://doi.org/10.11896/jsjkx.200900212 |
| [14] | 钱基德, 熊仁和, 王乾垒, 杜冬, 王在俊, 钱基业. 边缘计算在飞行训练中的应用 Application of Edge Computing in Flight Training 计算机科学, 2021, 48(6A): 603-607. https://doi.org/10.11896/jsjkx.201000035 |
| [15] | 钱甜甜, 张帆. 基于分布式边缘计算的情绪识别系统 Emotion Recognition System Based on Distributed Edge Computing 计算机科学, 2021, 48(6A): 638-643. https://doi.org/10.11896/jsjkx.201000010 |
|
||
首页