mtsp模型及求解word版(已修改)
2025-09-02 16:22 本頁面
【正文】 熱軋生產(chǎn)調(diào)度的多旅行商問題模型及求解摘 要：傳統(tǒng)對于熱軋調(diào)度的研究,往往采用的是串行策略，實質(zhì)是一種貪婪方法,可能導致局部最優(yōu)。本文從全局最優(yōu)觀點提出能夠同時產(chǎn)生一個班次中的M個軋制單元計劃的并行策略，并且根據(jù)實際生產(chǎn)約束，可以熱軋調(diào)度問題歸結(jié)為多旅行商問題模型。為了求解，將MTSP變換為單旅行商問題模型，并適用改進遺傳算法能有效搜索出最優(yōu)解。關(guān)鍵詞：熱軋生產(chǎn)；調(diào)度；旅行商問題；改進遺傳算法鋼鐵企業(yè)在實際編制熱軋生產(chǎn)調(diào)度時，一般都是從合同訂單預(yù)選池中挑選訂單，依次編制出M個軋制計劃單元[1]。這種策略模擬人工編制計劃的思想，采用串行策略建立了單旅行商模型[2]。但是這種策略類似于貪婪方法，有可能陷入局部最優(yōu)。一種合理的辦法是并行方法，即從訂單池中同時編制出M個軋制單元計劃。并行方法可以歸結(jié)為MTSP。1熱軋生產(chǎn)調(diào)度的問題描述 問題描述 將全部訂單看成一個個節(jié)點(相當于TSP中的城市)，一個軋制生產(chǎn)單元看成是經(jīng)過一定數(shù)目節(jié)點的一條旅行路徑，節(jié)點之間的距離(評價值)可定義為軋制規(guī)范的評價值（如相鄰板坯的寬度、厚度、硬度等必須滿足一定的約束條件），則熱軋生產(chǎn)調(diào)度問題可歸結(jié)為非對稱旅行商模型[3]。由于熱軋生產(chǎn)調(diào)度問題中的軋制單元計劃是一條開放路徑，每一個訂單只能軋制一次。如果一個熱軋調(diào)度包括M條軋制單元計劃，則存在M個開放路徑，并且任意兩個軋制單元計劃的開始和結(jié)束點的訂單都不相同。這意味著任意兩個軋制單元計劃之間沒有相同的點(訂單)，開始訂單也不確定，所以必須建立全新的模型。 熱軋調(diào)度問題進入標準MTSP問題的變換為了將熱軋調(diào)度問題轉(zhuǎn)換為MTSP問題,引進了M個虛擬節(jié)點(定單) 其編號為N+1,N+2,…,N+M。通過兩個步驟：第一步是一個虛擬節(jié)點被引進熱軋調(diào)度問題當中，要求所有的軋制單元計劃都從這個虛擬節(jié)點出發(fā)。這個虛擬節(jié)點既是源點也是收點，這樣就構(gòu)成了閉合回路。第二步是M1個附加節(jié)點被引進，這樣可以保證M個閉合回路的形成，同時滿足每個節(jié)點正好被訪問一次，也就是每一個生產(chǎn)定單正好被軋制一次[4]。2 熱軋生產(chǎn)調(diào)度的MTSP模型 評價指標、變量和參數(shù)定義按照軋制工藝規(guī)范約束,相鄰板坯之間的寬度、厚度和硬度等的變化越小，綜合衡量的指標越優(yōu)。因此，兩節(jié)點之間的距離可定義為相鄰軋件軋制參數(shù)的改變(跳躍)值；將相鄰板坯之間的寬度、厚度和硬度跳躍值之和作為懲罰值，對超出軋制規(guī)范約束的賦予一個較大的懲罰值。對任一軋制計劃單元，其優(yōu)化目標可定義為：每個軋制單元的總評價懲罰值(相鄰節(jié)點評價值之和)最小。假設(shè)有N個訂單將在一個班次內(nèi)的M個軋制單元計劃進行軋制，這N個訂單可以看成N個節(jié)點，M個軋制單元計劃可以看成M個旅行商。引進M個虛擬節(jié)點，那么熱軋計劃排出問題可以
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1