□高 聰

一、引言

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

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

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

圖1 彩涂機組合同計劃問題示意

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

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

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

二、求解方法

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

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

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

2.鄰域

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

（1）插入鄰域

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

（2）交換鄰域

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

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

（3）加速策略

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

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

3.改進算法

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

（1）禁忌搜索算法

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

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

（2）變鄰域搜索算法

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

變鄰域搜索算法的詳細流程如下：

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

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

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

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

三、實驗結(jié)果

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

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

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

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

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

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

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

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

四、結(jié)語

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