一种面向资源中断问题的调度方案修复方法及存储介质与流程

1.本发明涉及调度方案优化技术领域，尤其是涉及一种面向资源中断问题的调度方案修复方法及存储介质。


背景技术：

2.rip从经典的项目调度问题中衍生而来，问题的目标是在给定工期的情况下求解资源投入的最小值。考虑动态资源中断的资源投入问题(rip)的描述如下：项目由若干项作业构成，作业间存在一定的时序关系，在满足时序关系的条件下，作业即可开始执行，在执行过程中作业可以中断，释放其占用的资源，待到后续某个时刻继续执行。给定项目工期为t，项目中包含n项作业，全部作业需要使用k种不同的可更新资源，这些资源可以重复使用，资源集合r＝{1，2，
…
，k}，k∈r为资源编号，作业集合为j＝{1，2，
…
，n}，其中，1、n为虚作业，不占用时间和资源，j∈j为作业编号，将其执行的开始时间记为stj，结束时间记为ftj，工期为durj，且ftj＝stj+durj，执行时对第k种资源的用量为r
jk
，作业j的前序作业集合为pre(j)，作业j的后序作业集合为suc(j)，t时刻所有正在进行的作业对于第k种资源的使用量为r
tk
，t时刻第k种资源的上限为ur
tk
，资源k的单价为ck，项目完成时间超过给定项目工期的单位惩罚成本为c
″
。
3.rip问题求解涉及三项约束和目标，时序约束为不同的作业需要按照一定的顺序进行，即执行pre(j)后再执行作业j，执行作业j后再执行suc(j)；工期约束为项目需要在规定时间内完成，即最后执行的作业n的结束时间ftn需要早于工期t；资源约束即资源有限，同一时间进行的所有作业所使用的资源之和不能超过上限；目标函数为总成本z最小，一部分是传统的可更新资源成本最小化，一部分是工期的惩罚成本，是为了使该问题始终有可行解而添加的，还有一部分是重调度成本。
4.在作业进行的过程中，会遇到由于资源中断或不足导致作业中断的情况，这时需要重新安排调度计划，不受该中断资源限制并满足工序要求的作业正常进行，将受中断资源影响的作业中断并待到后续某个时刻继续执行，且根据时序要求，将被中断的作业的后序作业集合中的作业同样中断并向后推迟，重新执行的作业的开始时间由stj调整为st
′j，结束时间由ftj调整为ft
′j。为使发生中断后所有作业的重调度模式与原始调度模式相近，避免过大变动，在目标函数中加入重调度成本，规定重调度成本为作业开始时间的变动成本，作业开始时间发生变动时的单位成本为c
′
。最终，目标函数如下：
[0005][0006]
由于资源中断或不足会使原先的调度方案变为不可行解，因此，需要修复不可行解，得到新的调度方案。对于资源中断的问题，最简单的方法为平移算法。平移算法的主要思想是将所有受到影响的作业(在资源中断时间区间内执行的作业以及这些作业的所有后序作业)向后平移资源中断的时间长度。其算法效率较高，规则也非常简单易懂，但对于总工期较紧，延迟时间惩罚系数较高的项目来说，这种算法所产生的解成本往往过高，在实际
操作中不太可行。


技术实现要素：

[0007]
本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种面向资源中断问题的调度方案修复方法及存储介质。
[0008]
本发明的目的可以通过以下技术方案来实现：
[0009]
一种面向资源中断问题的调度方案修复方法，包括以下步骤：
[0010]
s1、获取资源k的资源中断区间[t
ks
，t
kf
]，获取调度方案，所述调度方案包括各个作业的开始时间和结束时间，根据调度方案得到集合a，a中的元素为执行时需要资源k且执行时间段与[t
ks
，t
kf
]交集不为空的作业，将集合a中开始时间早于t
ks
的作业的开始时间更新为t
ks
；
[0011]
s2、根据集合a中各个作业的开始时间和结束时间，计算资源中断区间内各个时刻对资源k的使用量，若存在使用量超过该时刻预设资源上限的时刻，则执行步骤s3，否则，以当前的调度方案作为修复后的调度方案；
[0012]
s3、定位到使用量超过预设资源上限的时刻t，t∈[t
ks
，t
kf
]，获取作业集合a
t
，a
t
中的元素为执行时需要资源k且时刻t时执行的作业，将作业集合a
t
中的作业按照预设规则排序，获取排序首位的作业，更新该作业及其后序作业的开始时间和结束时间，执行步骤s2。
[0013]
进一步的，步骤s1中，若作业j对资源k的使用量r
jk
＞0，且stj≤t
ks
＜ftj或t
ks
≤stj＜t
kf
，则作业j∈a，其中，stj和ftj表示作业j的开始时间和结束时间。
[0014]
进一步的，对于集合a中的作业j，若作业j的开始时间stj＜t
ks
，则将作业j的开始时间stj更新为st
′j＝t
ks
。
[0015]
进一步的，步骤s2具体为：
[0016]
按照时间顺序，根据调度方案确定资源中断区间内各个时刻的作业集合，时刻t的作业集合a
t
中的元素为时刻t执行的作业，即对于j∈a
t
，stj≤t＜ftj，stj和ftj表示作业j的开始时间和结束时间；
[0017]
根据作业集合计算得到各个时刻对第k种资源的使用量，其中，时刻t对资源k的使用量r
jk
表示作业j对资源k的使用量；获取资源中断区间内资源k在各个时刻的预设上限；
[0018]
遍历各个时刻，若对于均有r
tk
≤u
tk
，则以当前的调度方案作为修复后的调度方案，否则，执行步骤s3，其中，u
tk
为资源k在时刻t的预设上限。
[0019]
进一步的，步骤s3具体为：
[0020]
定位至第一个不满足r
tk
≤u
tk
的时刻t，获取时刻t的作业集合a
t
；
[0021]
将作业集合a
t
中的作业按照预设规则排序，获取排在首位的作业j，其开始时间为stj，将作业j的开始时间和结束时间向后平移固定长度，获取作业j的后序作业集合suc(j)，将suc(j)中各个作业的开始时间和结束时间向后平移固定长度。
[0022]
进一步的，固定长度的大小为(t
kf-stj)。
[0023]
进一步的，按照预设规则排序为：按照对第k种资源的需求量由大到小对集合a中
的作业进行排序。
[0024]
进一步的，每个作业预设置有执行优先级，按照预设规则排序为：按照执行优先级由低到高对集合a中的作业进行排序，执行优先级相同的作业按照对第k种资源的需求量由大到小排序。
[0025]
进一步的，步骤s2中，若集合a为空，则以当前的调度方案作为修复后的调度方案。
[0026]
一种计算机存储介质，其上存储有可执行的计算机程序，所述计算机程序被执行时实现上述的一种面向资源中断问题的调度方案修复方法。
[0027]
与现有技术相比，本发明具有以下有益效果：
[0028]
(1)计算资源中断区间内各个时刻的资源使用量，对比各个时刻中断资源的预设上限，在资源使用量超过预设上限后选择作业后移，本发明尽可能减少参与重调度的作业数量，从而降低了作业开始时间变动成本。
[0029]
(2)预设规则为根据资源使用量对作业进行排序，优先调度对中断资源使用量大的作业，完成在资源中断限制下的重调度，保证参与重调度的作业数量最少。
[0030]
(3)预设规则为根据预设优先级和资源使用量对作业进行排序，优先调度优先级低且对中断资源使用量大的作业，尽可能保证优先级高的作业的执行不受资源中断影响。
附图说明
[0031]
图1为调度方案修复方法的流程图；
[0032]
图2为资源中断区间和作业的示意图；
[0033]
图3为资源中断区间和作业开始时间更新的示意图。
具体实施方式
[0034]
下面结合附图和具体实施例对本发明进行详细说明。本实施例以本发明技术方案为前提进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。
[0035]
在附图中，结构相同的部件以相同数字标号表示，各处结构或功能相似的组件以相似数字标号表示。附图所示的每一组件的尺寸和厚度是任意示出的，本发明并没有限定每个组件的尺寸和厚度。为了使图示更清晰，附图中有些地方适当夸大了部件。
[0036]
实施例1：
[0037]
发明人在实践中发现，实际生产中资源中断的上限不为0时，平移算法会带来一部分不必要的变动成本，一部分作业虽然执行过程中需要使用中断资源，但是由于使用量足够小，因此资源中断时也可以正常执行，不需要进行调度，因此，提出了一种面向资源中断问题的调度方案修复方法，用于在资源中断且中断资源上限不为0时进行重新调度，如图1所示，包括以下步骤：
[0038]
s1、获取资源k的资源中断区间[t
ks
，t
kf
]，获取调度方案，调度方案包括各个作业的开始时间和结束时间，根据调度方案得到集合a，a中的元素为执行时需要资源k且执行时间段与[t
ks
，t
kf
]交集不为空的作业，将集合a中开始时间早于t
ks
的作业的开始时间更新为t
ks
；
[0039]
以作业j为例，在调度方案中，作业j的开始时间为stj，结束时间为ftj，工期为
durj，且ftj＝stj+durj，执行时对第k种资源的用量为r
jk
，若作业j对资源k的使用量r
jk
＞0，且stj≤t
ks
＜ftj或t
ks
≤stj＜t
kf
，则作业j∈a，即作业j是直接受资源k中断影响的作业。
[0040]
如图2所示，在资源k的资源中断区间中，有4种执行时需要资源k且执行时间段与[t
ks
，t
kf
]交集不为空的作业，按照调度方案，作业1是在资源中断前开始执行且结束时间早于中断结束，作业2是在资源中断后执行且结束时间早于中断结束，作业3是在资源中断后执行且结束时间晚于中断结束。
[0041]
对于集合a中的作业j，若作业j的开始时间stj＜t
ks
，即作业j在资源中断前已经执行，则将作业j的开始时间stj更新为st
′j＝t
ks
。
[0042]
如图3所示，在资源中断前已经执行的作业，作业已经执行了一段时间，因此资源发生中断后只需要考虑对其剩余的部分进行重调度，剩余部分的工期实际为dur
′j＝ft
j-t
ks
，故将其开始时间更新为t
ks
，结束时间仍为调度方案中的ftj。
[0043]
s2、若集合a为空，则以当前的调度方案作为修复后的调度方案，否则，根据集合a中各个作业的开始时间和结束时间，计算资源中断区间内各个时刻对资源k的使用量，若存在使用量超过该时刻预设资源上限的时刻，则执行步骤s3，否则，以当前的调度方案作为修复后的调度方案；
[0044]
步骤s2具体为：
[0045]
(1)按照时间顺序，根据调度方案确定资源中断区间内各个时刻的作业集合，时刻t的作业集合a
t
中的元素为时刻t执行的作业，即对于j∈a
t
，stj≤t＜ftj，stj和ftj表示作业j的开始时间和结束时间；
[0046]
步骤s1中的集合a中的元素是整个资源中断区间内所有受影响的作业，但是，这些作业的执行时间段会有交错，因此，不能直接将集合a作为各个时刻的作业集合。在编程实现时，可以将资源中断区间时间离散化为{0、1、2、
…
、t}，离散后0即t
ks
，t即t
kf
，根据调度方案，自0至t，分别确定每个时刻执行的作业集合a
t
。
[0047]
如图3所示，在阶段
①
内的各个时刻，作业集合为{作业1、作业4}，在阶段
②
内的各个时刻，作业集合为{作业1、作业2、作业4}，在阶段
③
内的各个时刻，作业集合为{作业2、作业4}，在阶段
④
内的各个时刻，作业集合为{作业2、作业3、作业4}，在阶段
⑤
内的各个时刻，作业集合为{作业3、作业4}。在编程实现时，也可以对资源中断区间进行阶段划分：获取所有作业的开始时间和结束时间，再加入t
ks
和t
kf
，去重后一起进行排序，相邻的两个时间节点之间为一个阶段，一个阶段内各个时刻的作业集合相同，因此，计算各个阶段的作业集合即可确定资源中断区间内各个时刻的作业集合。
[0048]
(2)根据作业集合计算各个时刻对第k种资源的使用量，其中，时刻t对资源k的使用量r
jk
表示作业j对资源k的使用量；获取资源中断区间内资源k在各个时刻的预设上限；
[0049]
每个作业对资源k的使用量r
jk
都是预先配置好的，因此可以快速计算得到各个时刻对第k种资源的使用量。资源短缺或中断时，资源中断区间内资源k在各个时刻的预设上限是根据资源k的中断情况得到的，如某次中断时，整个资源中断区间内各个时刻的预设上限都相同，均为一个固定值，如某次中断时，预设上限是波动的，资源中断区间的前半段预设上限为值1，后半段预设上限为值2等。资源短缺或中断时，并不是资源k立即清零，仍有少量资源k，预设上限的具体值就是根据剩余的少量资源k的量确定的。
[0050]
(3)遍历各个时刻，若对于均有r
tk
≤u
tk
，则以当前的调度方案作为修复后的调度方案，否则，执行步骤s3，其中，u
tk
为资源k在时刻t的预设上限。
[0051]
s3、定位到使用量超过预设资源上限的时刻t，t∈[t
ks
，t
kf
]，获取作业集合a
t
，，a
t
中的元素为执行时需要资源k且时刻t时执行的作业，将作业集合a
t
中的作业按照预设规则排序，获取排序首位的作业，更新该作业及其后序作业的开始时间和结束时间，执行步骤s2。
[0052]
步骤s3具体为：
[0053]
(1)定位至第一个不满足r
tk
≤u
tk
的时刻t，获取时刻t的作业集合a
t
；
[0054]
在编程实现时，步骤s2中按照时间顺序依次检查各个时刻是否满足r
tk
≤u
tk
，若检查到一个不满足的时刻，则定位至该时刻，获取该时刻的作业集合即可。
[0055]
(2)将作业集合a
t
中的作业按照预设规则排序，获取排在首位的作业j，其开始时间为stj，将作业j的开始时间和结束时间向后平移固定长度，获取作业j的后序作业集合suc(j)，将suc(j)中各个作业的开始时间和结束时间向后平移固定长度。
[0056]
将排在首位的作业往后移，从而使得该时刻执行的作业数量减少，对资源k的使用量降低，满足r
tk
≤u
tk
。作业j后移后，为了保证作业间的执行时序，作业j的后续作业也需要向后平移相同的时间长度。
[0057]
固定长度为(t
kf-stj)，即将作业j直接移到资源中断区间的结束时刻t
kf
，作业j的开始时间更新为t
kf
，结束时间更新为t
kf
+dur
′j。也可以灵活设置固定长度，如按照图3中的阶段划分，将作业j后移至下一个阶段。
[0058]
按照预设规则排序为：按照对第k种资源的需求量由大到小对集合a中的作业进行排序。这样排序后，可以首先将对资源k使用量较大的作业进行后移重调度，能够使参与重调度的作业数量尽可能少，间接降低了直接变动成本。
[0059]
每个作业预设置有执行优先级，按照预设规则排序为：按照执行优先级由低到高对集合a中的作业进行排序，执行优先级相同的作业按照对第k种资源的需求量由大到小排序。事先设定好作用的优先级，如某个作用的重要性较高，需要优先保证该作业的执行，则该作业的优先级设置为较高优先级，如可以设定非常重要、重要、一般、不重要四个优先级。这样可以根据作业执行的紧急程度，将优先级较低的作业后移重调度，能够使优先级高的作业的执行不受资源中断影响。
[0060]
为了更清楚地验证小规模作业下本技术的有效性，以平移算法作为对照组。为了消除资源中断的不确定性对实验结果带来的影响，即为了尽可能降低实验误差，实验中将不对资源中断进行随机采样，而是使用固定参数，将资源中断的参数设置为常数，资源中断开始时间为30，资源中断持续时间为10，资源结束时间为40，中断资源的种类为1，资源中断区间内各个时刻资源的预设上限相同，均为7。在这些参数的基础上，进行以下实验。
[0061]
目标函数如下：
[0062][0063]
资源k的单价为ck，项目完成时间超过给定项目工期的单位惩罚成本为c
″
，作业开始时间发生变动时的单位成本为c
′
，由于步骤s1中对资源中断前执行的作业的开始时间进
行了更新，因此以重调度方案和原始调度方案中的结束时间计算调度成本，ftj是原先的模板调度计划中作业j的结束时间，ft
′j是重调度后作业j的结束时间。作业集合j中包括n个作业，作业1和作业n是虚作业，不占用时间和资源，ck、c
′
和c
″
都是常数。
[0064]
根据实际情况，超期成本最为昂贵，由于重调度变动而产生的变动成本也远大于资源成本，有ck＜c
′
＜＜c
″
，本实施例中将三者定为10倍递增。
[0065]
在发生资源上限不为0的资源中断后，分别使用平移算法和本发明对调度方案进行修复，得到重调度方案。根据上述目标函数分别计算平移算法和本发明的重调度方案的总成本。对作业规模为30的算例进行了实验，实验结果如表1所示。zp代表平移算法的目标函数值，z1代表本发明的目标函数值，gap代表本发明相对平移算法的改进程度，gap＝(zp-z1)/zp
×
100％。
[0066]
表1作业规模为30的调度结果
[0067]
编号zpz1gap/％120575497.3722659187429.523175857367.41410595395.00510614995.386205896852.96710363596.62810636194.2692469167632.12101848128030.74avg1706.8662.369.14
[0068]
实施例2：
[0069]
一种计算机存储介质，其上存储有可执行的计算机程序，计算机程序被执行时实现实施例1中描述的一种面向资源中断问题的调度方案修复方法。
[0070]
以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术人员无需创造性劳动就可以根据本发明的构思作出诸多修改和变化。因此，凡本技术领域中技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。

技术特征：
1.一种面向资源中断问题的调度方案修复方法，其特征在于，包括以下步骤：s1、获取资源k的资源中断区间[t
ks
，t
kf
]，获取调度方案，所述调度方案包括各个作业的开始时间和结束时间，根据调度方案得到集合a，a中的元素为执行时需要资源k且执行时间段与[t
ks
，t
kf
]交集不为空的作业，将集合a中开始时间早于t
ks
的作业的开始时间更新为t
ks
；s2、根据集合a中各个作业的开始时间和结束时间，计算资源中断区间内各个时刻对资源k的使用量，若存在使用量超过该时刻预设资源上限的时刻，则执行步骤s3，否则，以当前的调度方案作为修复后的调度方案；s3、定位到使用量超过预设资源上限的时刻t，t∈[t
ks
，t
kf
]，获取作业集合a
t
，a
t
中的元素为执行时需要资源k且时刻t时执行的作业，将作业集合a
t
中的作业按照预设规则排序，获取排序首位的作业，更新该作业及其后序作业的开始时间和结束时间，执行步骤s2。2.根据权利要求1所述的一种面向资源中断问题的调度方案修复方法，其特征在于，步骤s1中，若作业j对资源k的使用量r
jk
＞0，且st
j
≤t
ks
＜ft
j
或t
ks
≤st
j
＜t
kf
，则作业j∈a，其中，st
j
和ft
j
表示作业j的开始时间和结束时间。3.根据权利要求2所述的一种面向资源中断问题的调度方案修复方法，其特征在于，对于集合a中的作业j，若作业j的开始时间st
j
＜t
ks
，则将作业j的开始时间st
j
更新为st
′
j
＝t
ks
。4.根据权利要求1所述的一种面向资源中断问题的调度方案修复方法，其特征在于，步骤s2具体为：按照时间顺序，根据调度方案确定资源中断区间内各个时刻的作业集合，时刻t的作业集合a
t
中的元素为时刻t执行的作业，即对于j∈a
t
，st
j
≤t＜ft
j
，st
j
和ft
j
表示作业j的开始时间和结束时间；根据作业集合计算得到各个时刻对第k种资源的使用量，其中，时刻t对资源k的使用量r
jk
表示作业j对资源k的使用量；获取资源中断区间内资源k在各个时刻的预设上限；遍历各个时刻，若对于均有r
tk
≤u
tk
，则以当前的调度方案作为修复后的调度方案，否则，执行步骤s3，其中，u
tk
为资源k在时刻t的预设上限。5.根据权利要求4所述的一种面向资源中断问题的调度方案修复方法，其特征在于，步骤s3具体为：定位至第一个不满足r
tk
≤u
tk
的时刻t，获取时刻t的作业集合a
t
；将作业集合a
t
中的作业按照预设规则排序，获取排在首位的作业j，其开始时间为st
j
，将作业j的开始时间和结束时间向后平移固定长度，获取作业j的后序作业集合suc(j)，将suc(j)中各个作业的开始时间和结束时间向后平移固定长度。6.根据权利要求5所述的一种面向资源中断问题的调度方案修复方法，其特征在于，固定长度的大小为(t
kf-st
j
)。7.根据权利要求1所述的一种面向资源中断问题的调度方案修复方法，其特征在于，按照预设规则排序为：按照对第k种资源的需求量由大到小对集合a中的作业进行排序。8.根据权利要求1所述的一种面向资源中断问题的调度方案修复方法，其特征在于，每
个作业预设置有执行优先级，按照预设规则排序为：按照执行优先级由低到高对集合a中的作业进行排序，执行优先级相同的作业按照对第k种资源的需求量由大到小排序。9.根据权利要求1所述的一种面向资源中断问题的调度方案修复方法，其特征在于，步骤s2中，若集合a为空，则以当前的调度方案作为修复后的调度方案。10.一种计算机存储介质，其特征在于，其上存储有可执行的计算机程序，所述计算机程序被执行时实现如权利要求1-9中任一所述的一种面向资源中断问题的调度方案修复方法。

技术总结
本发明涉及一种面向资源中断问题的调度方案修复方法及存储介质，方法包括：获取资源中断区间[t


技术研发人员：米雪菲
受保护的技术使用者：中银金融科技有限公司
技术研发日：2022.01.29
技术公布日：2022/5/25