Abstract: Multi-stage Coupled Integrated Scheduling Problem with Process Constraints(MCISP_PC)is prevalent in organizations with mixed-mode manufacturing.For the three stages of processing-transport-assembly,by combining with the multi-stage coupling characteristics,a Hybrid Estimation of Distribution Algorithm with Rule Heuristics(HEDA_RH)was proposed to solve MCISP_PC with the optimization objective of minimizing makespan.On the basis of sufficiently exploring the hierarchies and time-series correlation of the problem coupling constraints,the coding mode only for the processing stage was adopted,two rules were presented for each stages,and the better rule group was identified to complete decoding through the experiment.In HEDA_RH,by combining two block structure characteristics,Homotype Gather Block (HGB) and Isomerism Gather Block (IGB) that were found in individuals,the probabilistic model updating mechanism and two sampling methods were designed from a global perspective to better guide the search direction and increase the solving efficiency.A matrix cubic learning model was designed from a local perspective,which adaptively selected to change the search depth and rule execution strategy for improving the solution quality by accumulating quality information from six heuristics search operations.The effectiveness of HEDA_RH for solving MCISP_PC was verified with simulation comparison experiments.

Key words: rule heuristics, hybrid estimation of distribution algorithm, integrated scheduling, multi-stage coupling

摘要： 具有工艺约束的多阶耦合集成调度问题(MCISP_PC)普遍存在于现有混合生产制造企业中。针对加工-运输-装配3个阶段,结合多阶耦合性特征,提出结合规则启发式的混合分布估计算法(HEDA_RH)求解以最小化最大完工时间为优化目标的MCISP_PC。在充分挖掘问题耦合约束层级性和时序性基础上,采用只针对加工阶段的编码方式,并对各阶段分别提出两种规则,通过实验确定较优规则组以完成解码。在HEDA_RH中,结合个体中出现的同型聚集块和异形聚集块两种块结构特征,从全局角度设计概率模型更新机制和两种采样方式,较好地引导搜索方向以提高求解效率;从局部角度设计矩阵立方学习模型,通过积累6种启发式搜索操作优质信息,自适应地选择调整搜索深度及规则执行策略以改进解的质量。最后,通过仿真对比实验验证了HEDA_RH求解MCISP_PC的有效性。

关键词: 规则启发式, 混合分布估计算法, 集成调度, 多阶耦合