增强分布估计算法求解低碳分布式流水线调度
Enhanced estimation of distribution algorithm for low carbon scheduling of distributed flow shop problem

针对低碳分布式流水线调度问题(low carbon scheduling of distributed flow shop problem, DFSP_LC),提出了一种基于序关系的增强分布估计算法(enhanced estimation of distribution algorithm based on ordered relationship, OEEDA),用于最小化最大完成时间和总碳排放量. 在OEEDA的第一阶段,利用基于贝叶斯统计推断的分布估计算法(estimation of distribution algorithm based on Bayesian statistical inference, BEDA)在问题解空间进行一定时间的搜索,用于发现优质解并将其保存于非劣解集中.在OEEDA的第二阶段,提出了基于序关系的四维矩阵(four-dimensional matrix based on ordered relationship, OFDM)对优质解的序关系(即工件块结构及其位置信息)进行有效学习和积累,进而设计了在解中固定部分块结构的采样机制,可更加明确地指导算法的全局搜索方向.同时, 引入基于解、工厂间、工厂内的三种不同Insert融合的搜索方式,对两个阶段全局搜索得到的优质解区域进行较为细致的局部搜索.最后,通过仿真实验和算法对比验证了OEEDA 的有效性.
An enhanced estimation of distribution algorithm based on ordered relationship (OEEDA) is presented to minimize the makespan and total carbon emission for a low carbon scheduling of distributed flow shop problem (DFSP_LC).In the first stage of OEEDA,an estimation of distribution algorithm based on Bayesian statistical inference (BEDA) is utilized to perform the global search in the problem''s solution space for a certain period of time,with the purpose of finding good solutions and storing them in the non-dominated set.In the second stage of OEEDA,a four-dimensional matrix based on ordered relationship (OFDM) is proposed to effectively learn and accumulate the excellent solutions''information of ordered relationship,i.e.,the information of job blocks and their corresponding positions.Then,a sampling scheme that fixes some blocks in the solution is designed to guide the global search direction more clearly.Moreover,a search method based on three kinds of Insert operator,i.e.,solution-based Insert,inter-factory Insert,and intra-factory Insert,is introduced to execute a more thorough local search from the promising regions obtained by the above two stages’ global search.Finally,simulations and comparisons show the efficiency of the proposed OEEDA