融入概率学习的混合差分进化算法求解绿色分布式可重入作业车间调度

本文针对绿色分布式可重入作业车间调度问题(GDRJSSP),提出一种融入概率学习的混合差分进化算法(HDE PL),以实现最大完工时间和总能耗最小.根据GDRJSSP的问题特点,设计编码和解码规则,并采用差分进化算法执行全局搜索来发现优质解区域.为能更明确地引导全局搜索方向,设计基于贝叶斯网络结构的多维概率模型合理学习和积累优质解(即当前种群中的较优解)的模式信息.结合问题解的结构特征,提出基于关键路径的4种邻域结构来构造局部搜索,并设计基于非关键路径的节能策略来提升算法获取低能耗非劣解的能力.仿真实验和算法对比验证了HDE PL可有效求解GDRJSSP.

可重入作业车间排队网建模与缓冲区配置优化

针对定制型制造企业可重入作业车间,研究了排队网建模和缓冲区容量配置优化方法。首先,建立了具有任意拓扑结构的有限缓冲区开排队网模型,以分析作业车间生产活动的随机过程,将节点的输入/输出过程拟合为一般分布,并提出近似求解的速率迭代法,用以快速计算系统平均产出率和生产周期。其次,通过算例实验与仿真结果进行对比,验证了假设模型的有效性和求解方法的精确性,并分析了缓冲区容量对系统性能的影响。缓冲区容量配置优化问题是一个非线性整数规划问题,也是一个NP难组合优化问题,因此提出一种由速率迭代法与Polyblock算法嵌套迭代的优化方法,并通过案例结果进行了验证。

基于块结构性质的花粉算法求解可重入作业车间调度问题

针对可重入作业车间调度问题(Reentrant job shop scheduling problem, RJSSP),提出一种基于块结构性质的花粉算法(Flower pollination algorithm based on block structure properties,FPA_BSP),用于最小化总加权延误时间(Totalweighted tardiness, TWT)。首先,建立RJSSP基于析取图的数学模型,并证明在确定析取弧方向后,该模型的对偶模型为最大费用流问题模型。其次,设计扩展RSOV (Reentrant-smallest-order-value, RSOV)编码规则,将花粉算法的实数矢量个体转变为排列矢量,使其可对问题解空间进行全局搜索,以发现存在优质解的区域。然后,定义8种邻域结构,并基于最大费用流问题特性分析块结构内部性质,得到前4种邻域结构能改进TWT的判定条件,可用于避免对无效区域的搜索,进而提出融合多种邻域的高效局部搜索,对全局搜索发现的优质解区域进行细致搜索。试验和算法比较验证FPA_BSP的有效性。提出RJSSP的块结构性质,并将其与花粉算法结合得到求解RJSSP的有效算法FPA_BSP,首次将花粉算法用于求解车间调度问题。