使用規(guī)則挖掘?qū)崿F(xiàn)排程系統(tǒng)的規(guī)則制定

（北京機(jī)械工業(yè)自動化研究所有限公司，北京 100120）

0 引言

在中國制造2025的大環(huán)境下，越來越多的企業(yè)選擇將具體的生產(chǎn)業(yè)務(wù)與ERP、MES等信息化系統(tǒng)相結(jié)合，利用信息化的手段來管控，指導(dǎo)制造生產(chǎn)。而在這其中，對于實際的生產(chǎn)計劃的計劃調(diào)度則是十分重要的。高級計劃與排程系統(tǒng)（APS）通過對計劃、資源、時間等進(jìn)行管理從而達(dá)到最大化效益的目的，可以十分有效地管理企業(yè)的生產(chǎn)計劃。盡管APS系統(tǒng)的理論已經(jīng)非常豐富，在實際生產(chǎn)中的運(yùn)用效果卻不是很理想。這一情況的出現(xiàn)有多種原因，其中一個原因就是實際生產(chǎn)中的生產(chǎn)規(guī)則太過于復(fù)雜和多變，企業(yè)的生產(chǎn)人員也無法很清晰地將實際生產(chǎn)規(guī)則總結(jié)提煉為通用的規(guī)則，導(dǎo)致排程系統(tǒng)排程的結(jié)果并不是很準(zhǔn)確，需要頻繁的人工干預(yù)，從而使得效率大幅度降低。

然而，絕大部分的企業(yè)在生產(chǎn)過程中都會保留生產(chǎn)信息，這些大量的生產(chǎn)信息中暗中包含了企業(yè)生產(chǎn)的相關(guān)規(guī)則，所以可以利用規(guī)則挖掘方法以及粗集理論來對通用生產(chǎn)規(guī)則進(jìn)行總結(jié)與歸納，也可以利用不斷產(chǎn)生的生產(chǎn)信息進(jìn)行自學(xué)習(xí)，得到更加具有普適性的生產(chǎn)規(guī)則，從而更高效地指導(dǎo)生產(chǎn)，并且可以根據(jù)實際生產(chǎn)情況的變化而對排程規(guī)則進(jìn)行更新，可以更準(zhǔn)確地指導(dǎo)生產(chǎn)。

1 粗集理論的基本概念

知識是對對象進(jìn)行分類的規(guī)則，對象是用屬性集表示的，而知識則是屬性集之間的映射關(guān)系。對屬性集進(jìn)行映射就會產(chǎn)生不同的分類，而這些分類就是知識。

根據(jù)粗集理論，一個規(guī)則體系可以表達(dá)為S=（U，C∪D，V，f）。其中U={X1，X2，…，Xn}代表對象集合，A=C∪D代表屬性集合，子集C代表條件屬性集，子集D代表決策屬性集。并且有C∪D=A，C∩D=φ。若規(guī)則體系用二維表的方式表達(dá)，那么可以稱這個二維表為決策表，在這個表中每一行表示一個元素，每一列表示其屬性。

設(shè)U為對象的有限集，稱之為論域，對于任何子集X∈U，都可以稱X是一個U中的概念，U中的任何概念組可以稱之為關(guān)于U的抽象知識，簡稱知識。若有集合R={X1，X2，…，Xn}，其中Xi∈U，Xi≠φ，并且Xi∩Xj=φ，當(dāng)i≠j；i，j=1，2，…，n；且有∪ni=1Xi=U，則稱R為一個分類，Xi稱為R的一個等價類。論域U中的一個分類確定了U上的一個等價關(guān)系。同樣，論域U中的一個等價關(guān)系也確定了論域U的一個分類，所以可以利用等價關(guān)系對集合進(jìn)行分類。

屬性集A中的屬性分為條件屬性C與結(jié)論屬性D；確定條件屬性集上的等價類E_k與結(jié)論屬性集上的系統(tǒng)概念X，尋找Ek與X件的關(guān)系，若其結(jié)果有X包含Ek，則成為下近似；X與Ek的交集非空，則稱為上近似；X與Ek的交集為空，則稱為兩者無關(guān)；根據(jù)上述結(jié)果確定發(fā)現(xiàn)的規(guī)則，下近似中的條件屬性與結(jié)論屬性之間可以建立確定性規(guī)則，上近似中的條件屬性與結(jié)論屬性之間可以建立不確定性規(guī)則，而無關(guān)說明條件屬性和結(jié)論屬性毫無規(guī)則可言?；诖旨碚摰闹R發(fā)現(xiàn)主要涉及兩個重要的處理過程：求近似控件和縮減。實現(xiàn)規(guī)則發(fā)現(xiàn)的一個具體方法是通過在近似空間中尋找條件屬性關(guān)于結(jié)論屬性集中的最小依賴關(guān)系來完成的。

粗集理論的特點(diǎn)是不需要預(yù)先定某些屬性或者特征的定量描述，而是直接從給定問題的直接描述出發(fā)，通過不可分辨關(guān)系確定問題的近似域，從而找出該問題所對應(yīng)的知識，即為對象進(jìn)行分類的方法。

2 利用粗集理論與決策挖掘的APS排程規(guī)則提取

利用粗集理論和決策挖掘方法提取APS排程規(guī)則的主要過程如圖1所示。

圖1 規(guī)則提取過程

如圖1所示，首先得到企業(yè)的實際生產(chǎn)數(shù)據(jù)，此時需對企業(yè)的生產(chǎn)數(shù)據(jù)進(jìn)行整理與清洗，得到標(biāo)準(zhǔn)格式的條件屬性集-決策屬性集生產(chǎn)數(shù)據(jù)。然后利用粗集理論與規(guī)則挖掘的方式對生產(chǎn)數(shù)據(jù)進(jìn)行條件集與決策集的最小映射，挖掘出的映射關(guān)系即為規(guī)則，最后在企業(yè)的不斷生產(chǎn)中，生成新的生產(chǎn)數(shù)據(jù)，系統(tǒng)根據(jù)新的生產(chǎn)數(shù)據(jù)不斷的進(jìn)行優(yōu)化學(xué)習(xí)，使得排程規(guī)則更全，排程更加準(zhǔn)確。

基于以上提到的粗集理論，我們在得到了企業(yè)的生產(chǎn)數(shù)據(jù)進(jìn)行整理得到，時間-產(chǎn)品-設(shè)備的具體信息，其中時間可以作為權(quán)重系數(shù)，時間太久的規(guī)則可以降低權(quán)重甚至作廢。

首先我們對生產(chǎn)的設(shè)備進(jìn)行分類，由于生產(chǎn)的設(shè)備一般不會有很多種類，所以這一步由人工進(jìn)行分配，比較極端的情況有兩種：第一種是所有設(shè)備全部都一樣，不需要進(jìn)行分類。這個時候也不需要進(jìn)行排程規(guī)則的提取，因為沒有任何限制，這時候只要根據(jù)企業(yè)具體生產(chǎn)實際情況，將產(chǎn)品的生產(chǎn)計劃分配到具體的設(shè)備上進(jìn)行生產(chǎn)就可以。第二種情況是全部的生產(chǎn)設(shè)備全都不一樣，即每個設(shè)備為一個分類，這時候就不需要人工對設(shè)備進(jìn)行分類了。此時只要根據(jù)歷史數(shù)據(jù)對產(chǎn)品和生產(chǎn)設(shè)備之間的規(guī)則進(jìn)行抽取即可。

我們?nèi)∽钇胀ǖ那闆r，即有n種產(chǎn)品，有m個生產(chǎn)設(shè)備。其中m個生產(chǎn)設(shè)備可以劃分為M組，我們認(rèn)為每組生產(chǎn)設(shè)備可以生產(chǎn)的產(chǎn)品種類完全相同。即找到屬于生產(chǎn)設(shè)備的最小集合。假設(shè)M可以表示為M={M1，M2，…，Mn}，則根據(jù)生產(chǎn)的歷史數(shù)據(jù)中產(chǎn)品曾經(jīng)在某個生產(chǎn)設(shè)備上面生產(chǎn)過的信息可以得到ni∈Mj,i,j∈R。這樣我們其實就得到一條規(guī)則，即產(chǎn)品ni可以在設(shè)備集Mj上進(jìn)行生產(chǎn)。然后按照歷史數(shù)據(jù)不斷的將產(chǎn)品信息與設(shè)備集信息進(jìn)行對應(yīng)，這樣我們就可以得到一個產(chǎn)品與設(shè)備集對應(yīng)的關(guān)系。

這樣，只要企業(yè)的歷史生產(chǎn)數(shù)據(jù)足夠大，那么理論上歷史數(shù)據(jù)是可以包含所有生產(chǎn)情況的，根據(jù)一個粗略的判斷法則，當(dāng)一個分類擁有5k個已經(jīng)標(biāo)注的樣本時就可以達(dá)到可以接受的性能，當(dāng)擁有一千萬已經(jīng)標(biāo)注的樣本時就可以達(dá)到甚至超過人類進(jìn)行判斷的準(zhǔn)確性。依據(jù)這個法則，我們可以大致的估算一下我們得到的粗集規(guī)則是不是可以使用。當(dāng)然，如果不是非常準(zhǔn)確也沒有關(guān)系，因為在APS系統(tǒng)根據(jù)這個規(guī)則集進(jìn)行排程之后，計劃人員可以手工對排程結(jié)果進(jìn)行干預(yù)，比如在原規(guī)則集中沒有產(chǎn)品n1可以在設(shè)備集M1上生產(chǎn)的記錄，那么排程系統(tǒng)就不會將產(chǎn)品n1排程在設(shè)備集M1上進(jìn)行生產(chǎn)，但是如果計劃員在進(jìn)行確認(rèn)排程結(jié)果的時候認(rèn)為產(chǎn)品n1可以在此設(shè)備集上進(jìn)行生產(chǎn)，那么通過人工對排程結(jié)果進(jìn)行干預(yù)，將產(chǎn)品n1排程在屬于此設(shè)備集的任意設(shè)備上面進(jìn)行生產(chǎn)，那么系統(tǒng)就可以自動記錄這么一條規(guī)則，從而在下次對這個產(chǎn)品進(jìn)行排程的時候也會將設(shè)備集M1作為備選生產(chǎn)設(shè)備考慮進(jìn)去，這樣就會令計劃排程的結(jié)果越來越準(zhǔn)確。

3 具體實現(xiàn)以及規(guī)則評價

3.1 具體實現(xiàn)

我們以某橡膠密封圈加工企業(yè)作為測試對象，該企業(yè)每周生產(chǎn)六天，每天分為三班，每班生產(chǎn)的產(chǎn)品有可能和下一班次一樣，也有可能不一樣，并且班中也有可能換產(chǎn)品生產(chǎn)。如表一所示，我們收集了該企業(yè)82臺設(shè)備近一年的實際生產(chǎn)情況，一共102641條記錄，如表一所示，即每個班次每個設(shè)備上利用什么模具生產(chǎn)什么產(chǎn)品的相關(guān)信息。

表1 部分企業(yè)實際生產(chǎn)數(shù)據(jù)表

按照產(chǎn)品-模具作為條件，即產(chǎn)品代碼和模具代碼都相同的記錄會被視為相同的條件，按照這種分組方法可以將分為2030組。

表2 部分設(shè)備集合表

然后如表二所示，手工將8臺設(shè)備分為9個集合，保證每個集合中的機(jī)器都可以生產(chǎn)相同的產(chǎn)品。

圖2 規(guī)則表達(dá)方式

如圖2所示，由人工對生產(chǎn)排程的規(guī)則進(jìn)行梳理，產(chǎn)品-模具作為條件集，設(shè)備作為屬性集，將條件集與屬性集對應(yīng)即為一條規(guī)則。按照產(chǎn)品-模具-設(shè)備分組可以分出6658條規(guī)則，作為系統(tǒng)自動對產(chǎn)品-模具-設(shè)備集合進(jìn)行規(guī)則抽取的對照組。然后再利用上文描述的方法，在系統(tǒng)中自動將產(chǎn)品-模具-設(shè)備集信息進(jìn)行對應(yīng)，進(jìn)行相應(yīng)的規(guī)則抽取。從而得到一個粗集規(guī)則表，這個表就代表了對應(yīng)的產(chǎn)品，對應(yīng)的模具應(yīng)該在哪些設(shè)備集上面進(jìn)行生產(chǎn)，我們一共抽取出了5171條規(guī)則。將兩個規(guī)則集中的規(guī)則進(jìn)行一一對比后，相同的規(guī)則集有4263條。

3.2 規(guī)則評價

由此，按照得到的規(guī)則來算，系統(tǒng)自動得到了4263條規(guī)則，實際準(zhǔn)確的規(guī)則有6658條，自動抽取規(guī)則的準(zhǔn)確率達(dá)到了0.64。當(dāng)然由于每個設(shè)備集合中所含的設(shè)備數(shù)目是不同的，所以在規(guī)則抽取中尋找出設(shè)備數(shù)目較多的集合明顯比設(shè)備數(shù)目較少的集合要更有價值。此時我們再將設(shè)備集合中的設(shè)備數(shù)作為一個權(quán)重加入計算準(zhǔn)確率的公式，即對于每個產(chǎn)品-模具條件，自動抽取規(guī)則的準(zhǔn)確性X=numtest/numco，numtest表示系統(tǒng)自動抽取規(guī)則所得到的設(shè)備數(shù)目，numco表示準(zhǔn)確的規(guī)則中所包含的設(shè)備數(shù)目。對每一個產(chǎn)品-模具條件計算準(zhǔn)確性之后，再做一個平均，可以得到此時的準(zhǔn)確性已經(jīng)達(dá)到0.789。此方法的最大特點(diǎn)是可以快速進(jìn)行部署，只需要對得到的生產(chǎn)數(shù)據(jù)進(jìn)行簡單的數(shù)據(jù)清洗，就可以快速地得到較為準(zhǔn)確的結(jié)果，并且可以在以后的生產(chǎn)中自動地不斷優(yōu)化。

4 結(jié)論

本文利用粗集理論，通過不可分辨關(guān)系的概念，可以將對象劃分為多個近似域，找出這些對象中隱藏的關(guān)系，十分適合于制造業(yè)中復(fù)雜多變的生產(chǎn)環(huán)境。具體的來說有以下特點(diǎn)：

1）能夠比較快速的發(fā)掘并且更新企業(yè)生產(chǎn)排程的規(guī)則，從而快速部署APS高級排程系統(tǒng)；

2）當(dāng)生產(chǎn)數(shù)據(jù)足夠的情況下，排程的準(zhǔn)確度相較于啟發(fā)式排程方式高，從而減少人工干預(yù)的情況，令A(yù)PS排程系統(tǒng)實際的使用效果更好；

3）決策者的先驗知識可以很方便地在系統(tǒng)中進(jìn)行新增與維護(hù)，并且系統(tǒng)可以根據(jù)實際生產(chǎn)數(shù)據(jù)進(jìn)行自學(xué)習(xí)，從而令排程結(jié)果越來越準(zhǔn)確。

然而，有很多企業(yè)的生產(chǎn)數(shù)據(jù)是有時效性的，一定時間以前的生產(chǎn)數(shù)據(jù)表述的知識有可能是不準(zhǔn)確甚至是錯誤的，如何挑選生產(chǎn)數(shù)據(jù)與將結(jié)果規(guī)則集添加權(quán)重從而令得到的規(guī)則集更加準(zhǔn)確是本文未解決的難點(diǎn)，也是下一步研究的重點(diǎn)。