并行分布式处理是当前计算机发展的主要挑战问题之一,也是当前计算机科学的一个热点。在并行分布计算中,调度问题是分布计算的瓶颈问题之一。这个问题对发挥系统的并行计算能力、提高系统吞吐量具有非常重要的影响。良好的调度算法可以充分运用系统中每个处理机的计算能力,提高并行分布计算的效率。调度问题得不到解决,则会导致分布计算效率低下。上世纪50年代中期创立了仿生学,蚁群算法正是从仿生学的机理中受到启发而提出的一种新型进化算法和启发式随机搜索算法。蚁群算法具有分布式、鲁棒性好以及易于与其他方法结合的优点。蚁群算法主要用于求解不同的组合优化问题。目前蚁群算法的研究已经渗透到了多个应用领域,可以解决多维动态组合优化问题、离散优化问题等。处理机调度问题属于组合最优化问题,更是离散优化问题。而蚁群算法在求解离散优化问题上的卓越性能为使用蚁群算法求解处理机调度问题提供了可行性。本文主要研究蚁群算法在处理机调度问题中的应用。文章首先详细介绍调度问题和蚁群算法的定义、模型及其研究现状等,分析讨论了当前国内外一些求解调度问题的各类算法,为利用蚁群算法求解处理机调度问题提供了一定的理论基础。文章的主体部分包括三个方面:基于蚁群算法求解处理机调度问题、基于混合蚁群算法求解处理机调度问题以及基于蚁群算法求解实时系统中有时限约束的调度问题。文章的主要贡献及创新之处如下所示:1.文章提出了一种求解多处理机调度问题的蚁群优化算法。该算法在DAG图的基础上,用AOE(Active on Edge)图来表示任务之间拓扑顺序,图中的每一边条代表一个任务,边上的权重表示该任务的完成时间。AOE图比一般的DAG图更能表现出任务之间的优先约束关系,也能更好地贴近蚁群算法的设计思路。其次,将关键路径、任务的最早开始时间和任务的最迟开始时间等多种因素有机结合在一起,设计出了概率公式,避免了任务选择策略的单一,在一定程度上避免陷入局部最优解。最后用任务之间的“配合程度”来定义信息素,加快了算法的收敛速度。2.文章提出了一种适合蚁群算法的任务分配模型(Task-Allocation Model, TAM),该模型结合具体类型的处理机调度问题的特点,具有很好的可扩充性和灵活性。在TAM的基础上,设计了基于TAM的求解处理机调度的蚁群算法。为了克服蚁群算法的收敛速度慢、易陷入局部最优等局限性,我们在蚁群算法中加入遗传算子,设计了一种混合蚁群算法。充分发挥了两者的优点,既保证了较高的搜索效率,又保证了解的全局最优性;最后,在TAM的基础上,对动态处理机调度算法的设计与实现进行了探讨,为进一步的研究工作奠定了基础。3.文章提出一种求解有时限约束的调度问题的蚁群算法(The ACO for Deadline Scheduling Problem,简称ADSD)。此算法首先对任务集所对应的DAG图进行了扩展,得到了扩展的DAG图。根据这种设计,人工蚂蚁在图中遍历可以得到任务的拓扑序;此算法包括两种优化,一方面是任务列表的优化;另一方面是处理机分配策略的优化。由这两种优化衍生出两种概率公式的设计和两种信息素。算法利用启发式信息保证优先调度截止时间最早的任务,通过概率选择保证了其它情况的出现,避免出现局部最优解。上述三种算法的实验结果表明,我们提出的算法比其他类似的算法在较短的时间内找到更好的调度策略,更具有鲁棒性和灵活性。