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

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

A New Enhanced-Dynasearch & TS for the Pickling-rolling Scheduling Problem

Motivated by pickling-rolling production in steel industry, the pickling-rolling scheduling problem is to create a schedule by selecting and sequencing many proper coils from the candidate pool with consideration of the changeovers cost between adjacent coils. Besides the capacity constraints and practical production technical constraints, the flow requirement constraint is also considered so that the total weight of the selected coils belonging to the same downstream unit satisfies the production requirement of the corresponding downstream unit, the objective being to minimize the total transition cost and the penalty cost on the left capacity. The problem is formulated as an integer programming model and a new tabu search (TS) with the enhanced dynasearch algorithm is developed for it. A two-phase heuristic based on nearest insert method is proposed to act as the initial feasible solution to the tabu search. The proposed algorithm designs a double tabu list to fit the different neighborhood structure. For the solution to escape from the local optima, the enhanced dynasearch neighborhood is embedded in each iteration. The dynasearch neighborhood is polynomially searchable by dynamic programming and it can perform a multiple-exchange composite move by combining swap and inner-insert neighborhoods. Based on the analysis of the characteristics of the problem, block structure is defined and several properties of the feasible solution are derived to accelerate the search process. Computational results show that the enhanced-dynsearch & TS algorithm is effective for solving the problem and outperforms the standard one by 3.62% on average.