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

摘要：

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

关键词：酸轧生产调度、禁忌搜索、Dynasearch算法、Dynasearch邻域

所属期刊栏目：36

分类号：TP2(自动化技术及设备)

资助基金：国家高技术研究发展计划863计划2006AA04Z174;国家自然科学基金60674084;国家杰出青年科学基金70425003

在线出版日期：2010-06-08（万方平台首次上网日期，不代表论文的发表时间）

页码：304-313