鋼鐵企業(yè)軋線批調(diào)度問題的建模與最優(yōu)化方法的研究.pdf

1、鋼鐵企業(yè)加工過程可分為煉鐵區(qū)、煉鋼區(qū)和軋線區(qū)。軋線區(qū)的生產(chǎn)工藝及管理的主要特點是物料以離散件（工件）的形式送入產(chǎn)線，物流呈交叉網(wǎng)狀分布，部分產(chǎn)線具有高溫特征，由于產(chǎn)線加工設備調(diào)整費用高，物料之間需要進行集批，經(jīng)常以串聯(lián)批的生產(chǎn)方式在產(chǎn)線上進行加工。這種以批生產(chǎn)方式為主的生產(chǎn)調(diào)度問題被稱為批調(diào)度。軋線批調(diào)度問題是對于給定的被調(diào)度的工件集合確定批的組成和結構，以及在相應產(chǎn)線設備上的分配、排序和時間表的問題，是一類帶有復雜約束的組合最優(yōu)化問題

2、。研究其建模與優(yōu)化方法對于充分挖掘機組產(chǎn)能、提高生產(chǎn)效率、節(jié)能降耗、提高產(chǎn)品質(zhì)量具有重要意義。
　　鋼鐵企業(yè)的軋線生產(chǎn)主要覆蓋熱軋、酸軋、連續(xù)退火、電鍍鋅及彩涂等生產(chǎn)階段，本文分別從不同的軋線生產(chǎn)階段中提煉出如下的批調(diào)度問題:熱軋并行產(chǎn)線的生產(chǎn)調(diào)度問題、冷軋連退產(chǎn)線鋼卷生產(chǎn)排序問題、冷軋連退產(chǎn)線鋼卷生產(chǎn)成組批調(diào)度問題、冷軋電鍍鋅產(chǎn)線鋼卷排序問題、冷軋彩涂產(chǎn)線鋼卷排序問題、軋線鋼卷生產(chǎn)調(diào)度問題。針對上述不同的問題建立了相應的數(shù)學規(guī)劃

3、模型，并根據(jù)問題的特點分別開發(fā)了基于動態(tài)規(guī)劃的多項式最優(yōu)算法、基于列生成的最優(yōu)化算法、基于禁忌搜索(TS)和過濾和扇(F&F)算法的智能優(yōu)化算法，最后以連續(xù)退火產(chǎn)線為背景開發(fā)了批調(diào)度決策支持系統(tǒng)，論文主要工作如下:
　　(1)以熱軋生產(chǎn)階段加工過程為背景，提煉出并行產(chǎn)線的生產(chǎn)調(diào)度問題。該問題在軋批的組成給定情況下（板坯鏈優(yōu)先級約束），確定軋批在并行熱軋產(chǎn)線上，即熱軋階段中的分配及排序，使得高溫的板坯由于等待所引起的總的能源損失費用

4、最小。該問題的特征是帶有鏈式優(yōu)先級約束、板坯動態(tài)到達、目標函數(shù)考慮能損特征?；谝陨咸卣?，當考慮能損量隨板坯等待時間的變化呈線性關系時，該問題可歸結為P|chains，rjk，hot|∑fjk(waitjk）。針對該問題的強NP-難求解特性，提出了分支定價算法，在分支樹的每個節(jié)點提出列生成算法構造下界，針對列生成算法價格子問題采用常規(guī)動態(tài)規(guī)劃算法求解復雜度高的難點，提出了基于狀態(tài)空間松弛的動態(tài)規(guī)劃算法，明顯地提高了子問題求解效率。為了增

5、強分支定價算法求解該類問題的通用性，進一步將該算法擴展到能損量隨板坯等待時間的變化呈非線性關系的復雜情況。通過實驗驗證，無論對于線性能源損失函數(shù)還是非線性能源損失函數(shù)，提出算法均可在合理時間內(nèi)最優(yōu)求解中規(guī)模問題。
　　(2)以連續(xù)退火生產(chǎn)線為背景，提煉出冷軋連退產(chǎn)線鋼卷生產(chǎn)排序問題。該問題是確定鋼卷在一個連退產(chǎn)線上的處理順序，不僅需要考慮兩個連續(xù)退火的鋼卷之間的退火溫度、寬度、厚度切換關系，盡量使總的生產(chǎn)切換費用最小;還需要考慮任

6、意三個鄰接鋼卷之間的退火溫度、寬度、厚度切換關系，使得切換趨勢盡量平滑。通過將此問題歸結為一類特殊的旅行商問題，建立了數(shù)學規(guī)劃模型。針對此問題難于求解的特征，提出禁忌搜索算法進行近似求解。為了進一步改進算法性能，克服搜索過程易于陷入局部最優(yōu)的缺點，提出了基于交替路徑變換鄰域的kick策略，構造了多項式動態(tài)規(guī)劃算法搜索此鄰域?；趯嶋H數(shù)據(jù)的實驗驗證所提的基于禁忌搜索的算法在合理的計算時間內(nèi)可有效的求解工業(yè)生產(chǎn)規(guī)模的算例。
　　(3)

7、以連續(xù)退火生產(chǎn)線為背景，提煉出冷軋連退產(chǎn)線鋼卷生產(chǎn)成組批調(diào)度問題。該問題對于給定的鋼卷簇，需要確定鋼卷在一條連退產(chǎn)線上，簇的分批決策、加工順序及調(diào)度時間表，其特征在于鋼卷按簇的方式組織生產(chǎn)，不同簇之間存在大的調(diào)整時間和調(diào)整費用，同簇內(nèi)的鋼卷之間存在小的調(diào)整時間及調(diào)整費用。對于該問題當目標是最小化總的調(diào)整費用和提前拖期懲罰費時，建立了線性整數(shù)規(guī)劃模型，開發(fā)了混合禁忌搜索和過濾和扇(F&F)算法的求解方法。在混合算法中，禁忌搜索算法用于產(chǎn)生

8、初始解及產(chǎn)生候選移動，F(xiàn)&F算法通過搜索Filter-and-fan鄰域樹從候選移動中篩選構造出較好的組合移動。通過與CPLEX標準軟件求解結果比較，驗證了所提出的混合算法的有效性。
　　(4)以電鍍鋅生產(chǎn)線為背景，提煉出冷軋電鍍鋅產(chǎn)線鋼卷排序問題。該問題在滿足相同后處理方式的鋼卷連續(xù)從寬到窄進行加工（相同寬度的鋼卷要求連續(xù)加工，稱為簇）等實際生產(chǎn)約束的要求的情況下，確定一條電鍍鋅產(chǎn)線上，鋼卷之間總切換費用最小的鋼卷順序。針對該問

9、題建立了線性整數(shù)規(guī)劃模型?；趯栴}的最優(yōu)解的結構特征和性質(zhì)分析，開發(fā)了兩階段復雜度為O(nk3)的多項式算法對該問題進行最優(yōu)求解。算法第一階段對于一個簇邊界鋼卷給定情況下確定該簇內(nèi)鋼卷加工順序。針對簇內(nèi)鋼卷加工順序子問題，構造了多項式動態(tài)規(guī)劃算法對其進行最優(yōu)求解。算法第二階段確定簇之間的加工順序。針對簇間排序子問題，構造了簇邊界鋼卷為狀態(tài)變量的動態(tài)規(guī)劃遞歸方程，能夠在多項式時間獲得問題的最優(yōu)解。為了滿足一些實際工業(yè)問題的動態(tài)實時性要求

10、，基于提出的最優(yōu)解性質(zhì)，開發(fā)了構造式啟發(fā)式算法。通過實驗表明了兩階段最優(yōu)算法計算時間明顯小于CPLEX獲得最優(yōu)解的時間;提出的啟發(fā)式算法與最優(yōu)解非常接近，運行時間穩(wěn)定且平均運行速度快于兩階段最優(yōu)算法。
　　(5)以彩涂生產(chǎn)線為背景，提煉出單個加工單元鋼卷排序問題和多個加工單元鋼卷排序問題。這兩個問題是在滿足實際生產(chǎn)約束情況下，從候選鋼卷中選擇部分鋼卷，分別構造一條彩涂產(chǎn)線上一個加工單元中切換費用最小的鋼卷順序和一條彩涂產(chǎn)線上多個加

11、工單元中切換費用最小的鋼卷順序。問題特征在于彩涂生產(chǎn)線中兩次換輥之間機組加工能力有限，鋼卷集批生產(chǎn)，寬度、厚度、顏色切換等工藝約束，以及同時考慮普通卷和過渡卷的選擇和排序。單個加工單元鋼卷排序問題可歸結為帶容量約束的帶選擇獎懲的旅行商問題。針對單個加工單元鋼卷排序問題中排序和選擇耦合的特點，提出有效降低排序困難的統(tǒng)治規(guī)則，并構造偽多項式動態(tài)規(guī)劃算法決策基于給定鋼卷排序的最優(yōu)鋼卷選擇方案。多個加工單元鋼卷排序問題可歸結為帶選擇懲罰的車輛調(diào)

12、度問題。針對同時考慮多個加工單元的所引起的求解困難，開發(fā)了禁忌搜索算法，提出在每次迭代中搜索多個鄰域獲得組合移動的策略，克服了搜索單一鄰域易于陷入局部最優(yōu)的困難。為了評價所獲得解的性能，提出列生成算法構造下界。經(jīng)實驗驗證，禁忌搜索算法可快速獲得近優(yōu)解，列生成算法所獲得的下界是緊的。
　　(6)以存在無關并行生產(chǎn)線的酸軋生產(chǎn)階段為背景，提煉出軋線鋼卷生產(chǎn)調(diào)度問題。該問題決策鋼卷在無關并行產(chǎn)線上的分配情況和加工順序，其特征在于考慮無關

13、并行產(chǎn)線、同時考慮總完成時間和總拖期兩個優(yōu)化目標。針對問題特征，建立了數(shù)學規(guī)劃模型描述問題。針對多目標特性，提出基于理想點法的求解策略，其中，針對最小化完工時間的目標函數(shù)，建立線性規(guī)劃模型描述問題，從而獲得問題的理想點;針對最小化總拖期目標函數(shù)，提出基于局域搜索的啟發(fā)式算法進行求解;綜合以上結果，將考慮最小化完工時間的目標函數(shù)的理想點作為解的上界，將多目標函數(shù)轉化為一個評價解與理想點接近程度的單目標問題，并提出局域搜索算法獲得原問題非劣