基于優(yōu)先調(diào)度規(guī)則實時選擇模型解決加工車間調(diào)度問題

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

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

1 研究背景

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

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

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

2 問題探討

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

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

(1)

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

(2)

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

(3)

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

3 方法研究

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

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

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

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

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

使用機器學習算法對數(shù)據(jù)進行分析。總模塊架構(gòu)如圖1所示。

▲圖1 總模塊架構(gòu)

4 仿真模塊

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

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

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

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

5 學習模塊

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

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

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

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

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

6 應(yīng)用模塊

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

▲圖3 Tmin與Qmin+Cmin對比▲圖4 模型應(yīng)用過程

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

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

7 試驗

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

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

Z=PijGij

(4)

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

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

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

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

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

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

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

▲圖5 決策樹分類器

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

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

▲圖6 隨機森林訓練預(yù)測流程

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

表4 Tmin為目標分類結(jié)果

表5 Qmin為目標分類結(jié)果

表6 Cmin為目標分類結(jié)果

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

8 結(jié)束語

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

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