改进区块遗传算法解决分布式车间调度问题

Solving distributed-shop scheduling problems based on modified genetic algorithm

针对分布式车间调度问题,提出了改进区块遗传算法(modified block-genetic algorithm,MBGA)。用NEH和随机性两种方式得到高质量的初始解,然后进行统计分析,选出精英染色体,建立工件−车间分配矩阵和工件−机器排序矩阵,挖掘联系紧密的基因链组成区块。构建基于区块的人工染色体,并进行基因重组,提高解的质量和多样性。通过算例与其他知名算法进行比较,结果表明该算法优于其他算法,并具有较好的稳定性和准确性。

To solve distributed-job-shop scheduling problems,in this paper,we propose a modified block-genetic algorithm(MBGA).First,we initialize the solutions by combining NEH and random assignments.Then,by statistical analysis,we select an elite chromosome to establish a job-factory distribution matrix and job-machine sorting matrix to mine the block’s closely linked gene chain.Block-based artificial chromosomes are constructed and recombined to improve the quality and diversity of the solutions.The experimental results show that the performance of the proposed MBGA algorithm is superior to that of other well-known algorithms with respect to its stability and accuracy.