（控制理论与控制工程专业论文）基于免疫算法与分散搜索的钢铁生产调度研究.pdf

l j 童 d e p a r t m e n t ：d e p t o f a u t o m a t i o n m a j o r ：c o n t r o lt h e o r ya n de n g i n e e r i n g a u t h o r ：s u nk a i s u p e r v i s o r ：p r o f y a n gg e n k e s h a n g h a i j i a ot o n gu n i v e r s i t y m a y 2 0 0 9 - 吾 | 霉： 讳 川 ，。 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本 一 。 文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位做作者躲拊凯 日期：加。7 叮月幻日 一1 t扎”0 。 r t ：圯 - 恧 - 论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密留。 ( 请在以上方框内打“4 ”) 学位论文作者虢易3 制指导教师 醐：加( ) p 月珈 醐功 1 1 毒 簟 女 上海交通大学博士学位论文答辩决议书 所存 姓名孙凯学号0 0 4 0 3 2 2 0 1 4控制理论与控制工程 学科 指导教师杨根科 答辩 2 0 0 9 0 5 1 3 答辩 匕海交通大学闵行校区电信大楼二号楼4 0 6 日期地j _ 一 论文题h 基于免疫算法与分散搜索的钢铁生产调度研究 豸j 、凯q 堪t 妖蝌基亏炙寝3 6 【；砰删恩铀懈勾雯，9 。 翰硝巍参凌蚴谰及昶气如建鹳们俩钮宪，切燃 一懋燃凇滁，懈础3 唧 z 把傍扎。孓务阚权闻融遵獭樊金恼桑的卑舒谚裙铲l 逖看报爿j 7 仃 弓一瓣丁 撒炽j j j j 弓谛蟛，散弧鹳露删。 薪骈哟匆凯礴得弘毅什搽v 职务姓名- 职称单位签名 上脯赞做锐 教授 上海大学 睁膨救 链 许坳鸣 1 委员许晓鸣教授 上海理工大学 辩 委 委员 王行愚教授华东理工大学 蔓剐受i 员 瓜 委员席裕庚 教授上海交通大学 砌咙一 嚣 成 - 上海交通大学 喇贮 员 委员张卫东 教授 签 委员 名 委员 秘 5 吴沂军 工程师上海交通大学 芸溺犀 铒冉- 。 _博氟吮翰州，。i，t ql，女童弼1 ，一0确， 、嘲jljll，d【r! o，虹孺卧n0 t t 上海交通大学博士论文 摘要 生产调度是制造企业生产管理的关键，科学的制定和执行生产调度方案对提升 产品质量，缩短生产周期，减少在制品库存，降低物耗和能耗，降低生产成本，提 高企业竞争力有着极其重要的意义。钢铁生产调度是生产调度理论在钢铁行业特殊 环境中的应用，需综合考虑钢铁工艺生产要求、计算机系统和管理方法，以通过建 立合理的调度模型快速排定调度方案，使之成为钢铁生产过程的辅助决策工具。 免疫算法0 a ) 与分散搜索( s s ) 都是基于种群的进化算法，具有很强的全局搜索能 力，但在进化机制和搜索策略上有许多不同之处。本文主要以钢铁生产调度为背景， 针对各问题的生产工艺流程及工艺约束，分析其调度需求，建立调度模型，然后根 据不同问题的特点，选择适合的算法，并结合其他策略，设计求解该问题的优化算 法，通过应用工业生产数据来验证算法的有效性。从而为实际钢铁生产提供有效的 调度方案，为钢铁生产调度技术的进一步发展提供理论基础。本文取得的主要研究 成果为： 首先，本文研究了面向成本的流水作业( f l o w s h o p ) 调度问题。将经济指标融入 f l o w s h o p 调度问题中，提出一种面向成本的f l o w s h o p 调度问题的混合整数规划模型。 该模型综合考虑了影响调度决策的各种加权指标，如生产切换费用、机器空闲造成 的损失、工件提前拖期完工造成的损失等。基于免疫进化机制，在免疫算法框架中 引入一种自适应禁忌搜索( a t s ) 对种群进行局部改进，提出了一种新的免疫算法 ( i a a t s ) 求解该问题。算法充分利用免疫算法的全局寻优能力，并结合了禁忌搜索的 局部寻优能力，不同规模的仿真算例验证了该模型的可行性及算法的有效性。 其次，针对钢铁制造过程中的炼钢连铸调度问题，以控制连续浇铸及炉次在工 序间等待为约束，以总加工流程时间为目标函数，建立了该问题的混合f l o w s h o p 调 度模型。利用i a a t s 算法求解该问题，针对炼钢连铸调度问题的求解复杂性，设 计了一种新的抗体编码方案，并利用时间倒推法与线性规划结合的生产作业编排方 法求解抗体的亲和度。实验结果表明该算法是一种有效的炼钢连铸生产调度优化方 法，能够编制出实现连浇的可执行的炼钢作业计划，并且可以降低炉次在各工序间 等待造成的损失，减小总加工流程时间，从而达到降低企业运行成本、增加企业盈 摘要 利的目的。 再次，研究了钢铁企业中的热轧生产调度问题。根据热轧生产过程中的各种工 艺约束，以降低厚度、宽度、硬度跳变引起的惩罚及满足合同交货期为调度目标， 将热轧生产调度问题建模为奖金收集的车辆路径问题。该模型将热轧生产过程中板 坯选择与板坯排序结合起来，综合考虑了轧辊的更换成本以及客户服务水平等指标。 基于分散搜索“分散收敛集聚的进化机制，在分散搜索算法框架中嵌入极值优化 算法以提高算法局部搜索能力，提出了一种新的分散搜索算法( s s i e o ) 求解该问题。 利用实际生产数据对算法进行验证，仿真结果表明s s 1 e o 算法虽然不能保证取得全 局最优解，但是能够在合理的运算时间内求得比较满意的调度方案。 最后，研究了钢铁企业中的冷轧平整机批量轧制调度问题。冷轧平整机生产过 程中，不同薄钢板需要不同的表面粗糙度的轧辊下处理，而轧辊的表面粗糙度参数 随着轧制过程的进行将不断的衰减，且衰减的动态过程又与轧件的调度次序密切相 关。针对冷轧平整机轧件与轧辊参数耦合的特点，建立了设备参数动态变化下调度 的数学模型。以轧辊磨损函数为切入点，通过对轧辊磨损曲线的分段线性简化，将 复杂的调度问题分解为三个子问题，即聚类问题、尽最短路径问题( k - c s p p ) 、多级 最短路径问题。开发了解决基于分散搜索( s s i e o ) 和动态规划( d p ) 相结合的混合策 略，首先根据约束条件，将订单分配到不同的类中，然后通过s s 1 e o 算法对每个订 单类求解k - c s p p , 最后通过d p 算法将这些子问题的解合成为一个原问题的可行解。 并通过某大型钢厂的实际数据验证了算法的有效性。 关键词：钢铁生产调度；f l o w s h o p 调度问题；炼钢连铸调度问题；热轧生产调度问 题；平整机调度问题；免疫算法；分散搜索；禁忌搜索；极值优化 i i 3 番 t o i 。 p r o d u c t i o ns c h e d u l i n gi st h e k e ye l e m e n t i n m a n u f a c t u r i n ge n t e r p r i s e s ，a n d s c i e n t i f i c a l l yf o r m u l a t i n ga n de x e c u t i n gi tc a r ls h o r t e np r o d u c t i o nc y c l e ，r e d u c ei n v e n t o r i e s o fw o r ki np r o c e s s ，d e c r e a s et h ep r o d u c t i o nc o s ta n di m p r o v ee n t e r p r i s e sc o m p e t i t i v e p o w e ri nt h em a r k e t s t e e l - m a k i n gp r o d u c t i o ns c h e d u l i n gi st h ea p p l i c a t i o no fp r o d u c t i o n s c h e d u l i n gt h e o r yi nt h es t e e l m a k i n gc i r c u m s t a n c e ，a n di ts h o u l dc o n s i d e rs e v e r a la s p e c t s s u c ha st e c h n o l o g i c a lr e q u i r e m e n t so fs t e e l - m a k i n g ，c o m p u t e rs y s t e ma n dm a n a g e m e n t t e c h n i q u e s ，a n dt h e nm a k ei tb e c o m ea u x i l i a r yd e c i s i o n - m a k i n gt o o l sf o rt h es t e e l m a k i n g p r o c e s sb ye s t a b l i s h i n gr e a s o n a b l es c h e d u l i n gm o d e la n ds c h e d u l i n gs c h e m e i m m u n ea l g o r i t h m ( i a ) a n ds c a r e rs e a r c h ( s s ) a r ep o p u l a t i o n - b a s e de v o l u t i o n a r y a l g o r i t h m sw h i c hh a v es t r o n gg l o b a ls e a r c ha b i l i t y , b u tt h e yh a v em a n yd i f f e r e n c e si n e v o l u t i o nm e c h a n i s m ，s e a r c hs t r a t e g ya n ds oo n t h ep a p e rd i s c u s s e ss e v e r a ls c h e d u l i n g p r o b l e mi ns t e e l m a k i n gp r o d u c t i o n ，a n a l y z e st h e i rs c h e d u l i n gn e e d s ，p r e s e n t st h e i r m a t h e m a t i c a lm o d e l s ，d e v e l o p se f f e c t i v eo p t i m i z a t i o na l g o r i t h m st os e a r c ho p t i m a la n d n e a r - o p t i m a ls o l u t i o n s ，a n dt h e na p p l i e s i n d u s t r i a lp r o d u c t i o nd a t at oi l l u s t r a t et h e e f f e c t i v e n e s so ft h e s ea l g o r i t h m s t h em a i no b j e c t i v eo ft h ep a p e ri sp r o v i d i n ge f f e c t i v e a n dr e a s o n a b l es c h e d u l i n gs c h e m et os t e e l m a k i n gi n d u s t r i e sa n dp r o v i d i n gt h e o r e t i c a l f o u n d a t i o nf o rt h ei m p r o v e m e n to fs t e e l i n g m a k i n gs c h e d u l i n gt e c h n i q u e s t h em a i n r e s e a r c ha c h i e v e m e n t so ft h ep a p e ra r e ： f i r s t l y , t h ep a p e rh a ss t u d i e dt h ec o s t - d r i v e nf l o w s h o ps c h e d u l i n gp r o b l e m t h ep a p e r p r e s e n t sac o s t - d r i v e nm o d e lo ft h ef l o w s h o ps c h e d u l i n gp r o b l e m ( f s p ) b yi n v o l v i n g e c o n o m i ci n d e xi n t ot h ep r o b l e m t h ec o s tm o d e li sd e v e l o p e di nt e r m so fac o m b i n a t i o n o fm u l t i d i m e n s i o n a lc o s t sg e n e r a t e df r o mp r o d u c tt r a n s i t i o n s ，r e v e n u el o s s ，e a r l i n e s s t a r d i n e s sp e n a l t y , a n ds oo n an e wi m m u n ea l g o r i t h m ，c a l l e di a a t s ，c o m b i n e st h e s t r o n gg l o b a ls e a r c ha b i l i t yo fi aw i mt h es t r o n gl o c a ls e a r c ha b i l i t yo fa d a p t i v et a b u s e a r c h ( a t s ) t h ee x p e r i m e n t a ls i m u l a t i o nt e s t ss h o wt h ev a l i d i t yo ft h ec o s t - d r i v e n m o d e la n dt h ee f f e c t i v e n e s so ft h eh y b r i di a - a t sa l g o r i t h m s e c o n d l y , t h ep a p e rh a ss t u d i e dc o n t i n u o u sc a s t i n gs c h e d u l i n gp r o b l e m ( c c s p ) t h e p a p e rp r e s e n t s ah y b r i df l o ws h o ps c h e d u l i n gm o d e lf o rt h ep r o b l e m ，w h i c ht a k e s c o n t i n u o u sc a s t i n ga n dw a i t i n gt i m eo ff u r n a c e sa sc o n s t r a i n t s ，a n dt a k e st o t a lf l o w t i m eo f p r o c e s sa so b j e c t i v ef u n c t i o n ap r o d u c t i o ns c h e d u l i n gm e t h o dw h i c hc o m b i n e sh e u r i s t i c r u l ea n dl i n e a rp r o g r a m m i n gi sp r e s e n t e da f t e rc o n s i d e r i n gt h es o l v i n gc o m p l e x i t yo ft h e p a r a m e t e r s a n dm a c h i n ep e r f o r m a n c e i nc h a p t e r5 ，t h e p a p e rp r e s e n t sa n e f f e c t i v e d e c o m p o s i t i o n c o m b i n a t i o nm e c h a n i s mw h i c hd i v i d e st h ec o m p l e xs c h e d u l i n gp r o b l e m i n t ot h r e et r a c t a b l es u b p r o b l e m s ：c l u s t i n gp r o b l e m ，k - c o n s t r a i n e ds h o r t e s tp a t hp r o b l e m ( k - c s s p ) ，a n dm u l t i p h a s es h o r t e s tp a t hp r o b l e m am i x e ds t r a t e g yw h i c hc o m b i n e s s s i e ow i t hd y n a m i cp r o g r a m m i n g ( d p ) i sp r e s e n t e d ：f i r s t l y a s s i g n i n g o r d e r si n t o d i f f e r e n ts t a g e s ，a n dt h e ns o l v i n gt h ek - c s s po fe a c hs t a g eb ys s - i e o ，a n dc o m b i n i n gt h e s o l u t i o n so fs u b - p r o b l e m si n t oaf e a s i b l es o l u t i o nb yd pa tl a s tp h a s e t h ec o m p u t a t i o n a l e x p e r i m e n t sd e m o n s t r a t et h ee f f e c t i v e n e s so f t h ep r o p o s e ds t r a t e g y k e y w o r d s ：s t e e l m a k i n gp r o d u c t i o ns c h e d u l i n g ，f l o w s h o ps c h e d u l i n gp r o b l e m ， c o n t i n u o u sc a s t i n gs c h e d u l i n gp r o b l e m ，h o tr o l l i n gs c h e d u l i n gp r o b l e m ，s k i np a s s m i l ls c h e d u l i n gp r o b l e m ，i m m u n ea l g o r i t h m ，s c a t t e rs e a r c h ，t a b us e a r c h ，e x t r e m a l o p t i m i z a t i o n i v 1 3 簟 誊 0 鲁 1 4 免疫算法与分散搜索概述1 0 量 1 4 i 免疫算法1 0 1 4 2 分散搜索1 2 1 4 3 免疫算法与分散搜索比较1 4 1 5 本文主要研究内容1 5 第二章基于免疫算法的面向成本的f l o w s h o p 调度问题研究1 7 2 1 引言。1 7 2 2 f l o w s h o p 调度问题概述1 7 2 2 1 一般车间调度问题的特点和分类1 7 2 2 2 f l o w s h o p 调度问题描述1 8 2 2 3 f l o w s h o p 调度问题研究现状1 9 2 3 4 面向成本的f l o w s h o p 调度问题优化模型2 1 2 3 免疫算法求解面向成本的f l o w s h o p 调度问题2 4 2 3 1 抗体编码方案2 5 2 3 2 抗体亲和度和浓度函数2 5 2 3 3 免疫算子设计。2 6 2 3 4 抗体群更新2 7 2 3 5 基于自适应禁忌搜索的局部改进策略2 7 2 3 6 求解面向成本的f l o w s h o p 调度问题的免疫算法流程3 l 2 4 仿真结果3 2 2 5 本章小结3 6 第三章基于免疫算法的炼钢连铸生产调度问题研究。3 7 3 1 引言。3 7 3 2 炼钢连铸生产调度问题概述3 7 3 2 1 炼钢连铸生产工艺流程3 7 3 2 2 炼钢连铸生产调度特点与难点3 9 3 2 3 炼钢连铸生产调度研究现状。4 0 3 2 4 炼钢连铸生产调度的优化模型4 2 3 3免疫算法求解炼钢连铸生产调度问题4 4 目录 3 - 3 1 抗体编码方案4 5 3 3 2 时间倒推与线性规划相结合的方法求解抗体亲和度4 6 3 3 3 抗体浓度计算4 9 3 3 4 免疫算子设计5 0 3 3 5 抗体群更新5l 3 3 6 基于自适应禁忌搜索算法的局部改进策略5 1 3 3 7 求解炼钢连铸生产调度问题的免疫算法流程5 2 3 4 仿真结果5 3 3 5 本章小结5 5 第四章基于分散搜索的热轧生产调度问题研究5 7 4 1 弓l 言! ；7 4 2 热轧生产调度问题概述。5 7 4 2 1 热轧生产流程与工艺约束5 7 4 2 2 热轧生产调度问题的研究方法6 0 4 2 3 热轧生产调度问题的优化模型6 2 4 3 分散搜索求解热轧生产调度问题6 5 4 3 1 解编码方案与目标值定义6 6 4 3 2 启发式规则产生初始种群6 7 4 3 3 参考集构造与更新6 8 4 3 4 子集的拆分6 8 4 3 5 组合策略6 9 4 3 6 基于s w a p 算子的改进策略。7 0 4 3 7 基于极值优化算法的改进策略7 0 4 3 8 求解热轧生产调度问题的分散搜索算法流程7 4 4 4 仿真结果7 4 4 5 本章小结7 7 第五章基于分散搜索和动态规划的分解策略求解平整机调度问题7 9 5 1 引言7 9 5 2 平整机调度问题概述8 0 5 2 1 冷轧薄板工艺流程8 0 5 2 2 平整机调度问题的优化模型8 2 5 3 基于分散搜索和动态规划的分解策略求解平整机调度问题8 5 5 3 1聚类问题8 8 5 3 2 求解k 最短路径问题的分散搜索算法8 9 5 3 3 最短路径问题的动态规划算法9 4 5 4 仿真结果9 5 5 5 本章小结9 8 第六章总结与展望。9 9 6 1 本文工作总结：9 9 6 2 进一步的研究内容1 0 0 参考文献1 0 3 1 i 熨谢1 1 1 攻读博士学位期间已发表、录用和完成的论文1 1 2 v i 簟 1 鲁 簟 帮 0 鲁 7 、 i ， - 廿 1 1 引言 钢铁工业 至关重要。近 一流企业在技 的品种、规格等需求越来越多样化，客户需求呈现多品种、小批量的特点；同时对 产品的质量和交货期要求也越来越高。另一方面，钢铁企业对用户需求的预测越来 越困难，为了减小库存，节约成本，最有效的运作策略是将传统以预测为主轴的推 式生产系统改为以需求计划为主轴的拉式生产系统。企业将减少预测生产，而转变 。= 为按订单需求生产，并由批量生产模式转变成多品种、小批量生产模式。因此，在 新的生产环境下，各钢铁企业为了在市场竞争中占居有利地位，迫切需要提高生产 技术水平，实施先进的生产调度系统，制定科学合理的生产调度方案，以提高钢铁 企业的生产效率，改善产品质量，简化工艺过程，降低原材料、能量消耗和生产成 锰 本，从而增强钢铁制造企业的竞争能力。 生产调度是指产品在制造过程中，在满足各种生产约束( 如作业优先级、设备能 力、交货日期) 的前提下，实现人力、材料、机器等共享资源的有效配置及使用顺序， 以达到某性能指标最优的目的【1 1 。简单的说，生产调度就是在一定的时间范围内完成 特定的生产任务而分配资源，并使得预定的某些生产指标最优。实际的生产调度性 能指标大致可以分为三类： 生产能力指标：最大化生产效率、最短生产周期等，调度的主要目标是为提 高设备的利用率、缩短产品的生产周期，使工厂生产能力最大。 成本指标：最小化企业运营费用如库存成本、生产成本、产品拖期惩罚等。 客户满意指标：包括最小化提前或拖后交货期等。 钢铁生产调度是生产调度理论在钢铁行业特殊环境中的应用，本论文着重围绕 钢铁制造中的炼钢、连铸、热轧、冷轧等主要生产工序，针对各工序的生产模式， 分析其生产约束及调度需求，建立调度模型，并根据不同问题的特点，设计有效的 图1 - 1 钢铁生产工艺流程 f i g 1 - 1p r o d u c t i o np r o c e s so f s t e e li n d u s t r y 炼钢过程：炼钢过程从兑铁水开始，当铁水兑完后，紧接着往炼钢炉里加入钢 料和合金添加剂，然后吹氧、脱碳。经过一段时间的冶炼，当钢水的温度和成份达 到预定的目标值时，将钢水倒入可移动的钢包中，以进行后续工序。另外，根据订 单对钢级成份的要求，钢包中的钢水还可选择不同路径的炉外精炼，如：吹氨温站， 可对合金成份进行微调，并降低钢水中的硫含量；真空处理装置，可减少水中气体( 尤 其是氢气) 的含量；钢包精炼炉，可调节和控制钢水温度和成份，后续的浇铸过程做 好充分的准备。炼钢过程是一个以“炉次( 转炉的容量) 为单而进行的复杂的物理和 化学变化的过程。 2 鼍 j ； 帮 j 警 上海交通大学博士论文 连铸过程：连铸过程是将钢水浇铸成预定规格的固态板坯的过程。当装有钢水 包通过可旋转的回转台进入铸机位准备开浇时，首先打开钢包底部的流钢孔，水注 入铸机的中包内；然后打开中包的活动水口，让钢水流入下面的结晶器中，沿结晶 器周边冷凝成坯壳，当坯壳有一定厚度时，铸坯在拉坯机的驱动下，离晶器沿着弧 形排列的支撑辊下移；与此同时，铸坯被二次冷却装置进一步冷却；随后铸坯被切 割成定尺长的板坯，并直接运送到加热炉进行加热，以便进行轧制，或者板坯下线 被暂时存放在保温坑或板坯库中，需要时再送入加热炉加热。整个过程是连续进行 的，不能断流，因为对连铸机来说，每开启一次都需要更包和结晶器，断流就意味 着增加了调整时间和调整费用，因此为了提高生产率，生产费用，在中包寿命允许 的范围内，应尽可能地实现多炉连浇。浇铸过程是“浇次 为批量单位来进行的。 一个“浇次 是指在同一台连铸机上，使用同一包和结晶器连续浇铸的炉次的集合。 热轧过程：热轧带钢的s l n 过程是主炼钢区域的最后一道工序，其原材料是其 室 上游工序一连铸工序出来的板坯。连铸坯经过质量检查和表面处理后，进入步进式 加热炉进行加热，达n s l $ i j 所需的温度后，从加热炉内推出，经过高压水除鳞，再 经定宽压力机侧压成所需宽度，由输送辊道送入粗轧机s l $ i j 成钢坯。经粗轧机轧制 后，再运到精轧机进行精轧，从精轧机组出来的带钢穿过层流冷却装置，控制卷取 速度，经卷取机卷取形成热轧钢卷。热轧钢卷既可以直接作为成品出售，也可以成 搬 为冷轧工序的原料，钢卷经冷轧深加工后，形成更优质的冷轧带钢产品。 冷轧过程：冷轧是热轧的后续工序，冷轧薄板的厚度大约从o i n ：1 i r m - 0 7 m m 不等， 冷轧带钢具有表面光洁，平整，尺度精度高和机械性能好等优点。冷轧薄板加工是 典型的流程工业生产过程，主要包括酸洗、主轧、退火、平整、剪切、重卷、镀锌、 镀锡等多道机组工序。 钢铁生产主要流程包括炼钢、连铸、热轧和冷轧等主要工艺阶段，其过程和工 序间呈现顺序加工关系，且前后工序紧密衔接，存在着物质和能量的转换与传递。 因此，钢铁生产流程具有以下几个特点【2 j ： 生产过程是分段连续和半连续，生产计划往往是基于各个工厂单独进行编 制； 产品市场需求是多品种和小批量，钢铁企业生产组织要求大批量： 生产过程是多阶段的，但其工艺路线基本是单一固定的，前后工序的物流要 协调一致，时间节奏要匹配； 布置几乎固定 续性要求生产 直接影响到 优化，排序优 浇铸，分配板 将浇铸出来的 厚度和硬度跳 顺序以缩短物 流周期，提高生产率等等。钢铁生产调度问题具有多约束性和多目标性的特点【2 】，目 前，数学规划、人工智能算法等各种不同的方法都得到不同程度的应用与研究。 1 3 1 数学规划方法 数学规划方法是解决调度问题最传统的方法之一。它主要根据实际问题中的调 度问题，进行适当的假设和抽象，然后使用线性规划( l i n e a rp r o g r a m m i n g ，l p ) 、非 线性规划( n o n l i n e a rp r o g r a m m i n g ，n l p ) 、混合整数规划( m i x e di n t e g e rl i n e a r p r o g r a m m i n g ，m i l p ) 、动态规划( d y n a m i cp r o g r a m m i n g ，d p ) 及决策分析( d e c i s i o n a n a l y s i s ，d a ) 等方法对问题进行建模，进而采取精确算法或启发式算法进行求解。 在应用数学规划方法求解炼钢一连铸问题中，l a l l yc ta 1 【3 】提出了一种解决炼钢一 连铸问题的混合整数规划模型，但这个模型并没考虑炼钢一连铸生产管理实际环境的 复杂约束。t a n g 【4 】建立了炼钢一连铸生产调度整数规划模型并采用拉格朗日松弛法将 该问题变为线性规划模型求解，取得了很好的效果。b e l l a b d a o u i & t e g h e m 5 】针对炉 次在转炉阶段具有不同优先级的炼钢一连铸问题建立了混合整数规划模型，并使用标 准软件包o m p a r t n e r s 求解。h a r j u n k o s k i & c r r o s s m a n n 6 】提出了炼钢一连铸问题的混合 肆 一 上海交通大学博士论文 整数规划模型，并将该问题分解为若干小规模的子问题求解，该方法能够在较短的 时间内获得较高质量的解。 在热轧带钢生产调度领域，数学规划的方法通过建立热轧生产调度的优化模型， 采用精确的方法求得最优解。r e d w i n e & w i s m e r 7 1 提出了基于数学规划的订单调度模 型，并利用动态规划方法来解决离线钢铁企业生产调度问题。在这个模型中，考虑 了很多实际约束，然而太多的约束给计算带来了困难。w r i g h te ta 1 1 8 】针对热轧调度问 题建立了一个多目标数学模型。该模型不但考虑了组批问题，而且考虑了单元排序 问题，但由于该模型过于复杂，未应用现有算法进行求解。k o s i b ae ta 1 1 9 主要关注带 钢生产调度分析过程的发展。建立了一个不对称的旅行商问题( t s p ) 模型来建模和解 决带钢轧制问题。p a n & y a n g 1 0 1 将热轧批次问题建模为一个多目标的多路径问题，并 将该问题进一步分解为最小成本的多路径问题，背包问题和线性分配问题，最后采 用列生成法与h u n g a r i a n 算法结合的方法求解该问题。 。 辩 数学规划方法是隐含枚举整个空间的搜索方法，理论上能够提供调度问题的最 优解，但求解问题计算量太大，搜索效率低，当问题比较复杂时，一方面存在“组 合爆炸 问题，另一方面由于模型过于简化不能很好的解决问题。对于比较复杂多 变的生产调度来说，单一的数学规划方法存在求解空间大和计算困难等问题，所以 数学方法往往需要结合其他模型和方法，才能取得较好的效果。 1 3 2 人工智能算法 人工智能算法包括启发式方法、遗传算法、粒子群算法、模拟退火、禁忌搜索 等，它们主要用于解决大量的实际应用问题。目前，这些算法在钢铁生产调度中有 着广泛的应用。 ( 1 ) 启发式方法 启发式方法是相对于最优算法提出的，通常称为规则调度，是指系统运行时， 根据一定的规则和策略来决定下一步操作的调度方法。启发式方法主要建立在领域 知识的基础上，通过经验和规则减小问题的求解空间，指导问题的求解。启发式算 法并不一定能保证该解的最优性，甚至在多数情况下，无法阐述所得解与最优解的 近似程度，但是可大大减少大规模调度问题的求解时间。与传统的数学规划方法相 比，启发式方法的优点是直观、简单、实用，且花费求解时间较少、易于实现，在 5 第一章绪论 实际生产中有着非常广泛的应用。 m i n t o ne ta 1 提出了一种消除设备冲突启发式规则求解炼钢一连铸生产调度问 题，并取得了较好的效果。p a c c i a r e l l i & p r a n z o 1 2 1 根据炼钢一连铸生产调度的特点，建 立了该问题的决策图模型，并采用基于束搜索( b e a ms e a r c h ) 的启发式规则求解该模 型，通过算法结果与问题下界的比较，说明了该算法的有效性。李霄峰等1 3 1 针对炼 钢一连铸生产调度，建立了该问题的动态调度模型，并采用启发式规则求解。刘光航 等建立了综合考虑炉次的设备指派和作业排序的混合整数线性规划模型，在探讨 炉次设备指派规则、缓解资源冲突方法的基础上，提出了一种面向实际应用的启发 式算法。 ( 2 ) 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) ，是由m i c h i g a n 大学h o l l a n d 教授于1 9 7 5 年 首次提出的一种求解问题的全局搜索算法【15 1 。其借鉴生物界适者生存、优胜劣汰的 进化理论，以群体解为起点，通过自然选择的方式选取具有较高适应度的个体进入 下一代，被选择的个体再通过交叉操作产生新的个体，而变异操作用于保持群体的 多样性，通过不断的迭代循环，新的个体代替旧的个体，实现群体适应度的提高。 遗传算法采用简单的编码技术表示优化问题的解，以概率化的寻优方法搜索整个解 空间，具有内在的隐并行性和良好的全局寻优能力，在组合优化、生产调度、人工 智能等各种领域都有广泛的应用。 朱道飞等【1 6 】通过对炼钢连铸生产特点分析，建立一种炼钢连铸的遗传优化模 型，并采用遗传算法求解该问题。c h e ne ta 1 【1 7 】用带时间窗的车辆路径问题( v e h i c l e r o u t i n gp r o b l e mw i t ht i m ew i n d o w s ，v r p t w ) 建立热轧调度问题的模型，然后应用改 进的遗传算法求解该模型。t a n ge ta 1 【1 8 】等基于多旅行商( m u l t i p l et r a v e l l i n gs a l e s m a n p r o b l e m , m t s p ) 的模型提出了一个并行的热轧调度策略，并采用改进的遗传算法求 解。 ( 3 ) 粒子群优化算法 粒子群优化算法( p s o ) 是一种基于群智能方法的演化计算技术，其基本概念源于 对鸟群捕食行为的研究，是由k e r m e y & e b e r h a r t 于1 9 9 5 年提出的【1 9 1 。与遗传算法 类似，在p s o 算法中，系统初始化为一组随机解，通过迭代搜寻最优解。与遗传算 法不同的是，在p s o 算法中并没有使用交叉及变异操作，而是粒子在解空间追随全 6 释 峥 0 上海交通大学博士论文 局及局部最优的粒子进行搜索。在遗传算法中，染色体互相共享信息，所以整个种 群是比较均匀的向最优区域移动，而在p s o 算法中，只有全局及局部最优粒子给出 信息给其他粒子，这是单向的信息流动，整个搜索更新过程是跟随当前最优解的过 程。与遗传算法比较，在大多数情况下，所有的粒子可能更快的收敛于最优解。李 铁克【2 川考虑了带库存能力约束的集成批量计划与冷轧调度问题，提出了基于粒子群 的求解算法，取得不错的结果。 ( 4 ) 模拟退火 模拟退火算 法( s i m u l a t e da n n e a l i n g ，s a ) 最初是由m e t r o p o l i se ta 1 【2 1 1 提出， k i r k p a t r i c kc ta 1 【2 刁将其作为一种启发式的随机搜索算法，并成功的应用于组合优化问 题。s a 的理论基础为组合优化问题的求解过程与物理系统退火过程之间的相似性。 从某一初始温度开始，搜索过程以概率的方式从一个状态迁移到另外一个状态，最 终趋于全局最优解，整个搜索过程由温度参数t 来控制。s a 是局部搜索算