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

• 作者: 吴智铭 庞小红 赵宏立
• 来源期刊: 机械科学与技术
• 学科: 工学
• 关键词: 遗传算法 作业车间调度问题 并行遗传算法
• 年，卷（期）: 2004,（12）
• 页码范围: 1421-1425
• 页数: 5页
• 分类号: TP18
• 字数: 5738字
• 语种: 中文
• DOI: 10.3321/j.issn:1003-8728.2004.12.010

摘要

使用遗传算法求解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问题进行了求解实验.实验表明本方法有着良好的求解效率,也证明了对染色体再编码过程对此问题的重要性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴智铭	上海交通大学自动化研究所	121	2157	27.0	41.0
2	庞小红	上海交通大学自动化研究所	21	299	9.0	17.0
3	赵宏立	上海交通大学自动化研究所	2	79	2.0	2.0