算法测试与分析：优化方案

采用本书第3章所构造的多项目调度算例库对各类多项目抽样算法进行计算测试。多项目目标函数为加权项目总工期最小化，设定各项目权重均为1。所有算法均采用C语言编写，用GNU C编译，在CPU主频2GHz、内存1GB的计算机上进行运算。所有多次算法的最大循环次数都设置为5000次，即产生5000个有效的多项目进度计划。后续各章，在不另做说明的情况下，均采用相同的算例库、计算设备及参数设置。

在多项目RBRS中，分别采用SOF、MOF、SASP、LALP、MTS、MCS、MINSLK、MAXSLK、MINLFT、MAXLFT、MINLST、MAXLST共12种任务优先规则。在所有RBRS中，均设定参数α=ε=1。此外，还采用完全随机抽样（PRS）作为对比基准。

首先比较各类任务优先规则，均采用SSGS构造多项目进度计划，并选择PRS作为比较基准。计算所得结果如表5.4所示，并按照项目总工期均值从低到高排序。

表5.4　多项目任务优先规则调度效果比较

续表

在上述多项目调度任务优先规则中，MOF规则表现最优，其次是LALP和MTS。而SASP、MINLFT、MINSLK、MINLST及SOF均表现不佳，事实上还不如完全随机抽样方法。这一结果部分证实了Browning和Yassine（2010）的研究，即Kurtulus和Davis（1982）所推荐的SASP规则其实表现并不优秀。

对采用不同优先规则的RBRS进行计算测试，同样以PRS作为比较基准。计算结果如表5.5所示。(www.xing528.com)

表5.5　多项目RBRS调度效果比较

可以发现不同任务优先规则对于RBRS的调度效果具有显著影响。采用MINSLK、SOF、MINLST及MINLFT的RBRS，调度效果仍然不如PRS。对于单项目RBRS来说，MINLST是最佳任务优先规则（Drexl，1991；Schirmer and Riesenberg，1997），但对于多项目抽样调度而言，情况显然很不相同。采用SASP的RBRS略好于PRS。在上述优先规则中，采用MTS或MOF规则的RBRS，调度效果最好。

将RBRS与SSGS进行比较分析，可以发现在采用RBRS反复抽样后，多项目进度计划的质量整体得到了显著提高，如表5.6所示。除MINLFT外，采用RBRS使得多项目总工期均值压缩了1.24％至8.78％。对于MINLFT而言，在RBRS反复抽样后，多项目总工期均值略有上升。但是，对256个实例进行Wilcoxon Signed Ranks检验，可以发现这两个算法所得多项目总工期并无统计性显著差异。

表5.6　多项目RBRS对SSGS的改进效果

此外，在上述偏倚随机抽样算法中，采用了常用的参数设置α=ε=1。Schirmer和Riesenberg（1997）对于单项目调度的分析已经表明这未必是最佳参数设置。对于多项目调度的偏倚随机抽样，上述参数的合理设置值得后续进一步研究。