基于进化算法的多处理机任务调度器研究

作为并行分布式系统中的关键问题,多处理机任务调度在一般形式上是一个NP完全问题。快速而有效地实现在多机系统内的全局任务调度,无论在理论研究还是实际应用中都有十分重大的意义。 与主流的表调度算法不同,基于进化计算的多处理机任务调度算法是一种全局的概率搜索算法。保持一个候选解编码的群体,并在其上应用诸如选择、杂交和变异等的进化操作,经过许多代的演化而收敛于最优解,这就是进化计算的基本原理。 但目前,基于进化计算的多处理机调度算法都对遗传编码的方式和进化操作了扩展,在其中集成了关于任务调度的领域知识。我们认为,这样的改动完全违背了进化计算的本质,完全丧失了进化计算的特点。因此,我们提出了基于简单二进制编码和领域知识无关操作的经典进化(遗传)算法。通过分析和比较,我们证明了,经典进化算法在简单性、一致性以及工程应用中都明显的优势,并且只要设计合理的评价函数,经典进化算法的性能并不逊于扩展遗传算法。 在深入分析调度问题的基础上,我们设计了三类基于进化算法的多处理机任务调度器。从不计通信时间的简化形式,到面向异构系统的通用形式,三类算法都在其定义范围内取得了理想的结果。而这三类调度算法的设计和实现,也充分体现了经典进化算法对于问题的广泛适应性。 性能的测试和评价是多处理机任务调度问题研究中的一个重要方面。但目前对此仍然没有统一的标准。本文就这个问题进行了详细的讨论,分析了性能测试的基本原理,并在此基础上设计了进化任务调度器的测试方案。 通过对不同条件下进化任务调度器的测试,我们就各种问题参数和算法变量对调度器性能的影响进行了分析和比较。我们还对各类进化调度算法进行了横向和纵向的比较测试,对进化计算在多处理机任务调度算法中的应用进行了全面的总结。