若由三兄弟单独 监督事务,加固城防计划需时将因此延长
为缩短时长,诸葛亮建议分配更多人 监督各项事务。
因此他们为质量检控 士兵训练和军事建设重新分配监督人员
诸葛亮再次取出神算法板 求助。
>> 我们的英雄 终于明白,凭他们个人的力量是会把这个整个项目
完成的时间拖得太长了,而且呢他们也发现
对于一些子任务,譬如说,对于这个品质的保证 其实呢如果他们要检查这个
生产兵器的原材料,一个人是不够的,他们需要是三个 人。
要制造这个砖头的话他们需要 一个人去检查。
如果要看看做出来的兵器它们的 品质是好不好呢,他们需要两个人。
要看看这个城墙 加固之后够不够好呢,他们也需要两个人。
所以呢他们找了四个人来 负责这个品质的保证。
相同的 对于一些跟这个战斗有关联的一些子任务,他们也找了四个人来
去负责这个不同的子任务 跟这个军事的任务也是这样子,他们找来四个人了
我们可以看见,我们面对的问题已经不是在针对这个单元资源了
我们的资源是有多过一个,但是它们还是有限度的
这个新的问题我们叫它资源受限项目调度问题 英语我们叫
RCPSP 在这个问题里面呢,我们有一系列的任务
还有呢某些任务它们之间是有优先的次序的 我们还有一系列的资源
对每一个任务它进行的时候需要用
某一个资源的多少呢,我们放在一个二维的数组 res
里面 我们还有一个数组呢来代表每一个资源它使用的限度
我们呢就是在有限的资源之下,不超过我们资源的
容量之下,找出可以完成所有任务的最快的时间
这个可能是被研究最多的一个调度的问题 这个呢就是我们城防问题
一个加强的版本,它是一个 RCPSP 来的
在这个图里面,我们不单是把所有的任务列了出来,而且在里面 我们也表示它需要的时间。
任务跟任务之间,譬如说,这个要比这个任务要
提前完成呢,这个优先的次序也在这个图 里面表示了出来。
而且呢我们也表示了每一 有一些任务,它需要某一个资源,而且呢它需要这个
资源的一个容量。
我们也把 不同的资源它的限度也表示出来
好了,我们看看我们怎么把 我们之前调度的这个模型可以把它转化为
我们这个加强版本的一个模型。
我们先看看数据。
这个上 面的部分呢,我们之前已经看过了,就是不同的任务,
每个任务需要的时间 有多少个不同的优先的次序
还有呢就是我们不同任务它开始的时间 这个变量。
但是呢,我们现在要加 新的参数
第一个呢就是一个枚举类型的数据,来代表不同的
资源,然后呢不同的资源呢我们利用一个数组来代表 它们的限度。
然后我们还有一个呢就是一个二维的数组,来代表呢 每一个资源对于
每一个任务它的需求是多少 然后呢
我们的数据文件,这个也是我们之前看见过了。
我们不同的任务它们的 需要时间,而且呢我们也把它们的优先的次序也列了出来
要增加呢,就是后面这个。
我们有三种不同的资源 分别就是品质的控制、 对军事的、
对战斗的 然后每一个资源呢,它们的上限都是
4 然后我们也需要一个二维的数组,对每一行就是
每一个资源,每一个任务对它的资源的需求 好了
我们刚才看见不再是单元资源了,因为它们是非常 特别的。
因为一种资源呢往往是有多个相同的副本的 当我们讲机器的时候,我们有多于一部相同的机器
我们讲推土机的时候,我们有多于一个相同的推土机 对工人、 手术台、 飞机也是一样
但是我们怎么样可以为 相同的资源可以建模呢?我们需为每一个
新的资源呢,我们需要一个新的数组来代表这个 不同的任务对这个资源它的需求
而且呢我们还需要另外一个数组呢来代表这个资源它的一个限度
好了,其实我们看这个资源的 问题呢,我们可以利用图来帮助我们的理解的
我们在上面的方格呢,每一个就是代表一个任务
它们呢它长度就是这个任务需要的时间,但是它们的高度呢
就是它们对某一个资源它们的需求
好了,这个呢我们看见第一个任务,我们在 0
这个 时间开始,第二个任务它在 1 这个时间开始,而
3 这个任务呢 就在 4 这个时间开始。
我们刚才提到这个资源 的需求的图像化,其实是希望帮助大家去理解
我们怎么可以为这个资源建模 好了,我们有不同的任务,我们
不同任务呢它有可能对我们的资源呢有不同的需求
我们要保证的是什么呢?就是在不同的时间点 i
,在这个时间点 i 呢,我们看看不同的任务 t
这个红色的部分就代表呢,这个任务 t 是 在这个时间 i
的时候在进行的一个任务 那我们就要把这个任务在这个时间
i 对这个资源的需求 所有的任务的需求都把它加起来
我们要求这个总和呢是小于等于我们这个资源的上限 好了,
这个红色的部分为什么是代表这个任务是在 时间 i
在进行当中呢?因为我们要求这个 任务是在 i
之前已经开始了,然后 这个任务它的完成的时间是在
i 这个时间的后面,所以呢 如果这个条件是满足的话,这个任务
t 就是在时间 i 这时候 在进行当中。
好了,下面我就可以把我们刚才这个很复杂的表达
式利用一个图来介绍给大家 去看看。
在这个例子里面,我们有不同的任务
不同的任务呢,除了它们有不同的,它们的长度是代表它们不同的需要的时间
但是它们也有一个高度的,它们的高度就是 代表这个任务对我们这个资源的需求
好了,我们上面这个约束呢就是代表在 0
这个时间 我们所有任务在 0 这个时间对这个资源
的需求不可以超过我这个资源的上限 在第
1 这个时间也是,第 2 这个时间也是,第 3
到了 第 7 这个时间呢,我们所有 任务对这个资源的需求也不可以大于
它的上限 我们刚才看见呢就是怎么利用
时间分解这个方法呢为这个资源建模 这个方法呢有它的问题的,就是它的规模太大
因为它的规模就是任务的数目乘以这个时间点的数目
而且我们知道了在这个时间当中呢,有包含大量的时间段在里面的
我们其实还有另外一个方法呢 为这个资源建模,就是基于任务的分解
我们怎么利用任务的分解呢?这个是基于 我们知道资源会有超量的
情况呢,只会发生在某一个任务开始的时候 如果所有任务都在进行当中,没有新的任务
开始的话,根本就不会有这个资源的需求 超量的情况的出现的。
所以呢我们就可以 利用下面这个表达式呢,来表示这个条件了
我们呢是看看不同的任务 t2
然后再看看其他的任务 t 看看这个任务
t 呢,是否在 t2 开始的时候已经在进行当中
我们要明白这个 t 呢,也可以是 t2 本身的
然后如果是的话,我们就把这个任务 t
它对这个资源的需求 加起来,然后要求这个总和呢,是小于等于这个限度的
我们再看看我们刚才这个例子,我们这个例子里面呢有四个任务
不同的任务呢,对这个资源的需求都也不一样的 我们首先看看当时间是
0 的时候 我们看见呢,只有这个任务 第四个任务呢,是刚开始,而且呢它对这个
资源的需求呢,是比它的限度是为低的,所以这个没问题
然后我们去到时间点的第一点 在这里呢,刚好就是第二个任务呢,刚开始
而且呢,第四个任务呢,还是在进行 而且呢它们的对这个资源的需求加起来,还是
比这个限度呢为低,所以也没有问题 我们再看下一个时间点呢
不是第二个时间点,而是呢,我们要一跳就可以跳到这个第三个时间点了
因为在第二个时间点的时候,没有新的任务在开始
反而在第三个时间点呢,我们发觉,第三个任务跟第一个任务呢刚开始
然后我们也看看,它们对这个资源的总需求,发觉呢
还是比这个限度为低,所以呢,这个条件也是满足了
然后经过这个第三个时间点之后,我们 第四个时间点,到这个第四个时间点,我们也不需要
再去检查这个条件是否满足,因为 我们知道,再没有新的任务要开始了,所以呢
再不应该再有这个资源需求超量的情况可以出现
所以呢,我们就知道,在这个情况之下,我们这个资源是没有
它的需求没有给超量要求的 其实呢,我们刚才看见这个
约束的表达式呢,是可以有可以改良的地方的 就是呢,我们看一个
t2 这个任务 然后希望检查其他的任务是
在 t2 开始的时候,是在进行的任务 t 但是因为
t2 已经刚开始,所以呢它一定在进行当中的,所以这个 t 呢 一定不需要是等于 t2 的。
然后当然呢,我在这个 总和的计算当中,没有加入了
t2 的对这个资源的需求,我们要在后面
再把它的需求呢,加上来,然后要求这个资源的 需求的总和呢,是小于等于这个资源的限度
我们利用这个任务分解的方法来为这个资源建模呢
是比这个基于时间的分解呢,是有一个
优点的,它的优点呢就是因为它的规模呢,只是任务的
数目,它的平方,这个数字呢,其实是比基于时间的分解的 规模呢,是少很多的。
但是呢,这个方法呢也有它的缺点 就是呢,因为我们要检测的时间点呢,比较
少,所以呢就没有太多的信息可以传送到我们的求解器
所以呢我们的求解器把这个方法的建模出来的 结果来求解的时候呢,它的效率就比较低了
好了 你们也可能已经猜到,就是
通常我们最好的方法就是基于全局约束的 我们这个情况也不是例外。
其实在 MiniZinc 里面呢,我们还有一个叫
Cumulative 的全局约束,就是真正为了
帮助我们去解决这一类的资源约束问题 这个 Cumulative
这个全局约束呢,有四个不同的参数 其实第一、 第二、
第三个参数呢,是用来表达 一系列的任务,它们的开始的时间
每一个任务的持续时间 而且呢,这个任务对这个资源的需求
把它们通通呢,都利用一个数组来输入 然后最后一个参数呢,就是我们这个资源的限度
Cumulative 这个全局约束呢,就可以保证呢,我们刚才输入的一系列的
任务呢,它们的时间点跟它们资源
的需求呢,的用量,都不会超过已给的一个限度 这个呢,就是这个
Cumulative 这个全局约束它的语法
好了,我们来看看我们明不明白到底这个 Cumulative
这个全局约束,它的意义是什么来呢? 我们先看看一些例子。
我们这个例子里面呢,就有三个不同的 任务,第一个任务呢,它的开始时间是
0 而且呢,它的持续时间是 3,就是它的这个盒子的长度了
然后呢,它对这个资源的需求呢,是 1,就是它的高度了
然后第二个任务呢,是在第 1 个时间点开始
然后它的起始时间是 4,对这个资源的需求呢是
2 第三个任务呢,它是在这个第四个时间点开始
它的起始时间是 2,对这个资源的需求呢,也是
2 然后呢,我们所有的资源,它的限度就是为
3 到底这个,这几个参数
是否满足了我们 Cumulative 这个全局约束呢?
我们利用一个可视化的图,来帮助我们理解 Cumulative
它的意义是什么 虽然我们是利用不同的盒子来代表不同的任务
而且它的开始的时间啊,它的起始的时间,而且 还有它们的对这个资源的需求的时间
但是呢,它们并不是真的是盒子来的 其实呢,如果我们需要理解刚才这个问题
它对不同,这个这个资源的需求呢,我们要看 就是这一条红色的线,这个红色的线呢
就是代表我们这三个资源在不同的时间点 对这个资源的需求的总和是多少 我们来看看在
0 这个时间里面,我们只有第一个任务对这个资源有需求
这个是低于 3 这个限度的 到了第一个时间点的时候,第二个任务已经开始
它跟第一个任务加起来对这个资源的需求还是在这个 3
以内 好了,然后我们再过,过去呢,发觉,到了
第三个时间点的时候,我这个任务 1 已经完成,所以呢只有任务 2
才对这个资源有需求,但是它的需求呢,当然还是 小于我们这个资源的上限的
但是到了第四个时间点的时候,我们有一个新的任务 开始,就是第三个任务。
然后它对这个资源的需求是 2 但是我们还有一个在进行的任务就是第二个任务,它的需求也是
2,所以总需求呢就是 4 这个是比我们有的限度 3
呢,是为高的 所以我们就理解了我们这个全局约束呢,是不被满足的
我们再多来看两个例子 它们都很相似。
第一个例子呢,我们总共有 4 个任务也有它们的开始的时间,不同的持续时间的
还有对这个资源不同的需求,而我们这个资源的限度为 4
第二个例子呢,就是跟之前 一样也是 4 个任务,它们的
不同的任务的持续时间跟它们的对资源的 要求,而且我们资源的限度也是一样
不同的地方呢就是它们开始的时间不是固定的 是一个范围,是有弹性的。
好了,我们先来看第一个例子
我们利用刚才可视化的方法呢也可以明白知道 在第
0 到了第 2 个时间点也没有问题,对这个资源的要求也是在它的限度
4 以下,但是到了第 3 个时间点的时候,我们发觉,因为有一个
新的任务 3 ,另外一个新的任务 1
,它们刚开始 它们对这个资源的需求,再加上原来
已经在进行的任务 2 的需求加起来已经超过了
我们有的限度,所以呢这个约束呢不被满足的 好了,我们再看看
如果我们允许我们的不同的任务它开始的时间有一些弹性又怎么样呢?
我们其实发觉,原来把刚才这个第 2 个任务,如果把
它的开始的时间提前到第 0 个时间点呢,我们就可以
从 0 到第 7 个时间点这段时间里面,我们 4
个任务 对于这个资源的要求呢都可以在它的限度
4 底下,所以呢,我们这个约束呢是可以满足的
好了,我们再回到我们的城防加强这个模型
先看看这个变量,我们这有一个变量的 数组,这是代表呢每一个任务它开始的时间
约束方面就是某些任务呢,它们是有优先次序的
所以呢,我们表达的约束跟之前也是没有改变
但是我们有一个新的约束,就是我们要求呢,每一个资源 r
我们就要给它一个 cumulative 的全局约束,我们也把不同任务的它的开始时间
持续时间,而且呢这个 不同的任务它对这个资源
r 它的需求 我们要求呢它们的总和呢在每一个时间点
也是低于这个资源的限度的 最后就是我们的目标,我们的目标呢就是希望在整个项目
的最后完成的时间要最小化
这个就是开始时间加上这个项目的 持续时间,就是每一个项目的,每一个任务的它的
结束的时间,然后我们把最后结束 的一个任务,要把这个值要最小化
我们把这个模型求解,这个就是一个解了
在这个图里面呢,不同的方块呢就是代表不同的任务
而且呢我们也利用这个颜色来表示 不同的任务它对不同的资源的需求
这个那我们可以看看 这个任务呢,它其实是对两个资源呢都有需求的
好了,我们也在不同的时间点就是 有任务开始的时间点,也把对不同资源
的总需求也列出来,我们也可以看到呢
在这些我们看见的时间点里面呢,我们
对于这个资源的需求呢,也没有超过它们最大的值 它们的最大的值呢都是 4。
在这个新的调度的结果 之后呢,我们发觉,我们可以把整个城防加强的 任务呢,利用 90
天就可以把它完成了 所以我们三位英雄呢,现在就比较放心了
好了,我们来一个小结 这个
cumulative 的全局约束呢,是一个非常重要的全局约束 它在
1990 年代初的时候已经给提出来了
所以在之后呢,已经有很多人为它的传播进行了很多的研究 最基本呢,就有一个基于
timetable propagation 这个方案 这个方案呢,是等价于我们的时间分解的
但是却出来的效率呢,是比基于任务的分解呢是更快的 再好一点呢,是基于
edge finding 这个技术呢来为这个 cumulative
的约束呢进行这个传播 它也是基于这个时间分解的,但是呢,但是
并非是基于单一的时间来进行这个推理 然后也有对这个
edge finding 呢有一个 泛化,就是这个
energy based reasoning 这个是比 edge finding
呢,做更多的推理 但是它有一个问题呢,它的速度比较慢一点
我们最新的水平呢,就是基于这个 TTEF,就是 time table edge
finding 它是一个把这个 timetable 跟这个 energy based reasoning
结合的一个方法 就是现在最高效率的一个方法来了
我们在这一节里面可以看见就是对于一个
可续用的限量资源的一个建模 我们要保证呢,对这一类的资源的
需求呢在每一个时间点都不可以超过 它所有的限度。
我们看过不同的方法为它们建模,包括一个基于时间的分解
也有另外一个基于任务的分解 当然呢,还有一个是基于
cumulative 这个全局约束的分解 其实呢,我们看这个
RCPSP 这个问题呢,是一个非常核心的调度问题
很多现代的调度问题呢,都是这个 RCPSP 的一个变种
[空白_录音]