混合分布估计算法求解模糊分布式装配柔性车间调度问题

Hybrid estimation of distribution algorithm for distributed assembly flexible job shop scheduling problem with fuzzy processing time

针对分布式环境下作业时间的不确定性,本文以三角模糊数描述工件加工时间及产品装配时间,建立了以生产成本、拖期时间为目标的分布式装配柔性模糊车间调度模型(distributed assembly flexible job shop scheduling problem with fuzzy processing time,DAFJSPF),并提出了一种混合差分搜索及变邻域搜索的分布估计算法(HEDA-DEV)进行求解.首先,根据问题的特点,设计了一种新的多维编码方案;其次,提出基于概率模型的相似系数和两种变异算子,实现变异策略的动态选择;为提高算法的寻优能力,设计了5种变邻域结构,并按特定的搜索策略协同处理.最后,通过不同规模、不同柔性的实例仿真对比实验,验证了该算法在求解DAFJSPF具有较强的优势.

In view of the uncertainty of processing time in distributed environment,this paper describes the processing time and product assembly time with triangular fuzzy numbers,establishes a distributed assembly flexible job shop scheduling model(DAFJSPF)aiming at production cost and delay time,and proposes a hybrid estimation of distribution(EDA)-based optimization algorithm that integrates differential evolution(DE)-based evolutionary operators and variable neighborhood search(VNS),named HEDADEV,for solution.Firstly,the algorithm adopts a new multi-dimensional coding scheme according to the characteristics of the problem;secondly,the similarity coefficient and two mutation operators based on the probability model are proposed to realize the dynamic selection of mutation strategy;in order to improve the optimization ability of the algorithm,five kinds of variable neighborhood structures are designed,and the specific search strategy is used to make the cooperation.Finally,the comparison experiments of several scale and different flexibility examples verify that the algorithm has strong advantages in solving DAFJSPF.