混合分布估计算法求解考虑同步性和准时性的三阶段装配集成调度问题

Hybrid estimation of distribution algorithm for three-stage assembly integrated scheduling problem considering assembly synchronization and delivery punctuality

中文关键词  同步性  准时性  三阶段集成调度  EDA算法  数学规划  优化目标权重

英文关键词  assembly synchronization  delivery punctuality  three-stage integrated scheduling  estimation of distribution algorithm  mathematical programming  optimized objective weights

中文摘要

      本文研究以加工–运输–装配同步性和交货准时性的加权和为优化目标的三阶段装配集成调度问题 (3sAISP SP), 并基于问题特点设计混合分布估计算法(HEDA)进行求解. 首先, 分别建立3sAISP SP的数学规划模型 和排列模型. 其次, 在对问题模型特点分析的基础上, 设计合理的编码和解码规则, 同时利用HEDA中基于概率模型 的全局搜索以发现问题解空间存在优质解的区域. 然后, 为进一步提高算法性能, 设计3种局部搜索策略对优质解区 域进行细致搜索. 进而, 在小规模问题下, 将HEDA得到的较优解与优化求解器GUROBI得到的最优解进行比较, 验 证HEDA的求解结果接近最优解; 在较大规模问题下, 将HEDA与其他有效智能优化算法进行比较, 验证HEDA的求 解性能. 最后, 通过对优化目标中不同权重设置的实验分析, 给出加工–运输–装配同步性和交货准时性权重设置的 合理范围, 并得到考虑装配同步性有利于降低中间库存的结论.

英文摘要

      In this paper, a three-stage assembly integrated scheduling problem considering synchronization and punctuality (3sAISP SP) of process-transport-assembly with minimizing the weighted sum is proposed, and a hybrid estimation of distribution algorithm (HEDA) based on the problem’s characteristics is proposed to solve it. Firstly, a mathematical programming model and a permutation model of 3sAISP SP are formulated respectively. Secondly, after analyzing 3sAISP SP’s characteristics, the reasonable coding and decoding rules are designed, and HEDA’s global search based on the probability model is used to find the regions containing high-quality solutions in solution space. Thirdly, to further enhance HEDA’s performance, three neighborhood search strategies are devised to execute exploitation in the promising regions. Furthermore, comparisons between HEDA and GUROBI under the small scale problems demonstrate that the solutions obtained by HEDA are close to the optimal solution, and then comparisons among HEDA and other effective intelligent algorithms under the larger scale problems manifests the effectiveness of HEDA. Finally, through the experimental analysis of different weight settings in the optimization objective, the reasonable range of weight settings for process-transportassembly synchronization and delivery punctuality is given, and the conclusion that considering assembly synchronization is beneficial to reduce intermediate inventory is drawn.