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