多处理机调度问题是并行处理中的一个著名问题.调度的主要目的是优化并行程序在系统中运行的一些指标,本文中调度的主要目标是缩短调度后并行程序的执行时间和提高多处理机系统的利用效率.在一般情况下调度问题的复杂性是NP-complete的.对于规模比较大的调度问题,由于任务图的规模太大,一般调度算法将会由于内存的限制而不能胜任.一种途径是采用动态调度算法,但是由于动态调度算法是在程序运行时进行的,并且程序中的一些参数可以是预先未知,直到运行时才确定的,而且动态调度一般要对并行程序加一些前提上的约束,故算法设计比较复杂、困难;另一种途径是将比较好的调度算法并行化.本文首先介绍了一些背景知识,然后介绍了目前常用的各种调度模型和一些代表性的调度算法.再详细介绍两种典型调度模型BNP和UNC,阐明了设计UNC模型上的调度算法的理由.在结合已有的模拟退火算法和遗传算法的基础上,我们改进了现有的遗传调度算法,自适应地保存最优个体,并对其进行模拟退火,提出了在UNC模型上的自适应最优保存的模拟退火遗传调度算法SAMOAGSA.最后将该算法并行化,并在自强2000上高性能计算机上实现.本文采用香港科技大学Yu-Kwong Kwok提供的Benchmarks图集对本文算法和其它算法进行了比较分析.算法的比较结果显示算法对规模适中的任务图有较好的搜索效果,并且对于不同粒度的任务图而言,粗粒度的任务图的调度效果优于细粒度的任务图.该论文的主要贡献:1)将遗传算法与模拟退火相结合的混合遗传算法应用于调度问题;2)将其与其它调度算法进行了纵向、横向的比较;3)将其并行化及性能分析.