热轧实施计划中最优倒垛问题的整数规划模型及遗传算法  

INTEGER PROGRAMMING MODEL AND MODIFIED GENETIC ALGORITHM FOR OPTIMAL TURNED OUT SLAB PILE FOR HOT ROLLINE SCHEDULE

作　　者：唐立新[1] 杨自厚[1] 

机构地区：[1]东北大学系统工程研究所,沈阳110006

出　　处：《自动化学报》2000年第4期461-469,共9页Acta Automatica Sinica

基　　金：国家 8 6 3/CIMS计划支持项目!( 86 3- 511- 70 8- 0 0 9);国家自然科学基金资助项目 !( 7970 0 0 0 6 );国家教育部优秀年轻教师研

摘　　要：对钢铁企业板坯库中的最优倒垛问题建立了 0和 1整数规划模型 .这一模型是一个二次规划模型 ,且目标函数的系数与变量的取值相关联 ,属于 NP-难问题 ,获得较大规模的最优解是不可能或非常困难 .为了求解此问题 ,本文构造了改进遗传算法 :(1 )提出了适合于最优倒垛问题的遗传编码 ,运用此编码 ,不但能够产生可行的初始染色体 ,而且能够保证在交叉和变异操作后的染色体仍然可行 ;(2 )改进了遗传算法结构 ,在新的结构中 ,增加了一个培育操作 ,改进了交叉操作 .通过精选随机产生的问题例子的实验显示出 ,提出的算法的性能明显好于原系统的启发式算法 ,最好的改进率达到 7.0 4 % .The optimal turned out slab pile(TOSP) problem in the slab yard of iron & steel industry is formulated as a binary integer programming model in this paper. This is a quadratic programming model and the coefficients of the objective function are related to the values of variables. Because of NP hardness of TOSP problem, it is difficult, or even impossible, to find the optimal solution to the large scale actual problem. In order to solve TOSP, this paper develops the modified genetic algorithm(MGA) for this problem:1) to construct the genetic coding suitable for the optimal TOSP problem. It can not only generate feasible initial chromosomes, but also ensure chromosome feasibility after crossover and mutation.2) to form a MGA framework:a new cultivating operation is introduced; and crossover operationis improved. The computational experiments with the selected cases of the randomly produced problems show that the proposed new MGA is remarkably better than the original heuristics for Tosp problem, with the best improvement of 7 04%.

关 键 词：板坯酸垛 整数规划 遗传算法 热轧 轧钠 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]