mtsp模型及求解word版-在線(xiàn)瀏覽
2025-02-24 12:59本頁(yè)面
【正文】 關(guān)鍵詞 ： 熱軋生產(chǎn)；調(diào)度；旅行商問(wèn)題；改進(jìn)遺傳算法 鋼鐵企業(yè)在實(shí)際編制熱軋生產(chǎn)調(diào)度時(shí) ， 一般都是從合同訂單預(yù)選池中挑選訂單 ， 依次編制出 M 個(gè)軋制計(jì)劃單元 [1]。但是這種策略類(lèi)似于貪婪方法 ， 有可能陷入局部最優(yōu)。并行方法可以 歸結(jié)為 MTSP。由于熱軋 生產(chǎn)調(diào)度 問(wèn)題中的軋制單元計(jì)劃是一條開(kāi)放路徑 ， 每一個(gè)訂單只能軋制一次。這意味著任意兩個(gè)軋制單元計(jì)劃之間沒(méi)有相同的點(diǎn)(訂單 )， 開(kāi)始訂單也不確定 ， 所以必須建立全新的模型。通 過(guò)兩個(gè)步驟 ： 第一步是一個(gè)虛擬節(jié)點(diǎn)被引進(jìn)熱軋調(diào)度問(wèn)題當(dāng)中 ， 要 求所有的 軋制單元計(jì)劃都從這個(gè)虛擬節(jié)點(diǎn)出發(fā)。 第二步是 M1 個(gè)附加節(jié)點(diǎn)被引進(jìn) ， 這樣可以保證 M 個(gè)閉合回路的形成 ， 同時(shí)滿(mǎn)足每個(gè)節(jié)點(diǎn)正好被訪(fǎng)問(wèn)一次 ， 也就是每一個(gè)生產(chǎn)定 單正好被軋制一次 [4]。因此 ， 兩節(jié)點(diǎn)之間的距離可定義為相鄰軋件軋制參數(shù)的改變 (跳躍 )值 ； 將相鄰板坯之間的寬度、厚度和硬度跳躍值之和作為懲罰值 ， 對(duì)超出軋制規(guī)范 約束的賦予一個(gè)較大的懲罰值。 假設(shè)有 N 個(gè)訂單將在一個(gè)班次內(nèi)的 M 個(gè)軋制單元計(jì)劃進(jìn)行軋制 ， 這 N 個(gè)訂 單可以看成 N 個(gè)節(jié)點(diǎn) ， M 個(gè)軋制單元計(jì)劃可以看成 M 個(gè)旅行商。在數(shù)學(xué)模型建立上 ， 借助單 TSP 模型的表達(dá) ， 即等價(jià)于一個(gè)旅行商訪(fǎng)問(wèn) N+M 城市 [5]。Δ G、Δ W、Δ H 分別為熱軋軋制規(guī)范所允許的相鄰板坯最大厚度、寬度與硬度跳躍值。約束式 (2)表示任務(wù) i 之后軋制的任務(wù)有且只有一個(gè) ； 約束式 (3)表示在訂單 j 之前有且只 有一個(gè)任務(wù)被軋制 ； 約束式 (4)~(6)表示軋制規(guī)范 ， 其中式 (4)表示相鄰板坯寬度跳躍約束 ， 式 (5)表示相鄰板坯厚度跳躍約束 ， 式 (6)表示硬度等級(jí)跳躍約束 ； 約束式 (7)是為了避免在可行解中構(gòu)成子回路而引進(jìn)的約束 ； 約束式 (8)表示變量是 01 變量 [6]。因此兩節(jié)點(diǎn)之間的距離可定義為相鄰軋件的各軋制參數(shù)的改變(跳躍 )值之和 ， 以此作為相鄰板坯之間的對(duì)軋制參數(shù)寬度、厚度和硬度跳躍值懲罰。 3 改進(jìn)的遺傳算法解決旅行商問(wèn)題 將熱軋調(diào)度中的 N 種任務(wù)看成 N 個(gè)城市 ,把加工不同任務(wù)的轉(zhuǎn)換懲罰看成是城市之間的距離 ， 這樣就把 熱軋生產(chǎn) 問(wèn)題歸結(jié)為一個(gè)旅行商問(wèn)題 [7]。為了提高搜索的速度和效率 ， 并針對(duì) 對(duì)熱軋調(diào)度的 TSP 問(wèn)題 模型 ， 我們對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行改進(jìn) ， 得到了一種改進(jìn)的遺傳算法 (MGA)。 在兩交 換啟發(fā)交叉規(guī)則中 ， 由 2 個(gè)父代生成 1 個(gè)子代 ， 當(dāng) 2 個(gè)父代的鏈結(jié)構(gòu)接近時(shí) ， 通過(guò)HGA 交叉后 ， 子代不會(huì)有很大的改 善 [9]。 三交換啟發(fā)交叉方法的基本思想 選 3 個(gè)參加交配的染色體作為父代 ， 以 8 個(gè)城市 （訂單） 為例來(lái)說(shuō)明這一過(guò)程 ， 其中 dij 由 表 1 給出 ,父代染色體為 ： A = 3 2 1 4 8 7 6 5 B = 2 4 6 8 1 3 5 7 C = 8 7 5 6 4 3 2 1 SUM1=42， SUM2=40， SUM3=46(SUM1， SUM2， SUM3 分別為這 3
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1