调度智能体的工作原理和应用

调度agent设计为慎思型agent，在协商过程的三个阶段中都扮演全局决策者角色。下面详细说明调度agent在各个阶段开展的工作。

1.初始化阶段

sag首先根据aagi的注册结果，生成项目网络图，置于黑板系统，以便所有aagi都能读取。

其次，sag使用自身的问题求解器，调用启发式算法求得RCPSP问题的一个最优进度计划Sopt（RCPSP）及其对应的任务列表λopt（RCPSP）；同时参考已有文献（Debels and Vanhoucke，2007；Valls et al.，2008），计算各时刻的资源利用率（resource utilization rate，RUR）：

然后，sag根据λopt（RCPSP），赋予各任务优先权值。令posj表示任务j在λopt（RCPSP）中的位置，则任务j的优先权值计算公式为：

完成上述工作后，sag启动再调度流程，令s0=0，SS0={0}，置于黑板系统中，返回给各个任务agent一个响应rp0。

2.再调度阶段

sag在再调度阶段的操作包含n个步骤，分别为n个非虚拟任务分配资源、开始时间和执行时间。每个步骤可处理多个来自任务agent的请求，但只有一个任务agent能够请求成功并获得资源。

sag在每个步骤开始时，更新当前可行任务集ESstage，并通知ESstage中任务对应的任务agent提交资源请求。

如果当前步骤只有一个任务agent发送请求，则该请求成功。否则，sag按照以下步骤决定为哪个任务agent分配资源。

首先，对于aag（jj∈ESstage）的请求，sag计算任务j执行后，在该任务执行期间内每个时刻的资源利用率：

然后，sag计算这些时刻内的平均资源利用率。从t0开始的时间段l内的平均资源利用率为：(www.xing528.com)

因此，任务j执行后的平均资源利用率为：

再然后，sag计算任务的动态优先权值（dynamic priority value，DPV）：

其中，α是[0，1]区间内的系数，称为列表惯性系数（list inertial coefficient），表示新的调度方案遵循原RCPSP调度方案的程度。

最后，sag根据dpv（jj∈ESstage）的大小，确定一个请求成功的任务j*：

整个过程相当于一个1_SSGS算法（Ballestiín et al.，2008）。该阶段终止于ESstage中不再有非虚拟任务。此时，sag为虚拟结束任务n+1分配开始时间和结束时间，作为项目的总工期。相应的任务列表记为λ0（1_PRCPSP），可行进度计划记为S0（1_PRCPSP）。同时，sag存储本阶段各步骤产生的αstage（以数组形式记为Α0）作为迭代改进阶段的操作对象。

3.迭代改进阶段

迭代改进阶段sag对Α0进行改进，其基本思想是在每一次迭代中，保留与上一代任务列表峰片段对应的α，并尝试调整与非峰片段对应的α。该阶段的第一代以λ0（1_PRCPSP）和S0（1_PRCPSP）为改进对象，执行与再调度阶段类似的过程；所不同的是，该阶段sag在各个步骤的列表惯性系数α并不都是随机产生的：对于与峰片段对应的α，sag保留其在再调度阶段产生的值；而对于与非峰片段对应的α，sag重新随机产生一个[0，1]区间内的数值作为α的新值。

峰片段的识别采用Debels和Vanhoucke（2007）的做法。首先在区间上生成一个随机数作为峰片段的长度l。根据S0（1_PRCPSP）计算相应时间段内的总资源利用率（total resource utilization，TRU）：

其中，t0∈[0，sn+1−l]。sag从中识别出最大的一个TRU（t0，l）max，选取相应的时间段[t0，t0+l）作为资源利用高峰时间段。对应到任务列表上的子任务λpeak便是峰片段。峰片段的任务对应的α便是需要保留的值。

第一次迭代产生的任务列表和可行调度分别记为λ1（1_PRCPSP）和S1（1_PRCPSP），新产生的列表惯性系数记为Α1。此后的每一次迭代iter，均以上一次迭代的任务列表λiter−1（1_PRCPSP）、可行进度计划Siter−1（1_PRCPSP）以及列表惯性系数Αiter−1作为操作对象，执行再调度过程。算法终止于iter达到预设的最大迭代次数itermax。算法选取Sopt（RCPSP），S0（1_PRCPSP），S1（1_PRCPSP），…，Sitermax（1_PRCPSP）中最好的一个可行进度计划作为问题的最好解Sopt（1_PRCPSP）。