求解柔性作业车间调度的岛屿模型遗传算法

An Island Model Genetic Algorithm for Flexible Job Shop Scheduling Problem

针对多品种小批量复杂产品生产的调度优化问题,结合柔性作业车间调度问题与统一计算设备架构的特点,提出了一种求解柔性作业车间调度问题的岛屿模型遗传算法.设计了统一计算设备架构的存储模型及执行模型,给出了染色体编码、解码方式,并改进了遗传算法的选择、交叉、变异操作,最后定义了迁移操作.算法提高了遗传算法在统一计算设备架构上的并行处理效率,使用标准实验数据进行测试,结果表明了使用岛屿模型遗传算法求解柔性作业车间调度问题是有效的和可行的.

According to the scheduling problems combining the characteristics of Flexible Job Shop Sch in the multi-variety, small-batch complex production, and eduling Problem and Compute Unified Device Architecture, an island model genetic algorithm for Flexible Job Shop Scheduling Problem was proposed in this paper. First, a storage model and execution model which are well suited for Compute Unified Device Architecture was designed. Then the mode of chromosome encoding and decoding was shown and choosing, crossing, variation, transfer opera- tion of genetic algorithm are all improved. The algorithm raises parallel processing efficiency of genetic algorithm on computing unified device architecture. Comparing the results and efficiency with other algorithms using benchmark data, the experimental result shows that the algorithm is effective and feasible.