调度表和资源

12.1 时间、调度表和资源

STRIPS表示讨论了行动做什么，但是，因为表示是基于情景演算的，所以它不能讨论行动持续多久或者甚至行动何时发生，除了说它在另一个行动之前或之后。对于某些领域，我们也许希望谈论行动何时起止。例如，在货物递送领域，我们可能想知道装载某些货物的飞机何时会到，而不只是说当它完成飞行时将会到达。

在称为加工车间调度的通用应用家族中，时间是必不可少的。这类任务需要完成一组工作，每个工作由一个行动序列组成，其中每个行动有一个给定的持续时间并且可能需要某些资源。问题是要决定一个调度安排，以使在满足资源约束的情况下完成所有工作所需的时间最短。

一个加工车间调度问题的例子如图12.1所示。这是一个高度简化的汽车装配问题。有两项工作：装配汽车C1和C2。每项工作由3个行动组成：安装发动机、安装车轮以及检查结果。发动机必须最先安装（因为装上前轮以后将禁止接触发动机隔箱），当然检查必须在最后来做。

图12.1 装配两辆汽车的加工车间调度问题。符号Duration(d)的含义是执行行动需要d分钟。Engine(E1,C1,60)的意思是E1是一个发动机，适合底盘C1，并需要60分钟来安装

图12.1的问题能够用我们已经见过的任何一种规划器来解决。图12.2（如果你忽略数字的话）显示了偏序规划器POP得到的解。为了让它成为调度问题而不仅仅是规划问题，我们现在必须决定每个行动应该何时开始和结束。这意味着我们必须注意每个行动的持续时间，连同它们的顺序。行动效果中的符号Duration(d)（其中d必须被限制为一个数字）意为行动需要d分钟才能完成。

图12.2 图12.1加工车间调度问题的一个解。在顶端，给出了一个偏序规划形式的解。每个行动的持续时间在每个矩形的底部给出，在左上角用[ES, LS]列出了最早和最晚的开始时间。这两个数字间的差值是行动的松弛：具有零松弛的行动处于关键路径上，用粗箭头表示。图的底部，用时间线的方式显示了同样的解。灰色矩形表示时间区间，一个行动可以在这期间内执行，倘若遵守定序约束的话。灰色矩形中没有被占用的部分表示松弛

给定一个有持续时间的行动的偏序规划，如图12.2中所示，我们能够应用关键路径方法（CPM）来决定每个行动可能的开始和结束时间。经过偏序规划的一条路径是一个从Start开始到Finish结束的行动的线性有序序列。（例如，在图12.2的偏序规划中有两条路径）。

关键路径是总持续时间最长的路径。路径是“关键”的，这是因为它确定了整个规划的持续时间——缩短其它规划不会缩短整个规划，但是延迟关键路径上任何行动的开始将使整个规划慢下来。在图中，关键路径用粗线来表示。为了在最小总时间内完成整个规划，关键路径上的行动必须彼此之间没有延迟地执行。关键路径以外的行动有一些回旋余地——它们可以在一个时间窗口内执行。这个窗口根据最早可能开始时间ES和最迟可能开始时间LS来指定。数量LS−ES被称为行动的松弛。在图12.2中我们看到整个规划需要80分钟，关键路径上的每个行动都有0松弛（总是这样的），而装配 C1的每个行动都有一个10分钟的窗口，它们可以在这个窗口内开始。所有行动的ES 时间和LS时间一起构成了问题的一个调度表。

下面的公式可以作为ES和LS的定义以及描述计算它们的动态规划算法的轮廓：

ES(Start) = 0

ES(B)=maxAπB ES(A)+Duration(A)

LS(Finish) = ES(Finish)

LS(A)=minAπB LS(B)−Duration(A)

思路是我们从把 ES(Start)赋值为 0 开始。然后一旦我们得到一个行动 B，所有直接出现在 B 之前的行动的 ES都已经赋过值，我们就可以设 ES(B)为那些直接前继行动的最早完成时间的最大值，其中一个行动的最早完成时间定义为最早开始时间加上持续时间。这个过程重复进行直到每个行动被赋予一个 ES 值。LS 值用类似的方式计算，从 Finish 行动反向进行。细节留作一道习题。

关键路径算法的复杂度仅仅是O(Nb)，其中N是行动的个数，b是进入或离开行动的最大分支因子。（为了了解这点，注意对每个行动的LS和ES只计算一次，每次计算最多在b个其它行动上迭代）。因此，给定一个行动的偏序，寻找最小持续时间调度表的问题是很容易解决的。

具有资源约束的调度安排

现实调度安排问题由于资源约束的存在而复杂化。例如，给汽车安装发动机需要一台发动机起重机。如果只有一台起重机，那么我们就不能同时给汽车C1安装发动机E1和给汽车C2安装发动机E2；因此，如图 12.2 所示的调度表是不可行的。发动机起重机是可重用资源的一个例子——行动期间“被占用”，但是当行动结束时可以再次被利用的一种资源。注意，可重用资源无法在我们根据前提和效果进行的标准行动描述中处理，因为可用资源数量在行动完成后是不变的[8]。由于这个原因，扩充我们的表示以包含一个形如RESOURCE: R(k)的字段，意味着行动需要k个单位的资源R。资源需求既是先决条件——如果资源不可得，行动就不能被执行——也是临时的效果，从在行动持续期间可利用的资源 r 减少了 k 的意义上说。图 12.3 显示了如何扩展发动机装配问题以包含 3种资源：一台用于安装发动机的发动机起重机，一架用来安装车轮的车轮台以及两名检查员。图12.4 显示了具有最快完成时间的解，115 分钟。这比没有资源约束的调度表需要的 80 分钟长。注意，没有同时需要两名检查员的时刻，所以我们能够立即将两名检查员中的一名转移到更有生产价值的位置。

图12.3 需要资源的、装配两辆汽车的加工车间调度问题。可利用的资源包括一台发动机装配起重机，一架车轮装配台以及两名检查员。符号RESOURCE: r的意思是资源 r在行动执行期间被使用，但是当行动完成时再次变为空闲的

图12.4 图12.3中的考虑资源的加工车间调度问题的一个解。左边列出了3种资源，行动与它消耗的资源水平对齐地显示。取决于哪个装配先使用发动机装配起重机，有两个可能的调度表；我们显示了最优解，需要花费115分钟

资源表示为数值量，例如Inspectors(2)，而不是作为名称实体，诸如Inspectors(I1)和Inspectors(I2)，这是一种称为聚集的非常通用技术的一个例子。聚集的核心思想是当对象从其即刻效用的角度看完全不可区分时，把个体的对象聚合成数量。在我们的装配问题中，哪名检查员检查汽车是无关紧要的，所以不需要进行区分。（同样的思想在习题 3.9 的传教士和野人问题中也起作用。）聚集的本质是降低复杂度。考虑当假设一个调度表有10个同时发生的Inspect（检查）行动，但是只有9名检查员可用的情况下会发生什么。把检查员表示为数量，失败马上被检测出来，算法回溯转而尝试另一个调度表。而如果把检查员表示为个体，算法要对Inspect行动回溯尝试所有10!个分配检查员的方法，最终一无所获。

除了它们的优点，资源约束通过引入行动之间附加的相互作用而使调度安排问题变得更复杂。尽管使用关键路径方法的无约束调度安排是容易的，然而用最早可能完成时间寻找一个有资源约束的调度表却是NP难题。这个复杂度在实际中是与理论上一样常见的。1963年提出的一个具有挑战性的问题——为一个正好包含10台机器和每项工作有100个行动的10项工作的问题寻找最优调度表——在23年内一直没有得到解决（Lawler等人，1993）。已经有许多方法被尝试过，包括分支界限、模拟退火、禁止搜索、约束满足及第二部分的其它技术。一个简单而流行的启发式是最小松弛算法。它以一种贪婪方式调度行动。在每次迭代中，它考虑那些前辈都已经被调度安排而自身尚未调度的行动，并调度具有最小松弛的那个行动作为最早可能开始的。然后它更新每个受到影响的行动的ES和LS时间，并重复进行。启发式是基于与约束满足中的最大约束变量启发式一样的原理的。在实际应用中它通常工作得很好，但是对于我们的装配问题它产生了一个130分钟的解，而不是图12.4中的115分钟的解。

这一节中我们采用的方法是“先规划，后调度”：也就是说，我们将整个问题分成一个规划阶段和一个调度阶段，规划阶段选择行动并对其进行偏序排序以满足问题的目标，之后是调度安排阶段，时序信息被添加到规划中以确保满足资源和最终期限的约束。这种方法在现实世界的制造业和后勤安排中是常见的，其中规划阶段通常由人类专家完成。然而当有严格的资源约束时，某些合法的规划与其它的规划相比会通向好得多的调度表。如果是那样的话，通过在构建偏序规划期间考虑持续时间和重叠，而将规划和调度安排集成起来是有意义的。第十一章中的一些规划算法可以被扩充以处理这种信息。例如，通过与用因果连接检测冲突非常相似的方式，偏序规划器能够检测对资源约束的破坏。可以修改启发式，用以估计完成规划的总时间，而不仅是估计行动的总消耗。这是当前很活跃的一个研究领域。