（钢铁冶金专业论文）炼钢连铸优化排程的基础研究.pdf

内蒙古科技大学硕士学位论文 摘要 炼钢一连铸优化排程是目前的研究热点，东北大学唐立新、北京科技大学李铁克，国外 的c o n w a y 、n u m a o 等在这方面做了很多研究工作。炼钢一连铸排程是n p 完全问题，由于其 计算的时间复杂性很高，解空间很大，针对该模型文献中遗传算法，模拟退火等算法的计 算速度无法满足进度控制的要求。 炼钢一连铸排程问题的三约束模型含三维决策空间：任务委派，冶炼次序和冶炼时间。 当工艺路径复杂，连浇炉数多，各铸机的钢种不同时，前两个维度的组合数十分庞大。本 文提出一种维度变换方法，将任务委派和冶炼次序维度变换为承接外包的序列点和宜于外 包的炉次，缩小了可行解的空间。 文中确立了日程评价指标。连铸是一个工件成组问题( j o bg r o u p i n g ) ，因此连续性是 首要的评价指标。转炉是瓶颈，因此转炉负载的比例性是文中确立的第二个评价指标。设 备节奏性和工件节奏性是日程鲁棒性的支撑条件。三个评价指标用于确立最优解。 本研究为基础研究，为b 厂进度控制系统调试和改进算法提供了标杆( b e n c h m a r k ) 。 该进度控制系统已经在b 厂投入运行。 关键词：炼钢，连铸，优化，排程，标杆 内蒙古科技大学硕士学位论文 a b s t r a c t s t e e l m a k i n g - c o n t i n u o u sc a s t i n gs c h e d u l i n go p t i m i z a t i o ni sah o tr e s e a r c ht o p i c s ，o nw h i c h a l o to fr e s e a r c hw a sc a r r i e do u tb yt a n gl i x i n ，l it i e - k ea n dm a n yo v e r s e a ss c h o l a rs u c ha s c o n w a y ，n u m a o s t e e l m a k i n g - c o n t i n u o u sc a s t i n gs c h e d u l i n gi san p - c o m p l e t ep r o b l e ma n dt h e s p a c eo fi t ss o l u t i o ni sv e r yb i g t h u s t h ec o m p u t i n gs p e e do fa l g o r i t h m ss u c ha sg e n e t i ca l g o r i t h m a n ds i m u l a t e da n n e a l i n ga l g o r i t h mi nt h el i t e r a t u r ec a nn o tm e e tt h er e q u i r e m e n t so fs c h e d u l e c o n t r 0 1 t h et h r e e - c o n s t r a i n tm o d e lo fs t e e l m a k i n g - c o n t i n u o u sc a s t i n gs c h e d u l i n go b t a i n st h r e e d i m e n s i o nd e c i s i o ns p a c e ：t h et a s ka s s i g n m e n t ，t h ep r o c e s s i n gs e q u e n c ea n dt h et i m et a b l e c o m b i n a t o r i a ln u m b e ro ft h ef i r s tt w od i m e n s i o n si sv e r yh u g pw h e nt h ep r o c e s s i n gr o u t ei s c o m p l e x ，t h es i z eo fc o n t i n u o u sc a s t i n gi sl a r g ea n dt h es t e e lg r a d eo fe a c hc a s t i n gm a c h i n ei s d i f f e r e n t t or e s o l v et h i sp r o b l e m ，d i m e n s i o nt r a n s f o r mw a sp r o p o s e e di nt h i sp a p e r , t h ed i m e n s i o n o ft h et a s ka s s i g n m e n ta n dt h ep r o c e s s i n gs e q u e n c ea l et r a n s f o r m e di n t op r o p e rp o s i t i o ni ns e q u e n c e t oa c c e p to u t s o u r c i n ga n dp r o p e rh e a tf o ro u t s o u r c i n g , w h i c hg r e a t l yr e d u c e dt h ef e a s i b l es o l u t i o n s p a c e s c h e d u l ee v a l u a t i n gi n d i c a t o rw a sp r o p o s e di nt h i st h e s i s t h ec o n t i n u o u sc a s t i n gs c h e d u l i n gi s a j o bg r o u p i n gp r o b l e m t h e r e f o r et h ec o n t i n u i t yi st h em o s ti m p o r t a n te v a l u a t i n gi n d i c a t o r t h e c o n v e r t e ri sab o t t l en e c k , a n dt h ec o n v e r t e rl o a d sp r o p o r t i o n a l i t yi st h es e c o n de v a l u a t i n gi n d i c a t o r t h ee q u i p m e n t sr h y t h m i c i t ya n dt h ew o r k p i e c e sr h y t h m i c i t ya r e t h es u p p o r tc o n d i t i o n so f s c h e d u l er o b u s t n e s s t h r e ee v a l u a t i o ni n d i c a t o rw a se f f e c t i v e l yu s e di nc h o o s i n gt h eo p t i m a l s o l u t i o n t h i sr e s e a r c hw a st h eb a s i cr e s e a r c h ，w h i c hp r o v i d e sab e n c h m a r kf o rt h es c h e d u l ec o n t r o l s y s t e mt od e b u ga n dt oi m p r o v ea l g o r i t h mi nb a o t o us t e e lf a c t o r y t h i ss c h e d u l ec o n t r o ls y s t e m h a sa l r e a d yr u ni n t oo p e r a t i o ni nb a o t o us t e e lf a c t o r ys h e e t m e t a lm i l l k e yw o r d s ：s t e e l m a k i n g ，c o n t i n u o u sc a s t i n g , o p t i m i z a t i o n ，s c h e d u l i n g , b e n c h m a r k 2 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 内蒙古科技大学或其他教育机构的学位或证书所使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并 表示了谢意。 签名： 日期：习：丛 关于论文使用授权的说明 本人完全了解内蒙古科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 签名： ( 保密的论文在解密后应遵循此规定) 且薄 导师签名： 吼华 内蒙古科技人学硕士学位论文 引言 炼钢连铸优化排程实际上是解决在一定设备、资源约束条件下，如何安排设备， 以实现一个时间段内生产最大化的问题。它以提高生产效率，缩短交货期，降低库存等 为目标，在现代钢铁工业生产中扮演着重要的角色。如何构建先进、高效的优化排程系 统成为今天许多企业研究的热点之一。在本部分中，首先对炼钢一连铸生产背景进行了 简要分析，然后对本论文的主要内容和安排进行了介绍。 ( 1 ) 研究背景及意义 激烈的市场竞争对钢铁企业的生产管理特别是生产计划与调度管理提出了越来越高 的要求。市场的高要求，高产量，多品种增加了企业生产调度的困难性。旧的生产调度 模式，落后的人工调度方式已经满足不了现代化的生产需求，容易造成宏观生产失控， 实时监控紊乱等方面的问题，严重制约了生产力的发挥。生产计划与调度系统是钢铁企 业制造执行系统( m e s ) 的核心，在现代钢铁工业生产中扮演着重要的角色【。构建先 进，高效的生产计划与调度系统，可以大大提高生产计划调度的全局性、准确性、及时 性，加强对生产过程突发事件的处理能力，加强各生产环节之间的衔接，充分发挥企业 现有资源的生产能力，提高企业效益【2 ，3 ，4 1 。 b 厂c s p 生产线是由2 x 2 1 0 吨转炉、1 台l f 精炼炉、1 台c s p 连铸机构成。由于2 座转炉的生产能力远远大于c s p 连铸机的连铸能力，所以炼钢一连铸的钢水调度问题就 变得相对简单。通常是由车间调度人员，按照生产部下达的生产计划，根据自己的丰富 经验手工编制一个计划，就可以完成炼钢一连铸的生产调度。 2 0 0 7 年下半年，b 厂在原有c s p 生产线的基础上，新增宽厚板生产线，同时新增了 两台精炼炉( 一台l f 精炼炉，一台r h 精炼炉) 。新增的宽厚板生产线使得两座转炉同 时向c s p 和宽厚板提供钢水，两座转炉的生产能力和两台连铸机的连铸能力相当，而且 c s p 和宽厚板的产量不同。由于生产原料，装置操作和市场需求随时都可能发生变化， 因此所作的生产计划与调度安排，也常常要随时进行修改，这些安排和修改的工作量很 大，又有时间限制，有时安排不尽合理，甚至偶有错误，也是在所难免。这样导致炼钢 一连铸生产过程中钢水的排程问题的难度增加，继续采用以前那种人工编制调度计划的 方法难以解决b 厂目前复杂的生产调度问题。 本课题的研究工作是国家自然基金项目：钢铁制造短流程动态调度的基础研究( 批 准号7 0 6 6 2 0 0 2 ) 的一部分。 本课题的研究工作为b 厂在原有c s p 生产线的基础上新增宽厚板生产线后，转炉调 度钢水难度增加的问题提供了依据，为炼钢一连铸优化排程起到了指导性的作用，保证 生产流程连贯有序的进行。为提高本厂的生产能力、提高产品质量、减少库存、降低运 行成本、提高本厂的经济效益等具有重要的意义。 内蒙古科技大学硕士学位论文 ( 2 ) 本论文的主要研究内容及安排 基于以上背景分析，本课题针对b 厂炼钢一连铸排程存在的实际情况，探讨炼钢一连 铸优化排程的有效求解方法和优化模型的问题。本文以b 厂两座转炉共享钢水为主要研 究内容。 本文共分五部分。 第一部分，引言，简要介绍了本文的研究背景，即炼钢一连铸优化排程基础研究对 文献算法改进的必要性，及目前炼钢一连铸优化排程问题所做的工作及现状。 第二部分，文献综述，主要陈述炼钢一连铸排程问题的求解方法，并对几种方法进 行了比较和评述以及各种方法的应用效果。对各种求解方法进行了归纳、总结的基础 上，提出了本课题的思路。 第三部分，分析了b 厂炼钢一连铸排程实际存在的问题，介绍了模型的求解及如何 对结果评价。 第四部分，以b 厂炼钢一连铸2 4 小时工作时间内实际生产数据为例进行计算并对结 果分析评价。 第五部分，结论。 内蒙古科技人学硕士学位论文 1 绪论 1 1 炼钢连铸生产工艺流程 炼钢一连铸的生产为流程式生产。炼钢一连铸生产过程作为钢铁企业的关键工序，一 般包含若干个转炉、精炼和连铸设备，先由转炉把废钢或者铁水冶炼为钢水，钢水再通 过精炼炉进行调质和调温处理，然后由连铸机完成浇铸，并切割成各种尺寸的板坯，供 给下游生产工序或用户。从生产工艺的角度来看，本文所考虑的炼钢一连铸生产流程包 括炼钢，精炼和连铸三道工序。 ( 1 ) 炼钢 广义上说就是铁水通过氧化反应脱碳、升温、合金化的过程。它的主要任务是脱 碳、脱氧、升温、去除气体和非金属夹杂、合金化。炼钢的工艺过程是把高温条件下的 铁水进一步冶炼为含碳量更低的钢水，其基本作用是：降低含碳量；除去硫、磷等杂 质；调节合金元素的含量。 ( 2 ) 精炼 为了保证连铸机浇注出的板坯符合特定钢种的要求，冶炼出站的钢水还需要进行精 炼。精炼的作用是进一步调整钢水的温度和化学成分，另外也给连铸机协调进站，钢水 满足连续浇注提供了缓冲的空间，当炉次钢水提前到达连铸机时，可以在精炼炉上停 留，从而避免炉次在连铸机前等候、保证钢水的温度。 ( 3 ) 连铸 连续铸造是一种先进的铸造方法，其原理是将熔融的金属不断浇入结晶器中，凝固 了的铸件，连续不断地从结晶器的另一端拉出，它可获得任意长或特定长度的铸件。连 铸的发展引发了冶金工业的一场革命，连铸以显著提高钢材的成材率、缩短工艺流程、 节省大量厂房设备和物料运输、提高警惕产品质量的优势而迅速取代了模铸和初轧、开 坯工艺。目前世界先进国家连铸比9 6 ，而我国连铸比也以迅速的步伐超过了7 0 。 炼钢一连铸生产过程中，连铸机要求“定时、定温、定品质”地提供钢水，实现准 时制调度，而炼钢炉和精炼炉直接允许有一定的等待时间，因此，合理的安排炼钢炉、 精炼炉的生产节奏显得极为重要。 炼钢一连铸生产的工艺流程如图1 1 所示，一个炼钢厂会有多台炼钢设备、精炼设 备、浇铸设备以及相应的生产辅助设备，钢水一般要经过“炼钢一精炼一连铸”这样三个 大的工序铸造成坯，在炼钢和精炼的过程中还可能涉及多重处理。从现有的研究来看， 一般是把炼钢一连铸生产计划调度问题归结为在批量计划( 炉次和浇次计划) 的基础 上，以炉次为最小计划单位，以某一目标函数( 如最小等待时间、最小提前拖期费用 内蒙古科技大学硕士学位论文 或最小总流程时间) 最优为评价的一类多工件、多工序、多机的特殊车间作业排序问 题。其最终结果是要确定在何时、在何种设备上以何种顺序安排钢水从炼钢到连铸的生 产过程的各个工序 5 1 。 图1 1 炼钢连铸生产工艺流程示意图 1 2 炼钢连祷生产过程特点 炼钢一连铸是钢铁生产中重要的一个环节。铁水在转炉冶炼成钢水，经精炼处理 后，送至连铸机浇铸成满足合同要求的不同钢种、规格的钢坯，以供应市场或轧钢工序 需求。 从生产的组织管理、生产工艺要求和信息构成等方面分析，上述生产过程具有以下 特点和要求【6 】： ( 1 ) 间歇与连续方式相混杂的多阶段混合流程式生产过程。转炉、精炼设备为间 歇作业方式，为提高作业效率、降低机器设置次数和生产成本，连铸机在其中间包寿命 之内为连续作业方式。生产的总流程为炼钢一精炼一连铸，包括多个生产工序，各工序 又存在着多个( 多种) 生产设备，生产过程为多阶段混合流程式的。 ( 2 ) 物流衔接紧密，具有准时制要求。连铸生产工艺要求在一个连续生产周期内 浇铸的钢水成分和温度满足一定的工艺限制条件，必须协调间歇式和连续式作业工序的 生产节奏，使工序间物流传递满足正确成分、温度和时刻的要求，保证生产的持续性， 即最大限度的连铸。 ( 3 ) 产品种类、规格繁多，结构复杂。铸坯产品的钢种、规格繁多，决定了其产 品结构的复杂性。 ( 4 ) 生产管理与控制多种信息、多种功能集成。炼钢一连铸生产过程调度管理要 求实时监视各设备作业状态、跟踪各工序物流状态，在此基础上在线编制和调整调度计 划，实现整个生产过程的动态管理和控制。来源于管理级、过程自动化级、基础自动化 内蒙古科技大学硕士学位论文 级的多种性质、频度、用途及响应时间的不同信息在系统中有机集成，满足生产过程监 视、调度计划编制、设备管理、数据查询、统计报表等功能需求。 ( 5 ) 生产调度计划编制快速性与在线重调度能力。炼钢一连铸生产调度属混合流 程车间类调度问题，己被证明为n p 难题。实际生产情况的多变性和不稳定性决定了建 模的困难性和不准确性，要求系统能够准确构造适合现场情况的调度计划模型，快速编 制生产调度计划，并具有在线修改、重新生成新调度计划等机制。 1 3 炼钢连铸优化排程系统 在工业企业中，计划与调度系统是生产活动的组织和管理中心，它承担着生产活动 的分析和优化任务，并针对市场等环境因素的变化，为企业生产活动赋予柔性 和敏捷性，以实现企业利润的最大化r7 。 炼钢连铸生产计划与调度系统根据来自公司级计划系统的生产订单，制定生产作 业计划，将其转化为面向过程控制计算机的生产指令。对生产过程进行动态调整，包括 计划与调度、生产指令下达、数据采集与分析等功能。根据来t i 过程计算机的生产实绩 向公司计划系统报告生产订单的完成情况。与外部系统( 炼铁厂和轧钢厂) 进行计划协 调。工艺过程计算机负责接受生产指令，控制设备生产，向炼钢一连铸生产调度系统提 供有关生产实绩的信息 8 1 。图1 2 为炼钢一连铸车间生产调度环境。 图1 2 炼钢连铸车间生产调度环境 从计算机集成制造( c i m s ) 的角度来说，炼钢一连铸生产计划与调度系统是钢铁企 业的重要部分。炼钢一连铸生产计划与调度是在批量计划( 炉次和浇次计划) 的基础上， 以炉次为最小计划单位( 相当于机械行业的工件j o b ) ，在追求某一评价函数( 如最小等待 内蒙古科技大学硕士学位论文 时间、最小提前拖期费用或最小总流程时间) 最佳的情况下的一类多工件、多工序、多 机的特殊的j o b 。s h o p 排序问题。其最终结果是确定在何时、在何种设备上以何种顺序安 排钢水从炼钢炉到连铸机的生产过程的各个工序。它和一般机械力n - r _ 业生产调度问题的 最大区别，在于钢铁生产工艺的特殊性要求。炼钢一连铸生产过程，是被加工对象在高 温下，由液态( 钢水) 向固态( 拉铸成坯) 的转化过程。对物流的连续性与流动时间 ( 在各设备上的处理时间及工序设备之间的运输等待时间) 都有极高的要求，总体上属 于间歇准连续的工艺流程1 9 j 。钢铁企业的生产是一个从炼铁、炼钢、连铸直到热轧 冷轧的长流程的过程。要构建高效的c i m s 体系，就必须将这些工序的生产无缝的衔接 起来，而炼钢一连铸优化排程系统显然是重中之重，只有对炼钢一连铸生产过程进行很 好的控制和管理，才能使整个生产过程前后有序，达到成本的最小化和效益的最大化。 从钢铁企业e r p 的角度来说，加入w t o 给中国的钢铁企业带来了极大的挑战，同 时，信息时代的到来，也加快了我国钢铁企业实施e r p 的步伐。而炼钢一连铸优化排 程系统是钢铁企业生产中最为重要的部分。因此，可以说，没有炼钢一连铸优化排程系 统的成功，钢铁企业就不可能成功的推行e r p 。 从作业排序理论的角度来看，在传统的作业排序问题( 诸如f l o w s h o p 、j o b s h o p 排 序问题上) ，前人已经展开了广泛的研究。针对不同的设备数、工件数、加工路线和作 业排序目标，可以将这些问题划分为不同类型的问题。其中一部分已经得出了有效并证 明能得到最优解的启发式算法，如2 台设备n 个工件、以总流程时间最短为目标的 f l o w s h o p 问题，可以用j o h n s o n 算法来求解，所得出的解己被证明是最优解。但是，对 于稍微复杂的问题( 比如大多数j o b s h o p 排序问题) ，理论界尚未找到多项式时间算 法。而且，这里所探讨的炼钢一连铸生产计划与调度系统，除了本身具有的多机并行、 连续浇注的特点及难点外，还有无等待( 中间无库存) 、温度降低损失等特殊约束。因 此，炼钢一连铸生产计划与调度系统的研究为作业排序理论提供了有效的求解方法。 1 a 优化排程在炼钢连铸生产过程中的作用 炼钢一连铸生产过程是现代钢铁企业的核心工序，转炉把从高炉炼得的铁水进一步 冶炼为钢水，在精炼炉进行精炼以保证钢水的化学成分和温度，然后在连铸机浇注成各 种尺寸外形的板坯，供给下游生产工序或用户。因此，炼钢一连铸生产计划与调度对确 保钢铁企业生产的高效运行起着非常重要的作用。有以下四个方面： ( 1 ) 炼钢、精炼和连铸的衔接 炼钢一连铸是钢铁生产的关键环节，炼钢一连铸生产调度需要协调冶炼、精炼、连 铸三个工序的生产节奏，在满足对钢水温度以及连续浇注等工艺要求的前提下，充分利 用有限的设备资源、降低物耗和能耗，提高炼钢一连铸生产效率，并确保与后续轧钢工 内蒙古科技大学硕士学位论文 序的合理衔接与匹配。 在钢铁企业中，炼钢一连铸的生产在计划的连续性和通过时间方面有严格的要求和 限制，其中连铸机不仅有较长的作业时间以及安装时间，而且对计划的连续性有严格要 求，是生产过程中的瓶颈设备，生产计划与调度以连铸为中心。如果调度不合理，使计 划钢水在系统中等待、停留时间过长，就会引起钢水温降，当钢水温度不能满足连铸的 开浇温度，就可能导致断浇，现场就需要花费较长的时间和较多的材料消耗重新开浇， 造成不必要的损失。因此炉次不能在生产中有太长的等待，也不能太晚达到连铸机，即 提前和拖期都是不合理的，这实际是一种准时制的生产过程，对现场调度有较高的要 求。 ( 2 ) 品种、质量的衔接。为了生产高质量、高附加值产品，必须重视与连铸相配 套的炉外精炼技术、低过热度浇铸技术、电磁搅拌技术、无缺陷铸坯生产技术等。同时 为了保证成材的组织、性能，必须选择合适的连铸坯断面尺寸和压缩比应不小于6 ，较 高级产品的压缩比应不小于8 ，对于异形断面型钢，还必须考虑腰、腿各部的压缩比， 防止局部因加工不足而产生拉裂、皱纹等缺陷。对高级用途或中、高碳品种，要注意防 止铸坯的中心疏松、中心裂纹等对产品的不利影响。压缩比应在1 0 以上。 ( 3 ) 能量的衔接。在有条件的情况下，应争取提高连铸坯的出坯测试和争取热 装、热送或直接轧制，以最大限度地节能。目前世界各国正在争相研制和推广短流程工 艺、连铸坯带液芯轧制技术、以及有利于节能的热送方法和加热炉，这些都应引起足够 的重视。 ( 4 ) 生产能力的衔接。连铸的速度较慢而轧制的速度较快，连铸一旦开始就不能 中途停顿，而轧制则有换辊、换孔型和临时故障停机等问题，因此一旦衔接不好，就会 影响生产，造成冷坯落地。因此在车间平面布置和生产组织上都应有缓冲环节，如缓冷 坑、隧道式加热炉、热卷曲机等。最新推出的坯料头尾焊接、无头轧制技术，可减少中 途停机时间，许多现代化轧钢厂还设置了快速换辊及导卫装置，并采用计算机管理模 式，这些都有利于实现连铸连轧。为了使连铸和轧钢这两个工序能相互匹配，工艺布置 上一般的做法是用两台以上的连铸机或多流连铸机与一套连轧机相匹配，两个机组相距 很近，并设热坯摆渡车和冷坯台架，保温坑或双层保温、热交换炉等，各厂根据自己的 条件有不同的形式。 内蒙古科技大学硕士学位论文 2 文献综述 2 1 炼钢连铸优化排程求解方法 优化排程问题实质上是一种多约束、多目标的组合最优化问题。 组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是通过数学方法的研究去寻找离散事件的最 优编排、分组、次序或筛选等，是运筹学( o p e r a t i o n sr e s e a r c h ) 中的一个经典和重要的 分支。一个组合最优化问题可用三个参数( d ，f ，f ) 表示，其中d 表示决策变量的定 义域，f 表示可行解区域f = x l x e d ，甙x ) o ) ，f 中的任何一个元素称为该问题的可行 解，f 表示目标函数。满足f ( x 木) = t 】f l i i l f ( x ) ix e f 的可行解x 宰成为问题的最优解i l 。组合 最优化问题的特点是可行解集合是有限点集，其最优解是可以得到的。但实际问题的可 行解集合往往非常巨大，很难通过有效的方式从所有可行解中寻找最优解。故在实际求 解中往往采取一定的搜索策略或规则，从部分可行解中寻找较为合适的方法。 2 1 1 经典优化算法 经典优化算法属于精确算法，它总能保证寻求到问题的最优解。如d a n t z i n g 在2 0 世界4 0 年代提出的求解线性规划的单纯形法、l a n d 和d o i n g 与1 9 6 0 年提出的分支定 界法、b a l a s 于1 9 6 5 年提出的求解0 1 整数规划的隐枚举法等，都属于精确算法。许多 组合优化问题是n p h a r d 问题，通常认为n p h a r d 问题无法在多项式时间内求得最优 解。在经典算法在遇到大规模或超大规模的组合优化问题就会出现解空间膨胀问题，随 着问题规模的增大，求解难度将呈指数规律递增，算法一般无法在可接受的时间范围内 获得问题解。可见，在求解大规模的组合优化问题时，经典算法的计算量偏大，故经典 算法一般只能用于解决小规模的组合优化问题。另外，经典算法必须遵从模型形式，而 现实问题则往往存在这样那样的限制，有时很难将问题抽象成经典算法适用的模型形 式，这从另一个方面限制了经典算法的应用。常见的经典算法有以下三类。 ( 1 ) 线性规划法( l i n e a rp r o g r a m m i n g ) 。线性规划的数学含义是在满足一组线性 约束条件下，求出多变量线性函数的最优值。线性规划是运筹学的基本分支，1 9 4 7 年 d a n t z i g 提出的求解线性规划基本方法一单纯形法已有半个世纪的历史。1 9 7 9 年 k h a c h i g a n 提出计算线性规划的新方法一椭球法，证明了该方法在最坏计算量意义下为多 项式时的算法，因而在理论上胜过单纯形法，但实际计算效率明显劣于单纯形法。1 9 8 4 年k a r m a r k a r 提出求解线性规划问题的多项式时的算法，其计算效率也比单纯形法好。 受此方法启发，内点算法范畴里各式各样的方法被提出来了。原始对偶内点法是这类算 法中最重要和最有用的算法。以后基于线性规划的内点算法被推广到线性约束的凸二次 内蒙古科技人学硕士学位论文 优化和非线性规划问题。 ( 2 ) 整数规划法( i n t e g e rp r o g r a m m i n g ) 。整数规划是一类要求变量取整数值的数 学规划。若在线性规划中要求变量取整数值，则为线性整数规划( l i n e a ri n t e g e r p r o g r a m m i n g ) 。而对于仅要求部分变量为整数的数学规划问题，则称为混合整数规 划。对整数规划问题比较适用的解法有：适于纯粹整数规划( 所有自变量限制为整数) 问题的割平面法，适于0 1 整数规划问题的隐枚举法，以及适于任意整数规划问题的 分支定界法等。 ( 3 ) 分支定界法( b r a n c ha n db o u n d ) 。分支定界法是本世纪六十年代由 l a n d d o i g 和d a k i n 等人提出的一类求解整数规划或混合整数规划问题的方法，该方法 灵活且便于计算机求解，所以应用非常广泛。其基本思想是先求出整数规划问题a 所对 应的线性规划问题b 的最优解，如果该解不符合a 的整数条件，那么b 的最优目标函数 必是a 的最优目标函数的上界，而a 的任意可行解的目标函数值是其最优值的下界，然 后将b 的可行域分成子区域( 成为分支) ，逐步减小上界和增大下界，最终求得最优 解。 ( 4 ) 动态规划法( d y n a m i cp r o g r a m m i n g ) 。动态规划是运筹学的一个分支，是解 决决策过程( d e c i s i o np r o c e s s ) 最优化的数学方澍1 1 】。1 9 5 1 年，美国数学家b e l l l m e n 等人在研究多阶段决策过程的优化问题时，提出了著名的最优性原理。他们根据多阶段 过程的特点，将问题转化为一系列单阶段问题，然后逐个加以解决。最后求出整个问题 的最优决策序列。他们提出的“最优性原理 表明，在求解的每一个阶段中，最后的最 优策略只取决当前的状态，这样就创建立最优化问题求解的动态规划方法。动态规划的 实际应用非常广泛，在经济管理，生产调度，工程技术和最优控制方面都得到了广泛的 应用。黄可为等1 1 2 j 提出的炼钢组炉问题优化模型及其动态规划算法为动态规划在炼钢生 产中应用的一个很好的实例。他针对炼钢组炉计划编制中的集约优化问题，建立了各优 化目标下的数学模型，并利用动态规划法，对该优化问题进行了求解，经算法时间复杂 性分析和实际生产数据仿真演算，结果表明在一定的生产条件下，该算法能在合理的时 间范围内给出一批合同最优的组炉方案。 2 1 2 启发式算法 启发式算法是解决n p h a r d 问题的常用方法，它是建立在经验和规则判断基础上 的一种快速、近似的方法。启发式方法可以这样定义i ”j ：启发式算法是一种技术，这种 技术使得在可接受的计算费用( 指计算时间、占用空间等) 内去寻找最好的解，但不一 定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近 似程度。启发式方法的应用必须以对问题的深入研究为日仃提，只有在深入了解问题需求 内蒙古科技大学硕士学位论文 和结构后，才能提出合理有效的实现方法。另外，实际应用中，往往尝试采用不同的启 发式规则对问题进行求解，从最后结果中选择最好的解。启发式方法的种类繁多，常见 的方法有： ( 1 ) 基于规则的算法( r u l ep r o g r a m m i n g ) 。所谓基于规则的算法既是根据问题的 具体特征，按照经验设计解的创建策略，由此给出设计者认为合适的解。该解的效果与 设计者的经验能力直接相关。 ( 2 ) 启发搜索算法。启发搜索算法的核心问题是构造启发函数，用启发函数的思 想去解决传统的运筹学问题，可以提高求解的效率。启发搜索方法是解决运输和指派问 题较为有效的方法之一。 ( 3 ) 拉格朗日松弛算法( l a g r a n g i a nr e l a x a t i o n ) 。在大多数情况下，减少原问题 的部分约束往往使问题变得更容易求解。而拉格朗同松弛算法的基本原理正是将问题较 难解决的约束转换到目标函数中，同时保留问题的原有性质，经转化的问题将变得容易 求解。另外，拉格朗日方法能够给出问题的下界，并且可以和其它算法结合使用，大大 提高了算法效率。 ( 4 ) 专家系统方法【1 4 】。专家系统同样体现了一种规则思想。系统设计者们在研究 大量的专家知识和经验后，将实际中各种模糊的逻辑规则转化为一条条计算机可识别的 应用规则，形成计算机专家系统所需的知识库。专家系统然后根据现场情况从知识库中 产生调度方案，并能对意外情况采取相应的对策。专家系统和其它启发式方法一样，难 以评估所得到解的性能，另外其稳定性较差，即使问题规模发生细微的变化，也可能造 成问题最终解的较大变动，而这时往往需要对知识库进行更新，以适应问题变化后的要 求。 2 1 3 智能算法 实际生产问题形式越来越复杂，问题规模越来越庞大的情况下，使用经典优化算法 已经逐渐无法满足，而启发式算法无法保证解的优良性，且严重依赖于问题形式和设计 者对问题的了解程度。在这种背景下，研究者们从2 0 世纪8 0 年代初开始提出各种智能 计算方法。这些算法的实质依然是启发式规则，它们以求组合优化问题的全局最优解为 目标，但并不保证最终所得解与问题最优解的偏离程度。 ( 1 ) 遗传算法( g e n e r i ca l g o r i t h m ，g a ) 。遗传算法是在2 0 世纪7 0 年代初期由 美国密歇根( m i c h i g a n ) 大学的h o l l a n d 教授发展起来的。1 9 7 5 年，h o l l a n d 教授由于 受到生物进化论的启发提出的基于“适者生存”思想的一类高度并行、随机、自适应搜 索算法，即遗传算法。与其它启发式方法搜索顺序空间不同，遗传算法以解的种群作为 工作单元，模仿生物进化的适者生存原则指导搜索，改进目标。遗传算法逐渐发展成为 内蒙古科技大学硕士学位论文 一种通过模拟自然进化过程解决最优化问题的计算模型。利用遗传算法解最优化问题， 首先应对可行域中的点进行编码( 一般采用二进制编码) ，然后在可行域中随机挑选一 些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编码的 适应度。接着就像自然界中一样，利用选择机制从编码组中随机挑选编码作为繁殖过程 前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本，而适应度较低的 解则保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变 异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变 异算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁殖就产生 了下一代编码组。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最 后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。 ( 2 ) 模拟退火算法( s i m u l a t ea n n e a l i n g , a l g o r i t h m ，s a ) 。退火算法模拟思想最早 由m e t r o p o l i s l l 5 】在1 9 5 3 年提出，并由l ( i r kp a 仃i “1 6 】在1 9 8 3 年成功应用在组合优化问题 中，实践证明，模拟退火算法适合求解大规模组合优化问题，是一种求解n p h a r d 问 题的有效算法。s a 算法的出发点是基于物理退火过程和组合优化问题之间的相似性， 它是一种基于m o n t ec a r l o 迭代求解策略的随机寻优算法。需要指出的是，模拟退火算 法的收敛速度较慢，这对其应用的限制较大。 ( 3 ) 禁忌搜索算法( t a b us e a r c ha l g o r i t h m ，t s ) 。禁忌搜索算法是局部领域搜索 算法的推广，是人工智能在组合优化算法中的一个成功应用。1 9 8 6 年，g o l v e r 首先提 出了禁忌搜索的概念，进而形成了一套完整的算法。禁忌搜索算法为避免搜索结果掉入 局部最优，在搜索过程中引入搜索的历史信息，通过一个禁忌表来记录曾经历的局部最 优点，以此来指导算法在以后的搜索中不再或很少经过之前的局部最优点，从而达到跳 出局部最优解的目标。 ( 4 ) 人工神经网络算法( n e u r a l n e t w o r ka l g o r i t h m ，n n ) 。1 9 4 3 年，美国生理学家 m c c u l l o c h 和数学家p i t t s 建立了一个用来解决简单分类问题的模型，认知模型。认知 模型被认为是最早的神经网络模型。由于认知模型无法解决异或问题，人工神经网络的 研究一度陷于低潮。直到2 0 世纪8 0 年代，h o p f i e l d l l 7 , 1 8 j 将人工神经网络成功地应用于 组合优化问题中，m c c l e l l a n d 和r 岫e l h a n 【1 9 】构造的多层反馈学习算法成功地解决了单 隐含层认知网络的“异或”问题及其它的识别问题，才使神经网络重新成为研究的热 点。i j u 掣2 0 】提出一种用神经网络选择调度规则的方法，神经网络的输入对应于所有待 调度工件的加工路线和加工时间信息，输出对应于待选的调度规则。但该方法需要大量 的训练样本和很长的训练时间才能保证调度的效果；另外，随着问题规模的增大，网络 的规模也将急剧增大。 ( 5 ) 蚁群算法( a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ，a c o ) 。蚁群算澍2 1 j 是模仿真 内蒙古科技大学硕士学位论文 实的蚁群行为而提出的一种模拟进化算法。蚂蚁在行走过程中会在其经过的路上释放一 种信息素，后来的蚂蚁就可以根据这种信息素来指引自己的行动方向。这是一种正反馈 现象，当一条路径上经过的蚂蚁越多，其上的信息素浓度则越浓，而这条路径就最有可 能被后来的蚂蚁所选择。利用蚁群算法求解t s p 问题是蚁群算法一个极为形象的应 用。需要注意的是，蚁群算法求解t s p 问题的运算速度往往较慢。 ( 6 ) 微粒群算法( p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ，p s o ) 。1 9 9 5 年， k e n n e d y 和e b e r h 一2 2 2 3 1 等通过模拟一个简单的社会模型，开发了一种演化技术，即微 粒群算法。算法可用来求解复杂的优化问题。 上面列举的智能算法中，g a 、s a 、t s 和n n 等经过几十年的改进和发展，在理论 上和应用上都已获得巨大的进展。 在生产实际中应用各种现代优化算法时，由于实际遇到的问题往往存在这样那样的 差异，这就需要对原始算法做出一项改进，或者结合多种算法，取长补短，方可得到令 人满意的结果。 2 2 炼钢连铸优化排程问题研究现状 在过去的几十年中，人们对调度问题进行了大量的研究工作。从上个世纪5 0 年代 起，调度问题的研究就受到应用数学、运筹学、工程技术等领域科学家的重视，科学家 们利用运筹学中的线性规划、整数规划、目标规划、动态规划及决策分析方法，研究并 解决了一系列有代表意义的调度和优化问题。但是，人们普遍把c o n w a y ，m a x w e l l 和 m i l l e r 三人有关调度的研究工作作为调度理论研究的正式开则2 4 】，他们三人也被人们称 为调度理论的奠基人。此后3 0 多年的调度理论和应用研究都受到他们的影响。 2 0 世纪7 0 年代，人们开始注意并重视调度复杂性问题的研究，提出了用于研究算 法有效性和问题难度的计算复杂度理论瞄j ，许多调度问题被证明为n p 完全问题【1 2 1 。 2 0 世纪7 0 年代后期，经典调度理论取得了重要进展，并且作为一门应用数学学科 已经基本成熟，但是实际调度问题与经典调度问题还有相当的距离。有关调度理论没有 在实践中大规模应用的原因有很多说法，一种比较有说服性的说法是这样的：现有的调 度理论和方法对于解决实际调度问题仍然是不够的，需要重新考虑和进一步扩剧2 6 。 当然，严重阻碍经典调度理论研究取得重大进展和突破的关键还是调度问题的n p 性 质，实际调度问题往往都是非常复杂的，没有确定的物理和自然规律可循，因此是非常 难解的，并且大多是没有精确解的。因此，仅仅依靠经典调度理论中基于解析优化的技 术和方法，试图解决属于n p 完全问题的实际调度问题，不可避免地会遇到难以逾越的 障碍。 从2 0 世纪8 0 年代初开始，人们就一直在尝试并致力于解决实际调度问题，调度 内蒙古科技大学硕士学位论文 研究由理论研究转向应用研究阶段。在这样的历史背景下，应用人工智能、计算智能和 实时智能研究成果，解决实际调度问题的智能调度方法就走上了历史的舞台。大量的文 献反映了这方面的情况。n u m a o 等【2 7 l 用人工智能和人机交互结合解决炼钢一连铸调度 问题，d o m 掣2 8 】提出了基于f u z z y 集合和人工智能相结合的方法研究炼钢一连铸调度 问题。奥地利g m b h 钢厂给出炼钢一连铸调度的建模关键因素，并对炉次在机器上的分 配给出了调度模式1 2 9 。 我国钢铁企业优化排程问题的研究，起步较晚、方法落后，大部分采用人工调度、 召开调度会议的方法，生产的柔性较差，而且编制时间也长，不能适应多变的生产情 况。文献i 3 0 j 介绍了邯钢集团公司每天例行的生产调度会的形式；大约经过了现场调度、 会议调度、电话调度和电话电视调度几个发展阶段。可以看出，目前大部分钢厂出钢计 划的安排由人工来完成，这种方法效率低、调度人员工作强度大、出钢计划不尽合理， 不利于炼钢生产管理水平的提高。 随着国内企业生产和技术水平的不断提高，优化排程的研发也取得了长足的进步。 上海宝山钢铁公司作为国内钢铁企业的先进代表，今年来在计划自动编制技术和炼钢一 连铸、热轧一体化计划方面进行了有效的探索研究，其自主开发的连铸和热轧计划编制 系统，获得了较大的成功。宝钢从2 0 世纪8 0 年代到9 0 年代初期完成了一个完整的现 代钢铁联合体的建造，与此同时建立了一个完整的多级计算机控制系统【3 1 1 。从2 0 世纪 9 0 年代中期开始，以二期和三期工程为目标，宝钢开始了比较系统的l 2 模型自主研 发，并于1 9 9 8 年前后首先在炼钢过程控制模型取得突破，逐步形成了非常强的研发和 工程应用能力。图2 1 表示的是宝钢研究院自动化所经过近1 0 年形成的l i - l 4 模型技 术成果和能力。其中纵坐标表示控制系统的层级，横坐标表示工艺段( 见图中部的工艺 名称) ，如转炉等。阴影部