抽样算法对进度计划的影响及优化方案

基于优先规则的启发式算法是所有项目调度算法中应用最普遍也是最重要的一大类算法。这类启发式算法包含了两个部分，即进度生成机制和任务优先规则。基于SGS的启发式算法是决定性的，因为对于给定的优先规则，在SGS的每一阶段根据优先规则选取的任务是确定的，因此最终产生的项目进度也是确定的。重复这样的启发式算法，并不能改进算法产生的进度计划。如果在SGS中引入随机函数，不是直接根据任务的优先顺序，而是根据一定的概率来随机地抽取任务，那么就可以产生随机的进度计划。重复这样的随机过程，就可以生成一系列的项目进度计划，并从中选择较优的进度计划。

抽样算法的效率主要取决于所采用的随机函数。目前主要有三类抽样算法，即随机抽样、偏倚随机抽样及基于后悔值的偏倚随机抽样。

随机抽样方法给决策集Dg中的每个任务赋予完全相同的概率：

上述随机抽样方法事实上是完全随机的，无法有效利用任何启发式信息。偏倚随机抽样方法结合启发式算法中常用的任务优先规则，在SGS的每一阶段，给定某一优先规则，考虑候选任务集合Dg中的某一个任务（i，j），使该任务被选取的概率与其优先权相关，同时又保证候选任务集合Dg中所有任务的概率之和等于1。如此，可以根据特定优先规则设定的优先值vij赋予概率：

目前在单项目调度中比较有效的方法是基于后悔值的偏倚随机抽样方法（Schirmer and Riesenberg，1997）。与BRS类似，RBRS也结合了启发式信息，采用如下的概率赋值函数（Drexl，1991；寿涌毅，2005）：

其中，ρij为任务（i，j）的优先权与候选任务集合Dg中其他任务优先权的最大差值：(www.xing528.com)

在式（5.16）中，假定优先权是按升序排列的，即优先权取值越小，任务越优先。对于按降序排列的优先规则，则需要进行如下调整：

其中，M为一足够大的正数，以保证调整后的任务优先权v′（i，j）非负。

在式（5.15）中，参数ε>0用于保证ρ值为0的任务（即优先级最低的任务）也有一定的概率中选，一般选择ε=1（Schirmer and Riesenberg，1997）。参数α用于控制过程的随机性，当α非常大的时候，算法随机性降低；当α等于0时，所有任务具有相同的概率，退化成完全随机抽样。一般选取α=1（Kolisch，1996），但是Schirmer和Riesenberg（1997）的计算分析表明α=1并不保证有最好的调度效果。

在SGS的每一阶段，按式（5.15）定义的概率在候选任务集合Dg中随机地选取任务。根据式（5.16）可知，任务的中选概率与其优先级成正比的，优先级越高，中选概率就越大。因此，可以预计任务优先规则会对抽样算法产生显著影响。