薛 聰,郭 鵬,陳 宓,王麗敏

1(西南交通大學 機械工程學院,成都 610031)

2(軌道交通運維技術與裝備四川省重點實驗室,成都 610031)

尿素造粒塔是尿素生產(chǎn)中的重要設備,也是尿素生產(chǎn)流程中最后一個生產(chǎn)環(huán)節(jié)[1].其造粒原理是將成批次放置的滿足加工溫度要求的熔融尿素使用泵通過管道打到塔頂后噴出,從而形成高溫射流.高溫射流在下墜過程中通過空氣冷卻等過程快速斷裂成滴,自動凝成固體小顆粒,從而形成顆粒狀的尿素產(chǎn)品.而不同批次的熔融尿素在等待被注入泵內(nèi)的過程中,其溫度會隨著等待時間的增加而降低.當其開始加工時因為在等待過程中的溫度變化其溫度可能不符合加工溫度要求.也就是說熱加工環(huán)境中工件的溫度會隨著其開工時刻的增大而降低,當溫度降到一定數(shù)值以后,將不再滿足加工要求,即工時惡化問題.此時需要對不滿足加工溫度要求批次的熔融尿素進行二次加熱,或者監(jiān)控其溫度,當發(fā)現(xiàn)其溫度不滿足加工溫度要求時立即使用保溫設施對其進行保溫操作.二次加熱會增加此批次熔融尿素的加工時間和消耗額外的能量,從而增大產(chǎn)品拖期和能耗,造成產(chǎn)品延期交貨和增大生產(chǎn)成本;而使用保溫設施保溫雖然不會增加其加工時間但是會耗費更多的能耗成本.當造粒塔從一臺擴展到多臺,此時問題便擴展為考慮不同工作模式與工時惡化的并行機調(diào)度問題.及時交貨和能耗控制是生產(chǎn)成本控制的重要組成部分,因此,如何有效保證產(chǎn)品及時交貨以及精準的控制能耗是管理人員需要解決的關鍵決策問題[2].在此,本文以多臺尿素造粒塔的尿素生產(chǎn)過程為背景,從并行機加工環(huán)境出發(fā),對上述調(diào)度問題進行建模并設計優(yōu)化算法進行求解.

并行機調(diào)度問題長期以來吸引了大量學者的關注和研究[3],且節(jié)能調(diào)度方面的研究已有不少.孟磊磊等以能耗最小化為目標,提出了5 個考慮關機/重啟策略的不相關并行機調(diào)度模型[4].周炳海與顧佳穎提出了多目標免疫克隆選擇算法處理多資源約束下的非等效并行機節(jié)能調(diào)度問題[5].雷德明等提出了新型帝國競爭算法去處理多目標低碳并行機調(diào)度[6].與本文研究最為相關的則是在并行機調(diào)度問題中同時考慮節(jié)能與拖期最小化.Li 等基于分派規(guī)則提出了10 個啟發(fā)式算法去優(yōu)化能耗與總拖期[7].王永琦等結合問題的性質(zhì),設計了適用于該問題的混合教學算法[8].然而上述研究均未考慮工件開工時間延誤造成額外能耗或二次加熱帶來的工時惡化.本文針對尿素廠造粒塔生產(chǎn)過程,采用階梯惡化函數(shù)對其生產(chǎn)過程進行描述[9],并盡量減少生產(chǎn)過程中發(fā)生的能耗.

關于工時惡化的并行機調(diào)度問題亦開始受到關注,Ji 和Cheng 考慮了工時線性惡化情況下的并行機調(diào)度問題,并給出了機器數(shù)確定的情況下多項式近似算法[10].Wang 等在此基礎上進行了擴展,考慮機器在開始部分不可用的情況,并設計了啟發(fā)式規(guī)則[11].Guo 等為工時階梯惡化的并行機設計了布谷鳥搜索算法,在考慮工件間調(diào)整時間的基礎上上最小化了總拖期[12],此外Guo等還比較了不同的建模方式對問題求解效率的影響[13].變鄰域搜索[14]與集劃分建模策略[15]也相繼被用于工時階梯惡化的并行機調(diào)度問題.在考慮處理成本和收益的階梯惡化并行機調(diào)度問題中,Pei 等提出了變鄰域搜索的混合算法去最大化凈收益[16].遺傳算法也被改進用于求解不相關并行機帶惡化工件的調(diào)度問題[17].關于工時惡化的并行機調(diào)度問題在潛在機器擾動、學習效益與維護活動等方面均有擴展[18-20],但文獻[18-21]尚未涉及節(jié)能調(diào)度方面的拓展.

基于以上分析發(fā)現(xiàn),目前尚未出現(xiàn)同時考慮工時階梯惡化與能耗的并行機調(diào)度優(yōu)化研究.現(xiàn)有并行機調(diào)度算法在處理實際約束時存在大規(guī)模算例計算時間過長、算法收斂速度慢、求解質(zhì)量不高等問題,且難以將工作模式選擇考慮進去.本文針對有溫度要求的工件,在等待加工的過程中有保溫或者再加熱兩種方式,均需消耗一定能量.再加熱還會導致其加工時間發(fā)生惡化.以尿素廠造粒塔為研究背景,提出以加權總拖期與總能耗之和最小化為調(diào)度目標的工時階梯惡化并行機調(diào)度問題.通過分析問題構建了混合整數(shù)線性規(guī)劃模型,由于問題的NP-hard 特性,提出了遺傳變鄰域混合搜索算法(Genetic Algorithm-Variable Neighborhood Search,GA-VNS).通過集成遺傳算法(Genetic Algorithm,GA) 與變鄰域搜索(Variable Neighborhood Search,VNS)的優(yōu)勢有效實現(xiàn)了對問題的求解.通過算例計算結果,驗證了該算法在解決較大規(guī)模算例時的效率.

1 問題描述與數(shù)學建模

給定機器集合M={1,···,m},其中M為包含所有機器的集合,m表示機器的總數(shù),給定工件集合N={1,···,n},其中N為包含所有工件的集合,n為加工工件的總數(shù).每個工件均可在任意一臺機器上加工.假設所有的工件在時刻0 都是可用的,即工件的準備時間為0.在加工過程中機器不會因其他因素而中斷.工件集N中的所有工件均需在機器上加工.每臺機器最多同時加工一個工件.每個工件j(j∈N)都有相應的基本加工時間aj,交貨期dj,惡化工期hj.如果工件j的開工時刻sj早于惡化工期hj,則其實際加工時間pj等于基本加工時間aj.在等待加工的過程中,工件的溫度會逐漸下降,其開工時刻sj也在逐漸增大.而當工件j的開工時刻sj晚于其惡化工期hj時,工件的溫度將不再符合加工要求,為了使工件溫度滿足加工要求,有兩種模式可以選擇:(1)對工件進行二次加熱,將發(fā)生額外的懲罰時間bj,使得pj=aj+bj,并且還會有消耗額外的能量(bj×qj),其中qj為工件j加工時的單位時間能耗.此時,工件j的實際加工時間pj是其開工時刻的階梯函數(shù),額外消耗的能量為多出的加工時間內(nèi)消耗的能量;(2)將工件放在保溫設施里對其進行保溫處理,等到其開始被加工時再取出(將工件放進和取出保溫設施的時間忽略不計).保溫模式可使工件j不增加額外的懲罰時間,但使用保溫設施對工件進行保溫操作將會發(fā)生額外的能量消耗.在保溫模式下,工件的加工時間仍等于其基本加工時間aj,額外的能量損耗ej則可表示為:

式中,e0表示使用保溫設備對工件進行保溫操作時單位時間發(fā)生的能耗.

調(diào)度決策就是指派工件到各臺機器,同時選擇恰當?shù)墓ぷ髂Ｐ鸵员ＷC工件能夠順利完工,以求最小化總拖期時間與加工能耗.表1解釋了本文數(shù)學模型中的變量和符號.所提出的混合整數(shù)規(guī)劃模型如下:

目標函數(shù)為:

約束條件為:

上述模型中,目標函數(shù)(2)為最小化所有工件的加權總拖期與總能耗之和,其中 α 和 β表示所有工件在加工過程中的總拖期和總能耗的加權系數(shù),在本文數(shù)學模型計算過程中,α 和 β均取1.因此該模型的優(yōu)化目標為最小化所有工件的總拖期和總能耗之和.約束條件(3)確保每個工件只能指派給一臺機器.約束條件(4)強調(diào)如果工件i和工件j被分配到同一臺機器上加工,則它們不能同時加工.約束條件(5) 定義了工件的開工時刻并確保工件i的完工時刻ci、工件j的開工時刻sj和xij的取值保持一致,其中M為一個足夠大的數(shù),取約束條件(6)定義了工件j的完工時刻cj.約束條件(7)給出了工件j的拖期Tj,Tj=max(cj-dj,0).約束條件(8)確定了工件j的實際加工時間pj的取值范圍.約束條件(9)強調(diào)若工件j的開工時刻sj早 于或等于其惡化工期hj(pj≤sj),則二進制變量zj=1,否則等于0.約束條件(10)確保當工件j的開工時刻sj早 于其惡化期hj時,不會再使用保溫設施進行保溫操作.即當zj=1時,uj=0.約束條件(11)確保當工件j使用保溫設施保溫時,其實際處理時間pj等 于aj.約束條件(12)定義了當工件j使用保溫設施時額外消耗的能量ej.約束條件(13)確定了工件j從時刻0 開始到加工完成消耗的總能量Ej.約束條件(14)和(15)為決策變量的取值約束.

表1 數(shù)學模型中的符號

2 遺傳變鄰域混合搜索算法

由于考慮工時階梯的單機總拖期問題已被證明為NP-hard 的[22],本文所考慮的問題為并行機加工環(huán)境且考慮能耗,因此其也是NP-hard 的.隨著工件數(shù)的增加,很難通過精確的算法獲得問題的最優(yōu)解.在大規(guī)模問題求解尋找近優(yōu)解時,群集智能優(yōu)化算法求解效率明顯高于精確求解方法.遺傳算法能夠利用群集效應進行尋優(yōu),具有先天的并行搜索能力,故本文利用遺傳算法的這一特性進行大規(guī)模問題的求解.前期計算結果表明,若僅僅使用基本遺傳算法求解本文所提并行機調(diào)度問題,易陷入局部最優(yōu)解且求解效率相對較差.在此采用混合變鄰域搜索策略來提高算法性能.使用遺傳算法經(jīng)過一定迭代次數(shù)操作后的種群輸出的最優(yōu)染色體做為初始解,進一步實施變鄰域搜索,以達到提高算法質(zhì)量,提升運算效率的目的.因此,本文針對所提并行機調(diào)度問題的特性,集成考慮遺傳算法和變鄰域搜索的優(yōu)勢,提出了基于遺傳算法框架的遺傳變鄰域混合搜索算法.

2.1 編碼和解碼方式

編碼是整個算法的第一步,對算法效果有巨大影響.本文的編碼方式必須滿足兩方面的需求,一是要確定機器的指派問題,另一個則是要確定每臺機器上工件的加工順序.本算法采用實數(shù)編碼方式.每個解序列為從1 到n+m-1隨機排序的序列.其中大小從1 到n的實數(shù)分別表示n個工件的編號.大小從n+1到n+m-1的數(shù)字為分隔符來區(qū)分不同機器,也就是說明其左邊和右邊的工件不在同一個機器上加工.例如6 個工件,3 臺機器的算例.染色體序列(1,5,7,6,3,8,4,2)表示機器一加工工件1、5 且加工先后順序為(1,5),機器二加工工件6、3,且加工先后順序為(6,3),依次類推,此序列解碼結果如圖1所示.關于當工件開始加工時其溫度不滿足加工溫度要求時的工作模式選擇問題.本文采取隨機的策略選擇其開工時刻超過惡化工期時的工作模式,即當工件的開工時刻大于其惡化工期時,其選擇施加懲罰時間和使用保溫設施保溫的概率均為50%.

2.2 遺傳算法

2.2.1 遺傳算法種群初始化

初始化種群是本文整個算法的開端,其組成結構對整個算法影響很大.本文采用隨機生成的方式生成初始種群,以保證染色體可取到所有的可能調(diào)度序列.

圖1 染色解碼方式甘特圖表示

2.2.2 適應度函數(shù)

模型目標是最小化所有工件的加權總拖期與總能耗之和,因此本文的適應度函數(shù)為目標函數(shù)的倒數(shù):

其中,πi表示一個可行調(diào)度序列,αT(πi)+βE(πi)表示其目標值.

2.2.3 選擇策略以及精英保留

選擇的作用是可以從當前群體中選出優(yōu)良個體,使得好的個體有更大的機會保留下來并將其優(yōu)良的信息傳遞給下一代,因而可以逐步地向最優(yōu)解逼近.本文的選擇操作選用輪盤賭選擇方法,染色體被選中的概率L為:

在式(17)中,pnum為遺傳算法部分的種群數(shù)量.為防止產(chǎn)生新個體的同時破壞已有的優(yōu)良個體,本文采用了精英保留策略.精英保留就是在一次迭代過程中對種群進行選擇、交叉、變異等操作之后選出當前種群中適應值最大的個體,直接遺傳到下一代,下一次迭代時不對其進行遺傳操作.目的是保留最好的染色體,避免遺傳算子破壞其優(yōu)良性.

2.2.4 交叉操作

交叉操作是種群中產(chǎn)生新個體的主要步驟,好的交叉方法對于遺傳算法的效果也有顯著影響.由于順序交叉能夠在保留原有排列的基礎上融合不同排列的有序結構單元,本文選用兩點順序交叉(類OX),順序交叉的具體流程(圖2)如下:

步驟1.父代1 和父代2 配對,從父代1 中隨機選擇一段連續(xù)的基因,并將這段基因按順序放在子代1的起始部分;

步驟2.去除父代2 中包含父代1 被選基因段的基因;

步驟3.將父代2 中去除父代1 備選基因段后剩余的基因按順序依次填入子代1 的剩余位置.此時,獲得了完整的子代1 的基因.

同理,按照以上步驟,可從父代2 中隨機選取一部分基因段和父代1 中的出去被選基因段部分,按照上述步驟插入得到子代2.

2.2.5 變異操作

當遺傳算法通過交叉算子已接近最優(yōu)鄰域解時,利用變異操作可以提高其隨機搜索能力,且可以有效維持群體多樣性.本文選用隨機位置交換完成變異操作.隨機選中兩個元素進行位置調(diào)換即完成變異操作.如圖3示例:父代P1(5,8,7,1,3,4,6,2).選中第3 個元素7 和第6 個元素4 進行位置調(diào)換,即生成子代Q1(5,8,4,1,3,7,6,2).

圖3 隨機選擇變異示意圖

2.3 變鄰域搜索

變鄰域搜索算法[14]通過搜索多個鄰域結構能夠較好的避免陷入局部最優(yōu)解,是一種改進型的局部搜索算法.本文對使用遺傳算法經(jīng)過一定迭代次數(shù)操作后的最優(yōu)染色體進行變鄰域搜索操作,以進一步改善解的質(zhì)量.

變鄰域搜索算法的工作原理是通過各種鄰域結構對當前解實施變換,以產(chǎn)生可行解集合.目前關于調(diào)度問題的鄰域結構大多數(shù)是基于插入和交換操作.除了這些基本的鄰域結構,本文還引入了逆序操作.因此,本節(jié)使用插入和交換操作構造4 種鄰域結構,并使用逆序定義了一種鄰域結構.以下將分別對這5 種鄰域結構進行介紹.

鄰域搜索結構(Neighborhood Search) NS1 和NS2原理相似.兩者均是其中利用交換對當前解實施微小的變動.區(qū)別在于NS1 是從整個解序列的第一個元素開始到最后一個元素結束,依次隨機選擇一個與其不相等的元素進行交換,也就是把解序列內(nèi)的所有元素都與其他不重復的隨機位置進行交換,而NS2 則是在解序列中隨機選擇一個元素,將其插入到另一個不重復的隨機選定的元素上.在NS1 和NS2 的操作過程中只要解的質(zhì)量比原來的解好,立即接受其為當前解,并重新開始搜索;否則繼續(xù)搜索直至所有可能的組合均已完成.

鄰域搜索結構NS3 和NS4 有著類似的操作.兩者和NS1,NS2 不同的是NS3 和NS4 所進行的交換操作是兩兩交換,即同時交換的元素有4 個,成對交換.NS3 從解序列的前兩個元素開始到最后兩個元素結束,依次選擇兩個元素與另外隨機選擇的兩個不重復的元素分別進行交換.與NS1 和NS2 的區(qū)別一樣,NS4則是隨機的取兩個元素與另外一對兩個隨機的不重復的元素分別進行交換.其實施過程與NS3 相同.一旦發(fā)現(xiàn)給出的鄰域解有所改善,則將該鄰域解視為當前解,并再次開始搜索更好的解;否則繼續(xù)搜索直至搜索完成所有的鄰域結構.

為了進一步提高算法的性能,基于逆序操作的鄰域結構NS5 在上述4 個鄰域完成后實施.NS5 的具體操作為:從當前解序列中隨機選擇兩個元素,將兩者之間的工件全部逆序,以形成新的解.該步驟重復n+m-1次以尋找較好的解.與前4 個鄰域結構一樣,該鄰域結構只接受效果更好的解.

2.4 GA-VNS 算法框架

通過使用2.3 節(jié)的5 種鄰域搜索結構,再結合2.2 節(jié)的遺傳算法為VNS 算法提供初始解,即可對本文提出的問題實施GA-VNS 算法.GA-VNS 的終止條件為:(1)達到最大迭代次數(shù)Tp;(2)當前解連續(xù)nip次迭代沒有得到改善.若滿足上述兩個條件中的任意一個,則立即終止算法,并返回已求得的最好解.關于Tp和nip將在第3 節(jié)參數(shù)調(diào)試部分確定其具體取值.GA-VNS算法的程序架構如圖4所示.

圖4 GA-VNS 程序框圖

3 算例驗證

本章采用兩組算例驗證算法的性能,具體的參數(shù)取值見3.1 節(jié).所提出的遺傳變鄰域混合搜索算法將在3.2 節(jié)對算法關鍵參數(shù)進行參數(shù)調(diào)試.本節(jié)對比了Gurobi、GA、VNS[14]和GA-VNS 對小規(guī)模和大規(guī)模算例的計算效果,以驗證所提算法性能.本節(jié)所涉及的所有算法均在Visual Studio 2013 平臺使用C#語言編程實現(xiàn),在CPU (Intel 3.6 G)/RAM (8 GB)的個人計算機上運行.為了方便分析算法的性能,本節(jié)將求解得到的目標函數(shù)轉(zhuǎn)換成百分偏差,用R作為參數(shù)分析的響應變量,其值由式(18)決定.

式(18)中,Alg是 計算某算法R值時的當前算法,obj(Alg)則是當前算法計算10 次的平均目標值;Best是指在計算某一具體算例時本文所比較的包括Gurobi 在內(nèi)的4 種算法中計算10 次平均目標值最小的算法,obj(Best)則是最好算法計算10 次的平均目標值.分析式(18)可知,R值越小,說明當前算法的效果越好.

3.1 算例設計

本節(jié)采用兩組算例來驗證算法性能.其中小規(guī)模算例的工件數(shù)n∈{4,6,8,10,12} 和m∈{2,3,4},大規(guī)模算例的 工件數(shù)n∈{20,40,60,80,100} 和m∈{4,6,8},共計30 個算例.同一組算例運算10 次,取平均值為最終運算結果.對于各個工件,設定工件j基本加工時間aj,懲罰加工時間bj,惡化工期hj,工件j開工時刻晚于惡化工期選擇使用保溫工作模式時單位時間能耗e0,加工時單位時間能耗qj,交貨期dj.此處需要說明的是,本文中所有工件在保溫時單位時間能耗e0都是相等的,在此設為5.由于所研究的問題沒有廣泛可用的基準實例集,因此本文測試實例的數(shù)據(jù)參考了文獻[14]中產(chǎn)生數(shù)據(jù)的方法.工件j的基本加工時間aj為[1,100]間均勻分布的隨機數(shù);懲罰加工時間bj為[1,50]之間均勻分布的隨機數(shù);惡化工期hj為(0,D]之間均勻分布的隨機數(shù),其中其中w=0.5;工件在加工時單位時間能耗qj為[1,20]間均勻分布的隨機數(shù);工件交貨期dj等于aj+(0,20],即工件j的交貨期等于其基本加工時間aj與(0,20]之間均勻分布的隨機數(shù)之和.本文在計算時目標函數(shù)的加權系數(shù) α 和 β均取1,也就是本節(jié)所有算法計算的目標值都是總拖期與總能耗之和.

需要注意的是,Gurobi、GA 和VNS 實驗數(shù)據(jù)也是來源于此.GA 的算法結構采用本文遺傳算法部分的結構,VNS 的算法結構采用本文變鄰域搜索部分的內(nèi)容.設定Gurobi 運算時間為3600 s,如果在給定的時間內(nèi)沒有找到最優(yōu)解,則返回當前已發(fā)現(xiàn)的最好整數(shù)解.關于GA 和VNS 算法的終止條件,它們的最大循環(huán)次數(shù)Tp和當前解連續(xù)沒有得到改善的迭代次數(shù)nip與GA-VNS 的相同.

3.2 參數(shù)調(diào)試

算法求解的質(zhì)量和算法參數(shù)的選擇息息相關,本文所提GA-VNS 算法所涉及的主要參數(shù)為:用作GAVNS 算法初始解的遺傳算法的交叉概率Pc、變異概率Pm以 及GA-VNS 最大迭代次數(shù)Tp.基于初步測試,遺傳算法階段種群數(shù)量Pnum和最好個體連續(xù)未改善迭代次數(shù)nip分別設為50 和80.需重點調(diào)參的3 個關鍵參數(shù)的取值范圍如下:

Pc:0.6、0.7、0.8、0.9、0.99.

Pm:0.01、0.05、0.10、0.15、0.20.

Tp:100、200、300、400、500.

在GA-VNS 算法中,使用工件數(shù)為40 機器數(shù)為6 的大規(guī)模算例對每個參數(shù)都進行10 次求解運算,并對其求解結果實施單因素方差分析(ANOVA).為了方便分析不同取值水平下GA-VNS 算法的效果,圖5至圖7分別給出了3 個參數(shù)不同取值的均值圖和95% 置信水平下的Tukey 真實著性差異(Honestly Significant Difference,HSD)區(qū)間.

圖5 不同 Pc取值均值圖和TukeyHSD 區(qū)間

圖6 不同 Pm取值均值圖和TukeyHSD 區(qū)間

圖7 不同Tp取 值的均值圖和TukeyHSD 區(qū)間

從圖5可以看出,交叉概率Pc太小,會降低求解質(zhì)量,而當Pc值太大時,求解質(zhì)量也不是太理想.明顯得出當Pc取值為0.9 時,R值最小,算法效果最好;從圖6可以看出變異概率Pm過小對算法效果的影響并不大,當Pm的值為0.05 時,R有最小值,且隨著Pm越來越大,R值也越來越大.綜合來看,Pm設為0.05 最合適;圖7顯示當參數(shù)Tp取值水平為400、500 時,并未產(chǎn)生明顯差異,且二者擁有相近的均值,為保證更高的求解效率,400 是更好的選擇.故基于上述分析,交叉概率Pc=0.9,變異概率Pm=0.05,最大迭代次數(shù)Tp=400.

3.3 算例分析

在本節(jié)的計算中,同一組算例運算10 次,取平均值的整數(shù)部分,保留R值的小數(shù)后兩位與平均運行時間的小數(shù)后3 位為最終運算結果.對比了Gurobi、GA、GAVNS 和VNS 對小規(guī)模算例和大規(guī)模算例的運算結果.

表2列出了各個算法求解小規(guī)模算例的計算結果.從表2中可以看出,GA-VNS 和Gurobi 都能給出所有小規(guī)模算例的最好結果,且其解效果十分穩(wěn)定.從計算時間上來看,GA-VNS 的平均計算時間為0.232 s,且只有工件數(shù)為12,機器數(shù)為4 的算例計算時間超過1 s,其余均低于1 s.而Gurobi 的平均計算時間為1.166 s,這說明在求解質(zhì)量相同的情況下,GA-VNS 的求解效率要好于Gurobi.GA 和VNS 的計算時間比起GAVNS 來說相差無幾,但是兩者的求解質(zhì)量卻不及GAVNS.由表2可以看到,在全部15 個小規(guī)模算例中,VNS 只給出了8 個算例的最優(yōu)解,平均R值為0.804.與VNS 相比,GA 給出了13 個算例的最優(yōu)解,平均R值為0.107,優(yōu)于VNS,但還是不如GA-VNS 給出的解的質(zhì)量好.從基于小規(guī)模算例的計算結果可以看出,GA-VNS 表現(xiàn)出了最好的求解性能.

使用Gurobi、GA、VNS 和GA-VNS 求解大規(guī)模算例,計算結果見表3.由于問題的難求解性,Gurobi 僅能給出機器數(shù)為6 工件數(shù)為20、機器數(shù)為8 工件數(shù)為20 以及機器數(shù)為8 工件數(shù)為40 的近似最優(yōu)解.并且在求解所有大規(guī)模算例時,均耗光了計算時間都未找到最優(yōu)解,且還有12 個算例未找到可行解.總體來講,Gurobi 求解大規(guī)模算例的效果并不理想.GAVNS 給出的平均R值為0.007,明顯優(yōu)于Gurobi 和另外兩個啟發(fā)式算法.除了機器數(shù)為6,工件數(shù)為100 這一算例外,其余算例的最優(yōu)值Best均由GA-VNS 給出.在3 種啟發(fā)式算法中,GA-VNS 由于引入GA 輸入初始解和變鄰域搜索結構,使得其平均計算時間最長,平均計算時間為3.142 s.但考慮到GA-VNS 優(yōu)良的求解性能,付出的計算時間還是可以接受的.相比之下,GA 的運算時間是最短的,其平均計算時間為0.689 s.但從表3可明顯看出,雖然GA 的求解時間是最短的,但其求解效果在3 個啟發(fā)式算法中卻是最差的,平均R值達到了38.233,說明其求解精度還有很大的提高空間.VNS 的平均計算時間和GA-VNS 相差不大,為2.994 s,但在15 個大規(guī)模算例中,VNS 僅給出了一個最好的Best值,平均R值為5.24,且隨著工件數(shù)的增加,其R值也有逐漸增大的趨勢.總的來說,GA-VNS在較短的時間內(nèi)給出了不錯的近似最優(yōu)解,能夠有效解決同時考慮工時階梯惡化與能耗的并行機調(diào)度問題.

表2 小規(guī)模算例計算結果

表3 大規(guī)模算例計算結果

4 結論與展望

本文針對尿素造粒塔生產(chǎn)過程,提出了一類考慮工時惡化和能耗的并行機調(diào)度問題,建立了優(yōu)化目標為加權總拖期與總能耗的混合整數(shù)線性規(guī)劃模型.由于問題的難求解性以及工作模式選擇的特殊性,本文提出了基于遺傳算法框架的改進的遺傳變鄰域混合搜索算法.采用了單因素方差分析確定關鍵算法參數(shù),并基于隨機產(chǎn)生的兩組算例,分析了算法的性能.與數(shù)學求解器Gurobi、基本的遺傳算法與基本的變鄰域搜索算法的計算結果做了對比,結果驗證了本文所提算法的可行性與高效性.后續(xù)研究可引入動態(tài)規(guī)劃對兩類模式進行選擇,考慮結合更切合尿素造粒塔的實際生產(chǎn)情況的真實數(shù)據(jù)優(yōu)化問題,同時設計多目標的求解算法,把兩個優(yōu)化目標單獨研究.