一种基于启发式策略的任务高效调度方法

技术领域

本发明涉及计算；推算；计数的技术领域，特别涉及一种基于启发式策略的任务高效调度方法。

背景技术

任务调度作为一个经典的问题，经过多年的研究，各项成果已广泛应用于交通运输、医疗服务、零售业、生产制造以及网络资源调度等领域。

然而，随着行业的不断发展，任务调度也面临着更为复杂的要求，需要考虑的约束条件也随之增加，部分任务调度问题及其变种问题已经被证明是NP-hard问题，例如在医疗场景中的护士排班问题、在工业生产中的车间调度问题等。如何设计快速有效的调度算法成为业界的研究难题。

现有主流的任务调度算法主要分为数学规划法、启发式算法以及演化算法。覆盖度作为衡量任务调度方案质量的重要评估指标，通常用以评估某个任务在调度周期的某个时段上，资源提供的能力对于该时段内任务工作量的满足程度。虽然上述算法处理任务调度问题时，将覆盖度作为优化目标，已经取得了一系列成果，但是现实中部分任务调度场景要求在一定时限内生成高质量的任务调度方案，然而现有技术的算法往往时间复杂度高、算法结果不稳定，如何在保证调度方案的平均覆盖度和覆盖度均衡性的前提下实现任务的高效调度是亟待解决的。

发明内容

本发明解决了现有技术中存在的问题，提供了一种优化的基于启发式策略的任务高效调度方法。

本发明所采用的技术方案是，一种基于启发式策略的任务高效调度方法，所述方法按调度周期内时段顺序进行任务调度，基于资源集R、最长连续工作时段数量k以及当前时段生成一组当前时段内可用的资源集available_R，基于available_R和每种任务的工作量得到当前时段内每种任务所需的资源数量，根据当前时段内每种任务的工作量及每种任务所需的资源数量生成可行的调度方案。

优选地，对于任一任务，定义调度周期、任务集和约束条件，配置资源集及对应资源集中每个资源的能力值集；

所述约束条件包括必须遵守的硬约束和除硬约束外的软约束，所述软约束为任务的工作量的分配平均且均衡；

对应所述软约束设置评估指标，用于评估每个任务调度方案并取最优。

优选地，所述评估指标为平均覆盖度Ave_Coverage和覆盖度均衡性Coverage_Fairness，

其中，ap_task_it指代第i时段任务task_t被分配的资源能力值，W_task_it指代第i时段任务task_t的工作量，θ为任务的种类总数，n为时段总数；

评估指标中平均覆盖度Ave_Coverage与1的差值越小、且Coverage_Fairness越小，则评估越优。

优选地，基于available_R和每种任务的工作量得到当前时段内每种任务所需的资源数量包括以下步骤：

步骤1.1：根据可用的资源集available_R，计算资源的总能力值total_AP和平均能力值average_AP；

步骤1.2：确定当前时段可以分配给任务的总能力值totalap_d

步骤1.3：根据每种任务的工作量在当前时段总工作量的占比，计算出每种任务的预计可被分配的资源能力值ap_task_it；

步骤1.4：计算当前时段每种任务所需的资源数量resource_task_it。

优选地，

resource_task_it＝round_off(ap_task_it/average_AP)

其中，∑W_task_it是d

优选地，生成可行的调度方案包括以下步骤：

步骤2.1：获取可用资源的能力值集AP，计算AP中可用资源的平均能力值average_AP，并将资源能力值按升序排序后基于average_AP将资源集AP划分成两个子集；

步骤2.2：分别取两个子集的第一个能力值，获得对应的资源，作为第一个资源组合；

步骤2.3：以第一个资源组合做为触发点，计算下一个资源组合的期望平均能力值，以能力值平均矩阵CAM为索引，引导至第二个资源组合，依次类推；若任务预估所需资源数量为偶数，则按照资源组的形式搜索，直到所选资源组中的资源数量等于该任务预估所需资源数量，否则以若任务预估所需资源数量为奇数，则按照资源组的形式先行搜索，直到剩余最后一个资源，那么该资源也将会被视为一个资源组。

优选地，后一个资源组合的期望平均能力值为2倍的可用资源集的平均能力值与上一个资源组合的平均能力值之差。

优选地，所述方法的时间复杂度小于等于O(n×m

优选地，所述方法的空间复杂度为O(n×m

本发明涉及一种优化的基于启发式策略的任务高效调度方法，按调度周期内时段顺序进行任务调度，基于资源集R、最长连续工作时段数量k以及当前时段生成一组当前时段内可用的资源集available_R，基于available_R和每种任务的工作量得到当前时段内每种任务所需的资源数量，根据当前时段内每种任务的工作量及每种任务所需的资源数量生成可行的调度方案。

本发明的有益效果在于：

(1)通过资源的任务序列，识别其在当前时段内是否违反硬约束，从而保证调度方案的可用性；

(2)提出资源数量预估策略，通过预先估计任务所需资源数量，排除大量平均覆盖度较低和覆盖度均衡性较差的调度方案，缩小搜索空间；

(3)提出按组分配策略，通过当前时段任务的工作量和资源的能力值，以资源平均能力值为索引，快速搜索预估数量的资源组合；通过建立能力值平均矩阵动态缩小资源组合的搜索空间，进一步提升搜索效率。

附图说明

图1为本发明的流程图；

图2为本发明中能力值子集划分示意图；

图3为本发明中能力值平均矩阵示意图；

图4为本发明中移除cp

具体实施方式

下面结合实施例对本发明做进一步的详细描述，但本发明的保护范围并不限于此。

本发明涉及一种基于启发式策略的任务高效调度方法，所述方法按调度周期内时段顺序进行任务调度，基于资源集R、最长连续工作时段数量k以及当前时段生成一组当前时段内可用的资源集available_R，基于available_R和每种任务的工作量得到当前时段内每种任务所需的资源数量，根据当前时段内每种任务的工作量及每种任务所需的资源数量生成可行的调度方案。

对于任一任务，定义调度周期、任务集和约束条件，配置资源集及对应资源集中每个资源的能力值集；

所述约束条件包括必须遵守的硬约束和除硬约束外的软约束，所述软约束为任务的工作量的分配平均且均衡；

对应所述软约束设置评估指标，用于评估每个任务调度方案并取最优。

所述评估指标为平均覆盖度Ave_Coverage和覆盖度均衡性Coverage_Fairness，

其中，ap_task_it指代第i时段任务task_t被分配的资源能力值，W_task_it指代第i时段任务task_t的工作量，θ为任务的种类总数，n为时段总数；

评估指标中平均覆盖度Ave_Coverage与1的差值越小、且Coverage_Fairness越小，则评估越优。

本发明中，定义调度周期、任务、资源和约束条件；

调度周期是由一系列相同的时段组成，定义为D＝{d

在调度周期中每一个时段包含多种任务，用{Task_1,Task_2,…,Task_θ}进行表示；每一种任务的工作量都需要一定数量的资源来满足；

不同时段内，任务的工作量可能会发生变化，对资源的需求数量也会随之发生变化；

资源被定义为R＝{r

在任务调度问题中，资源提供能力值，去满足任务的工作量。以员工调度场景为例，假设某员工的能力值为1，在周一被分配执行白班任务，那么该员工在周一这天能完成白班任务的工作量为1。

当任务被分配给资源时，需要考虑任务调度场景中的约束条件。这些约束条件可以分成两类：

本发明中，给定一个调度周期D＝{d

硬约束H

-H

-H

同时，平均覆盖度Ave_Coverage最接近1；覆盖度均衡性Coverage_Fairness的值最小化。

基于available_R和每种任务的工作量得到当前时段内每种任务所需的资源数量包括以下步骤：

步骤1.1：根据可用的资源集available_R，计算资源的总能力值total_AP和平均能力值average_AP；

步骤1.2：确定当前时段可以分配给任务的总能力值totalap_d

步骤1.3：根据每种任务的工作量在当前时段总工作量的占比，计算出每种任务的预计可被分配的资源能力值ap_task_it；

步骤1.4：计算当前时段每种任务所需的资源数量resource_task_it。

resource_task_it＝round_off(ap_task_it/average_AP)

其中，∑W_task_it是d

本发明中，算法按调度周期内时段顺序进行任务调度，每个时段内任务-资源的配置过程包括识别可用资源、估算资源数量、搜索可行方案，资源集R、最长连续工作时段数量k以及当前时段d

本发明中，为了保证最终任务调度方案的可用性，调度方案需要满足所有的硬约束条件，即需要在各个时段对资源进行可用性识别，由于硬约束H

本发明中，首先提取d

本发明中，令r

生成可行的调度方案包括以下步骤：

步骤2.1：获取可用资源的能力值集AP，计算AP中可用资源的平均能力值average_AP，并将资源能力值按升序排序后基于average_AP将资源集AP划分成两个子集；

步骤2.2：分别取两个子集的第一个能力值，获得对应的资源，作为第一个资源组合；

步骤2.3：以第一个资源组合做为触发点，计算下一个资源组合的期望平均能力值，以能力值平均矩阵CAM为索引，引导至第二个资源组合，依次类推；若任务预估所需资源数量为偶数，则按照资源组的形式搜索，直到所选资源组中的资源数量等于该任务预估所需资源数量，否则以若任务预估所需资源数量为奇数，则按照资源组的形式先行搜索，直到剩余最后一个资源，那么该资源也将会被视为一个资源组。

后一个资源组合的期望平均能力值为2倍的可用资源集的平均能力值与上一个资源组合的平均能力值之差。

本发明中，由于各种任务的资源数量是由资源的平均能力值average_AP进行估算的，所以当调度方案中每一种任务被分配的资源数量等于预估数量，并且资源的平均能力值等于所有可用资源的平均能力值average_AP时，该方案必然能具有最高的覆盖度和最优的覆盖度均衡性；当实际分配给各种任务的资源，其平均能力值越接近可用资源的平均能力值average_AP，那么平均覆盖度Ave_Coverage离最优值1也就越近，覆盖度均衡性Coverage_Fairness距离最优值0也越近，因此生成的任务调度方案质量也就越高。

给定一个包含5个可用资源的集合AP，计算AP中可用资源的平均能力值average_AP，并将资源能力值按升序排序，然后根据average_AP将可用资源集AP划分成两个子集AP

接下来，算法采用按组分配的策略，搜索各种任务的资源组合；取出AP

然后，算法以能力值平均矩阵CAM为索引，查找最接近第二个资源组合的期望平均能力值Ep

上述方式适用于任务预估所需资源数量为偶数的情况。在对面估计的资源数量是奇数的情况时，最后一个资源将被视为一个资源组，同样遵循了资源组平均能力值(即最后一个资源的能力值)最大程度接近average_AP的原则进行定位。据此，算法可以生成一个由各种任务资源组合(RC_task_it)形成的候选方案。在上述例子中，资源r

本发明中，这些候选方案通过基于理想解相似度的顺序偏好技术(Technique forOrder Preference by Similarity to an Ideal Solution，TOPSIS)进行评估，以选择出当前时段的最终可行任务调度方案。TOPSIS将优化目标正交化，即所有的优化目标具有相同的优化方向，其次，因为优化目标的取值范围不同，TOPSIS对所有的优化目标进行标准化，使之能在同一个取值范围内，最后，TOPSIS对标准化后的结果进行评估并生成分数，分数越高，说明该结果的质量越高，平均覆盖度和覆盖度均衡性也就越优。

所述方法的时间复杂度小于等于O(n×m

所述方法的空间复杂度为O(n×m

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。