基于反饋校正機制的優(yōu)化算法設計及其在薄板軋制調(diào)度中的應用.pdf

1、組合優(yōu)化問題廣泛存在于科學研究和工程應用中的各個領域。設計快速、可靠的最優(yōu)化算法一直是研究者不懈努力的目標。隨著現(xiàn)代社會日益增多的復雜問題,傳統(tǒng)的確定性最優(yōu)化方法存在計算復雜性方面的局限性,而啟發(fā)式算法,包括現(xiàn)代智能優(yōu)化算法在內(nèi),盡管簡單、通用,但是不能保證解的質(zhì)量。因此如何設計一種集成兩種算法優(yōu)點并應用于實際問題的混合算法正成為學術界關注的熱點問題之一。而在鋼鐵生產(chǎn)中,尤其是在軋制調(diào)度問題中,存在著大量的組合優(yōu)化問題。軋制過程是鋼鐵生

2、產(chǎn)過程中的關鍵工序之一,優(yōu)化鋼鐵軋制過程直接關系到成品的質(zhì)量、庫存的成本、客戶的滿意度。因此,該研究具有重要的經(jīng)濟意義。
　　 本文提出了基于反饋校正機制的混合優(yōu)化算法,并分別針對薄板生產(chǎn)過程中的熱軋調(diào)度問題和冷軋連續(xù)鍍鋅生產(chǎn)線調(diào)度問題做了深入的研究,其創(chuàng)新點主要概括有如下兩個方面:
　　 從建模的角度,考慮了軋輥和軋件之間的耦合效應,建立了基于時變參數(shù)的調(diào)度模型。建模的難點是由于不同的軋件調(diào)度會造成不同程度的軋輥磨損,

3、軋輥的磨損程度會直接影響軋件的性能,從而影響后續(xù)的調(diào)度結果。軋件和軋輥的耦合效應在連續(xù)鍍鋅線的平整機生產(chǎn)過程中體現(xiàn)的尤為明顯。
　　 從算法的角度,設計了基于反饋校正原理的集成數(shù)學規(guī)劃和啟發(fā)式算法的混合算法框架。目的在于利用數(shù)學規(guī)劃的精確性和啟發(fā)式算法的快速性求解組合優(yōu)化問題。反饋校正算法的原理是通過算法之間的大量信息交互,使得在不影響最優(yōu)解的前提下簡化問題。
　　 具體研究內(nèi)容包括以下幾個方面:
　　 (1)提

4、出了解決非對稱旅行商問題(ATSP)的基于反饋校正原理的優(yōu)化算法框架。ATSP是許多工業(yè)生產(chǎn)調(diào)度問題原型,也是熱軋問題需要解決的一個關鍵子問題。該方法核心是依據(jù)ATSP問題松弛模型對偶關系推斷ATSP最優(yōu)解被排除弧集合的弧排除算法。算法框架以ATSP問題的弧集合作為“參考輸入”,以ATSP最優(yōu)解的上下界求解算法作為“控制對象”,以弧排除算法作為“反饋校正控制器”,其“反饋輸入”是“控制對象”的上下界差值。算法迭代過程中,上下界差值縮小,

5、排除弧集合增加,算法呈現(xiàn)出自收斂性。該框架將數(shù)學規(guī)劃方法和元啟發(fā)式算法系統(tǒng)的集成在一個統(tǒng)一的框架之中,無論從理論上和還是從仿真上都充分說明該自收斂算法是非常有效的。
　　 (2)建立了熱軋計劃、調(diào)度問題的基于多路徑、多目標的數(shù)學模型。與以往熱軋模型不同之處在于:(ⅰ)將同寬度連續(xù)軋制數(shù)量的限制建立為資源約束模型；(ⅱ)通過遞階目標層次結構,將原問題分解為易于解決的子問題求解。提出了基于數(shù)學規(guī)劃與啟發(fā)式方法相結合的混合策略。針對大

6、型工業(yè)調(diào)度問題,以求近優(yōu)解為出發(fā)點。算法的主要思想是根據(jù)對問題的宏觀分析,松弛模型的復雜約束,通過數(shù)學規(guī)劃定位最優(yōu)解或者近優(yōu)解的理想?yún)^(qū)域,然后由啟發(fā)式算法進行后續(xù)尋優(yōu)或者修復不可行解。相對與一般的混合算法,這種策略不僅可以找到相當出色的次優(yōu)解,并且能夠給出下界,可對解的性能做有效的評估。
　　 (3)針對復雜的連續(xù)鍍鋅生產(chǎn)線調(diào)度問題,考慮了軋輥性能與軋件之間耦合約束,并建立了時間相關旅行商問題(TDTSP)的調(diào)度模型,提出了基于

7、反饋校正機制的上、下界并行求解算法。以第二章提出的框架為基礎,在該框架之中嵌入了次梯度算法,使得在求解原始松弛問題的對偶問題過程中出現(xiàn)的大量對偶信息能夠被有效的利用以降低問題的規(guī)模,并在此基礎之上,歸納了解元素集排除過程及其算法實施的一般形式。而在一般的求解整數(shù)規(guī)劃過程中,是根據(jù)對偶理論求解原問題松弛問題的對偶問題獲得下界。如果該下界對應的解是可行的,則已經(jīng)找到了最優(yōu)解。若不可行,則采用分支定界或其他修復策略獲得最優(yōu)或者近優(yōu)解。這種串行

8、處理策略,只利用到了最后的下界信息,而沒有利用到求解對偶問題過程出現(xiàn)的大量對偶信息。因此,如果不能充分利用計算獲得的問題內(nèi)部信息作為指導,算法性能會降低。
　　 本文對鋼鐵生產(chǎn)中的關鍵問題之一批量軋制調(diào)度問題從建模和算法設計兩個方面都做了較為深入的探討,研究成果可為優(yōu)化鋼鐵生產(chǎn)物流水平,提高生產(chǎn)作業(yè)計劃與調(diào)度的效率和質(zhì)量提供理論與技術支持。本文研究工作受國家自然科學基金項目(No.60574063)和香港城市大學基金(No.Ci