（模式识别与智能系统专业论文）优化算法在钢铁企业生产计划调度中的应用.pdf

东北走学硕士学位论文摘要 优化算法在钢铁企业生产计划调度中的应用 摘要 钢铁企业中的很多生产实际问题，都可归结为优化问题，象生产计划调度方面的铁 钢平衡问题、炉机平衡问题、炉次计划和浇次计划、轧制计划、合同并批问题、生产能 力平衡问题、一体化生产调度等。生产计划与调度问题是整个生产管理过程中最重裂的 问题之一，对于有序组织生产、充分发挥生产设备能力、提高生产效率、提高钢铁企业 生产效益和增强企业的竞争力起着重要作用。 算法研究是生产计划调度问题的主要研究内容，以上提到的优化问题经过抽象后大 都为n p 难问题，而无法使用传统的运筹学方法在可接受时间内获得最优解。通过对这 些问题的特征分析，发现其非常适合用智能优化算法求解。本文即在对问题特性所做分 析的基础上，改进现有的智能优化算法，并把它们用到求解炼钢连铸连轧生产计划中， 较好地解决了这些n p 难问题。 本文针对求解t s p 问题，改进一种极大极小代数法，另外，分析并根据t s p 问题 所具有的高f d c 特性，从理论上解释禁忌搜索对初始解的强依赖性及最大最小蚁群算 法所具有的优良性能。接下来，针对基本搜索及蚁群算法的局限性，为充分发挥问题的 f d c 特性，提出两种新算法，即引入混沌机制的禁忌搜索算法及最大最小蚁群算法改进 算法，仿真实例验证了这些算法适于求解较大规模问题。 在此之后，建立了炼钢连铸计划中的定宽组炉数学模型，使用蚁群算法求解，对组 浇连连浇问题建模并使用两阶段法求解。并建立了热轧单元计划的数学模型，讨论单元 计划抽象出的t s p 问题所具有的f d c 特性，使用禁忌搜索及蚁群算法求解，另外，对 轧制批量计划建立更贴近生产实际的数学模型，办使用蚁群算法求解。 关键词：优化算法，轧制计划，旅行商问题，车辆路径问题，炉次计划，浇次计划 东北大学硕士学位论文 a b s t r a c t o p t i m a la l g o r i t h m sa n di t sa p p l i c a t i o n so fp l a n n i n ga n d s c h e d u l i n gp r o b l e m si ns t e e l w o r k s a b s t r a c t m a n yp r a c t i c a lp r o b l e m si ns t e e h v o r l ( sc a l lb ea b s t r a c t e d 醛o p t i m i z a t i o np r o b l e m s ，s u c h a st h ei r o n s t e e le q u i l i b r i u mp r o b l e m ，f u m a c e - m a c h i n ee q u i l i b r i u mp r o b l e m ，c h a r g ep l a na n d c a s tp l a n ，h o tr o l l i n gp l a n , c o n t r a c tm e r g e rp r o b l e m ，t h r o u g h p u te q u i l i b r i u mp r o b l e m ，a n d i n t e g r a t e dp r o d u c t i o ns c h e d u l i n gi nt h ep r o d u c t i o np l a na n ds c h e d u l i n ga r e a p r o d u c t i o np l a n a n ds c h e d u l i n gi so n eo ft h em o s ti m p o r t a n tp r o b l e m si nt h ep r o d u c t i o nm a n a g e m e n tp r o c e s s ， a st h e ym a k et h eo r g a n i z i n gp r o d u c t i o no r d e r l ya n df u l lu s eo ft h ea b i l i t yo ft h ee q u i p m e n t s ， i m p r o v et h ep r o d u c t i o ne f f i c i e n c y t h eb e n e f i ta n dt h ec o m p e t i t i o no f t h es t e e lc n t e 【p r i s e s a l g o r i t h mr e s e a r c hi st h ec e n t r a lp r o b l e m i nt h e p r o d u c t i o np l a na n ds c h e d u l i n g p r o b l e m s t h eo p t i m i z a t i o np r o b l e m sm e n t i o n e da b o v ea r ea l ln p h a r dp r o b l e m sa f t e rb e i n g a b s t r a c t e d , w h i c hc o u l dn o tb er e s o l v e db yt h et r a d i t i o n a lo p e t a t i o n a lr e s e a r c hm e t h o di na r e a s o n a b l et i m e 1 1 1 e ya r es u i t a b l et ob er e s o l v e db yt h ei n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s d e v e l o p e dt h e s ey e a r s b a s e do nt h ea n a l y s i st ot h ec h a r a c t e r i s t i c so ft h e s ep r o b l e m s ，i nt h i s d i s s e r t a t i o nt h ee x i s t e n ta l g o r i t h m sh a v eb e e ni m p r o v e da n di m p l i e dt os o l v et h es t e e l - m a k i n g c a s t - c o n t i n u o u sr o l l i n gp l a n n i n gw e l l 。t h ef o l l o w i n gn o v e lw o r k sh a v eb e e nd o n e ： t os o l v et h et s p , ai m p r o v e dh e u r i s t i cm e t h o dc a l l e dm a x i m u m m i n i m n r f la l g e b r a i c a l m e t h o dh a sb e e np r o p o s e d t h eh i g hf d cc h a r a c t e r i s t i co ft h et s pp r o b l e mh a sb e e n a n a l y z e d ，w h i c ht h e o r e t i c a l l ye x p l a i n st h eh i g hd e p e n d e n c eo ft h et a b us e a r c ho nt h ei u i t i a l a n s w e ra n dt h ee x c e l l e n tp e r f o r m a n c eo ft h em a x m i na n ts y s t e m b a s e do nt h el i m i t a t i o n s o fb a s i ct a b us e a r c ha n da n tc o l o n ya l g o r i t h m ，i no r d e rt om a k ef u l lu s eo ft h ef d c c h a r a c t e r i s t i cs oa st ob e t t e rs o l v et h et s pp r o b l e m ，t w on e wa l g o r i t h m sh a v eb e e np r e s e n t e d ， n a m e l yat a b ua p p r o a c ha t t a c h e dc h a o sa n dak i n do fi m p r o v e dm m a s t e s t ss h o wt h a tt h e y e s p e c i a l l yh a v et h ea b i l i t yt os o l v et h el a r g e - s c a l ep r o b l e m a f t e rt h e s e ，am a t h e m a t i c a lm o d e lo ft h ew i d t h - f i x i n gm a k i n g u po ff u r n a c ep r o b l e mi n t h es t e e l m a k i n ga n dc o n t i n u o u sc a s t i n gp l a n n i n gh a sb e e nd e v e l o p e d ，a n dt h e nak i n do fa n t c o l o n ya l g o r i t h mh a sb e e nd e v i s e dt os o l v ei t a l s ot h ec a s tp l a np r o b l e mh a sb e e nm o d e l l e d a n dak i n do ft w o p h a s em e t h o dh a sb e e np r o p o s e dt os o l v ei t a f t e rt h er o l l i n gu n i tp l a n p r o b l e mb e i n gm o d e l l e d ，t h ef d cc h a r a c t e r i s t i co ft h er o l l i n gu n i tp l a nh a sb e e nd i s c u s s e d ， a n dt h et a b us e a r c ha n da n tc o l o n ya l g o r i t h mi su s e dt os o l v ei t t or e s o l v et h er o l l i n gb a t c h 东北大学顾士学位论文a b s t r a c t p l a np r o b l e m ，am o d e lc l o s e rt ot h ep r a c t i c eh a sb e e nd e v e l o p e da n dt h ea c oa l g o r i t h mh a s a l s ob e e nd e v e l o p e d k e yw o r d s ：o p t i m i z a t i o na l g o r i t h m ，h o tr o l l i n gp l a n ，t s p ，v r p ，c h a r g ep l a n ，c a s tp l a n 独创声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加 以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本a 9 获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示诚挚的谢意。 学位论文作者签名： 列锩， 签字日期：。以，p 丫 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即 学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交 流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：导师签名 签字f j 期：签字h 期 东北大学硕士学位论文 第一章绪论 第一章绪论 1 1 钢铁企业信息化 1 1 1 钢铁企业信息化方案 近年来，钢铁企业面临的市场竞争环境发生了很大的改变，客户对钢材的品种、规 格( 如板坯宽度、厚度等) 的需求越来越多样化，对产品的质量和交货期要求也越来越高， 客户需求呈现多品种、小批量特点；另一方面，钢铁企业对用户需求的预测越来越困难。 为了减少库存、降低成本，最有效的运作策略是将传统的以预测为主轴的推式系统( p u s h s y s t e m ) 改为以需求计划( d e m a n dp l a n n i n g ) 为主轴的拉式系统( p u l ls y s t e m ) ”j 。企业生产 将减少预测性生产，而变成主要按订单生产，生产模式也由批量生产方式转变为多品种、 小批量生产方式。为此，大多数钢铁企业为适应竞争的需要，在全球生产制造集成化和 信息化的潮流推动下，开始实施先进的生产与经营管理模式和系统，以企业资源计划 ( e n t e r p r i s er e s o u r s ep l a n n i n g ) i 为代表的管理信息系统近年来在钢铁企业得到广泛实施。 同时，九十年代中期发展起来的制造执行系统( m a n u f a c t u r i n g e x e c u t i o ns y s t e m ) 成为企业 实现生产活动与管理信息系统的有效集成、进行优化运行、优化控制与优化管理的桥梁， 成为提高钢铁制造企业竞争力的关键技术。 l l l 2 l 3 l 4 兽 日犷一 车间调度级 过程控制级 l j 。 、 、广 以j 广一 图1 1 钢铁企业信息化系统框架 f i g1 1 i n f r a s t r u e t u r eo fl n f o r m a ti o ns y s t e mi nt h es t e e le n t e r p r i s e 从图1 1 可看出，对于钢铁企业而言，从企业高层领导的宏观决策到岗位工人的其 体操作，基本组钐 方式f 分五级，即决策级、管理级、车间调度级、过程控制级和、发备 控制缴1 2 。另外，为把钢铁生产制造岔信息化的基础和主要内容与企业核心业务组纵 方式紧密联系在起。经过多年的理论研究和实践探索，种简单合理的系统体系结构 鬻 东北大学硕士学位论文第一章绪论 ( e r p m e s p c s 三层结构) 已成为企业c i m s 系统配置的主要趋势。该结构摆脱了以往完 全按物理层次划分配置控制系统的模式，而按照生产管理与控制任务的要求和应用功能 的分担配置。 1 1 2 钢铁企业m e s 现状 m e s 以过程数学模型为核心，通过计算机网络向上下游、产供销一体化或集成化 方向发展，从生产现场底层到企业管理层，从供应链的原材料供货到产品的销售，广泛 采集信息，而计划、指令和计算结果从管理、操作层一直传递到控制层。以面向数据的 模型为核心系统，连接实时数据库和关系数据库，对生产全过程进行实时状态监视、过 程控制和设备诊断。在管理决策层进行物料平衡、成本控制、产品质量的一体化设计、 生产计划、调度、排产、企业资源计划、流程的离线与在线模拟与优化等。 钢铁行业具有一定的特殊性，产品生产工艺复杂、实时性要求高，m e s 技术在钢 铁企业中将占据着极其重要的地位。许多大钢铁厂多年来都在努力寻求m e s 的设计上 的突破。近年来，钢铁企业应用人工智能、运筹学和人工判断相结合的方法，取得了一 定进展。例如日本的m m 公司与同本钢管京洪钢铁厂研发的协同生产调度计划系统 s c h e p l a n ；澳大利亚b h p 钢铁公司的交互调度和实时生产监控智能支持系统1 s a ；英国 b r o n e r 钢铁公司开发的炼钢连铸生产调度系统：日本住友公司和歌山钢铁厂开发的板坯 连铸作业调度计划专家系统；韩国光阳钢铁厂开发的综合过程调整与调度系统h i p a s s 。 许多传统的控制设备制造商也推出了面向m e s 控制的系统平台，如： r o c k w e l l a u t o m a t i o n 的r s b i z w a r e 软件将排产与流程模拟相结合进行设计：s i m e n s e 结 合其在自动化和冶金两方面的技术优势丌始进军冶金c i m s 的市场。但这些软件产品均 是针对某个特定的工序控制问题而开发，尚未形成在行业中推广的产业化方案。这主要 是由于许多m e s 关键技术有待研究和解决，难点之一即为针对各生产过程的算法实施。 从钢铁企业m e s 具体实施的内容来看，炼钢、连铸、热轧作为钢铁企业生产流程 中的三个主要工序，在整个生产过程中起着关键的作用。它为钢铁产品生产的后续工序 提供原材料，对提高生产效率、产成品准时交货率及最终产品的质量均有显著作用。另 外，考虑到钢铁企业面临的市场竞争环境发生的巨大变化，传统的手工生产计划与调度 方式已经很难适应竞争激烈、快速变化的市场环境。因此，有必要寻求一种快捷、有效 的计划0 调度方法来适应不断变化的生产环境。而炼钢连铸连轧计划与调度作为m e s 的核心功能，探索和研究炼钢连铸连轧生产计划与调度理论、模世及方法对研究和i ：发 东北走学硕士学位论更第一章绪论 钢铁企, l km e sj l 有重要意义，使企业可以适应动态变化的市场环境和易变的生产坏境， 充分利用现有资源，提高设备利用率，缩短产品的生产周期，降低在制品库存，提高产 品的质量，最终提高企业的经济效益。 1 2 钢铁企业生产计划调度问题 生产计划和生产调度问题大部分都是n p - - h a r d 问题。对于n p 难题，求解所消耗 的时间是随着问题舰模增大而呈指数增长的，且这种问题具有容易描述，求解困难的特 点，但由于此类闯题具有很高的研究价值与实用价值，也吸引着众多的科学研究者，近 年来，许多新兴技术不断的被应用到生产计划和调度问题中。 1 2 1 生产调度 调度( s c h e d u l i n g ) l h 题包含三个基本的要素：任务、资源和目标。它是在空间和时间 上合理安排任务和资源，在满足技术和资源约束条件下，使预定目标达到最优。一般是 多约束、多目标和随机不确定优化的复杂问题，是一类典型的组合优化问题，且大多为 n p - - h a r d 问题。 调度问题是一类广泛存在于现实世界中的经典问题，具有深刻的实际背景，依据不 同应用背景，其任务、资源要素可以代表不同的事物。现实世界的各个领域中，凡是要 处理多个任务，就存在安排任务执行的相应的调度问题，这成为现代企业的重要研究问 题之一。由于其涉及合理安排任务与资源，保证目标的最优性，能够带来效率、效益、 成本等方面的巨大收益，调度问题因而成为应用数学、运筹学、管理科学的诸多学科的 热门研究课题，研究成果层出不穷【3 , 4 1 。 1 2 2 钢铁企业生产计划调度问题简介 钢铁企业中的很多生产问题可归结为优化问题，其中核心为m e s 框架下的生产计 划调度方面的铁钢平衡、炉机平衡、组炉和组浇连连浇问题、轧制计划、合同并批、生 产能力平衡、一体化生产调度等，下面对其中炉次计划、浇次计划、轧制计划作以介绍。 1 2 2 ，l 相关名词 首先介绍相关名词含义1 5 3 】： 钢种：根据化学成分及组织结构的差异，钢材被分为多个不同性能的种类，每个种 类具有不同的生产 艺； 板坯：具有一定厚度、宽度和重量，山一定的钢种 j r l 7 ：成的钢板： 东北九学硕士学位论乏 第一章绪论 钢铁企业m e s 具有重要意义，使企业可以适应动态变化的订场环境和易变的生产环境， 充分利用现有资源提高设各利用率，缩短产品的生产周期，降低在制品库存，提高产 品的质量，最终提高企业的经济效益。 1 2 钢铁企业生产计划调度问题 生产计划和生产调度问题大部分都是n p h a r d 问题。对于n p 难题，求解所消耗 的时间是随着问题规模增大而呈指数增长的，且这种问题具有容易描述，求解困难的特 点，但由于此类问题具有很高的研究价值与实用价值，也吸引着众多的科学研究者，近 年来，许多新兴技术不断的被应用到生产计划和调度问题中。 1 2 i 生产调度 调度( s c h e d u l i n g ) 牺 题包含三个基本的要素：任务、资源和目标。它是在空间和时间 上合理安捧任务和瓷源，在满足技术和资源约束条件下使预定目标达到最优。一般是 多约束、多目标和随机不确定优化的复杂问蹶，是一类典型的组合优化问题，且大多为 n p l l a r ；d 问题。 调度问题是一类广泛存在于现实世界中的经典问题，具有深刻的实际背景，依据不 f 司应用背景，其任务、资源要素可以代表不同的事物。现实世界的各个领域中，凡是耍 处理多个任务，就存在安排任务执行的相应的调度问题，这成为现代企业的重要研究问 题之一。由于其涉及合理安排任务与瓷源，保证目标的最优性，能够带来效率、效益、 成本等方面的巨大收益，调度问题因而成为应用数学、运筹学、管理科学的诸多学科的 热门研究课题，研究成果层出不穷i 圳。 1 2 2 钢铁企业生产计划调度问题简介 钢铁企业中的很多生产问题可归结为优化问题，其中核心为m e s 框架下的生产计 划调度方面的铁钢平衡、炉机平衡、组炉和组浇连连浇问题、轧制计划、合同并批、生 产能力平衡、一体化生产调度等，下面对其中炉次计划、浇次计划、轧制计划作以介绍。 12 2 1 相关名词 首先介绍相关名词含义”】： 钢种：根据化学成分及组纵结构的差异，钢材被分为多个不同性能的种类，每个种 类具有不同的q 三产： 艺； 扳坯：县青一定厚度、宽度和重量，一定的钢种加丁成的铡板： 板坯：县青一定厚度、宽度和重量，山一定的钢种加丁成的铡板： 东北走学硕士学位论更第一章绪论 钢铁企, l km e sj l 有重要意义，使企业可以适应动态变化的市场环境和易变的生产坏境， 充分利用现有资源，提高设备利用率，缩短产品的生产周期，降低在制品库存，提高产 品的质量，最终提高企业的经济效益。 1 2 钢铁企业生产计划调度问题 生产计划和生产调度问题大部分都是n p - - h a r d 问题。对于n p 难题，求解所消耗 的时间是随着问题舰模增大而呈指数增长的，且这种问题具有容易描述，求解困难的特 点，但由于此类闯题具有很高的研究价值与实用价值，也吸引着众多的科学研究者，近 年来，许多新兴技术不断的被应用到生产计划和调度问题中。 1 2 1 生产调度 调度( s c h e d u l i n g ) l h 题包含三个基本的要素：任务、资源和目标。它是在空间和时间 上合理安排任务和资源，在满足技术和资源约束条件下，使预定目标达到最优。一般是 多约束、多目标和随机不确定优化的复杂问题，是一类典型的组合优化问题，且大多为 n p - - h a r d 问题。 调度问题是一类广泛存在于现实世界中的经典问题，具有深刻的实际背景，依据不 同应用背景，其任务、资源要素可以代表不同的事物。现实世界的各个领域中，凡是要 处理多个任务，就存在安排任务执行的相应的调度问题，这成为现代企业的重要研究问 题之一。由于其涉及合理安排任务与资源，保证目标的最优性，能够带来效率、效益、 成本等方面的巨大收益，调度问题因而成为应用数学、运筹学、管理科学的诸多学科的 热门研究课题，研究成果层出不穷【3 , 4 1 。 1 2 2 钢铁企业生产计划调度问题简介 钢铁企业中的很多生产问题可归结为优化问题，其中核心为m e s 框架下的生产计 划调度方面的铁钢平衡、炉机平衡、组炉和组浇连连浇问题、轧制计划、合同并批、生 产能力平衡、一体化生产调度等，下面对其中炉次计划、浇次计划、轧制计划作以介绍。 1 2 2 ，l 相关名词 首先介绍相关名词含义1 5 3 】： 钢种：根据化学成分及组织结构的差异，钢材被分为多个不同性能的种类，每个种 类具有不同的生产 艺； 板坯：具有一定厚度、宽度和重量，山一定的钢种 j r l 7 ：成的钢板： 东北大学硕士学位论之第一章绪论 炉次：钢水的生产以炉为单佗，某钢种的一炉钢水称个“炉次”一般包龠了浇 注许多板坯所需要的钢水； 炉容：一炉钢水的总重量，般不同的钢种标准炉容不同； 出钢记号：每炉钢水在出炉时须指定一个“出钢记号”，以代表不旧的处理方式。 可使用的出钢记号呵能不只一个，其中有一个最期望用的记号称“主出钢记号”或“期 望记号”，其他可代替使用的记号称“副出钢记号”或“可代替记号”； 余材：钢水一般按标准炉容生产，但其中可能只有一部分是需要交付给客户的板坯， 标准炉容与交付量之差称为余材。大块的余材可放库存备用，生产中希望尽量减少余材： 浇次：连铸生产要尽可能实现多炉连浇，把在同一台连铸机上使用同一个中间包连 续浇铸的炉次的集合称作一c a s t ，浇次最大容量主要由连铸机中间包寿命决定，一般 为5 1 0 炉，每个c a s t 还有宽度限制，即可调宽两次，最大调宽量为1 0 0 ； 连连浇：把在同一台连铸机上连续浇铸的c a s t 的集合称作连连浇c a s t ，只要宽 度能过渡并满足调宽次数限制，每个连连浇c a s t 可以有多个c a s t ，使c a s t 越长越 好； 铸机分配：连连浇c a s t 组完后，每个c a s t 内各个炉次的顺序已定，c a s t 分配 到铸机上，就是每个c a s t 具体分配到哪台连铸机上，得到浇注顺序，非绝对时间； c a s t l o t ：c a s t l o t 是一个中间包里出钢记号相同的几个炉，一个c a s t 可以 有几个c a s t i ( ) t 。 1 2 2 2 炉次计划 炉次是炼钢的最小基本单位，一个炉次是指同时在同一个电弧炉或转炉内冶炼的合 同。组炉问题为炼钢连铸生产阶段的生产批量计划，编制炉次计划时，考虑设备和工艺 特点、各工序的产能和工序传搁时间，按合同及组炉条件组成炼钢炉次，然后赋炉次编 号，即可提交用于浇次计划的编制。 组炉问题可描述如下：| v 块板坯要分成若干个炉，每块板坯的主要参数包括：( 编 号，重量，钢种，主出钢已号，副1 出钢记号，副n 出钢记号) 。在一定的约束条 件下寻找板坯组合成炉策略，使某些指标性能最佳。 组炉问题的多目标性： f 1 ) 出钢记号数最少； r 2 ) 余材最少或炉数最少： ( 3 ) 按期望记号出钢重量最多。 4 东北走学硕士学位论文第一章绪论 组炉问题要：母虑的约束： ( 1 ) 钢级必须相； ( 2 ) 板坯宽艘必须相同： ( 3 ) 板坯最小宽度板坯宽度板坯最大宽度； ( 4 ) 板坯厚度必须相同； ( 5 ) 交货期牛f 近。 当出现合同的板坯需求不能组成一炉时在下列四种情况中做出权衡： ( 1 ) 放弃该炉次计划； ( 2 ) 扩大预选池板坯量； ( 3 ) 形成无委材： ( 4 ) 使板坯钢级升级。 1 2 2 - 3 浇次计划 连铸机是钢铁企业中投资较高的设备，为尽可能提高连铸生产效率，降低连铸机和 中间包的装卸费用，应该优化连铸机的生产调度计划，即c a s t 计划。在编制浇次计划 时，重点考虑各精练设备的能力和冶炼时间、热轧预定生产日期和板坯库情况，将组成 的炉次按浇注条件排序。一个理想的c a s t 计划应该是充分地利用中间包使用寿命的计 划，即应使尽可能多的炉次组成c a s t 计划。 组浇的对象是炉，每炉由许多板坯构成，己由组炉计划确定。虽然同炉内各板坯期 望出钢记号及宽度可能有差异，但每炉有唯一指定的出钢记号，统一的出钢宽度和厚度。 组浇问题中炉是最小单位，不可再分。 组浇连连浇问题可描述如下：炉钢水要分成若干连连浇，炉的主要参数为：( 编 号，重量，钢种出钢记号，宽度，厚度) 。在一定的约束条件下寻找炉次分组结合策 略，构成浇次计划，在满足组浇条件及浇次容量限制下尽可能实现多炉连浇。浇铸时， 每炉有个唯一的号，叫p o n o 号。 其中要考虑以下几个约束： ( 1 j 不同宽度的炉次组成同一浇时，一般是按照炉次宽度 b 宽到窄排列； ( 2 ) 同浇次内各炉厚度相同； ( 3 ) 同浇次的炉次宽度不能频繁变化，梢邻炉次之间的宽度变化小能太大； ( 4 ) 同浇次内各自、重量之和不能超过连铸机中问包寿命决定的个卜限值； ( 5 ) 满足i ：述条什的炉次必须被安排q 三产：。 一5 东北大学硕士学位论文第一章绪论 1 2 2 4 轧制计划 从连铸机出来的板坯，i 篇通过轧机轧制，形成带钢或其它规格的轧材。轧制计划包 括批量计划及其各单元计划的编制。批量计划从候选板坯中选择组成各个单元汁划，轧 制单元计划对选好的轧制单元进行排序。编制轧制计划要考虑的主要因素为：( 1 ) 产品 的质量；( 2 ) 轧辊更换成本：( 3 ) 轧辊的磨损。轧制计划的目标是使机组能力利用率最 高，轧制单元合理。 轧制批量计划：轧制计划主要是对一周生产计划编制后的板坯进行组轧及轧制单元 内板坯排序，以满足下游的生产并提高产品质量与工作效率，进而产生轧制单元。 轧制单元排序：组轧结束后，根据其自身工艺的要求，对单元内排序进一步优化以 提高产品质量，减小轧辊磨损，减少换辊周期。 1 3 组合优化问题 钢铁企业中很多问题可归结为组合优化问题，这里介绍何为组合优化问题。 组合优化( c o m b i n a t i o n a lo p t i m i z a t i o n ) 主要是采用数学方法来寻找离散事件的最优编 排和次序，其模型可以用三个参数( d ，) 表示，其中d 为决策变量的定义域；f 表示可行解区域f = 工i x e d ，g ( x ) 0 ；，为目标函数刚。 令x 是一个组合最优化问题的( 有限) 解的集合，假设对于每个解工e x r 。，都有 一个实数f ( x ) r 与之对应，f ( x ) 可以是求最大值问题，也可以是求最小值问题，而最 大值问题可以简单地转化为最小值问题，故下面的内容都是针对最小值问题进行讨论， 即研究如下形式的组合最优化问题： m 睁厂( 工) ( 1 1 ) 其中。，0 ) r 为优化问题( 1 1 ) 的目标函数，而变量x 称作决策变量，而决策变量工 满足的条件称作优化问题( 】1 ) 的约束条件，称问题( 1 1 ) 的所有解的集合z 为可行解集， 若工x ，则工为问题( 1 1 ) 的一个可行解。设工x ，如果f ( x + ) ，( 曲，v x x 成立， 称x 为问题( 1 1 ) 的全局最优解。 组合最优化问题( 1 1 ) 就是寻找x + x ，使 f ( x ) = r a i n f ( x ) ( 1 2 ) 组合优化问题的特点赴- 叮行解集合为有限点集，由于受计算时间和计算空间的制 约，一般通过制订一定的搜索规则和过样t ! ，从有限个状态中选择最优解。 东北大学硕士学位论文第一章绪 龟 1 4 优化算法 1 4 1 经典的最优化方法 求解以上的组合最优化问题的算法渊源已久，如d a n t z i g 在1 9 4 9 年提出的求解线性 规划问题的单纯形法、l a n d 和d o i n g 于1 9 6 0 年开发出的分枝定界法、b a l a s 于1 9 6 5 年 提出的求解0 一l 规划的隐枚举法等，都属于精确算法，即总能保证求得问题的全局最优 解，这也是它们的最大优势，不足之处在于计算量偏大，受求解问题规模的限制，通常 可求解问题的规模很小，各算法思想简述如下1 7 】： ( 1 ) 线性规划法 线性规划的数学含义是在满足一组线性约束条件下，求出多变量线性函数的最优 值。其通过将生产问题的目标函数与约束条件用线性规划方程表示出来，利用单纯形法 对问题进行求鼹，最终得到问题的最优解。 f 2 ) 整数规划法 整数规划是指所有自变量都限制为整数的数学规划。在整数规划中，如果仅有一部 分自交量限制为整数，就称为混合整数规划。对整数规划问题比较实用的解法有：适于 纯粹整数规划( 所有自变量限制为整数) 问题的割平面法，适于0 - 1 整数规划问题的隐枚 举法，以及适于任意整数规划问题的分技定界法等。大多数生产调度问题都可以表达为 整数规划的形式，但其有效解用的是组合规划，等效于分枝定界法与动态规划法的求解。 ( 3 ) 动态规划法 动态规划是一种求解调度问题的重要的数学规划方法。1 9 5 1 年，美国数学家b e l l m e n 等人根据一类多阶段决策问题的特点，将问题的整体按时间或空间特征分成若干前后衔 接的时空阶段，然后逐个加以解决，最后求出整个问题的最优决策序列。同时他们又提 出了解决这类问题的“最优性原理”，根据这个原理，在求解的每一个阶段中，最后的 最优策略只取决于当前的状态，这样就创建了最优化问题求解的动态规划方法，文献 【6 8 】给出了动态规划方法解决调度问题的实例。 ( 4 ) 分枝定界法 分枝定界法是本世纪六十年代由l a n d d o i g 和d a k i n 等人提出的一类求解整数规划 或混合整数规划问题的方法，该方法灵活且便于计算机求解，所以应用非常广泛。基本 思想是先求出整数规划问题a 所对嘘的线性规划闯题b 的最优解，如果该解不符合a 的整数条件，那么b 的最优目初、函数必是a 的最优目标函数的上界，而a 的仔意j + 彳， 东北大学项士学位论文第一章绪论 解的目标函数值是其最优值的下界，然后将b 的可行域分成予区域( 称为分支) ，逐步减 小上界和增大下界，最终求得最优解。g a r e y 等们、c h o 等【l o 】和l e e 等分别提出不同 的分枝定界法。 1 a 2 启发式方法 上述经典的运筹学方法能求得问题的最优解，但由于大多数生产计划、调度及相关 问题为n p 难题，随着问题规模的增大，求解难度将呈指数规律递增，从解决生产调度 问题的时间要求来看也不允许用这类方法来求解，对于较大规模问题而言其不具实际可 行性。另外，经典运筹学方法还存在问题适应方法的局限，即需要把问题抽象为可以应 用经典运筹学方法的模型形式才可使用相应运筹学方法，从而限制了其应用。m a c c a r t h y 和l i u 就曾指出经典的生产计划优化理论在实际生产中运用的很少，问题的最优化算法 一般只具有学术价值，缺乏实用价值。启发式方法因其能为多数调度问题找到近优解而 成为人们解决实际计划调度问题的一类方法，得到了广泛的应用。 ( 1 ) 启发式规则和专家系统方法 调度规则也称为调度规划，分派规则，优先级规则和启发式规则，是一类简单的启 发式方法，是一种在生产计划和调度问题研究中运用最广泛的启发式方法。 调度规则的最大优点是计算量小，但单个规则有效性低，适应性也较窄，经过适当 的组合，后面的两项劣势会有较大的提高，有时甚至能得到问题的最优解，比较有代表 性的是j o s e p h 等【1 2 】的瓶颈转移程序。国内也有许多这方面的研究，如何祯等【1 3 1 针对 n m f c 问题提出了最佳匹配方法，计算复杂度为0 ( n ( n + m ) ) ：黄德才等用其提出的 m r 算法得到了一个j o b s h o p 算例的最优解；陈秋双等”】对个双目标的j o b s h o p 问 题提出了两个基于s p t 规则启发式算法。 专家系统同样体现了一种规则思想。调度专家系统通常将领域知识和现场的各种约 束表示成知识库，然后根据现场情况从知识库中产生调度方案，并能对意外情况采取相 应的对策。使用专家系统的主要缺陷是难以评估所得到的解的性能，同时b n 使问题规模 发生很小的变化，所得的结果与最初的解相比也会有很大的不同。 ( 2 ) 拉格朗同松弛法 拉格朗同松驰算法是由e v e r e l 提出的一种求解复杂优化问题的近似算法，它是将原 问题中的某些约束吸收到目标函数“j 中，使松驰后的新问题在多项式时间内求得最优 解，这个最优懈能够逼近原问题的最优解。 东北大学硕士学位论文第一章绪论 近年该方法己成为解决复杂车间调度问题的一种重要的方法，如王朝辉等l 嘲研究 j o b s h o p 问题时，在目标函数中引入了拉格朗目乘子，l u l l 等在研究并行机器调度问 题时使用了拉格朗日松驰技术，熊锐等1 7 1 用这种方法求解集成车间计划与调度问题。 1 4 3 智能计算方法 实际生产的问题规模越来越大，而且越来越复杂，给求解带来了相当大的困难，已 无法使用传统的运筹学方法求得最优解；而启发式算法解的优良性无法保证且依赖于针 对问题的设计技巧，对研究者提出了更高的要求。在这种背景下，人们不得不去寻找更 有效的启发式方法。人工神经网络( n e u r a ln e t w o r k ，叼、遗传算法( g e n e t i ca l g o r i t h m ， g a ) 、模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 和禁忌搜索算法( t a b us e a r c h ，t s ) 、蚁群最优化 ( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 等各种智能优化算法相继问世，为求解组合最优化问题 提供了新的途径，在生产计划调度中的应用已形成一股研究热潮。 ( 1 ) 人工神经网络 对于神经网络理论的探索性研究以1 9 4 3 年美国生理学家w s m c c u l l o c n 和数学家 w a p i t t s 提出的二值神经元模型为代表。主要思想是用人工神经元相互连接组成一个 计算网络，并行商效地求解问题。它的 要特点是能够自学习，通过给网络提供一定训 练的样本，根据网络的实际输出与希望输出之间的偏差，利用某种方法逐步修改各人工 神经元之间的连接权，使之形成求解某些问题的能力。 人：亡神经网络已被用来求解调度问题，国内张长水等、于海滨等1 2 0 提出的基于 h o p f i e l d 模型的f l o w s h o p 排序方法中，大部分结果与最优结果相当逼近，然而人工神 经网络的效率受训练影响很大，并且在问题规模较大时，存在计算速度慢和结构参数难 以确定的弱点。 ( 2 ) 模拟退火算法 模拟退火算法( s a ) 是k i r k p a t r i c k 等于八十年代初提出的，适合解大规模组合优化问 题，是一种解n p c o m p l e t e 问题的通用有效算法。s a 算法是基于m o n t ec a r l o 迭代求解 策略的一种随机寻优算法，其出发点是基于物理退火过程与组合优化之问的相似性，s a 由某一较高初温开始，利用具有概率突跳特性的m e t r o p o l i s 抽样策略在解空问中进行随 机搜索，伴随温度的小断下降重复抽样过程，最终得剑问题的全局最优解，如 q 澎等l 构造了f l o w s h o p 题的模拟退火算法。总体来看，该算法能够渐近收敛于全局最优解， 并具有多项式算法复杂特 峰。但是小同的抽样方式实现的最优差异较大，且算法有效性 东北大学硕士学位论文第一章绪论 随问题规模的增大有缓慢下降的趋势。另外，它的收敛速度较慢，难以用于实时动态调 度环境，这些都限制了其应用。 ( 3 ) 遗传算法 遗传算法( g a ) 为j h o l l a n d 于1 9 7 5 年受生物进化论的启发提出的基于“适者生存” 思想的一类高度并行、随机、自适应搜索算法，与其它启发式方法顺序搜索空问不同， 该算法以解的种群作为工作单元，模仿生物进化的适者生存原则指导搜索改进目标。 遗传算法的基本思想可描述为：一定数目的经过基因编码的个体组成一个初始种 群，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近优解。在每一代中， 根据问题域中个体的适应度大小选择个体，并借助自然遗传学的遗传算子进行组合交叉 和变异，产生出代表新解集的种群1 2 2 1 。从而使新种群象自然进化一样更适应环境。 各种现代启发式方法是方法适应问题，即方法具有更广泛的适用性，而各种运筹学 方法需要问题适应方法，即把问题抽象为典型形式才可使用相应的运筹学方法解决。使 用m i c h a l e w i c z l 2 3 1 提出的“强方法”( 与问题相关程度高的方法属于“强方法”) 和“弱 方法”( 与问题相关程度低的方法是“弱方法”) 的概念区分各算法，阐述各种算法对问 题的相关性和求解效率。m i c h a l e w i e z 证实了在算法设计合理的前提下，“强方法”的性 能优于“弱方法”，从而可把运筹学方法看为“强方法”，而各类现代启发式方法及蚁群 优化等智能算法为“弱方法”。 1 5 本文的主要研究工作及章节安排 钢铁企业中，生产计划与调度问题是整个生产管理过程中的最重要问题之一，对提 高钢铁企业生产效益和增强企业的竞争力起着重要作用。由于这些问题一般规模较大， 考虑因素较多，生产工艺约束比较复杂，因此在建立数学模型和对模型求解的过程中要 对问题进行具体、系统地分析，尤其对实际应用中的大规模问题求解时，传统的精确算 法已不能实现问题的要求，而在使用蚁群算法等近似算法时，需要根据问题的特性对算 法进行专门的设计，以适应实际问题的需要，获得较好的近优解，编制出效率较高的生 产计划。本文即重点研究使用优化算法解决钢铁企业的生产计划问题。全文安排如下： 第一章介绍课题的研究背景； 第二章分析t s