再调度阶段优化方案

再调度阶段引入允许一次抢占的机制，利用由PVopt（RCPSP）转化的PV（1_PRCPSP）的信息，通过aagi与sag间的请求与响应完成任务开始时间的重新安排。计算步骤详述如下：

（1）黑板系统显示，ES1={1a，2a，3a}；此时aag1、aag2和aag3启动，分别计算各自在非抢占和抢占情况下的开始时间。对于任务1、2和3，都有sj=sja，因此，三个任务都只有一个方案，即非抢占调度方案。

三个任务agent分别发送各自的请求：

sag根据收到的请求，计算三项任务执行后的资源利用率：

sag产生（0，1）区间上的随机数α1，假设α1=0.2。计算各项任务的动态优先权值：

由于dpv2>dpv1>dpv3，故aag2请求成功。

因此，任务2的开始时间安排为s2=0；将任务2加入SS0中，形成SS1={0，2a，2b}。此时的部分进度计划（partial schedule）如图10.7所示。

图10.7　再调度阶段步骤1的部分进度计划

（2）黑板系统更新，显示ES2={1a，3a}。此时aag1、aag3启动，分别计算各自在非抢占和抢占情况下的开始时间。对于任务1和3，都有sj=sja，因此两个任务都只有非抢占调度方案。

两个任务agent分别发送各自的请求：

sag根据收到的请求，计算两个任务执行后的资源利用率：

取α2=0.3，计算动态优先权值：

由于dpv1>dpv3，故aag1请求成功。

因此，任务1的开始时间安排为s1=2；将任务1加入SS1中，形成SS2={0，1a，1b，2a，2b}。此时的部分进度计划如图10.8所示。

图10.8　再调度阶段步骤2的部分进度计划

（3）黑板系统更新，显示ES3={3a，4a}。此时aag3、aag4启动，分别计算各自在非抢占和抢占情况下的开始时间。对于任务3和4，都有sj=sja，因此两个任务都只有非抢占调度方案。

两个任务agent分别发送各自的请求：

sag根据收到的请求，计算两个任务执行后的资源利用率：

取α3=0.5，计算动态优先权值：

由于dpv3>dpv4，故aag3请求成功。

因此，任务3的开始时间安排为s3=2；将任务3加入SS2中，形成SS3={0，1a，1b，2a，2b，3a，3b}。相应的部分进度计划如图10.9所示。

图10.9　再调度阶段步骤3的部分进度计划

（4）黑板系统更新，显示ES4={4a，5a，6a}。此时aag4、aag5和aag6启动，分别计算各自在非抢占和抢占情况下的开始时间。对于任务4、5和6，都有sj=sja，因此三个任务都只有非抢占调度方案。

三个任务agent分别发送各自的请求：

sag根据收到的请求，计算三个任务执行后的资源利用率：

取α4=0.8，计算动态优先权值：

由于dpv4>dpv5>dpv6，故aag4请求成功。

因此，任务4的开始时间安排为s4=6；将任务4加入SS3中，形成SS4={0，1a，1b，2a，2b，3a，3b，4a，4b}。相应的部分进度计划如图10.10所示。

图10.10　再调度阶段步骤4的部分进度计划

（5）黑板系统更新，显示ES5={5a，6a，7a}。此时aag5、aag6和aag7启动，分别计算各自在非抢占和抢占情况下的开始时间。由于任务5、6和7，都有sj=sja，因此三个任务都只有非抢占调度方案。

三个任务agent分别发送各自的请求：

sag根据收到的请求，计算三个任务执行后的资源利用率：

取α5=0.2，计算动态优先权值：(www.xing528.com)

由于dpv6>dpv5>dpv7，故aag6请求成功。

因此，任务6的开始时间安排为s6=9；将任务6加入SS4中，形成SS5={0，1a，1b，2a，2b，3a，3b，4a，4b，6a，6b}。相应的部分进度计划如图10.11所示。

图10.11　再调度阶段步骤5的部分进度计划

（6）黑板系统更新，显示ES6={5a，7a，8a}。此时aag5、aag7和aag8启动，分别计算各自非抢占和抢占情况下的开始时间。

对于任务5，有s5a=7，d5a=2，s5=13。因此，任务5有两套方案，如图10.12所示。aag5需要计算抢占情况下的效用：

假设aag5的阈值为0.4，则抢占效用超过阈值（0.43>0.4），将提交抢占方案。

图10.12　任务5的两套调度方案

对于任务7和8，都有sj=sja，因此这两个任务都只有非抢占调度方案。

三个任务agent分别发送各自的请求：

sag根据收到的请求，计算三个任务执行后的资源利用率：

取α6=0.5，计算动态优先权值：

由于dpv5>dpv7>dpv8，故aag5请求成功。任务5的开始时间安排为s5a=7，d5a=2；将子任务5a加入SS5中，形成SS6={0，1a，1b，2a，2b，3a，3b，4a，4b，5a，6a，6b}。相应的部分进度计划如图10.13所示。

图10.13　再调度阶段步骤6的部分进度计划

（7）黑板系统更新，显示ES7={5b，7a，8a}。此时aag5、aag7和aag8启动，分别计算各自在非抢占和抢占情况下的开始时间。

对于aag5，由于需要调度的是任务5的第二部分，即子任务5b，因此只有非抢占调度方案。对于aag7和aag8，由于sj=sja，均只有非抢占方案。

三个任务agent分别发送各自的请求：

sag根据收到的请求，计算三个任务执行后的资源利用率：

取α7=0.5，计算动态优先权值：

由于dpv5>dpv7>dpv8，故aag5请求成功。子任务5b的开始时间安排为s5b=13，d5b=3。将子任务5b加入SS6中，形成SS7={0，1a，1b，2a，2b，3a，3b，4a，4b，5a，5b，6a，6b}。相应的部分进度计划如图10.14所示。

图10.14　再调度阶段步骤7的部分进度计划

（8）黑板系统更新，显示ES8={7a，8a}。aag7和aag8启动，分别计算各自在非抢占和抢占情况下的开始时间。对于任务7和8，都有sj=sja，因此两个任务都只有非抢占调度方案。

两个任务agent分别发送各自的请求：

sag根据收到的请求，计算两个任务执行后的资源利用率：

取α8=0.5，计算动态优先权值：

由于dpv7>dpv8，故aag7请求成功。任务7的开始时间安排为s7=13。将任务7加入SS7中，形成SS8={0，1a，1b，2a，2b，3a，3b，4a，4b，5a，5b，6a，6b，7a，7b}。相应的部分进度计划如图10.15所示。

图10.15　再调度阶段步骤8的部分进度计划

（9）黑板系统更新，显示ES9={8a}。aag8启动，并计算其在非抢占和抢占情况下的开始时间。由于s8=s8a，故任务8只有非抢占调度方案。

aag8发送请求：

sag收到aag8的请求。由于只有一个请求，因此aag8请求成功。任务8的开始时间安排为s8=15。将任务8加入SS8中，形成SS9={0，1a，1b，2a，2b，3a，3b，4a，4b，5a，5b，6a，6b，7a，7b，8a，8b}。相应的部分进度计划如图10.16所示。

图10.16　再调度阶段步骤9的部分进度计划

（10）最后，sag为虚拟结束任务9安排开始时间和结束时间，均为17，生成新的调度方案：

至此，再调度阶段完成。sag在这一阶段所积累的策略体现为各步骤中随机生成的α值：（0.2，0.3，0.5，0.8，0.2，0.5，0.5，0.5，−），其中α9未生成。之后，MAO算法进入迭代改进阶段，其中的sag对每一阶段的α进行改进，以试图生成更好的调度方案。