基于非支配不等式的不相关并行机调度方法及其相关设备

摘要

本公开提供一种基于非支配不等式的不相关并行机调度方案，深入分析了时间窗口间复杂的相互交叠关系，改进模型线性松弛上界。设计了一种新的预处理算法，能成功调度更多的待处理对象。具体的，首先通过在模型中引入表示待处理对象是否调度到实施主体对应的时间窗口的第一变量和表示所述待处理对象分配到所述时间窗口对应的开始时间的第二变量，然后分析时间窗口之间的冲突和关系，在模型中加入与时间窗口交叠相关的非支配不等式，根据不同情况得到相应的调度方案并进行调度。得到了一个新的改进混合整数线性规划模型，避免了引入“大M”变量，具有更紧的线性松弛上界。避免了所有待处理对象之间引入0‑1变量，提高了调度方案的求解效率。

说明书

技术领域

本公开涉及混合整数线性规划技术领域，尤其涉及一种基于非支配不等式的不相关并行机调度方法及其相关设备。

背景技术

对地观测卫星是响应用户需求，通过搭载的遥感器(有效载荷)对地球表面进行成像的一类卫星平台。由于观测需求的“爆发性”增长和资源的有限性，调度对于提高观测效率至关重要。通常，对地观测卫星在低轨运行，每天可以绕地球运转十几到几十个圈次。显然，卫星只有在飞越目标上空时才能成功观测，即目标必须在卫星可视范围内。因此，目标观测具有时间窗口约束。由于每天绕地运行多个轨道圈次，加上传感器灵活的机动能力和视场范围，卫星能够从多个相邻轨道对同一目标进行观测。因此，单个卫星观测单个目标可能存在多个时间窗口。由于轨道不同，不同卫星观测同一目标的时间窗口也不同。进一步，在两个连续观测目标之间，卫星需要进行一定转换操作，包括传感器关机、侧摆、姿态稳定和重新启动。因此，如果把每个卫星看作一台实施主体，每个目标看作一个待处理对象，则对地观测卫星调度问题可以被描述为具有多个时间窗口和转换时间的不相关并行机调度问题。

类似的问题同样存在于生产车间的实施主体调度和企业的人员排班，其中只能在实施主体或员工的工作时间窗口内分配待处理对象或待处理对象。此外，大部分情况下，实施主体和员工只在白天工作。另一个典型应用是具有多个时间窗口的团队定向问题，在睡眠时间和工作时间客户不能被访问。不同的是，上述问题中的时间窗口仅依赖于实施主体或待处理对象之一，而可见性是由卫星的轨道和目标位置共同决定的，所以时间窗口同时依赖于待处理对象和实施主体。

发明内容

有鉴于此，本公开的目的在于提出一种基于非支配不等式的不相关并行机调度方法及其相关设备。

基于上述目的，本公开提供了一种基于非支配不等式的不相关并行机调度方法，包括：

响应于确定第一变量为1，待处理对象在对应的时间窗口内被处理，响应于确定第一变量为0，令第二变量为0；根据所述第一变量和第二变量调度所述待处理对象，其中，所述第一变量表示所述待处理对象是否调度到实施主体对应的时间窗口，是则所述第一变量为1，否则所述第一变量为0，所述第二变量表示所述待处理对象分配到所述时间窗口对应的开始时间，每个所述待处理对象最多被调用一次；

响应于确定第一待处理对象的最晚可结束时间小于第二待处理对象的最早可开始时间与实施主体转换时间之和，所述第二待处理对象在所述第一待处理对象之前被处理；响应于确定所述第一待处理对象的最晚可结束时间大于所述第二待处理对象的最早可开始时间与实施主体转换时间之和，所述第二待处理对象在所述第一待处理对象之后被处理；

响应于确定第三变量为1，所述第一待处理对象在所述第二待处理对象前被处理；响应于确定第四变量为1，所述第一待处理对象在所述第二待处理对象后被处理；其中，所述第三变量和第四变量分别表示所述第一待处理对象和所述第二待处理对象的调度次序，所述第三变量和第四变量满足转换时间约束、一致性约束和域约束；

根据全部所述时间窗口的交叠信息，得到非支配不等式；

根据上述条件建立混合整数线性规划模型并求解，得到调度待处理对象总收益最大值的调度方案，并根据所述调度方案进行调度。

基于同一发明构思，本公开还提供了一种不相关并行机调度装置，包括：

第一处理模块，被配置为响应于确定第一变量为1，待处理对象在对应的时间窗口内被处理，响应于确定第一变量为0，令第二变量为0；根据所述第一变量和第二变量调度所述待处理对象，其中，所述第一变量表示所述待处理对象是否调度到实施主体对应的时间窗口，是则所述第一变量为1，否则所述第一变量为0，所述第二变量表示所述待处理对象分配到所述时间窗口对应的开始时间，每个所述待处理对象最多被调用一次；

第二处理模块，被配置为响应于确定第一待处理对象的最晚可结束时间小于第二待处理对象的最早可开始时间与实施主体转换时间之和，所述第二待处理对象在所述第一待处理对象之前被处理；响应于确定所述第一待处理对象的最晚可结束时间大于所述第二待处理对象的最早可开始时间与实施主体转换时间之和，所述第二待处理对象在所述第一待处理对象之后被处理；

第三处理模块，被配置为响应于确定第三变量为1，所述第一待处理对象在所述第二待处理对象前被处理；响应于确定第四变量为1，所述第一待处理对象在所述第二待处理对象后被处理；其中，所述第三变量和第四变量分别表示所述第一待处理对象和所述第二待处理对象的调度次序，所述第三变量和第四变量满足转换时间约束、一致性约束和域约束；

不等式生成模块，被配置为根据全部所述时间窗口的交叠信息，得到非支配不等式；

调度模块，被配置为根据上述条件建立混合整数线性规划模型并求解，得到调度待处理对象总收益最大值的调度方案，并根据所述调度方案进行调度。

基于同一发明构思，本说明书一个或多个实施例还提供了一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如上任意一项所述的方法。

从上面所述可以看出，本公开提供的基于非支配不等式的不相关并行机调度方法及其相关设备，通过在模型中引入表示待处理对象是否调度到实施主体对应的时间窗口的第一变量和表示所述待处理对象分配到所述时间窗口对应的开始时间的第二变量，然后分析时间窗口之间的冲突和关系，根据不同情况的到相应的调度方案并根据调度方案进行调度，同时在模型中加入与时间窗口交叠相关的非支配不等式。得到了一个新的改进混合整数线性规划模型(MILP)模型，避免了引入“大M”变量，具有更紧的线性松弛上界。避免了所有待处理对象之间引入0-1变量，提高了调度方案的求解效率。

附图说明

为了更清楚地说明本公开或相关技术中的技术方案，下面将对实施例或相关技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本公开的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本公开实施例的基于非支配不等式的不相关并行机调度方法流程图；

图2为本公开实施例的基于非支配不等式的不相关并行机调度方法预处理流程图；

图3(a)、图3(b)为本公开实施例的两个时间窗口的不同情况示意图；

图4(a)-(j)为本公开实施例的三个时间窗口的不同情况示意图；

图5为本公开实施例的非支配不等式寻找流程图；

图6为本公开实施例的不等式识别和添加示例示意图；

图7为本公开实施例的基于非支配不等式的不相关并行机调度装置结构示意图；

图8为本公开实施例的电子设备结构示意图。

具体实施方式

为使本公开的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本公开进一步详细说明。

需要说明的是，除非另外定义，本公开实施例使用的技术术语或者科学术语应当为本公开所属领域内具有一般技能的人士所理解的通常意义。本公开实施例中使用的“第一”、“第二”以及类似的词语并不表示任何顺序、数量或者重要性，而只是用来区分不同的组成部分。“包括”或者“包含”等类似的词语意指出现该词前面的元件或者物件涵盖出现在该词后面列举的元件或者物件及其等同，而不排除其他元件或者物件。“连接”或者“相连”等类似的词语并非限定于物理的或者机械的连接，而是可以包括电性的连接，不管是直接的还是间接的。“上”、“下”、“左”、“右”等仅用于表示相对位置关系，当被描述对象的绝对位置改变后，则该相对位置关系也可能相应地改变。

如背景技术部分所述，现有的不相关并行机调度问题存在于生产生活的各个方面。申请人在实现本公开的过程中发现，现有的针对具有多个时间窗口的不相关并行机调度问题的解决方法非常有限。许多学者已经研究了具有时间窗口的不相关并行机调度问题，并将研究工作扩展到卫星调度领域。为了提高跟踪和数据中继卫星系统(TDRSS)天线的利用率，Rojanasoonthon和Bard研究了具有时间窗口的不相关并行机调度问题。首先，建立了一个混合整数线性规划模型，考虑该模型过于复杂，难以求解现实中的大规模问题。他们采用了两种启发式算法求解模型，首先是贪婪随机自适应搜索算法(GRASP)，算法包含两个阶段。第一阶段，通过贪婪函数对待处理对象进行排序，按照顺序逐个调度每个待处理对象产生初始可行解。第二阶段通过待处理对象插入和交换邻域搜索局部最优解。然后，提出了一种类似动态规划的启发式算法，称为R-B算法。R-B启发式算法的基本思想是通过由待处理对象之间的优先关系构造无环有向图，然后搜索有向图的最长路径。考虑元启发式算法通常无法获得最优解，并且不能保证和评估解的最优性，Rojanasoonthon和Bard进一步试图求解该问题最优解。基于问题的特殊结构，将混合整数线性规划模型重构为独立子集主问题和多个最短路定价子问题，设计了分支定价求解算法。更全面地说，采用上述GRASP启发式算法求解定价子问题。他们的研究中，每个待处理对象具有多个时间窗口，但每个待处理对象在每台实施主体上最多只有一个或两个时间窗口，并没有考虑更多时间窗口的情况。

Chen研究了对地观测卫星调度问题，是一个具有时间窗口的不相关并行机调度问题的变体。研究中，每个待处理对象在每台实施主体上具有多个时间窗口。通过深入分析可行时间窗口之间的相互依赖关系，设计了一个新的混合整数线性规划模型，并通过改进的约束使模型线性松弛更加紧。然后，提出了一种预处理算法减小问题规模，便于算法求解。但在实际工作中，传统模型由于引入了“大M”参数，所以模型的线性松弛很难获得紧的上界。传统模型中，对于任何两个待处理对象i，j和任何一个实施主体k，都需要定义一个0-1变量

有鉴于此，本公开一个或多个实施例提供了一种不相关并行机调度方案，进一步深入分析了时间窗口间复杂的相互交叠关系，改进模型线性松弛上界。设计了一种新的预处理算法，能成功调度更多的待处理对象。具体的，首先通过在模型中引入表示待处理对象是否调度到实施主体对应的时间窗口的第一变量和表示所述待处理对象分配到所述时间窗口对应的开始时间的第二变量，然后分析时间窗口之间的冲突和关系，在模型中加入与时间窗口交叠相关的非支配不等式，根据不同情况的到相应的调度方案并根据调度方案进行调度。得到了一个新的改进混合整数线性规划模型(MILP)模型，避免了引入“大M”变量，具有更紧的线性松弛上界。避免了所有待处理对象之间引入0-1变量，提高了调度方案的求解效率。

以下，通过具体的实施例来详细说明本公开一个或多个实施例的技术方案。

参考图1，本说明书一个实施例的基于非支配不等式的不相关并行机调度方法，包括以下步骤：

步骤S101、响应于确定第一变量为1，待处理对象在对应的时间窗口内被处理，响应于确定第一变量为0，令第二变量为0；根据所述第一变量和第二变量调度所述待处理对象，其中，所述第一变量表示所述待处理对象是否调度到实施主体对应的时间窗口，是则所述第一变量为1，否则所述第一变量为0，所述第二变量表示所述待处理对象分配到所述时间窗口对应的开始时间，每个所述待处理对象最多被调用一次；

本实施例中，所述待处理对象和实施主体在不同的实施场景下可以是不同的，在机械零件加工的场景中，待处理对象可以是待加工的零件，实施主体可以是车床；在车辆路径问题中，待处理对象可以是车辆的路径，实施主体可以是车辆本身；在卫星调度的场景中，待处理对象可以是卫星的工作任务，实施主体可以是卫星本身。

步骤S102、响应于确定第一待处理对象的最晚可结束时间小于第二待处理对象的最早可开始时间与实施主体转换时间之和，所述第二待处理对象在所述第一待处理对象之前被处理；响应于确定所述第一待处理对象的最晚可结束时间大于所述第二待处理对象的最早可开始时间与实施主体转换时间之和，所述第二待处理对象在所述第一待处理对象之后被处理：

步骤S103、响应于确定第三变量为1，所述第一待处理对象在所述第二待处理对象前被处理；响应于确定第四变量为1，所述第一待处理对象在所述第二待处理对象后被处理；其中，所述第三变量和第四变量分别表示所述第一待处理对象和所述第二待处理对象的调度次序，所述第三变量和第四变量满足转换时间约束、一致性约束和域约束；

步骤S104、根据全部所述时间窗口的交叠信息，得到非支配不等式；

步骤S105、根据上述条件建立混合整数线性规划模型并求解，得到调度待处理对象总收益最大值的调度方案，并根据所述调度方案进行调度。

本步骤中，所述混合整数线性规划模型可以表示为：

其中，所述模型表示最大化调度待处理对象总收益，包含两个虚拟待处理对象，分别是{0，n+1}，对应于开始待处理对象和终止待处理对象，J为所述待处理对象的集合，M为所述实施主体的集合，i，j∈J∪{0，n+1}，k∈M，l∈TW

本实施例中，每个待处理对象应在其某一个时间窗口内调度；否则，无法被调度。此外，每个待处理对象应当一次被处理完成而不中断，因此本模型专注于非抢占调度，调度目标是最大化被处理待处理对象的总收益。

本实施例中，所述混合整数线性规划模型具体包括：

该约束保证每个待处理对象最多被调度一次。

该约束为第一变量

上述两个约束为时间窗口约束，对应于步骤S101的：所述响应于确定第一变量为1，所述待处理对象在对应的时间窗口内被处理，响应于确定第一变量为0，令第二变量为0。其中，t

对于两个待处理对象i，j(第一待处理对象，第二待处理对象)在实施主体k上的两个时间窗口

该约束为转换时间约束，对应于步骤S102的：响应于确定第一待处理对象的最晚可结束时间小于第二待处理对象的最早可开始时间与实施主体转换时间之和，所述第二待处理对象在所述第一待处理对象之前被处理。其中，t

对于两个待处理对象i，j在实施主体k上的两个时间窗口

该约束为转换时间约束，对应于步骤S102的：响应于确定所述第一待处理对象的最晚可结束时间大于所述第二待处理对象的最早可开始时间与实施主体转换时间之和，所述第二待处理对象在所述第一待处理对象之后被处理。

如果两个待处理对象i，j都调度在实施主体k上，不能确认这两个待处理对象的被处理顺序。因此，需要引入辅助0-1变量：第三变量

另外，第一变量

同时，第三变量

可见，本实施例中，通过引入第二变量t

下面，给出本公开的不相关并行机调度方法的一个具体的应用场景。算法通过C++调用CPLEX 12.8 API实现，编译器为Visual Studio 2017，运行在Intel(R)Core(TM)i7-5960 X CPU@3.00GHz(16processors)计算机，64Gb内存，操作系统为Windows 7。

为了评估本公开模型和算法的性能，通过仿真模拟创建了大量问题实例。本例中待处理对象为工件，执行主体为机器。机器数目分别为5、10、15和20台。此外，每个时间间隔中的时间窗口数量分别在[5，10]、[10，15]、[15，20]和[20，25]范围内服从均匀分布随机生成。根据机器的数量，工件数量分别设置为从小规模到大规模。因此，工件数最小为100，最大为1200。工件加工时间在[240，360]的范围内均匀分布，每台机器的转换时间在[180，300]范围内均匀分布随机生成。此外，调度周期设置为24小时。时间窗口的长度以秒为单位在区间[400，2000]内生成。通过不同数目的机器和工件组合，共产生了47个问题实例。表1给出了所有问题实例的详细参数。

表1：测试实例

表1中，列“Instance”表示每个实例的标识符。此外，列“|M|”、“|I|”、“|J|”、“|EJ|”和“|TW|”分别表示机器数目、每个间隔中的时间窗口数目、工件数目、有效工件(具有可用时间窗口)数目和时间窗口总数。

为了测试本实施例中的模型和算法的性能，将求解结果与Chen等的模型和算法性能进行了比较。比较结果如表2所示，其中“Objective”表示目标函数值，即被处理待处理对象的总收益。“Gap”表示可行解与最优解上界的距离，由(UB-Fea)/UB计算得到，其中UB表示最优解上界，Fea表示可行解目标函数值。求解时间设置为20分钟，如果20分钟内找到最优解，则在列“Time(s)”中显示求解时间。

如表2所示，本实施例的方法和Chen等的方法对于大部分实例都能求得最优解。具体而言，本实施例的方法求得最优解的实例数量大于Chen等的方法(39>34)。此外，针对两种方法都能求得最优解的实例(33个)，大部分实例(21个)本实施例的方法求解时间小于Chen等的方法。主要原因是：1)本实施例的预处理算法使得更多工件被预调度，减小了问题求解规模；2)由于加入更多有效不等式，本实施例的模型线性松弛上界更紧，便于问题求解；

表2：本实施例的模型和求解算法的性能评估

作为一个可选的实施例，参考图2，对于前述实施例中的不相关并行机调度方法，在求解所述模型之前，还可以对所述时间窗口进行预处理。

对于不少于四个时间窗口的情况，还可以通过前向滚动时间窗口算法对所述时间窗口进行预处理，包括以下步骤：

S201、获取每台所述实施主体的时间节点信息；

S202、根据所述时间节点信息按照先后顺序访问所述实施主体上的时间节点，响应于确定已经访问的时间窗口数量小于或等于3，更新所述已经访问的时间窗口的结束时间，更新后的结束时间不超过当前时间节点，并调度剩余的待处理对象；

S203、响应于确定所述已经访问的时间窗口中的待处理对象能够被成功调度，预调度所述已经访问的时间窗口中的待处理对象，并将所述已经访问的时间窗口中的待处理对象在所有实施主体上的时间窗口删除；

S204、响应于确定所述已经访问的时间窗口数量大于3，按时间先后顺序对时间窗口结束时间在前的待处理对象进行预调度，每次成功预调度一个待处理对象后，更新所述已经访问的时间窗口中剩余待处理对象的时间窗口的开始时间，直到剩余未预调度的待处理对象时间窗口数小于或等于3时，调度剩余的待处理对象。

本实施例中，对于一个时间窗口，显然只有一种情况。对于任意两个时间窗口，存在两种情况，令η

参考图3(a)，

参考图3(b)，

如果

对于任意三个时间窗口，对于三个待处理对象i、j和q的三个交叠的时间窗口

在本实施例中，参考下面前向滚动时间窗口算法流程。通过对多个时间窗口面对的不同情况进行预处理，能够减小问题规模和提高求解效率。

作为一个具体的示例，通过与Chen等的预处理策略比较，测试了本文预处理算法的性能。首先，表3中“Our preprocessing I”表示本实施例中提出的预处理算法，“Ourpreprocessing II”表示本实施例中预处理算法和Chen等的预处理算法的结合。表5列出了比较结果，其中“Num”是预处理中调度的待处理对象数目。“Objective”和“Time(s)”分别表示的是预调度待处理对象的总收益和预处理的求解时间。

通过表3中的结果，可以观察到本实施例的预处理策略I和II的预调度待处理对象的数目总是大于等于Chen等的预调度待处理对象数目。此外，对于大部分实例(47个中的34个)，预调度待处理对象的数目大于Chen等的预处理待处理对象的数目，由粗体标记。因此，与Chen等的算法相比，本实施例的算法在预处理方面有了很大改进。此外，关于本实施例的预处理策略I和II，所有实例预调度待处理对象数目相同。因此，得出结论，本实施例的预处理算法II的求解时间小于预处理算法I，由粗体标记，两种算法组合在提高预处理算法效率方面发挥重要作用。

在一些实施例中，参考下面流程，也可以通过后向滚动时间窗口算法对所述时间窗口进行预处理，后向滚动时间窗口算法的步骤与前向滚动时间窗口算法类似，只不过访问时间节点的顺序是从后往前的倒序。因此，后向滚动时间窗口算法可以看作是前向滚动时间窗口算法的镜像，即时间窗口开始时间变为结束时间，结束时间变为开始时间。

作为一个可选的实施例，对于前述实施例中的步骤S104，所述根据全部所述时间窗口的交叠信息，得到非支配不等式，包括：

当交叠的时间窗口数量为两个时，令η

参考图3(a)，响应于确定

参考图3(b)，响应于确定

根据得到的不等式，寻找非支配不等式。

作为一个可选的实施例，对于前述实施例中的步骤S104，所述根据全部所述时间窗口的交叠信息，得到非支配不等式，还包括：

当交叠的时间窗口数量为三个时，令η

参考图4(a)，响应于确定

参考图4(b)，响应于确定

参考图4(c)，响应于确定

参考图4(d)，响应于确定

若

若

参考图4(e)，响应于确定

参考图4(f)，响应于确定

参考图4(g)，响应于确定

参考图4(h)，响应于确定

参考图4(i)，响应于确定

否则，若

若

若

若

若

若

若

若

若

若

若

参考图4(j)，响应于确定

否则，若

若

若

根据得到的不等式，寻找非支配不等式。

作为一个可选的实施例，参考图5，对于前述实施例中的根据得到的不等式，寻找非支配不等式，具体包括：

S301、对每台实施主体按时间先后顺序访问每个时间节点；

S302、响应于确定当前时间节点t是某一时间间隔的第一个开始时间节点，记录该时间间隔的开始时间BeginTime和该时间间隔的第一个时间窗口

S303、响应于确定当前时间节点是某一时间窗口的结束时间节点，更新已经访问的时间窗口的集合，得到所述已经访问的时间窗口中的待处理对象在时间区间[BeginTime，t]上的有效不等式；

S304、将所述有效不等式与已存在的不等式集合中的不等式进行比较，响应于确定所述有效不等式是支配不等式，丢弃所述有效不等式；响应于确定所述有效不等式是非支配不等式，将所述有效不等式加入到所述不等式集合中；

S305、响应于确定所述不等式集合中存在被所述有效不等式支配或被共同支配的不等式，将被支配的不等式从所述不等式集合中移除；

S306、响应于确定所述当前时间节点t是某一时间间隔的最后一个时间窗口的结束时间节点，删除所述第一个时间窗口

S307、将所述不等式集合中所有的非支配不等式加入到所述模型。

本实施例中，提出了一种算法来寻找和识别有效不等式。类似与预处理算法，不等式识别和搜索算法也基于时间节点和滚动时间窗口的。其中，不等式支配的定义如下：

定义1：对于两个有效不等式

注意若不等式

定义2：对于一个不等式e:

定义3：如果一个不等式e既不被另一个不等式支配，也不被其他k(k≥2)个不等式共同支配，则不等式e为非支配不等式；否则e是一个支配不等式。

本实施例中，为了防止约束过多，模型过于庞大，只加入非支配不等式。

作为一个具体的示例，参考图6，有5个待处理对象，每个待处理对象都与一个被处理时间窗口。交叠的5个时间窗口形成一个可行时间间隔。另外，5个待处理对象的被处理时间分别为6，6,8，5，4。为便于描述，每两个待处理对象之间的转换时间设为0。该假设不会影响算法工作流程。

表4详细描述了不等式的添加过程。不等式x1+x2+x4≤2由已存在不等式x1+x2≤1和隐含的不等式x4≤1共同支配，因此x1+x2+x4≤2被丢弃(第0轮，时间14)。得到的不等式x2+x3+x4≤2由已存在不等式x1+x2+x3+x4≤2支配(第1轮，时刻16)。进一步，不等式集合中的不等式x1+x2+x3+x4≤2由新得到的不等式x3+x4≤1和现有的不等式x1+x2≤1共同支配(第2轮，时间16)。因此，不等式x1+x2+x3+x4≤2从不等式集合中被移除。最后，只有非支配不等式x1+x2≤1和x3+x4≤1被添加到模型。

表4不等式识别和添加过程

本实施例中，通过加入非支配不等式，可以使得模型更容易求解。

作为对比，参考表5，本实施例中模型的不等式数目大于Chen等的模型中不等式数目。此外，由于忽略了受支配不等式，模型的不等式数目要远远小于包含所有不等式的模型。根据理论分析结果，模型的不等式数目应该几乎是原始模型的1/2(n

表5：对于不同强化策略的性能评估

需要说明的是，本公开实施例的方法可以由单个设备执行，例如一台计算机或服务器等。本实施例的方法也可以应用于分布式场景下，由多台设备相互配合来完成。在这种分布式场景的情况下，这多台设备中的一台设备可以只执行本公开实施例的方法中的某一个或多个步骤，这多台设备相互之间会进行交互以完成所述的方法。

需要说明的是，上述对本公开的一些实施例进行了描述。其它实施例在所附权利要求书的范围内。在一些情况下，在权利要求书中记载的动作或步骤可以按照不同于上述实施例中的顺序来执行并且仍然可以实现期望的结果。另外，在附图中描绘的过程不一定要求示出的特定顺序或者连续顺序才能实现期望的结果。在某些实施方式中，多任务处理和并行处理也是可以的或者可能是有利的。

基于同一发明构思，与上述任意实施例方法相对应的，本公开还提供了一种基于非支配不等式的不相关并行机调度装置。

参考图7，所述基于非支配不等式的不相关并行机调度装置，包括：

第一处理模块，被配置为响应于确定第一变量为1，待处理对象在对应的时间窗口内被处理，响应于确定第一变量为0，令第二变量为0；根据所述第一变量和第二变量调度所述待处理对象，其中，所述第一变量表示所述待处理对象是否调度到实施主体对应的时间窗口，是则所述第一变量为1，否则所述第一变量为0，所述第二变量表示所述待处理对象分配到所述时间窗口对应的开始时间，每个所述待处理对象最多被调用一次；

第二处理模块，被配置为响应于确定第一待处理对象的最晚可结束时间小于第二待处理对象的最早可开始时间与实施主体转换时间之和，所述第二待处理对象在所述第一待处理对象之前被处理；响应于确定所述第一待处理对象的最晚可结束时间大于所述第二待处理对象的最早可开始时间与实施主体转换时间之和，所述第二待处理对象在所述第一待处理对象之后被处理；

第三处理模块，被配置为响应于确定第三变量为1，所述第一待处理对象在所述第二待处理对象前被处理；响应于确定第四变量为1，所述第一待处理对象在所述第二待处理对象后被处理；其中，所述第三变量和第四变量分别表示所述第一待处理对象和所述第二待处理对象的调度次序，所述第三变量和第四变量满足转换时间约束、一致性约束和域约束；

不等式生成模块，被配置为根据全部所述时间窗口的交叠信息，得到非支配不等式；

调度模块，被配置为根据上述条件建立混合整数线性规划模型并求解，得到调度待处理对象总收益最大值的调度方案，并根据所述调度方案进行调度。

为了描述的方便，描述以上装置时以功能分为各种模块分别描述。当然，在实施本公开时可以把各模块的功能在同一个或多个软件和/或硬件中实现。

上述实施例的装置用于实现前述任一实施例中相应的基于非支配不等式的不相关并行机调度方法，并且具有相应的方法实施例的有益效果，在此不再赘述。

基于同一发明构思，与上述任意实施例方法相对应的，本公开还提供了一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上任意一实施例所述的基于非支配不等式的不相关并行机调度方法。

图8示出了本实施例所提供的一种更为具体的电子设备硬件结构示意图，该设备可以包括：处理器1010、存储器1020、输入/输出接口1030、通信接口1040和总线1050。其中处理器1010、存储器1020、输入/输出接口1030和通信接口1040通过总线1050实现彼此之间在设备内部的通信连接。

处理器1010可以采用通用的CPU(Central Processing Unit，中央处理器)、微处理器、应用专用集成电路(Application Specific Integrated Circuit，ASIC)、或者一个或多个集成电路等方式实现，用于执行相关程序，以实现本说明书实施例所提供的技术方案。

存储器1020可以采用ROM(Read Only Memory，只读存储器)、RAM(Random AccessMemory，随机存取存储器)、静态存储设备，动态存储设备等形式实现。存储器1020可以存储操作系统和其他应用程序，在通过软件或者固件来实现本说明书实施例所提供的技术方案时，相关的程序代码保存在存储器1020中，并由处理器1010来调用执行。

输入/输出接口1030用于连接输入/输出模块，以实现信息输入及输出。输入输出/模块可以作为组件配置在设备中(图中未示出)，也可以外接于设备以提供相应功能。其中输入设备可以包括键盘、鼠标、触摸屏、麦克风、各类传感器等，输出设备可以包括显示器、扬声器、振动器、指示灯等。

通信接口1040用于连接通信模块(图中未示出)，以实现本设备与其他设备的通信交互。其中通信模块可以通过有线方式(例如USB、网线等)实现通信，也可以通过无线方式(例如移动网络、WIFI、蓝牙等)实现通信。

总线1050包括一通路，在设备的各个组件(例如处理器1010、存储器1020、输入/输出接口1030和通信接口1040)之间传输信息。

需要说明的是，尽管上述设备仅示出了处理器1010、存储器1020、输入/输出接口1030、通信接口1040以及总线1050，但是在具体实施过程中，该设备还可以包括实现正常运行所必需的其他组件。此外，本领域的技术人员可以理解的是，上述设备中也可以仅包含实现本说明书实施例方案所必需的组件，而不必包含图中所示的全部组件。

上述实施例的电子设备用于实现前述任一实施例中相应的基于非支配不等式的不相关并行机调度方法，并且具有相应的方法实施例的有益效果，在此不再赘述。

所属领域的普通技术人员应当理解：以上任何实施例的讨论仅为示例性的，并非旨在暗示本公开的范围(包括权利要求)被限于这些例子；在本公开的思路下，以上实施例或者不同实施例中的技术特征之间也可以进行组合，步骤可以以任意顺序实现，并存在如上所述的本公开实施例的不同方面的许多其它变化，为了简明它们没有在细节中提供。

另外，为简化说明和讨论，并且为了不会使本公开实施例难以理解，在所提供的附图中可以示出或可以不示出与集成电路(IC)芯片和其它部件的公知的电源/接地连接。此外，可以以框图的形式示出装置，以便避免使本公开实施例难以理解，并且这也考虑了以下事实，即关于这些框图装置的实施方式的细节是高度取决于将要实施本公开实施例的平台的(即，这些细节应当完全处于本领域技术人员的理解范围内)。在阐述了具体细节(例如，电路)以描述本公开的示例性实施例的情况下，对本领域技术人员来说显而易见的是，可以在没有这些具体细节的情况下或者这些具体细节有变化的情况下实施本公开实施例。因此，这些描述应被认为是说明性的而不是限制性的。

尽管已经结合了本公开的具体实施例对本公开进行了描述，但是根据前面的描述，这些实施例的很多替换、修改和变型对本领域普通技术人员来说将是显而易见的。

本公开实施例旨在涵盖落入所附权利要求的宽泛范围之内的所有这样的替换、修改和变型。因此，凡在本公开实施例的精神和原则之内，所做的任何省略、修改、等同替换、改进等，均应包含在本公开的保护范围之内。