基于区块进化算法求解置换流水车间调度问题  

Block-based Evolutionary Algorithm for Permutation Flow-shop Scheduling Problem

作　　者：裴小兵[1] 赵衡 Pei Xiaobing;Zhao Heng(College of Management,Tianjin University of Technology,Tiaajin 300384,Chin)

机构地区：[1]天津理工大学管理学院,天津300384

出　　处：《系统仿真学报》2018年第8期3170-3178,共9页Journal of System Simulation

基　　金：天津市社科项目(TJYY17-013)

摘　　要：针对置换流水车间调度问题,提出了一种混合区块模型的全局进化算法。通过对优秀染色体的统计与采样构建位置矩阵概率模型,并依关联规则挖掘出具有优势信息的连续或不连续基因组成优势区块,结合优势区块与概率模型组合出高适应度的人造解;依劣势染色体构建突变概率模型,指导后期的基因突变操作。提出基于位置概率交换与NEH插入两种高效局部搜索方法,以进一步筛选优势解。通过对Reeves和Taillard标准测试集的仿真测试和算法比较验证了所提出算法出色的搜寻能力和有效性。To solve the permutation flow-shop scheduling problem（PFSP）, an effective new global evolutionary algorithm based on block model is developed. The probability model is built based on the information of job position through sample and statistic on the good chromosomes, and the association rule is applied to extract continuous or discontinuous blocks which contain job information respectively. The superiority blocks with position probability model for artificial chromosome combinations are integrated. The disadvantage gene is excavated according to the inferior chromosome and used for the later mutation operation. Two efficient local search methods called position model-based interchange and NEH-based insertion are proposed to furtherfilter the dominant solution. Simulation results on Reeves and Taillard suites and comparisons with other well-known algorithms validate its excellent searching ability and efficiency of the proposed algorithm.

关 键 词：置换流水车间调度 组合区块 概率模型 人造解 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]