一种任务调度方法及其装置与流程

本技术涉及调度领域，尤其涉及一种任务调度方法及其装置。

背景技术：

1、调度问题是大型制造、物流、生产等环节中最常见的问题之一，在不同的场景下，调度总是有不同的意义。例如：物流调度主要是指在物流过程中，物流公司根据待发货物的重量、去向、规格、加急程度等对所属的车辆和人员进行合理的安排和调度。

2、已有技术中，往往采用穷举的方式来进行调度问题的计算，这会导致计算开销过大。

技术实现思路

1、本技术公开了一种任务调度方法，可以在保证求解效果的情况下，降低求解的开销(时间开销和算力开销)。

2、第一方面，本技术提供了一种任务调度方法，所述方法包括：获取第一任务的多个不同的第一时间窗组合；每个所述第一时间窗组合包括执行所述第一任务的一个候选时间窗，以及执行多个第二任务中每个所述第二任务的一个候选时间窗；所述第一任务为所述多个第二任务的父任务，且所述第一任务为第三任务的子任务；根据每个所述第一时间窗组合中所述第一任务的候选时间窗和所述多个第二任务的候选时间窗之间的重合度，从多个所述第一时间窗组合中确定执行所述第一任务以及所述多个第二任务时使用的时间窗组合；根据所述执行所述第一任务以及所述多个第二任务时使用的时间窗组合，确定执行所述第三任务时使用的时间窗。

3、本技术实施例的思路在于，在进行父任务-子任务的求解时，首先获取到父任务-子任务的多个时间窗组合，不同的时间窗组合是父任务-子任务的不同的候选时间窗的组合，之后，可以从多个时间窗组合中选择父任务和子任务之间在时间窗上重叠度更高的时间窗组合，从而降低整体的时间开销，且，首先进行较细粒度(也就是在树状任务结构中，更靠近叶子方向的任务，也就是更远离根部方向任务)的父任务-子任务的求解，然后再基于较细粒度的父任务-子任务的求解结果，进行上一层级的父任务-子任务的求解，相比通过穷举进行求解的方式，可以在保证求解效果的情况下，降低求解的开销(时间开销和算力开销)。

4、在一种可能的实现中，所述第三任务包括所述第一任务在内的多个子任务，所述根据所述执行所述第一任务以及所述多个第二任务时使用的时间窗组合，确定执行所述第三任务时使用的时间窗，包括：获取所述第三任务的多个不同的第二时间窗组合；每个所述第二时间窗组合包括执行所述第三任务的一个候选时间窗，以及执行所述多个子任务中每个所述子任务的一个候选时间窗；每个所述第二时间窗组合中所述第一任务的候选时间窗为所述执行所述第一任务以及所述多个第二任务时使用的时间窗组合中指示的；根据每个所述第二时间窗组合中所述第三任务的候选时间窗和所述多个子任务的候选时间窗之间的重合度，从多个所述第二时间窗组合中确定执行所述第三任务以及所述多个子任务时使用的时间窗组合。

5、本技术实施例中，可以先对最细粒度的父任务-子任务进行求解，然后逐步向更粗粒度的父任务进行求解。

6、在一种可能的实现中，所述重合度与第一信息有关：所述第一信息与第一时间长度正相关，所述第一信息与第二时间长度负相关，所述第一时间长度为父任务与包括的一个子任务之间重合的时间窗的长度，所述第二时间长度为子任务的时间窗的长度。第一信息可以表示父任务和子任务之间的时间窗的相对相容程度，数值越大表示父任务和子任务的之间的匹配度越大。

7、在一种可能的实现中，所述第一信息为所述第一时间长度和所述第二时间长度的比值。

8、在一种可能的实现中，所述重合度与第二信息有关：所述第二信息与第三时间长度正相关，所述第二信息与第四时间长度负相关，所述第三时间长度为父任务与包括的每个子任务之间重合的时间窗的长度的加和，所述第四时间长度为父任务的每个子任务的时间窗的长度的加和。第一信息可以表示父任务和子任务的整个系统之间的时间窗的相对相容程度，数值越大表示父任务和子任务的之间的匹配度越大。

9、在一种可能的实现中，所述第二信息为所述第三时间长度和所述第四时间长度的比值。

10、第二方面，本技术提供了一种任务调度装置，所述装置包括：

11、获取模块，用于获取第一任务的多个不同的第一时间窗组合；每个所述第一时间窗组合包括执行所述第一任务的一个候选时间窗，以及执行多个第二任务中每个所述第二任务的一个候选时间窗；所述第一任务为所述多个第二任务的父任务，且所述第一任务为第三任务的子任务；

12、调度模块，用于根据每个所述第一时间窗组合中所述第一任务的候选时间窗和所述多个第二任务的候选时间窗之间的重合度，从多个所述第一时间窗组合中确定执行所述第一任务以及所述多个第二任务时使用的时间窗组合；根据所述执行所述第一任务以及所述多个第二任务时使用的时间窗组合，确定执行所述第三任务时使用的时间窗。

13、在一种可能的实现中，所述第三任务包括所述第一任务在内的多个子任务，所述调度模块，用于：

14、获取所述第三任务的多个不同的第二时间窗组合；每个所述第二时间窗组合包括执行所述第三任务的一个候选时间窗，以及执行所述多个子任务中每个所述子任务的一个候选时间窗；每个所述第二时间窗组合中所述第一任务的候选时间窗为所述执行所述第一任务以及所述多个第二任务时使用的时间窗组合中指示的；根据每个所述第二时间窗组合中所述第三任务的候选时间窗和所述多个子任务的候选时间窗之间的重合度，从多个所述第二时间窗组合中确定执行所述第三任务以及所述多个子任务时使用的时间窗组合。

15、在一种可能的实现中，所述重合度与第一信息有关：所述第一信息与第一时间长度正相关，所述第一信息与第二时间长度负相关，所述第一时间长度为父任务与包括的一个子任务之间重合的时间窗的长度，所述第二时间长度为子任务的时间窗的长度。

16、在一种可能的实现中，所述第一信息为所述第一时间长度和所述第二时间长度的比值。

17、在一种可能的实现中，所述重合度与第二信息有关：所述第二信息与第三时间长度正相关，所述第二信息与第四时间长度负相关，所述第三时间长度为父任务与包括的每个子任务之间重合的时间窗的长度的加和，所述第四时间长度为父任务的每个子任务的时间窗的长度的加和。

18、在一种可能的实现中，所述第二信息为所述第三时间长度和所述第四时间长度的比值。

19、第三方面，本技术实施例提供了一种装置，包括存储器、处理器以及总线系统，其中，存储器用于存储程序，处理器用于执行存储器中的程序，以执行如上述第一方面及第一方面任一可选的方法。

20、第四方面，本发明实施例还提供一种系统，该系统包括至少一个处理器，至少一个存储器以及至少一个通信接口；处理器、存储器和通信接口通过通信总线连接并完成相互间的通信；

21、存储器用于存储执行以上方案的应用程序代码，并由处理器来控制执行。所述处理器用于执行所述存储器中存储的应用程序代码，以得到任务调度结果；其中存储器存储的代码可执行以上提供的一种任务调度方法。

22、通信接口，用于与其他设备或通信网络通信，以将所述任务求解结果发送至所述设备或通信网络。

23、第五方面，本技术实施例提供了一种计算机可读存储介质，所述计算机可读存储介质中存储有计算机程序，当其在计算机上运行时，使得计算机执行上述第一方面及其任一可选的方法。

24、第六方面，本技术实施例提供了一种计算机可读存储介质，所述计算机存储介质存储有一个或多个指令，所述指令在由一个或多个计算机执行时使得所述一个或多个计算机实施上述第二方面及其任一可选的系统。

25、第七方面，本技术实施例提供了一种计算机程序，当其在计算机上运行时，使得计算机执行上述第一方面及其任一可选的方法。

26、第八方面，本技术提供了一种芯片系统，该芯片系统包括处理器，用于支持终端设备或服务器实现上述方面中所涉及的功能，例如，发送或处理上述方法中所涉及的数据；或，信息。在一种可能的设计中，所述芯片系统还包括存储器，所述存储器，用于保存终端设备或服务器必要的程序指令和数据。该芯片系统，可以由芯片构成，也可以包括芯片和其他分立器件。

27、本技术在上述各方面提供的实现方式的基础上，还可以进行进一步组合以提供更多实现方式。