一种求解随机有限缓冲区流水线调度的混合差分进化算法

摘要

针对随机有限缓冲区流水线调度问题(Flow shop scheduling problem,FSSP),提出混合差分进化(Differential evolution,DE)算法 OHTDE,用来最小化提前/拖后指标和最小化总体完成时间指标.oHTDE将DE和最优计算量分配(Optimal computing budget allocation,OCBA)技术以及假设检验(Hypothesis test,HT)有效结合.DE用于执行全局搜索和局部搜索;OCBA用于对有限计算量进行合理分配,从而保证优质解得到较多仿真计算量,提高了在噪声环境下获得优质解的置信度;HT 用于在统计意义上比较解的性能,从而定程度上避免在解空间相近区域进行重复搜索.进而,对由OCBA和HT确定的优质解执行一种特殊的交叉操作,加强DE的局部开发能力.同时也采用有限马氏链理论对OHTDE的随机收敛性进行了分析.仿真实验和算法比较验证了算法的有效性和鲁棒性.