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

对钢铁企业板坯库中的最优倒垛问题建立了0和1整数规划模型.这一模型是一个 二次规划模型,且目标函数的系数与变量的取值相关联,属于NP-难问题,获得较大规模的最 优解是不可能或非常困难.为了求解此问题,本文构造了改进遗传算法:(1)提出了适合于最 优倒垛问题的遗传编码,运用此编码,不但能够产生可行的初始染色体,而且能够保证在交叉 和变异操作后的染色体仍然可行;(2)改进了遗传算法结构,在新的结构中,增加了一个培育 操作,改进了交叉操作.通过精选随机产生的问题例子的实验显示出,提出的算法的性能明显 好于原系统的启发式算法,最好的改进率达到7.04％.

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

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 operation is 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%.