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

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

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

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.