基于數(shù)據(jù)挖掘的船舶平面分段智能調(diào)度模型設(shè)計(jì)

，，

(1.上海交通大學(xué) 船舶與海洋工程國家重點(diǎn)實(shí)驗(yàn)室，上海 200240;2.高新船舶與深海開發(fā)裝備協(xié)同創(chuàng)新中心，上海 200240)

解決船舶生產(chǎn)調(diào)度問題，常見的方法有調(diào)度優(yōu)先規(guī)則和調(diào)度優(yōu)化算法。調(diào)度優(yōu)先規(guī)則雖然決策速度快，但在稍復(fù)雜的問題上調(diào)度性能達(dá)不到要求；而調(diào)度優(yōu)化算法雖然調(diào)度性能較好，但決策速度是其不可忽視的瓶頸之一。針對(duì)這種問題，有學(xué)者通過挖掘優(yōu)化算法的調(diào)度求解數(shù)據(jù)，提取調(diào)度知識(shí)和規(guī)則，得到的數(shù)據(jù)挖掘模型能夠很好地逼近優(yōu)化算法性能[1-5]。但目前大部分研究涉及的調(diào)度問題類型主要是Job Shop問題，對(duì)流水線調(diào)度問題的研究較少，在船舶生產(chǎn)調(diào)度問題分析上未見采用類似的思路。另外，大部分學(xué)者的目的是為了驗(yàn)證思路的可行性，因而在數(shù)據(jù)挖掘過程中僅選用一種機(jī)器學(xué)習(xí)模型，沒有進(jìn)行模型的對(duì)比。為此，考慮設(shè)計(jì)一種基于數(shù)據(jù)挖掘的平面分段智能調(diào)度模型，并開發(fā)原型軟件，為解決船舶生產(chǎn)調(diào)度問題提供新的思路。

1 智能調(diào)度模型設(shè)計(jì)

采用模塊化思想，基于數(shù)據(jù)挖掘技術(shù)設(shè)計(jì)船舶平面分段智能調(diào)度模型，模型組成見圖1。

出于數(shù)據(jù)獲取的難易程度及數(shù)據(jù)質(zhì)量方面的考慮，數(shù)據(jù)源暫時(shí)只采用優(yōu)化解數(shù)據(jù)。

1.1 平面分段調(diào)度問題模型

分析圖2所示的平面分段流水線調(diào)度問題。該流水線配置了拼板、底板焊接、縱骨安裝、縱骨焊接、縱桁及肋板裝配、縱桁及肋板焊接、檢查運(yùn)出等7個(gè)工位[6]。實(shí)際生產(chǎn)過程中，在建分段經(jīng)由同步運(yùn)輸輥由一個(gè)工位輸送至另一個(gè)工位。

考慮如下調(diào)度問題：任一平面分段的建造都要依次完成7道工位的加工；各工位間沒有緩沖工位，每個(gè)工位一次只能加工一個(gè)分段；在建分段離開當(dāng)前工位后，下一個(gè)工件才能進(jìn)入當(dāng)前工位。

建立上述平面分段流水線調(diào)度問題的數(shù)學(xué)模型，各符號(hào)說明如下。

n為分段數(shù)量；m為工位數(shù)量；

i為分段標(biāo)號(hào)，i=1,2,,n;

j為工位標(biāo)號(hào)，j=1,2,,m;

Pi,j為分段i在工位j上的加工時(shí)間；

Di,j為分段i離開工位j的時(shí)間；

Ci為分段i的完工時(shí)間；

假設(shè)S=[S1,S2,,Sn]表示一批分段的加工排序。

DS1,0=0

(1)

DS1,j=DS1,j-1+PS1,j,1≤j≤m

(2)

DSk,0=DSk-1,1,2≤k≤n

(3)

DSk,j=max(DSk,j-1+PSk,j,DSk-1,j+1)

2≤k≤n,1≤j≤m-1

(4)

DSk,m=DSk,m-1+PSk,m,2≤k≤n

(5)

Ci=DSk,m

(6)

根據(jù)實(shí)際生產(chǎn)的一般要求，以最小化最大完工時(shí)間為優(yōu)化目標(biāo)：

(7)

1.2 調(diào)度知識(shí)模式與特征定義

調(diào)度問題確定后，需要定義調(diào)度知識(shí)模式[7]，即機(jī)器學(xué)習(xí)的“輸出”。結(jié)合常用調(diào)度規(guī)則與實(shí)際生產(chǎn)經(jīng)驗(yàn)，確定調(diào)度知識(shí)模式如下：對(duì)于同時(shí)等待加工的兩個(gè)工件，優(yōu)先選取哪個(gè)工件進(jìn)行加工。對(duì)于多個(gè)分段同時(shí)等待加工的問題，可以使用多次兩兩比較的方法解決。

根據(jù)船舶平面分段流水線調(diào)度問題的特點(diǎn)，選取兩個(gè)平面分段在各個(gè)工位上加工時(shí)間的差值與比值作為機(jī)器學(xué)習(xí)特征。

以3個(gè)工位、2個(gè)分段(記為分段1和分段2)的情況為例展開說明。表1展示了2個(gè)分段在各個(gè)工位的加工時(shí)間(分鐘)。假設(shè)分段1在分段2之前進(jìn)行加工。根據(jù)2個(gè)分段的加工時(shí)間及加工順序，構(gòu)造機(jī)器學(xué)習(xí)的特征數(shù)據(jù)，結(jié)果見表2。

表1 分段加工時(shí)間 min

表2 特征數(shù)據(jù)

特征1-4是分段1與分段2加工時(shí)間的比值，特征5-8是分段1與分段2加工時(shí)間的差值；分段1在分段2之前加工，故數(shù)據(jù)標(biāo)注為1。第二條特征數(shù)據(jù)的構(gòu)造過程與此類似，特征1-8分別是分段2和分段1加工時(shí)間的比值與差值，但分段2在分段1之后加工，故數(shù)據(jù)標(biāo)注為0。

為消除量綱對(duì)某些機(jī)器學(xué)習(xí)模型的影響，最終訓(xùn)練模型之前，對(duì)特征值進(jìn)行歸一化處理。

1.3 灰狼算法

考慮到灰狼算法受到灰狼社會(huì)等級(jí)制度和狼群獵食行為的啟發(fā)，控制參數(shù)較少，在保證優(yōu)化效率的同時(shí)更容易實(shí)現(xiàn)[8]。標(biāo)準(zhǔn)灰狼算法主要用于求解連續(xù)型優(yōu)化問題，求解離散調(diào)度問題時(shí)需要使用隨機(jī)鍵編碼的LOV(Largest order value)規(guī)則[9],將連續(xù)型的位置向量轉(zhuǎn)化為離散型的工件排序。使用隨機(jī)鍵編碼LOV規(guī)則對(duì)實(shí)數(shù)變量Xi=[xi,1,xi,2,,xi,n]按照非升序排列，得到工件排序。以4個(gè)工件的問題為例，基于LOV的轉(zhuǎn)化過程見表3。

表3 基于LOV的轉(zhuǎn)換示例

1.4 機(jī)器學(xué)習(xí)性能度量

智能調(diào)度模型中選用決策樹、支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)三種機(jī)器學(xué)習(xí)模型，并根據(jù)分類精度和召回率兩種性能度量指標(biāo)進(jìn)行模型選擇。精度和召回率指標(biāo)的描述[10-12]見表4。

表4 分類精度和召回率

2 原型軟件開發(fā)

采用python編程語言和numpy+scipy+pandas+sklearn+appJar(基于Tkinter)開源框架完成原型軟件開發(fā)。系統(tǒng)智能調(diào)度模型子界面見圖3。

3 實(shí)例計(jì)算

3.1 機(jī)器學(xué)習(xí)模型訓(xùn)練

考慮建造一批(20個(gè))不同尺寸的平面分段，首先使用灰狼算法計(jì)算得到50個(gè)案例的優(yōu)化解。每個(gè)優(yōu)化序列中有20個(gè)分段，將不同分段加工時(shí)間的比值與差值作為特征，兩兩比較，總共得到380×50=19 000條標(biāo)注數(shù)據(jù)。

特征有加工時(shí)間差和加工時(shí)間比兩種類型，為消除不同特征之間量綱不同的影響，在訓(xùn)練機(jī)器學(xué)習(xí)模型之前，使用z-score標(biāo)準(zhǔn)化方法對(duì)各個(gè)特征進(jìn)行預(yù)處理。

為了得到合理的模型參數(shù)，使用了網(wǎng)格搜索技術(shù)調(diào)整“超參”，針對(duì)不同的模型分別采用了相應(yīng)的設(shè)置以防止過擬合。使用3重交叉驗(yàn)證的方式訓(xùn)練模型，最終確定的決策樹模型中，最大層數(shù)為10，最小葉節(jié)點(diǎn)樣本個(gè)數(shù)為15；神經(jīng)網(wǎng)絡(luò)模型包括3層神經(jīng)元，中間層神經(jīng)元個(gè)數(shù)為15，模型復(fù)雜度懲罰項(xiàng)alpha為0.01；支持向量機(jī)模型懲罰項(xiàng)參數(shù)C為1，核參數(shù)為rbf。

表5列出了三種機(jī)器學(xué)習(xí)模型的性能度量結(jié)果。綜合考慮精度和召回率兩種指標(biāo)，選擇效果最好的神經(jīng)網(wǎng)絡(luò)模型進(jìn)行后續(xù)的分類預(yù)測(cè)。

表5 三種機(jī)器學(xué)習(xí)模型的分類精度和召回率

3.2 智能調(diào)度模型性能評(píng)估

考慮10個(gè)新的調(diào)度案例，分別選用優(yōu)先調(diào)度規(guī)則、灰狼算法及智能調(diào)度模型進(jìn)行求解。優(yōu)先調(diào)度規(guī)則采用SPT規(guī)則。SPT規(guī)則是應(yīng)用最廣泛的優(yōu)先調(diào)度規(guī)則之一，已被證明在較簡單的調(diào)度問題上能夠取得較為理想的調(diào)度結(jié)果[13]。

三種求解方法得到的結(jié)果的makespan值見表6。

表6 三種求解方法結(jié)果的makespan對(duì)比

為進(jìn)一步評(píng)估智能調(diào)度模型的效果，構(gòu)建性能參數(shù)指標(biāo)如下。

η(method)=

(8)

式中：η(method)為其他方法相對(duì)于灰狼算法的相對(duì)性能度量；Mi(method)為某種方法在第i個(gè)測(cè)試案例上獲得的makespan；Mi(best)為灰狼算法獲得的makespan；n為測(cè)試案例數(shù)。

SPT規(guī)則、智能調(diào)度模型的性能參數(shù)指標(biāo)計(jì)算見表7?？梢钥闯?，智能調(diào)度模型比SPT規(guī)則效果更好，與灰狼算法的調(diào)度性能差距在5%以內(nèi)。

表7 性能參數(shù)指標(biāo)對(duì)比

另一方面，三種方法的平均求解耗時(shí)見表8。其中，SPT規(guī)則決策速度最快，而智能調(diào)度模型的求解耗時(shí)約為灰狼算法的1/12。這表明智能調(diào)度模型在逼近優(yōu)化算法性能的同時(shí)，具備速度和效率上的優(yōu)勢(shì)：僅需一次離線訓(xùn)練，即可使用訓(xùn)練好地模型快速求解新的問題。

表8三種方法求解平均耗時(shí)ms

SPT規(guī)則灰狼算法智能調(diào)度模型60020 1001 600

4 結(jié)論

提出的船舶平面分段智能調(diào)度模型，通過調(diào)度知識(shí)模式和特征定義、優(yōu)化求解、機(jī)器學(xué)習(xí)模型訓(xùn)練及對(duì)比選擇等過程，較好地解決了調(diào)度求解速度與性能的平衡問題，一定程度上可以突破優(yōu)化算法決策速度的限制，對(duì)實(shí)現(xiàn)船舶生產(chǎn)實(shí)時(shí)動(dòng)態(tài)調(diào)度具有借鑒意義。但是調(diào)度問題數(shù)學(xué)模型中只考慮了加工時(shí)間這一主要因素，沒有考慮到工位、工人工作時(shí)間、工作機(jī)械故障等因素的影響。后續(xù)將研究plant simulation等工業(yè)生產(chǎn)仿真軟件建模，考慮更復(fù)雜的船廠生產(chǎn)情況，并進(jìn)一步通過數(shù)據(jù)挖掘得到更貼合船舶實(shí)際生產(chǎn)的調(diào)度知識(shí)。