本文第一章对遗传算法及其基本理论进行了简要的回顾，然后在第二章里对并行遗传算法从其分类、工作机理等方面进行了介绍。 本文第三章里对有关的MPI并行编程技术进行了介绍。并在第四章里给出了用MPI实现的粗粒度并行遗传算法基本程序的说明。 在第五章中，本文在基本粗粒度并行遗传算法的实现基础上，提出一种用基因块编码的并行遗传算法（简称BCPGA）。 旅行商问题（Traveling Salesman Problem，TSP）是经典的组合优化问题。本文将BCPGA应用于一个100城市的旅行商问题中。实验证明此方法可以提高遗传算法的搜索效率,并且在相同条件下，BCPGA明显优于单纯的粗粒度并行遗传算法。 Job-Shop问题是经典的生产线调度问题。使用遗传算法求解Job-Shop问题的一个关键问题是编码。在第六章里，本文提出了一种求解Job-Shop问题的新的遗传算法的方法RPGA（Re-encoding Parallel GA）。最后，本方法使用MPI并行编程技术实现了粗粒度的并行模型，在此模型上对Fisher和Thompson的 10x10问题进行了求解实验。