□高 聰

一、引言

本文研究的彩涂機(jī)組合同計(jì)劃是國(guó)內(nèi)某大型鋼鐵企業(yè)中面臨的實(shí)際問題，目標(biāo)是協(xié)調(diào)企業(yè)內(nèi)各機(jī)組之間的關(guān)系，從而優(yōu)化彩涂機(jī)組的庫(kù)存結(jié)構(gòu)，使彩涂機(jī)組可以得到更好的調(diào)度，降低生產(chǎn)成本，提高生產(chǎn)效率。一個(gè)彩涂產(chǎn)品的合同需要5道主要工序才能到達(dá)彩涂機(jī)組的前庫(kù)，分別為煉鐵、煉鋼、熱軋、冷軋和熱鍍鋅。由于生產(chǎn)工藝的限制，屬于同一合同的板卷通常不能在機(jī)組上連續(xù)生產(chǎn)。這導(dǎo)致屬于同一合同的板卷分處于各個(gè)機(jī)組的前庫(kù)之中。屬于同一合同且處于同一機(jī)組前庫(kù)內(nèi)的板卷稱為該合同的子合同。

一些機(jī)組，比如熱軋機(jī)組和冷軋機(jī)組，在調(diào)度方面的約束限制較少，其調(diào)度具有較大的自由度。在制定這些機(jī)組的調(diào)度計(jì)劃時(shí)更多的是考慮下游各機(jī)組的物流平衡。這就給工序機(jī)組的協(xié)調(diào)生產(chǎn)提供了可能。前道機(jī)組參照彩涂機(jī)組提供的時(shí)間表生產(chǎn)彩涂機(jī)組的子合同，子合同按照彩涂機(jī)組希望的時(shí)間到達(dá)彩涂機(jī)組前庫(kù)，從而達(dá)到優(yōu)化彩涂機(jī)組庫(kù)存結(jié)構(gòu)的目的，進(jìn)而降低生產(chǎn)成本和提高生產(chǎn)效率。

圖1為對(duì)彩涂機(jī)組進(jìn)行合同計(jì)劃前后的生產(chǎn)時(shí)間表，（a）中顯示根據(jù)子合同所在機(jī)組與機(jī)組間最小生產(chǎn)周期計(jì)算得到子合同對(duì)彩涂機(jī)組的最早到達(dá)時(shí)間；根據(jù)子合同最早到達(dá)時(shí)間，產(chǎn)生一個(gè)預(yù)調(diào)度；（b）中顯示根據(jù)得到的預(yù)調(diào)度和機(jī)組間平均生產(chǎn)周期，倒推得到子合同在各前道機(jī)組上的理想生產(chǎn)時(shí)間。機(jī)組間最小生產(chǎn)周期是指當(dāng)板卷具有最高優(yōu)先級(jí)時(shí)在機(jī)組間的生產(chǎn)間隔時(shí)間。機(jī)組間平均生產(chǎn)周期為通過以往生產(chǎn)數(shù)據(jù)統(tǒng)計(jì)的板卷在機(jī)組間的生產(chǎn)間隔時(shí)間。

圖1 彩涂機(jī)組合同計(jì)劃問題示意

子合同是彩涂機(jī)組合同調(diào)度問題的基本單位，屬于同一個(gè)合同的子合同除重量外的其他所有屬性都相同，比如寬度、厚度、涂層顏色等。一個(gè)合同中的任意子合同拖期，則該合同拖期。若有多個(gè)子合同拖期，則該合同的拖期量等于所有子合同中拖期量的最大值。

目前，已經(jīng)有很多關(guān)于鋼鐵工業(yè)調(diào)度問題的研究，但對(duì)鋼鐵企業(yè)內(nèi)部多機(jī)組之間協(xié)調(diào)的研究還比較少。Okano等[1]研究了冷軋區(qū)的調(diào)度問題，并且開發(fā)了一個(gè)復(fù)雜的智能算法求解此問題。Tang和Wang[2]研究了面向在庫(kù)板卷的彩涂機(jī)組調(diào)度問題，其調(diào)度對(duì)象均為在庫(kù)板卷，在計(jì)算拖期懲罰時(shí)，以板卷為單位。Wang和Tang[3]研究了包含尚未到庫(kù)的板卷的彩涂機(jī)組的調(diào)度問題，該研究只能被動(dòng)地接受板卷的到達(dá)時(shí)間，因此軋制單元的開始時(shí)間也需要被決定，以滿足生產(chǎn)的連續(xù)性。本文與Wang和Tang[3]研究的區(qū)別在于，本文根據(jù)彩涂機(jī)組合同計(jì)劃問題的結(jié)果可以給出子合同在各個(gè)機(jī)組上推薦的生產(chǎn)時(shí)間，并假設(shè)子合同可以按照期望的時(shí)間完成，因此軋制單元之中不允許有空隙，且目標(biāo)函數(shù)中不存在預(yù)處理費(fèi)用及庫(kù)存費(fèi)用。

本文設(shè)計(jì)了禁忌搜索算法和變鄰域算法以在合理的計(jì)算時(shí)間內(nèi)求得問題的近優(yōu)解。

二、求解方法

本節(jié)介紹彩涂機(jī)組合同計(jì)劃問題的求解方法。首先介紹產(chǎn)生初始解的啟發(fā)式算法，然后介紹在禁忌搜索和變鄰域算法中用到的2種鄰域，以及1種加速領(lǐng)域搜索的策略。

1.產(chǎn)生初始解

1個(gè)解由m個(gè)軋制單元組成，Πk為第k個(gè)軋制單元的順序，則1個(gè)解S可表示為S={Π1,Π2, …,Πm}。令S[i]表示解S中的第i個(gè)子合同。初始解的產(chǎn)生方式為串行方式，即先產(chǎn)生第一個(gè)軋制單元，然后產(chǎn)生第二個(gè)，直到所有子合同都被調(diào)度。初始解啟發(fā)式算法是基于貪婪思想設(shè)計(jì)的，即每次都找到與已調(diào)度的最后的子合同之間過渡費(fèi)用最少的子合同加入到調(diào)度中。

2.鄰域

禁忌搜索算法和變鄰域搜索算法都是基于鄰域搜索的算法。下面將介紹本文使用的2種鄰域，即插入鄰域和交換鄰域，以及加速鄰域搜索的策略。

（1）插入鄰域

插入鄰域是由在基解基礎(chǔ)上實(shí)施插入移動(dòng)得到的新解的集合。插入移動(dòng)將1個(gè)子合同從原來(lái)的位置移動(dòng)到一個(gè)新的位置上。在本文中，由于彩涂機(jī)組的寬度約束的限制，1個(gè)子合同在原所在軋制單元內(nèi)的可移動(dòng)空間非常小，插入移動(dòng)通常是將1個(gè)子合同在軋制單元之間進(jìn)行移動(dòng)。

（2）交換鄰域

1個(gè)對(duì)P(i,j)，表示1個(gè)交換移動(dòng)，交換的對(duì)象是子合同S[i]和S[j]。通過對(duì)解S實(shí)施交換移動(dòng)P(i,j)可以得到新解S'=Pij(S)。交換鄰域Nswap為式（1）。

被交換的子合同重量上會(huì)有差異，而且由于子合同是在不同軋制單元之間進(jìn)行交換，可能會(huì)導(dǎo)致移動(dòng)涉及的軋制單元的容量溢出。修復(fù)的過程等同于插入鄰域中的修復(fù)。

（3）加速策略

屬于同一合同的子合同，除重量外，具有完全相同的屬性。子合同間的過渡費(fèi)用不涉及子合同的重量，因此屬于同一合同的子合同之間的過渡費(fèi)用和切換時(shí)間均為0。在交換和插入移動(dòng)中，如果被移動(dòng)的子合同與同屬1個(gè)合同的其他子合同相鄰，則此子合同不能被單獨(dú)移動(dòng)，而需將所有相鄰的屬于同一合同的子合同都一起移動(dòng)。這樣做的原因是將屬于同一合同的子合同分開移動(dòng)，對(duì)目標(biāo)函數(shù)帶來(lái)改進(jìn)的可能性很小。另外，將屬于同一合同的子合同一起移動(dòng)，可以在一定程度上減少算法的計(jì)算時(shí)間。

根據(jù)彩涂機(jī)組的工藝規(guī)程，如果嘗試將較窄的子合同安排在較寬的子合同之前，此移動(dòng)就可以從鄰域中除去，以減少鄰域規(guī)模，加速搜索過程。

3.改進(jìn)算法

本文設(shè)計(jì)了2種智能優(yōu)化算法，禁忌搜索算法和變鄰域搜索算法。下面將分別介紹這2種算法。

（1）禁忌搜索算法

由于大部分插入操作都需要被修復(fù)，因此搜索插入鄰域的時(shí)間會(huì)比搜索交換鄰域長(zhǎng)很多。禁忌搜索算法中的鄰域搜索是鄰域Nswap。長(zhǎng)度為TL的禁忌表被用來(lái)記錄最近TL次迭代中進(jìn)行移動(dòng)的逆移動(dòng)以防止算法陷入局部最優(yōu)當(dāng)中。禁忌表中的元素為形如(i,j)的對(duì)，表示對(duì)子合同i和j進(jìn)行交換移動(dòng)。如果鄰域Nswap中的解Pij(S)被選中做為下一次迭代的基解，則對(duì)(S[i],S[j])被加入到禁忌表中，并將禁忌表中的第一個(gè)元素從禁忌表中刪除。如果(S[i],S[j])或(S[j],S[i])已經(jīng)存在于禁忌表中，1個(gè)移動(dòng)P(i,j)被認(rèn)為是禁忌的。當(dāng)f(Pij(S))

鄰域搜索是在鄰域Nswap中找到不被禁忌的移動(dòng)產(chǎn)生的最好解，或者盡管被禁忌但破禁的移動(dòng)產(chǎn)生的解。禁忌搜索使用的停止準(zhǔn)則為最大迭代次數(shù)MaxIter和最大無(wú)改進(jìn)迭代次數(shù)MaxIterWI。兩者任何一個(gè)被滿足，禁忌搜索算法停止。

（2）變鄰域搜索算法

變鄰域搜索算法（Variable Neighborhood Search, VNS）是Mladenovic和Hansen[4]在1997年提出的一種超啟發(fā)式算法。變鄰域搜索是基于鄰域搜索的，與其他基于鄰域搜索的超啟發(fā)式算法不同，變鄰域搜索不使用kick、記憶、雜交等手段，而只是通過鄰域搜索擴(kuò)大算法搜索的范圍，并且只有當(dāng)有歷史最優(yōu)解被改進(jìn)時(shí)算法才會(huì)前進(jìn)。通過這種方式，歷史最優(yōu)解中好的片段和特征可以最大程度地被保留，并且被應(yīng)用到新的希望鄰域的搜索中。變鄰域搜索的核心思想是系統(tǒng)地變換鄰域搜索使用的鄰域。目前，變鄰域搜索算法已經(jīng)被用來(lái)解決很多組合最優(yōu)化問題[5～8]。Hansen和Mladenovic[9]對(duì)變鄰域搜索的原則和應(yīng)用進(jìn)行了綜述。本文的變鄰域搜索使用了交換鄰域和插入鄰域。

變鄰域搜索算法的詳細(xì)流程如下：

——步驟1：初始化令S為初始解，Iter=0；

——步驟2;Iter=Iter+1；如果Iter=MaxIter，變鄰域搜索算法結(jié)束；否則轉(zhuǎn)步驟3；

——步驟3:隨機(jī)選擇Nswap(S)中的1個(gè)解S'；在Nswap(S')中找到鄰域最優(yōu)解S''，如果f(S'')

——步驟4:隨機(jī)選擇Ninsert(S)中的1個(gè)解S'；在Ninsert(S')中找到鄰域最優(yōu)解S''，如果f(S'')

三、實(shí)驗(yàn)結(jié)果

為了驗(yàn)證所提出模型和算法的有效性，本文使用了國(guó)內(nèi)某鋼鐵企業(yè)的6組實(shí)際生產(chǎn)數(shù)據(jù)進(jìn)行測(cè)試。數(shù)據(jù)包括所有機(jī)組前庫(kù)內(nèi)的屬于彩涂合同的板卷信息。根據(jù)調(diào)研得到機(jī)組間的最短生產(chǎn)周期和平均生產(chǎn)周期。算法使用C語(yǔ)言編寫，運(yùn)行在Intel Core i5-10210U CPU和409 6MB內(nèi)存的個(gè)人計(jì)算機(jī)上。

表1和表2給出了禁忌搜索算法、變鄰域搜索算法的模擬仿真結(jié)果及企業(yè)前1年彩涂機(jī)組的平均績(jī)效。涉及到企業(yè)技術(shù)參數(shù)的保密，表中的所有數(shù)據(jù)都被歸一化。Ncw列表示顏色切換次數(shù)，Ntar列表示每千噸拖期合同個(gè)數(shù)，Vwd列表示每千噸寬度跳躍，Vtk表示每千噸厚度跳躍，WTturn表示軋制單元平均重量。表中ENP為彩涂機(jī)組的2004年平均業(yè)績(jī)，SimTS為基于禁忌搜索算法結(jié)果的模擬仿真數(shù)據(jù)，SimVNS為基于變鄰域搜索算法結(jié)果的模擬仿真數(shù)據(jù)。對(duì)禁忌搜索算法和變鄰域搜索算法，最大迭代次數(shù)均為200代。禁忌搜索的最大無(wú)改進(jìn)迭代次數(shù)為100次，禁忌表長(zhǎng)度為41。由于企業(yè)只能給出機(jī)組的年平均業(yè)績(jī)而沒有問題的目標(biāo)函數(shù)，且只關(guān)心實(shí)際生產(chǎn)指標(biāo)而不關(guān)心目標(biāo)函數(shù)，因此表1和表2中沒有給出目標(biāo)函數(shù)的對(duì)比，而只是各項(xiàng)指標(biāo)的對(duì)比。

表1 禁忌搜索算法與模擬仿真的結(jié)果比較

表2 變鄰域搜索算法與模擬仿真的結(jié)果比較

根據(jù)表1和表2的對(duì)比結(jié)果，可以得出以下結(jié)論：

（1）對(duì)目標(biāo)函數(shù)中的所有指標(biāo)，基于智能算法的解的模擬仿真結(jié)果均好于彩涂機(jī)組平均績(jī)效。

（2）變鄰域搜索的解在各指標(biāo)上均優(yōu)于禁忌搜索算法。

（3）禁忌搜索算法在計(jì)算時(shí)間上略少于變鄰域搜索算法，平均少6.05%。

四、結(jié)語(yǔ)

本文研究了彩涂機(jī)組合同計(jì)劃問題，給出了此問題的數(shù)學(xué)模型。并對(duì)此NP難問題提出了2種啟發(fā)式算法，即禁忌搜索算法和變鄰域搜索算法?；?種算法產(chǎn)生解進(jìn)行模擬仿真，同彩涂機(jī)組之前1年的平均生產(chǎn)成績(jī)進(jìn)行對(duì)比，證明了本文提出算法的有效性。在各個(gè)指標(biāo)的對(duì)比中，變鄰域搜索算法均優(yōu)于禁忌搜索算法。變鄰域搜索算法的計(jì)算時(shí)間較禁忌搜索算法時(shí)間稍長(zhǎng)6.05%。目前，內(nèi)嵌變鄰域搜索算法的決策支持系統(tǒng)已經(jīng)開發(fā)并在國(guó)內(nèi)某大型鋼鐵企業(yè)中實(shí)際使用。