一种使用再编码染色体求解Job-Shop问题的并行遗传算法

摘要

使用遗传算法求解Job-Shop问题的一个关键问题是编码.本文提出了一种求解Job-Shop问题的新遗传算法--RPGA(Re-encoding Parallel GA).此方法的编码方式将Job-Shop问题转换为一个TSP(Traveling Salesman Problem)问题,使得关于TSP问题的遗传算法的方法可以用于解决Job-Shop问题.这种编码方式可以满足Job-Shop问题对工件加工顺序的要求,避免在进化过程中产生非可行解.RPGA最重要的特点在于染色体的再编码过程,再编码过程根据各工序的开工时间先后对染色体的各基因重新赋值,使得编码空间和解空间一一对应.最后,本方法使用MPI并行编程技术实现了粗粒度的并行模型,在此模型上我们对Fisher和Thompson的10×10问题进行了求解实验.实验表明本方法有着良好的求解效率,也证明了对染色体再编码过程对此问题的重要性.