林 劍,李揚(yáng)遠(yuǎn),陳蒙蒙,干夢清,王凌武

(浙江財(cái)經(jīng)大學(xué) 信息管理與人工智能學(xué)院,浙江 杭州 310018)

0 引言

電線電纜已被廣泛用于建筑、通信、能源、交通等工業(yè)領(lǐng)域,隨著線纜生產(chǎn)企業(yè)數(shù)量和產(chǎn)能的不斷提升,目前我國已成為了世界上第一大線纜生產(chǎn)國,行業(yè)總產(chǎn)值已超過萬億元規(guī)模[1]。作為傳統(tǒng)制造行業(yè),線纜生產(chǎn)線具有產(chǎn)品種類多、管理復(fù)雜等特點(diǎn),在生產(chǎn)車間管理上仍以人工經(jīng)驗(yàn)為主,這導(dǎo)致了我國線纜企業(yè)的數(shù)字化和智能化管理水平普遍不高,嚴(yán)重影響了企業(yè)效益和競爭力。因此,研究分析線纜生產(chǎn)過程中的復(fù)雜工程問題,并提出相應(yīng)解決方案,對于推動(dòng)傳統(tǒng)企業(yè)的數(shù)字化轉(zhuǎn)型升級,實(shí)現(xiàn)經(jīng)濟(jì)社會(huì)可持續(xù)發(fā)展具有重要意義。

線纜生產(chǎn)調(diào)度優(yōu)化是線纜生產(chǎn)管理的關(guān)鍵技術(shù)。對企業(yè)而言,合理的調(diào)度方案不僅可以縮短產(chǎn)品制造周期,還可以有效提高人員工作效率、設(shè)備利用率、減少能源和物質(zhì)損耗,從而達(dá)到降低成本和提高經(jīng)濟(jì)效益的目的。

由于線纜生產(chǎn)過程的復(fù)雜特性,目前針對線纜生產(chǎn)調(diào)度優(yōu)化的文獻(xiàn)還較少,相關(guān)研究尚處在起始階段。ALTARAZI等[2]首次針對線纜生產(chǎn)調(diào)度問題開展了研究,并提出一種基于混合整數(shù)規(guī)劃的求解方法。但是正如該文獻(xiàn)所述,隨著訂單數(shù)量的增加,所用方法將難以有效求解目標(biāo)問題。SADEGH等[3]建立了線纜生產(chǎn)的單機(jī)調(diào)度優(yōu)化模型,并提出了基于混合貪婪算法的求解方法,但是該研究僅考慮了線纜生產(chǎn)中的拉絲和擠塑工藝環(huán)節(jié)。隨著群智能算法研究的不斷深入,其在實(shí)際優(yōu)化問題中的應(yīng)用已受到越來越廣泛的關(guān)注,紀(jì)明[4]提出一種基于遺傳算法(Genetic Algorithm,GA)的線纜車間調(diào)度方法,并以交貨延期最小化為優(yōu)化目標(biāo)進(jìn)行研究;趙宇[5]進(jìn)一步將NSGA-II算法用于解決多目標(biāo)線纜生產(chǎn)調(diào)度模型。值得注意的是,上述研究都沒有同時(shí)考慮線纜生產(chǎn)過程中的模具安裝時(shí)間和模具數(shù)量約束。

Jaya算法是RAO[6]于2016年提出的一種群智能優(yōu)化算法,該算法主要通過解個(gè)體不斷靠近最優(yōu)解并遠(yuǎn)離最差解,以實(shí)現(xiàn)解的質(zhì)量提升,得到更優(yōu)解。與其他群智能算法相比,Jaya算法具有無參數(shù)、結(jié)構(gòu)簡單、易實(shí)現(xiàn)、魯棒性強(qiáng)等優(yōu)點(diǎn)。目前Jaya算法已被應(yīng)用于解決各領(lǐng)域的復(fù)雜問題包括車間調(diào)度[7]、圖像處理[8]、參數(shù)識別[9-11]、機(jī)器學(xué)習(xí)[12]、結(jié)構(gòu)設(shè)計(jì)[13]、能源分配[14]等。

本文針對線纜生產(chǎn)調(diào)度問題,在Jaya算法框架下,通過融合高效的搜索策略,提出一種基于離散Jaya(Discrete Jaya,DJaya)算法的線纜生產(chǎn)調(diào)度優(yōu)化方法,以有效提升傳統(tǒng)電纜行業(yè)生產(chǎn)與管理效率。仿真實(shí)驗(yàn)結(jié)果表明,DJaya算法在求解線纜生產(chǎn)調(diào)度問題中能得到較好的尋優(yōu)結(jié)果,表現(xiàn)出較高的魯棒性和穩(wěn)定性。

1 線纜生產(chǎn)調(diào)度問題

1.1 問題描述

線纜生產(chǎn)調(diào)度問題可描述為:存在一個(gè)線纜生產(chǎn)線,有多臺機(jī)器同時(shí)生產(chǎn)若干個(gè)訂單,每個(gè)生產(chǎn)訂單只包含一種線纜產(chǎn)品規(guī)格,不同規(guī)格線纜對應(yīng)不同的生產(chǎn)工藝,且主要通過拉絲退火、束絲/絞線、擠塑、成纜、擠護(hù)套、鎧裝等工藝環(huán)節(jié)實(shí)現(xiàn)不同規(guī)格線纜的生產(chǎn),具體如圖1所示。

線纜生產(chǎn)的每一工藝環(huán)節(jié)由具備相應(yīng)功能的加工機(jī)器和配套模具完成,一臺機(jī)器在加工不同規(guī)格線纜時(shí)通常需要切換模具,且該過程需耗費(fèi)一定的模具安裝時(shí)間。線纜生產(chǎn)過程中不同工藝環(huán)節(jié)結(jié)束后都會(huì)生成線纜成品。線纜生產(chǎn)調(diào)度優(yōu)化旨在完成線纜生產(chǎn)任務(wù)的基礎(chǔ)上合理安排不同訂單相應(yīng)工序的加工設(shè)備和時(shí)序,以達(dá)到完工時(shí)間、提前/拖期懲罰成本等目標(biāo)最優(yōu)化。因此,線纜生產(chǎn)調(diào)度問題可視為一類帶安裝時(shí)間和資源約束的柔性作業(yè)車間調(diào)度問題,本質(zhì)上屬于NP難問題。

1.2 數(shù)學(xué)模型

minF=min{maxCi},?i=1,2,…,N。

(1)

s.t.

Bi(j+1)>Cij,?i=1,2,…,
N;j=1,2,…,n;

(2)

B′i′k≥C′ik+xii′k×Sii′k,?i,i′=1,2,…,N;

(3)

(4)

(5)

ygit={0,1},?i=1,2,…,N,t∈[1,Ci]。

(6)

其中:Ci為訂單Ji的完工時(shí)間;約束(2)規(guī)定了同一個(gè)訂單中后一個(gè)工序的開始時(shí)間必須小于前一個(gè)工序結(jié)束時(shí)間;約束(3)表示同一機(jī)器上兩個(gè)連續(xù)生產(chǎn)但不同規(guī)格的工序之間需考慮模具安裝時(shí)間;約束(4)給定了線纜生產(chǎn)中某一工序上的模具數(shù)量限制;約束(5)和(6)分別限定了決策變量xii′k和ygik的取值范圍。

2 離散Jaya算法

2.1 基本Jaya算法

Jaya算法是一種簡單有效的求解復(fù)雜優(yōu)化問題的方法,僅需少量的公共控制參數(shù),如種群大小和迭代次數(shù)。

假設(shè)f(X)是目標(biāo)函數(shù),在迭代尋優(yōu)過程中,Xij表示種群中第i個(gè)解中第j維變量的值,Xbj和Xwj分別表示種群中最優(yōu)和最差解中第j維變量的值,r1j和r2j是第j維空間上生成的兩個(gè)隨機(jī)數(shù),r1j,r2j∈[0,1]。Jaya算法通過控制解個(gè)體不斷向最優(yōu)解靠攏并遠(yuǎn)離最差解,以實(shí)現(xiàn)針對目標(biāo)問題的尋優(yōu)。新解的生成和替換方式為:

(7)

Jaya算法的基本步驟如下:

步驟1初始化種群和算法參數(shù)。

步驟2每次迭代過程中確定種群中的最優(yōu)解和最差解。

步驟3根據(jù)式(7)生成新的解個(gè)體。若新解更優(yōu),則替換原解,否則保留原解。

步驟4重復(fù)步驟2和步驟3,直到滿足終止條件,并輸出到目前為止找到的最優(yōu)解。

2.2 編解碼策略

針對線纜生產(chǎn)調(diào)度問題,本文采用基于工序的單列編碼方式對訂單進(jìn)行編碼,每個(gè)解個(gè)體都采用一個(gè)工序序列表示,序列中的每一個(gè)數(shù)字都由一個(gè)訂單編號表示,數(shù)字出現(xiàn)的次數(shù)代表該訂單所處的工序數(shù)。如圖2所示為一個(gè)解個(gè)體的編碼示意圖,其中第一個(gè)數(shù)字“1”指訂單1的第一個(gè)工序,第二個(gè)數(shù)字“2”指訂單2的第一個(gè)工序,第三個(gè)數(shù)字“1”指訂單1的第二個(gè)工序,依此類推。

對于每一個(gè)可行解,高效的解碼策略可有效提升算法尋優(yōu)性能。針對每個(gè)工序序列,本文提出一種基于左移的解碼策略(Left-shift based Decoding Scheme,LDS)以獲取解適應(yīng)度值并生成可行調(diào)度方案。解碼策略以最小化最大完工時(shí)間準(zhǔn)則為序列上的每個(gè)工序安排機(jī)器進(jìn)行生產(chǎn)。通過在解碼過程中融入左移方法,盡可能緊湊地將工序安排在機(jī)器上,使機(jī)器利用率和調(diào)度效率進(jìn)一步提升。工序左移策略可描述如下:

(8)

(9)

綜上所述,所提出的LDS描述如下:

步驟1按順序遍歷可行解上的每一個(gè)工序,對于當(dāng)前工序Oij,找到其可行機(jī)器k。

步驟2判斷緊前工序?qū)?yīng)規(guī)格與待插入工序Oij規(guī)格是否一致,若不一致則考慮模具安裝時(shí)間。

步驟3判斷資源數(shù)量,并使用左移策略尋找最早開始時(shí)間。

步驟4記錄工序開始時(shí)間、結(jié)束時(shí)間、指派機(jī)器等信息。

步驟5更新資源數(shù)、機(jī)器加工序列,回到步驟1,直到所有工序遍歷完畢。

2.3 搜索策略

(1)優(yōu)先工序交叉算子

交叉算子是產(chǎn)生新個(gè)體的主要操作方式,一定程度上決定了算法性能的優(yōu)劣。優(yōu)先工序交叉[15]算子(Precedence Operation Crossover, POX)是使用最廣泛且效果最好的交叉操作之一。POX交叉算子可有效保證訂單編號在父代和子代中出現(xiàn)的次數(shù)保持一致,且工序間的順序約束關(guān)系不被破壞。POX交叉操作的示例如圖3所示,具體操作過程如下:

步驟1隨機(jī)選擇兩個(gè)父代個(gè)體P1和P2,由P1和P2產(chǎn)生的兩個(gè)子代個(gè)體分別為C1與C2。

步驟2將父代個(gè)體P1隨機(jī)劃分為兩個(gè)非空訂單集合P11和P12,并滿足P11∪P12=P1,P11∩P12=?。

步驟3將P1中屬于集合P11的訂單所對應(yīng)的工序基因復(fù)制到C1上相同的基因位置,然后從P2中刪除C1上已確定的基因,并將P2中剩余的基因從左到右依次填充到C1的空基因位上。

步驟4按照步驟3的類似操作生成C2,從而得到子代個(gè)體C1與C2。

(2)反向?qū)W習(xí)策略

X′=A+B-X。

(10)

OBL策略的操作流程如下:

步驟1假設(shè)種群中解X的編碼信息為{J1,J2,J3,…Jn},則根據(jù)基因位置索引范圍計(jì)算出的反向解X′為{Jn,Jn-1,Jn-2,…J1}。

步驟2計(jì)算X與X′的適應(yīng)度。

步驟3若X′的適應(yīng)度優(yōu)于X,則使用X′替換X,否則保留X。

2.4 DJaya算法框架

在Jaya算法基本框架下,基于單列編碼方式和左移解碼策略,采用POX和OBL方法,提出一種DJaya算法模型,其算法流程如圖4所示。

(1)初始化策略

1)初始化算法參數(shù):初始化種群大小Pop,最大迭代次數(shù)Itr;

2)解個(gè)體編碼與生成策略:在生成自然序列的基礎(chǔ)上通過隨機(jī)混洗方式不斷生成Pop個(gè)初始解個(gè)體,以提高初始解的多樣性;

3)計(jì)算解個(gè)體的適應(yīng)度值:基于本文所提出的LDS解碼策略,計(jì)算每個(gè)個(gè)體的最大完工時(shí)間,并作為個(gè)體適應(yīng)度。

(2)離散Jaya策略

1)隨機(jī)系數(shù)生成:生成二進(jìn)制數(shù)r1和r2,即r1,r2∈{0,1},且滿足r1+r2=1。

2)新解生成:基于Jaya算法中如式(7)所示的解生成方式,提出DJaya算法中生成解個(gè)體的離散化公式如下所示:

XtN=Xt?(r1·XtB+r2·XtW)。

(11)

式中:XtB表示在第t次迭代過程中最優(yōu)解;XtW表示在第t次迭代過程中最差解;?代表交叉操作。當(dāng)r1=1時(shí),將當(dāng)前解與當(dāng)前最優(yōu)解XtB使用POX交叉算子進(jìn)行交叉操作;反之,當(dāng)r2=1時(shí),則將當(dāng)前解進(jìn)行OBL策略生成反向解,并保留適應(yīng)度更高的解。

(3)更新及終止策略

判斷POX和OBL操作執(zhí)行后生成的新解,若新解優(yōu)于原有解個(gè)體的最大完工時(shí)間,則用新解替換原解,否則保留原解。當(dāng)?shù)螖?shù)滿足結(jié)束條件時(shí)終止操作,并輸出最優(yōu)解。

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證所提DJaya算法的有效性,本文基于線纜企業(yè)生產(chǎn)過程中的實(shí)際數(shù)據(jù),構(gòu)建包含30個(gè)算例的實(shí)例集。此外,考慮到目前有關(guān)線纜生產(chǎn)調(diào)度問題的研究尚處于起步階段,相關(guān)文獻(xiàn)較少。因此,除了基本Jaya算法外,實(shí)驗(yàn)還采用文獻(xiàn)[4]中提出的GA算法和應(yīng)用廣泛的差分進(jìn)化算法(Differential Evolution,DE)[17]作為對比算法來驗(yàn)證所提DJaya算法的有效性。所有算法的最大迭代次數(shù)Itr=100,種群大小Pop=30,其中GA和DE算法一次迭代可能經(jīng)過2次評估,DJaya和基本Jaya算法則需一次評估。實(shí)驗(yàn)環(huán)境為Intel Core-i5-9300H處理器,16 GB內(nèi)存,2.4 Ghz主頻,編程采用C++語言實(shí)現(xiàn)。

實(shí)驗(yàn)1本實(shí)驗(yàn)基于訂單的小規(guī)模實(shí)例進(jìn)行測試,每個(gè)實(shí)例標(biāo)記為a_b,其中a表示訂單數(shù),b表示該測試集序號。通過比較DJaya算法與GA、DE、Jaya算法在小規(guī)模實(shí)例集上的尋優(yōu)結(jié)果,以驗(yàn)證DJaya算法的性能。所有算法運(yùn)行次數(shù)設(shè)置為20次,比較結(jié)果如表1所示,其中Max和Min分別表示最大完工時(shí)間的最大及最小值,Avg和Std分別表示得到的平均最大完工時(shí)間及標(biāo)準(zhǔn)差值,最后一行為10個(gè)算例上的數(shù)據(jù)平均值。從表1可以看出,DJaya算法在所有算例上均能得到最優(yōu)結(jié)果,最優(yōu)解的平均最大完工時(shí)間要優(yōu)于其他3種算法,并且標(biāo)準(zhǔn)差值也要小于其他算法。這說明DJaya算法在尋優(yōu)精度和能力上均強(qiáng)于其他算法。

表1 不同算法在實(shí)例集10_1～10_10上的尋優(yōu)結(jié)果比較

實(shí)驗(yàn)2為了進(jìn)一步證明DJaya算法的求解效果,本實(shí)驗(yàn)基于實(shí)例集50_1～50_10和100_1～100_10進(jìn)行仿真分析,且所有算法均獨(dú)立運(yùn)行20次。

不同算法針對實(shí)例集50_1～50_10和100_1～100_10尋優(yōu)后得到的運(yùn)行結(jié)果如表2和表3所示。由表2和表3可知,與其他算法相比,DJaya算法所得平均值和標(biāo)準(zhǔn)差值最優(yōu),最小值和最大值相差較小。與此同時(shí),相較于GA和DE算法,DJaya算法需要更少的評估次數(shù)收斂到更優(yōu)解,這說明DJaya算法能夠有效求解大規(guī)模問題實(shí)例,且能保證解的質(zhì)量。這進(jìn)一步驗(yàn)證了DJaya算法在求解線纜生產(chǎn)調(diào)度問題上的有效性和穩(wěn)定性。

表2 不同算法在實(shí)例集50_1～50_10上的尋優(yōu)結(jié)果比較

表3 不同算法在實(shí)例集100_1～100_10上的尋優(yōu)結(jié)果比較

實(shí)驗(yàn)3為了進(jìn)一步驗(yàn)證DJaya算法的尋優(yōu)性能,本實(shí)驗(yàn)基于實(shí)例50-1、50-2、100-1和100-2進(jìn)行仿真分析,比較不同算法在20次獨(dú)立實(shí)驗(yàn)下的數(shù)據(jù)分布和收斂性能。不同算法尋優(yōu)得到的小提琴圖與箱線圖比較結(jié)果如圖5所示。由圖可見,相較于其他算法,DJaya算法具有更優(yōu)的最大完工時(shí)間,且數(shù)據(jù)結(jié)果集中分布于平均值附近,從而進(jìn)一步表明DJaya算法具有更好的收斂性和穩(wěn)定性。此外,對比算法在不同實(shí)例上的收斂曲線對比結(jié)果如圖6所示。由圖可知,DJaya算法具有更快的收斂速度,且能收斂得到更優(yōu)解。最后,本文給出關(guān)于實(shí)例10-1的調(diào)度方案,如圖7所示,其中符號“A”表示工序之間的模具切換時(shí)間。

綜上所述,DJaya較其他算法而言,具備更優(yōu)的收斂性及穩(wěn)定性,且能在較少的時(shí)間內(nèi)快速地找到問題的最優(yōu)解。因此,可以認(rèn)為本文所提出的DJaya算法在解決線纜生產(chǎn)調(diào)度問題上具有較好的有效性和穩(wěn)定性。

4 結(jié)束語

針對線纜生產(chǎn)調(diào)度優(yōu)化問題的特點(diǎn),本文在Jaya算法框架下,通過融入高效鄰域搜索策略,提出了一種DJaya算法。首先,采用基于工序的單列編碼方式來表示解個(gè)體,并通過基于左移的解碼策略生成可行調(diào)度方案。其次,在DJaya算法中引入了POX交叉算子以繼承最優(yōu)解的優(yōu)秀信息,并通過OBL策略遠(yuǎn)離最差解個(gè)體,進(jìn)而實(shí)現(xiàn)針對問題解空間的有效搜索。最后,基于線纜企業(yè)生產(chǎn)數(shù)據(jù),本文構(gòu)建了3類具有不同規(guī)模大小的標(biāo)準(zhǔn)實(shí)例集。基于不同規(guī)模實(shí)例集進(jìn)行的仿真實(shí)驗(yàn)結(jié)果表明,DJaya算法在求解線纜生產(chǎn)調(diào)度優(yōu)化問題過程中表現(xiàn)出較高的有效性和穩(wěn)定性。今后的研究將進(jìn)一步提升算法性能,以解決更符合線纜生產(chǎn)實(shí)際的問題實(shí)例,同時(shí)也將嘗試應(yīng)用于解決生產(chǎn)制造、交通運(yùn)輸、工程管理等領(lǐng)域存在的復(fù)雜調(diào)度優(yōu)化問題。