□ 王 磊 □ 張 賀 □ 劉 毅 □ 石 剛

寧波吉利羅佑發(fā)動機零部件有限公司 浙江寧波 315336

1 研究背景

隨著制造業(yè)的高速發(fā)展,市場對產品的個性化要求越來越高,需要解決在快速變化的市場環(huán)境下小批量、定制化需求和復雜多變的內外部因素等問題。挖掘制造企業(yè)產能是解決上述問題的有效方式。影響產能的因素有很多,其中包括工藝規(guī)劃的合理性、生產調度的合理性等。生產調度是影響生產的重要因素,合理的生產調度能保證生產過程高效有序地運行,激發(fā)企業(yè)的生產潛力。為有效保證生產調度的最優(yōu)化,需要將傳統(tǒng)的生產調度方式與新一代的信息技術進行融合,使生產調度過程更具準確性、柔性化。

在優(yōu)化生產調度策略時,需要考慮的參數(shù)眾多,且具有動態(tài)性,在理論研究和實際應用上都具有復雜性。在學術界,根據(jù)調度的復雜度不同,形成許多優(yōu)化調度問題的方法,主要分為四類。第一,預留調度時間的優(yōu)化方法。預留出因為設備故障而影響調度的時間,該方法能夠很好地解決因意外而導致調度調整的問題,且具有很強的魯棒性,但是因設備故障具有不確定性,容易導致預留時間的準確性較低。第二,基于優(yōu)先調度規(guī)則的方法。諸多文獻證明,多個優(yōu)先調度規(guī)則的聯(lián)合使用,根據(jù)生產狀況的變化不斷切換,要比單個優(yōu)先調度規(guī)則在整個生產范圍內表現(xiàn)出更好的性能,在生產過程標準化程度高的企業(yè)表現(xiàn)得更好。第三,仿真方法。能在較短的時間內呈現(xiàn)出未來生產過程和得出結果,但是無法實時改變生產工藝流程,且解決調度問題方法不一,優(yōu)選過程工作量巨大。第四,生產調度問題優(yōu)化建模及算法。在實際生產中,存在諸多限制,以一個或多個目標構建數(shù)學模型后,用盡可能優(yōu)的算法以盡量短的時間得出盡可能優(yōu)的解,問題針對性高,解決能力強,但在高隨機性和動態(tài)性的生產環(huán)境下,自適應和自學習能力差,易導致解決問題的滯后性。

筆者以生產的標準化、信息化為基礎,為降低生產調度問題的復雜性和解決問題的滯后性,構造出一個能實時為每個設備選擇優(yōu)先調度規(guī)則的系統(tǒng),以最小化完工時間、最小化延遲時間、最小化完工時間和延遲時間之和為目標。當生產能力滿足時,優(yōu)化設備利用率。當生產能力不足時,優(yōu)化設備利用率和減少訂單上產品的延遲時間。對此,筆者首先利用仿真工具找出各個目標下應該施加給設備上的優(yōu)先調度規(guī)則組合,然后從獲取的數(shù)據(jù)組合中提取知識,構建模型,最后檢驗該模型的適應性。

2 問題探討

加工車間生產調度過程是極其復雜的,有文獻總結得出在每個設備上具有α個操作的β個設備和γ個工件的加工車間中將可能出現(xiàn)(βα×α！)j×(j!)個加工序列。如果α=β=γ=2,將可能出現(xiàn)256個加工序列,如果α=β=γ=3,將可能出現(xiàn)91 833 048個加工序列,即隨著α、β、γ的增加,加工車間調度的復雜度將呈現(xiàn)爆炸式增長。

筆者主要考慮優(yōu)化加工車間調度問題,把生產能力足夠和生產能力不足的情況分開研究。對于定制化、多品種小批量生產方式的企業(yè),訂單到達率高且訂單中包含多種類別的產品,面對這些工藝流程、加工時間不一的產品,如何在生產能力足夠的情況下保證該訂單上所有類別產品的完工時間,在生產能力不足的情況下降低訂單延遲時間,已成為優(yōu)化生產資源配置、最大滿足客戶需求的重中之中。訂單中產品最小化完工時間Tmin為:

(1)

式(1)確保了生產資源的最高利用率。如生產能力不足,訂單中產品最小化延遲時間Qmin為:

(2)

式(2)能最大化減少訂單延遲時間。最小化訂單上產品完工時間和延遲時間之和Cmin為:

(3)

式(3)既能優(yōu)化生產資源配置,又能最大化滿足客戶需求。Tij為產品i在設備j上的加工時間,i=1,2,3,…,m,j=1,2,3,…,n,Di為第i產品的交貨期。

3 方法研究

方法研究主要分為三個步驟。

(1) 以單類型產品的批量為單位,借助仿真工具針對每一設備使用不同調度規(guī)則,尋找出同一類別中產品最小化延遲時間、最小化完工時間、最小化產品延遲時間和完工時間之和的優(yōu)先調度規(guī)則組合。

(2) 避免對比所有調度規(guī)則組合的情況,找出同類別產品的最優(yōu)調度組合,基于步驟(1)收集到的數(shù)據(jù),使用數(shù)據(jù)挖掘技術提取數(shù)據(jù),尋找出每一個設備的最優(yōu)調度規(guī)則。

(3) 實際生產中,訂單依據(jù)客戶需求的緊急程度可分為緊急訂單和普通訂單兩種,合理安排這兩種訂單,最大化地滿足客戶需求。

筆者提出的方法分為仿真模塊、學習模塊和應用模塊。仿真模塊滿足數(shù)據(jù)要求,學習模塊創(chuàng)造出調度規(guī)則選擇的模型,應用模塊滿足處理新訂單的需求,驗證在實際生產過程中模型運用的效果。

使用機器學習算法對數(shù)據(jù)進行分析?？偰K架構如圖1所示。

▲圖1 總模塊架構

4 仿真模塊

(1) 對原始數(shù)據(jù)庫的產品進行分類,劃分的依據(jù)為各產品在工序上的加工時間、開始加工前的創(chuàng)建時間、工藝流程、該類別中產品的總數(shù)。

(2) 從優(yōu)先調度規(guī)則庫中選出一個或多個調度規(guī)則,確定設備前將要加工的產品的加工隊列。

(3) 計算出優(yōu)先調度規(guī)則下的該類別下所有產品在某設備下的完工時間、延遲時間、完工時間與延遲時間之和,并以最小化為目標選出最優(yōu)的優(yōu)先調度規(guī)則組合。

(4) 將該類別相關數(shù)據(jù)與其最終確定的最優(yōu)優(yōu)先調度規(guī)則組合聯(lián)系起來存入標簽數(shù)據(jù)庫中,以備知識提取時使用。

5 學習模塊

▲圖2 標簽數(shù)據(jù)庫生成

隨機選取的樣本數(shù)據(jù)見表1。Ti為第i類產品的加工時間,Fi為第i類產品的加工數(shù)量,Ei為第i類產品的交貨期,DR1、DR2、DR3表示事先構建好的調度規(guī)則1、調度規(guī)則2、調度規(guī)則3。

表1 部分樣本數(shù)據(jù)表

以隨機森林分類器為例,預測效果統(tǒng)計見表2。訓練樣本和測試樣本同為表1樣本,其中P列對訓練集預測出的結果,R列為預測結果的置信度,與表1實際最優(yōu)調度規(guī)則相比,表現(xiàn)出較好的性能。

表2 預測效果統(tǒng)計

6 應用模塊

選取最優(yōu)完工時間與延遲時間之和對應的優(yōu)先調度規(guī)則與最優(yōu)完工時間或最優(yōu)延遲時間所對應的規(guī)則不一樣的樣本,Tmin對應的優(yōu)先調度規(guī)則與保證Qmin和Cmin的優(yōu)先調度規(guī)則效果差距很小,甚至持平,表明同時考慮完工時間和延遲時間所使用的調度規(guī)則既能較好保證優(yōu)化產品延遲時間,又能保證優(yōu)化產品總加工時間。Tmin與Qmin+Cmin對比如圖3所示。

▲圖3 Tmin與Qmin+Cmin對比▲圖4 模型應用過程

在實際生產過程中,依照客戶對交貨期的需求,管理人員依照車間制造能力將新到達訂單分為普通訂單和緊急訂單,然后利用已構建好的模型,確定該訂單生產過程所經(jīng)過設備的優(yōu)先調度規(guī)則。模型應用過程如圖4所示,數(shù)據(jù)庫包含所有類別下屬性。

當產品總交貨時間大于產品實際加工時間時,說明車間生產能力足夠,按照以最優(yōu)化產品完工時間為目標構建的模型2去指派優(yōu)先調度規(guī)則,以優(yōu)化源配置,提高生產效率。當產品總交貨時間小于產品實際加工時間時,說明生產能力不足,按照以最優(yōu)化產品完工時間與延遲時間之和為目標構建的模型1去指派優(yōu)先調度規(guī)則,以達到最小化訂單的交貨延遲的目的。

7 試驗

為了驗證以上結果,筆者首先使用仿真工具找出每個目標最優(yōu)化下每個設備所對應的優(yōu)先調度規(guī)則,把優(yōu)先調度規(guī)則分為兩類。一類是單個優(yōu)先調度規(guī)則,如先進先出原則、最短生產時間規(guī)則等。另一類是混合優(yōu)先調度規(guī)則,如產品經(jīng)過所有設備的總加工時間與最短路徑樹混合、產品的總剩余工作時間與產品在設備上的處理時間混合等。

所提出的混合優(yōu)先調度規(guī)則所對應的參數(shù)則為產品在設備上的處理時間、產品經(jīng)過所有設備的總加工時間、產品的總剩余工作時間、產品的交貨期兩兩混合,表達式為:

Z=PijGij

(4)

式中:Pij為第i個工件在第j個設備上加工時的具體參數(shù)值;Gij為第i個工件在第j個設備上加工時的具體參數(shù)值。

110株可育大豆ms1輪回群體核心種質的單株產量在2.13～29.05 g，其中，單株產量超過區(qū)域試驗對照品種黔豆7號(13.38 g)的有23株，占20.91%；超過地方品種銅科豆2號(12.78 g)的有24株，占21.82%。說明，大豆ms1輪回群體核心種質對本地區(qū)的大豆高產育種具有利用潛力。

以上選取的優(yōu)先調度規(guī)則都以參數(shù)值從小到大或從大到小確定隊列中作業(yè)的加工優(yōu)先級。

試驗所考慮的問題是Lenstra提出的經(jīng)典的四臺設備車間調度問題,該問題一直被廣泛地探討和研究。針對提出的四臺設備車間調度問題,提出以下假設:① 單個設備一次只能連續(xù)處理一個工件;② 設備故障時間和工件在設備與設備之間的運送時間不予考慮。

基于文獻生成數(shù)據(jù)的方法,隨機生成100個類別的產品,以各產品在工序上的加工時間、開始加工前的創(chuàng)建時間、工藝流程、該類別中產品的總數(shù)來劃分類別。每個類別下產品數(shù)量服從[10,50]的隨機分布,產品加工時間服從[20,400]的隨機分布,并用工序上加工時間0表示未經(jīng)過該工序,該產品的交貨期以產品的瓶頸工序加工時間為均值、方差為20的正態(tài)分布。部分生成樣本數(shù)據(jù)見表3。Ji為設備,每個類別包含多種產品,每個類別的設備加工時間為該類別下所有產品在該設備加工的時間,數(shù)量為該類別下產品數(shù)量的總和,交貨期為該類別對應訂單的交貨期。

表3 部分樣本數(shù)據(jù)

在實際生產中,雖然經(jīng)過仿真能為每個類別的產品在加工過程中優(yōu)選出優(yōu)先調度規(guī)則組合,但是以筆者選取的22個優(yōu)先調度規(guī)則和四臺設備交貨期,需要仿真的次數(shù)為23 425次,這是極其龐大的工作量。為解決此問題,構建一個能快速選擇優(yōu)先調度規(guī)則的模型是十分必要的。結合仿真結果,很明顯是一個多標簽分類問題,在使用各類分類器以時間成本和準確率構建模型時,發(fā)現(xiàn)決策樹分類器和隨機森林分類器效果較好。決策樹分類器如圖5所示。

▲圖5 決策樹分類器

決策樹分類器中每個節(jié)點表示要分類的樣本中的特征,每個分支表示節(jié)點可以采用的值。實例從根節(jié)點開始進行分類,并根據(jù)其特征值的重要程度進行排序,A1、A2、A3為三個屬性,a、b、c為屬性值,PDRi為最優(yōu)調度規(guī)則。

隨機森林訓練預測流程如圖6所示。把整個數(shù)據(jù)集D劃分為訓練集和測試集,訓練集數(shù)據(jù)為數(shù)據(jù)集的子集。訓練集包括多個子集,由決策樹對這些子集分別訓練學習,形成多個決策樹,即多個規(guī)則。測試數(shù)據(jù)中的測試樣本按照多個規(guī)則進行學習,每一規(guī)則會使該測試樣本分到一類中,對劃分到的類進行計數(shù),統(tǒng)計次數(shù),最后得到最大的和的對應類就是該測試樣本的最終預測結果。

▲圖6 隨機森林訓練預測流程

模型構建時,將訓練集和測試集劃分為7∶3對模型進行訓練驗證。使用五次交叉驗證,以正確率和時間為指標。使用隨機森林分類器和決策樹分類器的分類結果見表4、表5、表6。

表4 Tmin為目標分類結果

表5 Qmin為目標分類結果

表6 Cmin為目標分類結果

由表4、表5、表6可知,在正確率上,隨機森林分類器表現(xiàn)出更好的效果,但是模型構建的時間則較長。如果允許模型更新間隔時間較長,選用隨機森林分類器效果更佳。但是如果模型更新間隔時間要求短,為了保證模型適應性的滯后性低,選用決策樹分類器效果更佳。分類器的良好選擇對模型依靠生產環(huán)境的不斷變化進行實時更新具有重要意義。

8 結束語

筆者選取單個優(yōu)先調度規(guī)則和混合優(yōu)先調度規(guī)則,聯(lián)合使用仿真技術和數(shù)據(jù)挖掘技術構建了一個能實時且高效的為設備指派優(yōu)先調度規(guī)則的模型,消除了使用單純的使用仿真技術優(yōu)選優(yōu)先調度規(guī)則工作量大的弊端,減輕了解決車間調度問題的復雜性,并且對研究比在多項式復雜度內被驗證問題更困難解決的問題具有重要意義。

相比于前人的研究,優(yōu)化了產品最小化完工時間和產品的延遲時間,進一步挖掘了制造車間的生產能力,解決了在生產力不足時同時進行多訂單生產情況下,既能優(yōu)化產品完工時間,又能優(yōu)化產品交付延遲時間的雙目標問題,更高質量地滿足客戶的需求。