论文部分内容阅读
具有资源约束的项目调度问题因其实际和理论意义一直是调度领域的重点内容。以往研究者提出了多种多样的算法，这些算法主要侧重于采用不同的算法结构和数学技巧来进行研究，很少有文献直接从搜索算法实质的角度出发来进行算法设计。针对这种情况，本论文对算法设计流程和搜索解空间的定义作了详细研究，主要研究工作如下：
(1)澄清了算法设计的主要阶段以及各个阶段的主要任务。认为设计调度算法可以从两个阶段来进行理解，一是调度解的构造阶段，另一个是调度解在搜索解空间内的迁移阶段。在构造解阶段，算法的主要任务是发现构成调度解的组成成分的最优组合过程；在解空间迁移搜索阶段，算法的主要任务是发现迁移的有利方向。
(2)定义了一种新的调度解表示方法，并给出了距离的定义。该方法描述了项目调度问题中各个活动之间的连接关系，可以与任何启发式框架混用，在更高的层次上体现了解的调度性质。
(3)扩展了前向-后向调度思想，定义了反向问题。反向问题保持了原问题的资源约束，活动间的先后关系约束与原问题相反。在反向问题中，所有正向问题的搜索操作都采用同样的方式进行，算法在需要的时候利用反向搜索一个解群来更新另一个解群。反向问题的定义，给算法设计带来了更多的灵活性。
(4)按照分散搜索的思想设计了分散搜索算法。通过对基本分散算法的各个因素作了仿真分析，给出了调整方法。调整的结果得到了混合遗传算法和进化算法。通过对项目调度问题标准库中实例的仿真分析，混合遗传算法和进化算法都可以解决大规模调度问题，并在产生比较少解的情况下，得到最优解以及最优解出现的个数都达到了很高的水平。
(5)根据新的表示方法，给出了解空间分解算法。并比较了一次分解算法和多次分解算法的效果。
(6)根据新表示方法的二值性，设计了量子进化算法。指出了量子算法的一般结构以及调整方法，给出了单量子算法和双量子遗传算法。
仿真结果说明了本文思想的正确性和算法的有效性。