（控制理论与控制工程专业论文）基于反馈校正机制的优化算法设计及其在薄板轧制调度中的应用.pdf

p h d d i s s e r t a t i o n t h eo p t i m i z a t i o na l g o r i t h mw i t hf e e d b a c ka n ds e l f - t u n i n g m e c h a n i s ma n da p p l i c a t i o n si nt h er o l l i n gb a t c hs c h e d u l i n g d e p a r t m e n t ： m a j o r ： a u t h o r ： s u p e r v i s o r ： p r o b l e m d e p t o f a u t o m a t i o n c o n t r o lt h e o r ya n de n g i n e e r i n g p a nc h a n g c h u n p r o f y a n gg e n k e s h a n g h a ij i a ot o n gu n i v e r s i t y j u n e2 0 0 9 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 学位论文作者签名：淫辛瘤 日期：ad 卜年弓月7 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。 保密口，在_ 年解密后适用本授权书。 本学位论文属于 不保密咽。 ( 请在以上方框内打“4 ) 学位论文作者签名：赫专 指导教师签名： 日期：a 。6 7 年月弓。日 日期：a 。7 年 上海交通大学1 尊士学位论文答辩决议书 所柏j 控制理论与控制：1 i 样姚名潘常春学号0 0 4 0 3 2 9 0 1 7 学科 指导教师杨根科 答辩 2 0 0 9 0 6 2 5 答辩 电信学院2 号楼4 0 6j 一, 日期地 论文题h 基于反馈校t t ) l $ i j 的优化算法设计及其在薄板轧制调度, pi l ：jj 、7 1 | j 投票表决结果：7 7 7( 同意票数实到委员数应到委员数)答辩绌论：9 螽矗 口来通过 评语和决议： 。 潘常春的博士论文提出了一种“反馈校正机制的组合优化方法，对钢铁企业中薄板轧制调度 问题开展了建模与优化研究，论文选题具有重要的理论意义及实用价值。论文的主要结果如i 卜： ( 1 1 提出了解决非对称旅行商问题的基于反馈校正原理的优化算法框架。 论基础和系统深入的专业知识，独立进行科研的能力强荔妄期中口黔鞭楚，i n j p l 口j 咫止碉。台 j _ ii _ 致同_ 通过其 囊一i j ： ：士学位隐：，心长篇羔羹 t i 夏i 孓”叠x ；气- ：o 。：夥、斌瓠、) 、龟士箕叁 鬻囊蓊虢+ 。- 。，夔7 - | ： “：一藤蘩鬃穗_ 节年馨迦u t 幺嚣： 茁毫： 麓兹勰舔蘸参参徽j 二。 职称 单位 签名 籀 # h 。勘 乎， n 案 4 - t 髫、r 唧b o 。葛。 ；麟顾牵生 教授 华东删工大。誓 琵荔l 窆幽蔷i 二女i 哺i 起彰舞 。： 麓薹 两对- 绳 刺潮j渡员，周武能 教授 东华火学 鬻j 熬獭x 席裕庚教授上海交通大学 谣话汝 蓊j 费z 。一、f ；a 委员汪小帆 教授f - 海交通大学 挣椰 j石 成 骱纱 ? 争j 员 委员 李少远教授j ：海交通大，# 签 乙互忍起 t 一- 委员 王景成教授j ：海，爻通人学 名 丧逸泼 畦 委员 杨根科教授上 f l f 交通人学 嫁： 三胁 1 f ：?秘1 5 吴沂军丁程师h 每它通：人学 o耩w罐一 攥罐 ， ， 歹j 摘要 基于反馈校正机制的优化算法设计及其在薄板t l $ i j 调度中的应 用 摘要 组合优化问题广泛存在于科学研究和工程应用中的各个领域。设计快速、可靠 的最优化算法一直是研究者不懈努力的目标。随着现代社会日益增多的复杂问题， 传统的确定性最优化方法存在计算复杂性方面的局限性，而启发式算法，包括现代 智能优化算法在内，尽管简单、通用，但是不能保证解的质量。因此如何设计一种 集成两种算法优点并应用于实际问题的混合算法正成为学术界关注的热点问题之 一。而在钢铁生产中，尤其是在轧制调度问题中，存在着大量的组合优化问题。轧 制过程是钢铁生产过程中的关键工序之一，优化钢铁轧制过程直接关系到成品的质 量、库存的成本、客户的满意度。因此，该研究具有重要的经济意义。 本文提出了基于反馈校正机制的混合优化算法，并分别针对薄板生产过程中的 热轧调度问题和冷轧连续镀锌生产线调度问题做了深入的研究，其创新点主要概括 有如下两个方而： 从建模的角度，考虑了轧辊和轧件之间的耦合效应，建立了基于时变参数的 调度模型。建模的难点是由于不同的轧件调度会造成不同程度的轧辊磨损，轧辊的 磨损程度会直接影响轧件的性能，从而影响后续的调度结果。轧件和轧辊的耦合效 应在连续镀锌线的平整机生产过程中体现的尤为明显。 从算法的角度，设计了基于反馈校正原理的集成数学规划和启发式算法的混 合算法框架。目的在于利用数学规划的精确性和启发式算法的快速性求解组合优化 问题。反馈校正算法的原理是通过算法之间的大量信息交互，使得在不影响最优解 的前提下简化问题。 具体研究内容包括以下几个方面： ( 1 ) 提出了解决非对称旅行商问题( a t s p ) 的基于反馈校正原理的优化算法框 架。a t s p 是许多工业生产调度问题原型，也是热轧问题需要解决的一个关键子问题。 该方法核心是依据a t s p 问题松弛模型对偶关系推断a t s p 最优解被排除弧集合的 弧排除算法。算法框架以a t s p 问题的弧集合作为“参考输入”，以a t s p 最优解的 上下界求解算法作为“控制对象”，以弧排除算法作为“反馈校正控制器”，其“反 摘要 馈输入”是“控制对象”的上下界差值。算法迭代过程中，上下界差值缩小，排除 弧集合增加，算法呈现出自收敛性。该框架将数学规划方法和元启发式算法系统的 集成在一个统一的框架之中，无论从理论上和还是从仿真上都充分说明该自收敛算 法是非常有效的。 ( 2 ) 建立了热轧计划、调度问题的基于多路径、多目标的数学模型。与以往热轧 模型不同之处在于：( i ) 将同宽度连续轧制数量的限制建立为资源约束模型；( i i ) 通 过递阶目标层次结构，将原问题分解为易于解决的子问题求解。提出了基于数学规 划与启发式方法相结合的混合策略。针对大型工业调度问题，以求近优解为出发点。 算法的主要思想是根据对问题的宏观分析，松弛模型的复杂约束，通过数学规划定 位最优解或者近优解的理想区域，然后由启发式算法进行后续寻优或者修复不可行 解。相对与一般的混合算法，这种策略不仅可以找到相当出色的次优解，并且能够 给出下界，可对解的性能做有效的评估。 ( 3 ) 针对复杂的连续镀锌生产线调度问题，考虑了轧辊性能与轧件之间耦合约 束，并建立了时间相关旅行商问题( t d t s p ) 的调度模型，提出了基于反馈校正机 制的上、下界并行求解算法。以第二章提出的框架为基础，在该框架之中嵌入了次 梯度算法，使得在求解原始松弛问题的对偶问题过程中出现的大量对偶信息能够被 有效的利用以降低问题的规模，并在此基础之上，归纳了解元素集排除过程及其算 法实施的一般形式。而在一般的求解整数规划过程中，是根据对偶理论求解原问题 松弛问题的对偶问题获得下界。如果该下界对应的解是可行的，则已经找到了最优 解。若不可行，则采用分支定界或其他修复策略获得最优或者近优解。这种串行处 理策略，只利用到了最后的下界信息，而没有利用到求解对偶问题过程出现的大量 对偶信息。因此，如果不能充分利用计算获得的问题内部信息作为指导，算法性能 会降低。 本文对钢铁生产中的关键问题之一批量轧制调度问题从建模和算法设计两个方 面都做了较为深入的探讨，研究成果可为优化钢铁生产物流水平，提高生产作业计 划与调度的效率和质量提供理论与技术支持。本文研究工作受国家自然科学基金项 目( n o 6 0 5 7 4 0 6 3 ) 和香港城市大学基金( n o c i t y u l 2 2 3 0 5 ) 的资助。 关键字：热轧计划调度：连续镀锌线调度：组合优化：整数规划；次梯度算法；反 馈优化：元启发式方法；旅行商问题；时间相关的旅行商问题：车辆路由问题：最 短路径问题；解元素集合排除算法； a b s t r a c t t h eo p t i m i z a t i o na l g o r i t h mw i t hf e e d b a c ka n d s e l f - t u n i n g m e c h a n i s ma n d a p p l i c a t i o n si nt h er o l l i n gb a t c hs c h e d u l i n g p r o b l e m a b s t r a c t o p t i m i z a t i o np r o b l e me x i s t sw i d e l yi na l ld o m a i n so fs c i e n t i f i cr e s e a r c ha n d e n g i n e e r i n ga p p l i c a t i o n s m u c he f f o r th a sb e e n ，a n dw i l lc o n t i n u et ob c ，d e v o t e dt ot h e d e s i g no fg o o do p t i m i z a t i o na l g o r i t h m s ，t h a ti st h ea l g o r i t h mw h i c hf i n de x t r e m ao rn e a r e x t r e m ar e li a b l ya n dq u i c k l y t r a d i t i o n a ld e t e r m i n i s t i cm e t h o d sa p p e a rt ob eu n r e a li s t i c w h e ns o l v i n gc o m p l e xp r o b l e mi n v o l v i n gi nm o d e mp r a c t i c a la p p l i c a t i o n sd u et og r e a t c o m p u t a t i o n a lc o m p l e x i t y h e u r i s t i cm e t h o d s ，i n c l u d i n gi n t e l l i g e n t o p t i m i z a t i o n a l g o r i t h m s ，a r es i m p l e ，g e n e r a la n dc a nb ei m p l e m e n t e de a s i l yb u tt h e yc a nn o tp r o v i d e s o l u t i o n sw i t hq u a l i t yg u a r a n t e e d s o ，h o wt od e s i g nah y b r i da n da p p l i c a b l ea l g o r i t h m w i t hb o t ha d v a n t a g e so ft h et w ok i n d so fm e t h o d si sa t t r a c t i n gm o r ea n dm o r ei n t e r e s t s o f w o r l d w i d ed o m a i ns c h o l a r s m e a n w h i l e ，t h e r ea r em a n yo p t i m i z a t i o np r o b l e m sa r i s i n gi n s t e e lp r o d u c t i o n ，i np a r t i c u l a r l yi nr o l l i n gb a t c hs c h e d u l i n gp r o b l e m t h er o l l i n gp r o c e s si s o n eo ft h em o s ti m p o r t a n tp a r t si nt h ew h o l ep r o c e d u r eo fs t e e lp r o d u c t i o na n dt h u si so f g r e a ti m p o r t a n c ew i t hr e s p e c tt oi m p r o v i n gt h ef i n a lp r o d u c tq u a li t y , t or e d u c i n gt h e i n v e n t o r yc o s ta n dt om a k i n gam o r er e s p o n s i v ep o s i t i o nt o w a r d sc u s t o m e r s t h e r e f o r e ， t h er e s e a r c hi so fg r e a te c o n o m i c a lp r o f i t s i n t h i sd i s s e r t a t i o n ，an o v e lo p t i m i z a t i o nm e t h o dw i t hf e e d b a c ka n ds e l f - t u n i n g m e c h a n i s mi sp r o p o s e d m o r e o v e r , t h eh o ts t r i pm i l l ( h s m ) s c h e d u l i n gp r o b l e ma sw e l l a st h ec o n t i n u o u sg a l v a n i z i n gl i n e ( c g l ) s c h e d u l i n gp r o b l e mb a s e do nt h ep r o p o s e d m e t h o da r es t u d i e dc a r e f u l l y c o n c r e t e l y , t h em a j o rc o n t r i b u t i o n si n v o l v e di n t h i s d i s s e r t a t i o na r et w o f o l d ： f r o mt h ev i e w p o i n to ft h em o d e l i n g ，at i m e - d e p e n d e n tp a r a m e t e rm o d e li s e s t a b l i s h e dt oc o n s i d e rt h ec o u p l i n ge f f e c tb e t w e e nj o b s ( c o i l so rs l a b s ) a n dt h em a c h i n e ( r o l l s ) t h em u t u a l - e f f e c tl i e si nt h a tj o b st h r o u g ht h em i l lw i l lw e a rt h er o l l sa n dc h a n g e p h y s i c a lp a r a m e t e r so fs u r f a c eo f r o l l sm e a n w h i l et h ep h y s i c a lp a r a m e t e r so fs u r f a c ew i l l d e t e r m i n et h ep o s t e r i o rr o l li n gs e q u e n c et oa v o i df a b r i c a t i n gs u b s t a n d a r dp r o d u c t s s u c h m u t u a l - e f f e c ti sn o t a b l ee s p e c i a l l yi nt h ep r o c e s so fs k i np a s si nc g l f r o mt h ev i e w p o i n to ft h ea l g o r i t h m ，an o v e la l g o r i t h mw i t hf e e d b a c ka n d s e l f - t u n i n gm e c h a n i s mi sp r o p o s e dt os o l v ec o m b i n a t o r i a lo p t i m i z a t i o ni nw h i c ht h e m a t h e m a t i c a lp r o g r a m m i n ga n dt h eh e u r i s t i cm e t h o d sa r ei n t e g r a t e ds y s t e m a t i c a l l y t h e m o t i v a t i o ni st ot a k ef u i la d v a n t a g eo fb e t ht h et w ok i n d so fa l g o r i t h m st os o l v ec o m p l e x c o m b i n a t o r i a lp r o b l e m s t h em o s tp r o m i n e n ta d v a n t a g eo ft h ea l g o r i t h ml i e si nt h a t a l g o r i t h m si n v o l v e di nt h eh y b r i df r a m e w o r ki si n t e r a c t i v et h r o u g has i m p l em e c h a n i s m ， i i i a b s t r a c t w h i c hc a l lr e d u c et h es e a r c h i n gr e g i o nw i t h o u te x c l u d i n gt h eo p t i m a l i t y t h em a i nt o p i c si n c l u d e di nt h i sd i s s e r t a t i o na r eg e n e r a l i z e da sf o l l o w s ： f 1 ) an o v e la l g o r i t h m i cf r a m e w o r kb a s e do nt h ef e e d b a c ka n ds e l f - t u n i n gm e c h a n i s m i sp r o p o s e dt os o l v et h ea s y m m e t r i ct r a v e l i n gs a l e s m a np r o b l e m ( a t s p ) a t s pa n di t s v a r i a t i o n sa r ev e r yc o m m o n l yu s e dm o d e l st of o r m u l a t em a n yp r a c t i c a lp r o b l e m s h e r e ， a t s pi sak e ys u b p r o b l e mt h a th a st od e a lw i t hi no r d e rt os o l v et h eh s ms c h e d u l i n g p r o b l e m t h em a i ni d e ah i n ti nt h e 仃a m e w o r ki st h a tw ed e v e l o pa na l g o r i t h mt oe x c l u d e i n c r e a s i n g l ya r c s n o tb e l o n g i n gt ot h eo p t i m a ls o l u t i o nu s i n gt h ed u a li n f o r m a t i o n p r o d u d e dd u r i n gs o l v i n gt h ed u a lp r o b l e mo f t h er e l a x e da t s pp r o b l e m i nt h ef r a m e w o r k ， t h es o l u t i o nc o m p o n e n t ss e ti sr e g a r d e da st h e “r e f e r e n c ei n p u t ”，a n dt h ei o w e r - b o u n d s o l v e ra sw e l la st h eu p p e rb o u n ds o l v e ri ss e r v e da st h e “c o n t r o l l e dp l a n t t h ea l g o r i t h m o fe x c l u d i n ga r c sn o tb e l o n g i n gt ot h eo p t i m a ls o l u t i o ni su s e da st h e “c o n t r o l l e r ”a n dt h e g a pb e t w e e nt h el o w e rb o u n da n dt h eu p p e rb o u n di se m p l o y e da s t h ei n p u tt ot h e c o n t r o l l e r d u r i n gt h ep r o c e s so fi t e r a t i o n s ，t h eg a pb e t w e e nt h ei o w e rb o u n da n dt h e u p p e rb o u n di sr e d u c e dg r a d u a l l y s o ，t h ec a r d i n a l i t yo ft h ee x c l u d i n ga r c s e tw i l lb e a u g m e n t e dw h i c hg u a r a n t e e st h ea l g o r i t h m ss e l f - c o n v e r g e n c et ot h eo p t i m a ls o l u t i o n t h e m a t h e m a t i c a lp r o g r a m m i n ga n dt h eh e u r i s t i cm e t h o da r ei n t e g r a t e ds y s t e m a t i c a l l y t h e s u p e r i o r i t yo ft h eh y b r i da l g o r i t h mo v e ras i n g l em e t h o dc a nb ei l l u s t r a t e dt h e o r e t i c a l l y a n dt h ec o m p u t a t i o n a le x p e r i m e n t sv e r i f yt h ee f f i c i e n c y ( 2 ) t h eh s mp l a n n i n ga n ds c h e d u l i n gp r o b l e mi sm o d e l e d a sam u l t i - r o u t ea n d m u l t i o b j e c t i v ep r o b l e m ( m r m o p ) i td i f f e r sf r o me a r l i e rw o r ki nt h ef o l l o w i n gt w o a s p e c t s ：( i ) t h er e s t r i c t i o no fl i m i t i n gt h en u m b e ro fs l a b sp r o c e s s e dc o n s e c u t i v e l yw i t ht h e s a m ew i d t hw i t h i nas i n g l er o u n di sf o r m u l a t e da sar e s o u r c ec o n s t r a i n t ( i i ) b yd e f i n i n ga h i e r a r c h i c a lc o s ts t r u c t u r ei ti sn a t u r a lt od e c o m p o s et h em r m o pi n t os e v e r a l w e l l s t u d i e d s u b - p r o b l e m s a m i x e ds e r i a l s t r a t e ：g y i s d e v e l o p e d t h a t c o m b i n g m a t h e m a t i c a lp r o g r a m m i n ga n dl o c a lh e u r i s t i c s t os o l v i n g al a r g e s c a l ei n d u s t r i a l p r o b l e m ，t h es t r a t e g y , f r o mt h ev i e w p o i n to ff i n d i n gs u b - o p t i m a ls o l u t i o n s ，f i r s te m p l o y t h em a t h e m a t i c a lp r o g r a m m i n gt ol o c a t et h em o s tp r o m i s i n gs e a r c h i n gr e g i o na n dt h e nl e t h e u r i s t i c sp e r f c i r mt h ef u r t h e ro p t i m i z a t i o no rr e p a i rs o m ei n f e a s i b l es o l u t i o n s c o m p a r e d w i t hs o m ee x i s t i n ga l g o r i t h m s ，n o to n l yc a n o u rm e t h o df i n dap r o m i s i n gs o l u t i o n ，b u ta l s o i tp r o v i d e sat i g h ti o w e rb o u n dt oe v a l u a t et h ef o u n ds o l u t i o n c o m p u t a t i o n a lr e s u l t sa r e p r e s e n t e dc o m p a r e dw i t hs e v e r a lp r o m i s i n gm e t h o d so np r a c t i c a ld a t aw h i c hd e m o n s t r a t e t h ee f f i c i e n c yo ft h ep r o p o s e da l g o r i t h m ( 3 ) at i m ed e p e n d e n tt r a v e l i n gs a l e s m a np r o b l e m ( t d t s p ) i sm o d e l e df o r t h e c o m p l e xc g ls c h e d u l i n gp r o b l e mi nw h i c ht h ec o u p l i n ge f f e c tb e t w e e nt h em a c h i n e a n d j o b si sc o n s i d e r e d ap a r a l l e lh y b r i da l g o r i t h mf r a m e w o r kw i t hf e e d b a c ka n ds e l f - t u n i n g m e c h a n i s mi sp r e s e n t e dt h a ts i m u l t a n e o u s l yu t i l i z e st h el o w e rb o u n da n du p p e rb o u n d b a s e do nt h ef r a m e w o r kp r e s e n t e di nc h a r t e r2 ，t h es u b g r a d i e n ta l g o r i t h mi si n c o r p o r a t e d t ou t i li z et h ei n f o r m a t i o ng e n e r a t e di nt h ep r o c e s so fs o l v i n gt h ed u a lp r o b l e mo ft h e r e l a x e dp r i m a lp r o b l e mi no r d e rt or e d u c et h es e a r c h i n gr e g i o n f u r t h e rs t e p ，w ea l s o 划- a b s t r a c t p r e s e n tt h eg e n e r a l i z e df o r ma n dl t sa l g o r i t h m i ci m p l e m e n t a t i o na b o u th o w t or e d u c et h e s o l u t i o nc o m p o n e n ts e tw i t h o u te x c l u d i n gt h eo p t i m a ls o l u t i o n t h ep r o c e s si sv e r y d i f f e r e n tf r o mt h et y p i c a lw a yt oh a n d l et h ei n t e g e rp r o g r a m m i n gp r o b l e mw h e r eo n l yt h e b e s ts of a rl o w e rb o u n di su s e dt oo b t a i na no p t i m a li n t e g e rs o l u t i o n f o re x a m p l e ，t h eb e s t s of a rl o w e rb o u n di sc o m m o n l ye m b e d d e di ns o m eu p p e r - l a y e rf r a m e w o r ks u c ha sb r a n c h a n db o u n da l g o r i t h mi ft h es o l u t i o nc o r r e s p o n d i n gt ot h el o w e rb o u n di si n f e a s i b l e t h u s ， p l e n t y o fi n f o r m a t i o np r o d u c e dd u r i n gs o l v i n gt h ed u a lp r o b l e mi sd i s c a r d e d t h e p e r f o r m a n c eo f t h ea l g o r i t h mi sd e g e n e r a t e dd u et ot h ei n e f f i c i e n tu s a g eo ft h eo b t a i n e d i n f o r m a t i o n i ns u m m a r y , t h em o d e l sa n da l g o r i t h m sf o rt h er o l l i n gb a t c hs c h e d u l i n gp r o b l e m ，o n e o ft h ek e yp a r t si nt h ee n t i r e s t e e lp r o d u c t i o n ，a lew e l le x p l o r e di nt h er e s e a r c h t h e a c h i e v e m e n t sc a np r o v i d et h e o r e t i c a la n dt e c h n i c a ls u p p o r tf o ro p t i m i z i n gl o g i s t i c si nt h e s t e e lp r o d u c t i o np r o c e s sa n de n h a n c i n gt h ee f f i c i e n c ya n dq u a l i t yo fp r o d u c t i o np l a n n i n g a n ds c h e d u li n g t h ew o r ki ss u p p o r t e db yg r a n t sf r o mn a t i o n a ln a t u r a ls c i e n c e f o u n d a t i o no fc h a i n ( g r a n tn o 6 0 5 7 4 0 6 3 ) a n dc i t yu n i v e r s i t yo fh o n g k o n g ( g r a n tn o c i t y u i2 2 3 0 5 ) k e y w o r d s ：h s ms c h e d u l i n gp r o b l e m ；c g ls c h e d u l i n gp r o b l e m ；c o m b i n a t o r i a l o p t i m i z a t i o n ；i n t e g e rp r o g r a m m i n g ；s u b g r a d i e n to p t i m i z a t i o n ；f e e d b a c ko p t i m i z a t i o n ； m e t a - h e u r i s t i c s ；a t s p ；t d t s p ；v r p ；s o l u t i o nc o m p o n e n t s e te x c l u d i n ga l g o r i t h m ； v - 目录 目录 第一章绪论1 1 1 引言1 1 1 1 组合优化理论及分类1 1 1 2 组合优化算法研究的关键问题一3 1 2 研究背景、意义及现状4 1 2 1 钢铁生产流程概述5 1 2 2 钢铁生产作业计划调度问题特点及主要内容6 1 2 3 钢铁轧制过程及其调度研究现状8 1 3 生产调度问题与组合优化的关系1