增强分布估计算法求解低碳分布式流水线调度  

Enhanced estimation of distribution algorithm for low carbon scheduling of distributed flow shop problem

作　　者：杨晓林 胡蓉[1] 钱斌[1] 吴丽萍 YANG Xiao-lin;HU Rong;QIAN Bin;WU Li-ping(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming Yunnan 650500,China)

机构地区：[1]昆明理工大学信息工程与自动化学院

出　　处：《控制理论与应用》2019年第5期803-815,共13页Control Theory & Applications

基　　金：国家自然科学基金项目(51665025);云南省应用基础研究计划项目(2015FB136);云南省教育厅科学研究基金项目(2017ZZX149)资助~~

摘　　要：针对低碳分布式流水线调度问题(DFSP–LC),提出了一种基于序关系的增强分布估计算法(OEEDA),用于最小化最大完成时间和总碳排放量.在OEEDA的第1 阶段,利用基于贝叶斯统计推断的分布估计算法(BEDA)在问题解空间进行一定时间的搜索,用于发现优质解并将其保存于非劣解集中.在OEEDA的第2 阶段,提出了基于序关系的四维矩阵(OFDM)对优质解的序关系(即工件块结构及其位置信息)进行有效学习和积累,进而设计了在解中固定部分块结构的采样机制,可更加明确地指导算法的全局搜索方向.同时,引入基于解、工厂间、工厂内的3种不同Insert融合的搜索方式,对2个阶段全局搜索得到的优质解区域进行较为细致的局部搜索.最后,通过仿真实验和算法对比验证了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.

关 键 词：碳排放 流水线调度 序关系 四维矩阵 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] X322[自动化与计算机技术—控制科学与工程]