Computer Science ›› 2022, Vol. 49 ›› Issue (5): 244-249.doi: 10.11896/jsjkx.210300120

• Computer Network • Previous Articles     Next Articles

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   

  1. 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) 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

CLC Number: 

  • TP301
[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.
[1] JI Yan, DAI Hua, JIANG Ying-ying, YANG Geng, Yi Xun. Parallel Multi-keyword Top-k Search Scheme over Encrypted Data in Hybrid Clouds [J]. Computer Science, 2021, 48(5): 320-327.
[2] . Data Selection Strategy for Data-intensive Applications in Cloud [J]. Computer Science, 2012, 39(6): 30-34.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!