混合云下具有交付期约束的众包任务调度算法

doi:10.11896/jsjkx.210300120

计算机科学 ›› 2022, Vol. 49 ›› Issue (5): 244-249.doi: 10.11896/jsjkx.210300120

混合云下具有交付期约束的众包任务调度算法

严磊, 张功萱, 王添, 寇小勇, 王国洪

南京理工大学计算机科学与工程学院南京210094

收稿日期:2021-03-11 修回日期:2021-07-20 出版日期:2022-05-15 发布日期:2022-05-06
通讯作者: 张功萱(gongxuan@njust.edu.cn)
作者简介:(237459461@qq.com)
基金资助:
国家自然科学基金(61773206)

Scheduling Algorithm for Bag-of-Tasks with Due Date Constraints on Hybrid Clouds

YAN Lei, ZHANG Gong-xuan, WANG Tian, KOU Xiao-yong, WANG Guo-hong

School of Computer Science and Technology,Nanjing University of Science and Technology,Nanjing 210094,China

Received:2021-03-11 Revised:2021-07-20 Online:2022-05-15 Published:2022-05-06
About author:YAN Lei,born in 1996,postgraduate.His main research interests include cloud computing,Web service and distributed computing system.
ZHANG Gong-xuan,born in 1961,Ph.D,professor,is a member of China Computer Federation.His main research interests include cloud computing,Web services and distributed system.
Supported by:
National Natural Science Foundation of China(61773206).

摘要/Abstract

摘要： 由多个任务组成的众包任务(Bag-of-Tasks,BoT)被广泛应用于各种领域,一般在混合云下执行。与调度问题中传统的截止时间约束不同,交付期约束允许BoT应用程序的完成时间超过预先指定的交付期,但会产生延迟惩罚。在这种情况下,为了降低总成本,文中提出了一种高效的和声搜索算法(Efficient Harmony Search,EHS),用于在混合云下优化调度任务。该算法通过随机搜索和微调得到初始任务序列,然后通过改进和声搜索步骤和产生新和声记忆库的方式,在一次搜索过程中可以获得大量优质和声,大大提高了和声搜索的效率,加快了算法的收敛速度。通过不断迭代,获得全局最优解,即使总成本最低的BoT应用调度方案。实验结果表明,相比其他算法,该算法在性能上有显著提升,可以有效地降低调度众包任务的总成本。

关键词: 高效的和声搜索算法, 混合云, 交付期, 众包任务, 总成本最小化

Abstract: Bag-of-Tasks (BoT) applications consisting of multiple tasks are widely used in various fields.Different from the traditional deadline constraint in scheduling problems,a due date constraint allows the BoT applications to finish more than a predetermined due date,but would result in the tardiness penalty.In this case,in order to reduce the total cost,the efficient harmony search (EHS) algorithm is proposed to optimize the scheduling tasks in hybrid clouds.The algorithm obtains the initial task sequence by random search and fine tuning.By improving the harmony search steps and the way of generating new harmony memory,a large number of high-quality harmony can be obtained in one search process,which greatly improves the efficiency of harmony search and speeds up the convergence speed of the algorithm.Through continuous iteration,the global optimal solution is obtained,that is to say,BoT application scheduling scheme has the lowest total cost.Experimental results show that compared with other algorithms,the proposed algorithm has significant improvement in performance,which can effectively reduce the total cost of scheduling BoT applications.

Key words: Bag-of-Tasks, Due date, Efficient harmony search algorithm, Hybrid clouds, Total cost minimization

中图分类号:

TP301

严磊, 张功萱, 王添, 寇小勇, 王国洪. 混合云下具有交付期约束的众包任务调度算法[J]. 计算机科学, 2022, 49(5): 244-249. https://doi.org/10.11896/jsjkx.210300120

YAN Lei, ZHANG Gong-xuan, WANG Tian, KOU Xiao-yong, WANG Guo-hong. Scheduling Algorithm for Bag-of-Tasks with Due Date Constraints on Hybrid Clouds[J]. Computer Science, 2022, 49(5): 244-249. https://doi.org/10.11896/jsjkx.210300120

参考文献

[1]HU M,VEERAVALLI B.Requirement-Aware Scheduling ofBag-of-Tasks Applicationson Grids with Dynamic Resilience[J].IEEE Transactions on Computers,2012,62(10):2108-2114.
[2]TERZOPOULOS G,KARATZA H D.Bag-of-Task Scheduling on Power-Aware Clusters Using a DVFS-Based Mechanism[C]//2014 IEEE International Parallel & Distributed Proces-sing Symposium Workshops.IEEE,2014:833-840.
[3]THAI L,VARGHESE B,BARKER A.A Survey and Taxonomy of Resource Optimisation for Executing Bag-of-Task Applications on Public Clouds[J].Future Generation Computer Systems,2018,82:1-11.
[4]XIE G,GANG Z,YAN L,et al.Fast Functional Safety Verification for Distributed Automotive Applications during Early Design Phase[J].IEEE Transactions on Industrial Electronics,2017,65(5):4378-4391.
[5]LI J,XIE G,LI K,et al.Enhanced Parallel Application Schedu-ling Algorithm with Energy Consumption Constraint in Heterogeneous Distributed Systems[J/OL].Journal of Circuits,Systems and Computers,2019,28(11).https://www.worldscientific.com/doi/abs/10.1142/S0218126619501901.
[6]XIE G,HUANG J,LI Y,et al.System-Level Energy-Aware Design Methodology Towards End-To-End Response Time Optimization[J/OL].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2019.https://ieeexplore.ieee.org/abstract/document/8732346.
[7]ZHOU J L,HU X S,MA Y,et al.Improving Availability ofMulticore Real-Time Systems Suffering Both Permanent and Transient Faults[J].IEEE Transactions on Computers,2019,68(12):1785-1801.
[8]LEI M,KRITIKAKOU A,SENTIEYS O.Energy-Quality-Time Optimized Task Mapping on DVFS-enabled Multicores[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2018,37(11):2428-2439.
[9]MO L,KRITIKAKOU A,SENTIEYS O.Controllable QoS for Imprecise Computation Tasks on DVFS Multicores with Time and Energy Constraints[J].IEEE Journal on Emerging and Selected Topics in Circuits and Systems,2018,8(4):708-721.
[10]WANG J,QIU M,GUO B.Enabling real-time information ser-vice on telehealth system over cloud-based big data platform[J].Journal of Systems Architecture,2017,72:69-79.
[11]GARCÍA-VALLS M,DUBEY A,BOTTI V.Introducing thenew paradigm of Social Dispersed Computing:Applications,Technologies and Challenges[J].Journal of Systems Architecture,2018,91:83-102.
[12]WU T,GU H,ZHOU J,et al.Soft Error-Aware Energy-Effi-cient Task Scheduling for Workflow Applications in DVFS-Enabled Cloud[J].Journal of Systems Architecture,2018,84:12-27.
[13]ZHOU X,ZHANG G,SUN J,et al.Minimizing cost and make-span for workflow scheduling in cloud using fuzzy dominance sort based HEFT[J].Future Generation Computer Systems,2019,93:278-289.
[14]ZHOU J,JIN S,ZHOU X,et al.Resource Management for Improving Soft-Error and Lifetime Reliability of Real-Time MPSoCs[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2018,38(12):2215-2228.
[15]TERZOPOULOS G,KARATZA H D.Bag-of-Task Schedulingon Power-Aware Clusters Using a DVFS-Based Mechanism[C]//2014 IEEE International Parallel &Distributed Processing Symposium Workshops.IEEE,2014:833-840.
[16]ZHANG Y,SUN J,ZHU J.An Effective Heuristic for Due-Date-Constrained Bag-of-Tasks Scheduling Problem for Total Cost Minimization on Hybrid Clouds[C]//2016 IEEE International Conference on Progress in Informatics and Computing.2016:479-486.
[17]BOSSCHE R,VANMECHELEN K,BROECKHOVE J.Cost-Efficient Scheduling Heuristics for Deadline Constrained Workloads on Hybrid Clouds[C]//IEEE Third International Confe-rence on Cloud Computing Technology & Science.IEEE,2011:320-327.
[18]WANG B,SONG Y,SUN Y,et al.Managing Deadline-Con-strained Bag-of-Tasks Jobs on Hybrid Clouds with Closest Deadline First Scheduling[J].KSII Transactions on Internet & Information Systems,2016,10(7):2952-2971.
[19]PELAEZ V,CAMPOS A,GARCIA D F,et al.AutonomicScheduling of Deadline-constrained Bag of Tasks in Hybrid Clouds[C]//International Symposium on Performance Evaluation of Computer & Telecommunication Systems.IEEE,2016:1-8.
[20]ARDAGNA D,CASOLARI S,PANICUCCI B.Flexible Distri-buted Capacity Allocation and Load Redirect Algorithms for Cloud Systems[C]//IEEE International Conference on Cloud Computing.Washington DC,USA:IEEE,2011:163-170.
[21]ZHANG Y,SUN J.Novel Efficient Particle Wwarm Optimization Algorithms for Solving QoS-demanded Bag-of-tasks Sche-duling Problems with Profit Maximization on Hybrid Clouds[J].Concurrency and Computation:Practice and Experience,2017,29(21):e4249.1-e4249.19.
[22]ZHANG Y,ZHOU J,SUN J.Scheduling Bag-of-Tasks Applications on Hybrid Clouds Under Due Date Constraints[J/OL].Journal of Systems Architecture.https://www.sciencedirect.com/science/article/pii/S1383762119304618.
[23]STAVRINIDES G L,KARATZA H D.Performance Evaluation of a SaaS Cloud Under Different Levels of Workload Computational Demand Variability and Tardiness Bounds[J].Simulation Modelling Practice and Theory,2019,91:1-12.
[24]ZHANG X S,YU D H,NIE X C,et al.Spatiotemporalcrowdsourcing online task allocation based on predictive ana-lysis[J].Computer Engineering,2019,45(6):67-74.
[25]WANG C X,YU D H,ZHANG W S,et al.Module Allocation Algorithm for Software Crowdsourcing Based on Core Degree Sorting[J].Computer Engineering,2019,45(7):66-70.
[26]XING H,CHEN R,TANG W J.Online Task Allocation Strategy for Spatial Crowdsourcing Based on Prediction Algorithm[J].Computer Engineering,2020,46(9):27-34,43.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

混合云下具有交付期约束的众包任务调度算法

Scheduling Algorithm for Bag-of-Tasks with Due Date Constraints on Hybrid Clouds

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

Metrics

本文评价

推荐阅读 0

[1]	柳鹏, 刘波, 周娜琴, 彭心怡, 林伟伟. 混合云工作流调度综述 Survey of Hybrid Cloud Workflow Scheduling 计算机科学, 2022, 49(5): 235-243. https://doi.org/10.11896/jsjkx.210300303
[2]	季琰, 戴华, 姜莹莹, 杨庚, 易训. 面向混合云的可并行多关键词Top-k密文检索技术 Parallel Multi-keyword Top-k Search Scheme over Encrypted Data in Hybrid Clouds 计算机科学, 2021, 48(5): 320-327. https://doi.org/10.11896/jsjkx.200300160
[3]	刘漳辉, 赵旭, 林兵, 陈星. 混合云环境下基于模糊理论的科学工作流数据布局策略 Data Placement Strategy of Scientific Workflow Based on Fuzzy Theory in Hybrid Cloud 计算机科学, 2021, 48(11): 199-207. https://doi.org/10.11896/jsjkx.200900009
[4]	黄引豪, 马郓, 林兵, 於志勇, 陈星. 混合云环境下面向代价优化的工作流数据布局方法 Cost-driven Workflow Data Placement Method in Hybrid Cloud Environment 计算机科学, 2019, 46(11A): 354-358.
[5]	张桂鹏, 陈平华. 一种混合云环境下基于Merkle哈希树的数据安全去重方案 Secure Data Deduplication Scheme Based on Merkle Hash Tree in HybridCloud Storage Environments 计算机科学, 2018, 45(11): 187-192. https://doi.org/10.11896／j.issn.1002-137X.2018.11.029
[6]	范菁,沈杰,熊丽荣. 混合云环境中数据敏感工作流调度 Scheduling Data Sensitive Workflow in Hybrid Cloud 计算机科学, 2015, 42(Z11): 400-405.
[7]	王宗江,郑秋生,曹健. 混合云中的一个高效协调器 Efficient Coordinator in Hybrid Cloud 计算机科学, 2015, 42(1): 92-95. https://doi.org/10.11896/j.issn.1002-137X.2015.01.022