摘要
使用遗传算法求解Job Shop问题的一个关键问题是编码。本文提出了一种求解Job Shop问题的新遗传算法———RPGA(Re encodingParallelGA)。此方法的编码方式将Job Shop问题转换为一个TSP(TravelingSalesmanProblem)问题 ,使得关于TSP问题的遗传算法的方法可以用于解决Job Shop问题。这种编码方式可以满足Job Shop问题对工件加工顺序的要求 ,避免在进化过程中产生非可行解。RPGA最重要的特点在于染色体的再编码过程 ,再编码过程根据各工序的开工时间先后对染色体的各基因重新赋值 ,使得编码空间和解空间一一对应。最后 ,本方法使用MPI并行编程技术实现了粗粒度的并行模型 ,在此模型上我们对Fisher和Thompson的 10× 10问题进行了求解实验。实验表明本方法有着良好的求解效率 ,也证明了对染色体再编码过程对此问题的重要性。
Representation scheme plays a very important role for genetic algorithm(GA), especially in job-shop scheduling problems. In this paper, we present the RPGA(Re-encoding Parallel GA).RPGA converts a job-shop scheduling problem(JSSP) directly into a traveling salesman problem(TSP), thus many of the previous GA techniques for TSP can be used to resolve JSSP. This representation scheme produces no infeasible solutions. The characteristic of this method is its re-encoding scheme, which realizes a unique mapping between the coding space and the solution space. A coarse-grained parallel model is used to implement RPGA. The famous FT10×10 problem is carried out with RPGA. The result proves the efficiency of RPGA and the crucial effect of the re-encoding scheme.
出处
《机械科学与技术》
CSCD
北大核心
2004年第12期1421-1425,共5页
Mechanical Science and Technology for Aerospace Engineering
基金
国家自然科学基金项目 (60 0 7740 11
70 0 710 17)资助
关键词
遗传算法
作业车间调度问题
并行遗传算法
Genetic algorithm
Job-shop scheduling problem
Parallel genetic algorithm
