在徐庶指导下刘备击败曹仁的青龙阵大军
但随后徐庶因家事回乡，就向刘备建议招募 诸葛亮为军师。
三兄弟前后三次拜访诸葛亮 诸葛亮为三兄弟的诚意所感动，答应出山相助
其后刘备相信诸葛亮更能发挥神算法板的威力 就将宝物交予他。
曹操依然对荆州虎视眈眈 以计划举兵攻打刘备。
因此，诸葛亮建议刘备加强 城防。
加强城防有三个要务：修砌城墙 生产兵器以及选拔精兵
若要修砌城墙，则需先造砖以及招募工匠 而两者都需要军费支持。
生产兵器亦要添置材料和招募工匠 亦需军费支持。
为招募精兵则需先以军费招募
新兵，再进行兵器训练和城防训练，再从中选拔精英
当中的训练需待到兵器生产和城墙修砌完成后方可进行
各项事务前后相扣，计划如何按序完成也绝非易事
为尽早完成，诸葛亮举出神算法板求解
>> 诸葛亮终于加进了这个刘备的大营了
他来到的第一件事情就是要建议他们要加强这个城防
要达到这个目标呢，首先要把这个城墙加固
然后也需要招募多一些的 士兵，给他们进行训练，而且呢选拔一个精英部队
要做到两个事情呢，我们有三项的任务
第一项就是要把这个城墙加固，然后也需要制造
多一点的兵器，而且呢要对这个士兵进行
这个加强的训练，而且呢要选拔一个精英的部队
好啦，我们先讲 第一项，看看这要求是什么。
我们要 加固这个城墙呢，首先我们要招募 好的工匠，然后我们也需要这个
制造砖头，然后这个工匠才可以 把这个城墙呢，加固了。
在每一个任务里面我们 可以看见一些数字，它们就是代表每一个任务呢，它们需要的时间
但是事情也没有那么简单 没有钱的话，根本就什么都不可以做。
所以呢我们在招募这个 工匠跟这个制造这个砖头之前呢，肯定要筹钱
好啦，我们看看这个第二项 就是生产更多的兵器。
我们首先呢需要 去买一些原材料，去制造这个兵器
包括这个铁跟木头。
而且呢，也需要招募不同的工匠 然后这个工匠呢才可以制造这个兵器出来的
跟之前一样呢，之前其实我们还是需要钱的
第三项就是我们需要训练我们的精英部队
第一，我们首先要招募士兵，然后呢
需要对这个士兵呢，进行这个兵器的训练
同时我们也可以对这个士兵呢进行这个防守的训练
然后我们就可以呢，去选拔这个精英部队出来了 那这个问题呢，更复杂。
因为呢，我们要招募士兵之前 我们需要钱。
我们要对这个士兵训练兵器的使用的话
之前我们先要把这个兵器做出来
我们要训练他们的防守，先要把这个城墙呢加固
所以呢，我们把刚才所有的任务
合成呢，就变成一个不简单的一个调度的任务了
而且呢，我们是希望把完成所有任务的时间尽量呢就是最小化的
这个就是我们刚才看见这个 基本的调度问题的一个图的版本。
在这个图上面呢，每一个 方格呢就是代表一个任务。
而且呢这个方格 它们的长度呢是表示这个任务需要的时间
而且我们也看见一些带箭头的一些线，这些线呢就是代表
不同任务之间，它们的优先的次序
好啦，我们面对就是一个基本的 调度的问题。
这个问题呢其实是一个非常重要的一个 离散优化问题的一种
在一个基本的调度问题里面呢，首先我们有一个持续 时间的任务。
而且呢任务之间它们有优先的次序 就是说，有某一些任务呢它需要是在另外一个任务
完全这个完成之后它们才可以开始的。
而且我们的目标 通常呢，就是希望把最后一个任务的完成的时间最小化
这个就是一个基本调度问题了 我们先讲一讲我们怎么替这个时间建模
在离散优化当中呢，我们是不用一个 连续的变量来为这个时间建模的
我们呢，是用这个整数来对这个时间建模了 可能你可以说，如果你们有一个
七天的调度问题，而且呢我们是要看看每一分钟的 时间的，那这个时间的范围就变得非常的大了
但是呢，在这个这一类的调度问题里面呢我们 不需要关心所有的时间点的，我们通常呢关心的就是
任务最早开始的时间，或者是任务最后可以 完成的时间。
所以呢这个时间的范围不是一个大的问题 好啦，我们看看我们这个基本
调度问题的数据，还有我们的变量
首先我们有一个枚举类型的数据，就是代表我们 不同的任务。
然后呢一个数组呢就代表我们每一个任务呢 它的所需要的时间。
而且还有一个参数呢 就是代表我们在这个问题里面，我们有多少数量的 优先的次序。
然后呢，利用这个参数呢 我们就可以定义一个数组。
这个数组呢，是个二维的数组 这个二维的数组里面呢，每一行呢，都有两个任务。
就代表了第一个任务 是比第二个任务要优先的。
它的意思就是说第二个 任务开始的时候，一定要第一个任务已经完全的这个完成才可以
然后我们也定义另外一个参数叫 t。
这个 t 这个参数呢就是 所有这个任务它所需要的时间的总和。
我们就利用这个 t 呢 就作为我们的变量的范围了。
我们的变量就是每一个 任务它的开始的时间。
这个 t 呢 就是我们所有任务可以开始的时间的一个 上限。
好啦，我们也可以看看我们
这个要加强这个城防这个问题，我们的数据文件 这个就是我们的任务
包括我们去怎么去 筹钱啊、
招募这个士兵啊 还有其它。
而且呢，对每一个任务呢我们也 有另外一个数组呢，来代表每一个任务它们所需要的时间
在我们的问题里面总共有 14 个 优先的次序。
我们就在利用下面这个 二维的数组呢来表达。
譬如说我们这里说 我们要招募了士兵才可以
给这个士兵训练他们怎么好好的利用这个兵器
譬如说我们要有钱之后我们才可以生产一些砖头
这里就说我们要把这个兵器做了出来才可以 训练士兵对兵器的使用。
其它的，大家都可以慢慢去看 我们在这个问题里面只有一类的
约束，就是呢，有某一些的任务呢它们是有优先的 次序的。
我们就在我们刚才 这个二维的数组里面把所有有
优先次序的任务都拿出来，我们记得第一个任务是要比第二个任务要
优先的，那我们就要求第一个任务它的开始的时间
加上这个任务需要的时间，这个加起来呢其实就是这个 任务完成的时间。
我要这个是小于等于 我们第二个任务开始的时间。
这个就是我们需要的条件了 我们的目标就是把最后完成这个任务它的
完成的时间要最小化。
那最后这个任务完成的时间就是
每一个任务加上它的所需要的时间，然后我们找最大的值出来，然后我们要把这个 最小化。
如果我们利用 这个跟踪这个功能呢，我们就可以发现
我们刚才这个问题 MiniZinc
呢，是会把 这一系列的约束生成出来的
好了，这个就是我们基本的调度问题的一个解。
我们可以看见 在这个上面，我们有不同的任务，而且呢
这个方格呢它的长度是代表这个任务呢 它的需要的时间。
它们不同的安排呢就是代表这个任务在什么的时间
去开始的，譬如说，我们要筹钱呢，我们就一开始就要做了，然后我们就可以去
招募士兵，去买制造兵器的材料，我们也可以
招募这个工匠，我们也可以制造这个砖头，如此类推
我们最后一个任务呢可以在第 75
天开始，然后呢，我们最后把所有任务 完成呢我们只需要 85 天。
在这里呢，其实就每一个任务它们的开始的时间
你们有可能说，啊，你这个问题
里面的约束都非常简单，它们都是线性的，有可能你们也知道它们其实它的
它们的形式呢是根据这个我们叫差分逻辑约束这个形式出现的
我们要注意呢就是，就算是一个等式的话，我们也可以
把它们转化为等价的利用这个小于等于这个形式出现的
如果我们有一个问题，里面所有的约束都是
差分逻辑约束来的话，其实呢我们就可以用一个非常简单的算法
就是基于最长或者是最短路径这个算法 就可以很有效率地去把这个问题呢求解了
但是我们曾经也讲过，在现实里面我们往往呢
就不但有这一些基本的约束，我们还有很多 额外的约束在我们的问题里面。
通常这一类的额外的约束呢 就把我们问题的结构破坏了，就再不可以利用
一些很有效率、 已经开发了的算法来解决我们这个问题 好了，我们来一个小结
这个我们看见的这个基本调度的问题呢是很多复杂的离散
优化问题的一个共有的部分。
在一个基本调度问题里面，主要的 约束呢就是有一系列的任务呢，它们是有优先的次序的
我们也明白呢这个问题非常简单，所以它的
约束呢都是线性的，而且呢它们也可以利用一些
现有的非常有效率的算法呢来把 这类的问题去求解。
但是刚才呢，我已经讲过了 往往我们在现实的问题里面，我们的问题不但是有
基本的约束的，还有其它很多额外的约束
那我们的原来的已经开发的算法呢，就不在可以应用了
[空白_录音]
Prof. Jimmy Ho Man LeeProfessor
Prof. Peter James StuckeyProfessor
