强化Dynasearch TS算法求解酸轧生产调度问题

摘要

酸轧生产调度的主要任务是在满足酸轧机组生产工艺和能力约束下,考虑下游机组的流向需求,为保证生产连续性和平滑过渡的要求,从给定候选池中选择适合的板卷构成一个酸轧调度单元.针对此问题,本文建立了以最小化过渡费用和调度单元剩余容量惩罚费用为目标的整数规划模型,提出了一种嵌入强化Dynasearch算法的禁忌搜索混合算法.该混合算法采用基于最小插入法的两阶段启发式产生初始解,根据采用邻域结构的不同设计双禁忌表,为了避免算法陷入局部最优,在禁忌搜索的每次迭代过程中嵌入Swap邻域和Inner-insert邻域相结合的多交换Dynasearch邻域,并设计了多项式动态规划算法搜索该邻域.针对问题的特征,提出了Block分区结构,基于此分析了多个可行解性质,有效降低了搜索空间.与一般禁忌搜索算法比较,结果表明所提出的强化Dynsearch & TS(Tabu search)算法求解效果明显优于一般TS算法,平均改进量为3.62%,算法运行时间大大缩短.验证了该算法在解决此类问题的有效性.