宋中山，陳雯穎，孫 翀，帖 軍

(中南民族大學 計算機科學學院，武漢 430074)

一種基于數(shù)據(jù)挖掘的制造業(yè)工廠設(shè)備布局方法

宋中山，陳雯穎，孫 翀，帖 軍

(中南民族大學 計算機科學學院，武漢 430074)

針對經(jīng)典的求解單行直線型布局算法中需要大量參數(shù)、要求設(shè)備等概率使用的限制，提出了一種基于數(shù)據(jù)挖掘的制造業(yè)工廠設(shè)備布局方法FMDM.FMDM采用數(shù)據(jù)挖掘Apriori算法對已有的生產(chǎn)調(diào)度計劃或柔性作業(yè)車間調(diào)度問題的調(diào)度解進行挖掘，根據(jù)貪心方法在頻繁項的基礎(chǔ)上獲得的初步布局方案，給出了將候選方案進行篩選得到最終方案的算法CACULATE_EDIT_DISTANCE.實驗結(jié)果表明：該方法可對無參數(shù)的初建車間進行有效的初步布局，不限制設(shè)備的使用概率，能實現(xiàn)多工件共享設(shè)備，多工件并發(fā)生產(chǎn)，且FMDM結(jié)果作為經(jīng)典算法的輸入可提高經(jīng)典算法的收斂速度.

數(shù)據(jù)挖掘，Apriori算法，貪心算法，直線型布局

設(shè)備布局問題是制造系統(tǒng)常見問題之一，與企業(yè)的生產(chǎn)率和生產(chǎn)成本密切相關(guān).產(chǎn)品從原材料進廠到出廠的整個生產(chǎn)周期中處于加工檢驗的時間僅占整個生產(chǎn)周期的5%～10%，而處于停滯和搬運的時間占90%～95%；從費用來看，總經(jīng)營費用的20%～50%是物料搬運費，這嚴重影響了企業(yè)的生產(chǎn)效率.合理的設(shè)施布局可以使制品過程順暢流通，縮短產(chǎn)品在工位與工位之間的運送時間，使物料搬運費用減少10%～30%，節(jié)約企業(yè)成本，縮短生產(chǎn)周期，使生產(chǎn)消耗最小化，生產(chǎn)效益最大化[1].所以機器設(shè)備布局問題成為制造業(yè)亟待解決的問題.

在遺傳算法被提出后，陸續(xù)出現(xiàn)了蟻群算法、模擬退火算法、禁忌搜索算法等各種算法在設(shè)備布局問題上的研究與應(yīng)用[2-4].文獻[5]根據(jù)車間的設(shè)備布局參數(shù)及物流信息，運用遺傳算法優(yōu)化目標函數(shù)求解布局方案，文獻[6]將原車間作為初始種群，采用遺傳算法進行優(yōu)化設(shè)計，通過選擇、交叉、變異等操作得到更合理的車間布局方案.這些算法雖然可以很好的求解布局最優(yōu)解，但是模型要求提供的參數(shù)卻不易獲得，特別在車間建成初期.本文提出一種基于數(shù)據(jù)挖掘的制造業(yè)工廠設(shè)備布局方法(FMDM，F(xiàn)acility Layout Method for Manufacturing Based on Data Mining)，在已有的生產(chǎn)調(diào)度計劃或柔性作業(yè)車間調(diào)度問題(FJSP)的調(diào)度解上調(diào)用數(shù)據(jù)挖掘算法[7]，不需要各種設(shè)備參數(shù)，幫助工廠對建設(shè)中的車間進行設(shè)備布局規(guī)劃.FMDM克服了經(jīng)典算法基于設(shè)備等概率使用的限制，考慮了實際生產(chǎn)中多工件共享設(shè)備，多工件并發(fā)的情況.另一方面，考慮到經(jīng)典求解算法對初始解的依賴性比較大，如禁忌搜索算法，不合理的初始解不容易找到較優(yōu)的布局，而好的初始解可以極大地提高算法效率.本文將FMDM的結(jié)果作為初始解來運行禁忌搜索算法，可以提高經(jīng)典算法收斂速度.

1 問題描述

在設(shè)備布局問題中，單行設(shè)備布局問題是比較特殊的一種布局形式，其物料傳輸時間短且費用低.單行布局將所有的設(shè)備按照一定的要求安排在一行內(nèi)，滿足產(chǎn)品加工需求，采用搬運物料總距離最短作為衡量該布局模型的優(yōu)化目標.單行直線型布局可描述為n臺設(shè)備{M1,M2, …,Mn}按照一定的方向沿一條直線放置的線性排列，如圖 1所示.

圖1 單行線型布局的物流運動方式Fig.1 Logistics movement of Single Straight line layout

本文在研究中做以下假設(shè)和抽象:

(1)所有設(shè)備由其中心點代表，忽略其具體細節(jié)形狀，忽略其長和寬的長度.

(2)所有設(shè)備擺放時與車間的長度方向平行，代表機器的中心點在一條水平直線上.

(3)設(shè)備之間的物流路徑平行于車間長度方向，且設(shè)備等距離擺放，任意兩個相鄰的機器之間的距離記為單位長度1.

令M={M1,M2, …,Mn}為待布局的設(shè)備集，j={j1,j2, …,jm}為待加工工件集，J={J1,J2, …,Jm}為工件加工工序集合，Ji表示工件ji的加工序列.

在單行線型布局中常見的物流運動方式有以下4種：重復運動(在一臺設(shè)備上重復加工)；順次運動(按照加工順序依次在設(shè)備上加工)；迂回運動(跳過其中一臺或幾臺設(shè)備進行加工)；返回運動(先在后面的設(shè)備上加工再在前面的設(shè)備上加工).

n臺設(shè)備間物流方向上的編輯距離矩陣D為：

d指工件按加工工序產(chǎn)生的編輯距離，其中PQ是指工件加工過程中所經(jīng)過的設(shè)備組.

本文的研究目標可概括為：找到在加工過程中，工件物流運動成本最低的設(shè)備布局序列.FMDM根據(jù)工件加工工序計算候選設(shè)備序列的編輯距離d，使用此編輯距離作為該設(shè)備布局序列對應(yīng)的搬運物料總距離，算法的目標函數(shù)即轉(zhuǎn)換為找到使得d最短的設(shè)備序列，編輯距離越小設(shè)備序列越合理.

2 解決方案

FMDM算法利用FJSP的調(diào)度結(jié)果或已有的生產(chǎn)調(diào)度計劃，通過數(shù)據(jù)挖掘Apriori算法產(chǎn)生設(shè)備布局序列，對初建車間或計劃中的車間進行設(shè)備布局規(guī)劃[8].FMDM的主要步驟包括以下內(nèi)容：(1)清理柔性工廠工作調(diào)度數(shù)據(jù)并生成事務(wù)數(shù)據(jù)庫；(2)使用Apriori算法挖掘事務(wù)數(shù)據(jù)庫中的頻繁項；(3)調(diào)用GREEDY_SET_COVER生成初步候選布局方案，調(diào)用CACULATE_EDIT_DISTANCE算法選擇最終直線設(shè)備布局方案.

2.1 清理數(shù)據(jù)并生成事務(wù)數(shù)據(jù)庫

算法的數(shù)據(jù)對象是FJSP調(diào)度結(jié)果集或已有的生產(chǎn)調(diào)度計劃，首先對生產(chǎn)調(diào)度結(jié)果進行清理，將無效的和不完整的數(shù)據(jù)刪除，保證后續(xù)算法的準確性.

將生產(chǎn)調(diào)度結(jié)果作為一個事務(wù)數(shù)據(jù)庫，每條柔性作業(yè)調(diào)度結(jié)果或生產(chǎn)調(diào)度計劃元組轉(zhuǎn)換為事務(wù)數(shù)據(jù)表中的若干元組.轉(zhuǎn)換方法如下.首先讀取一條調(diào)度結(jié)果或生產(chǎn)調(diào)度計劃，獲得當前調(diào)度結(jié)果集中的工件集合及對應(yīng)的工序碼和設(shè)備碼.然后取出當前工序集合中的一個工序，重復下列動作直至當前工序集為空：為此工序新建一個事務(wù)元組并分配一個唯一的事務(wù)ID號，接著根據(jù)此工序和調(diào)度結(jié)果集中的設(shè)備碼獲取當前工件的設(shè)備序列項集，并將該序列項集寫入事務(wù)項屬性.當所有的調(diào)度結(jié)果都按上述過程處理完畢后，輸出事務(wù)數(shù)據(jù)庫.經(jīng)過上述處理后事務(wù)數(shù)據(jù)表最終為二維表，包含事務(wù)ID屬性和事務(wù)項屬性.

FJSP結(jié)果的一個元組如圖 2所示.

圖2 柔性作業(yè)調(diào)度元組Fig.2 Tuples of flexible job-shop scheduling

在圖2中，基于設(shè)備編碼的基因串顯示設(shè)備集為M={M1,M2,M3,M4}，待加工工件集j={j1,j2,j3,j4}，對應(yīng)的工件加工工序集為J={J1,J2,J3,J4}，其中J1=M1,M2,M3，J2=M4,M4,M1，J3=M3,M4,M2，J4=M2,M1,M2.根據(jù)上述步驟生成事物數(shù)據(jù)庫D，如表 1所示.

表1 事務(wù)數(shù)據(jù)庫D

2.2 使用Apriori算法挖掘頻繁項

對2.1中產(chǎn)生的事務(wù)數(shù)據(jù)庫調(diào)用Apriori算法，挖掘事務(wù)數(shù)據(jù)庫中的頻繁項[8]，Apriori算法對以工件為ID，以加工設(shè)備序列為事務(wù)項的事務(wù)數(shù)據(jù)庫進行頻繁項挖掘，其結(jié)果包含了加工設(shè)備之間的關(guān)聯(lián)，而這些關(guān)聯(lián)以工件的加工序列為依據(jù)，以此建立加工序列和設(shè)備布局之間的聯(lián)系.此步驟利用已有的知識和經(jīng)驗對設(shè)備布局的求解過程進行優(yōu)化和簡化，充分考慮了工件加工順序?qū)υO(shè)備布局的影響，由此得出的設(shè)備布局方案也將有利于工件的加工過程.計算過程如下.

步驟1：順序掃描事務(wù)數(shù)據(jù)庫，根據(jù)最小支持度獲得頻繁一項集.

步驟2：產(chǎn)生k+1項集.將前k-1項相同的k項集兩兩連接生產(chǎn)候選的k+1項集，生成完所有的候選項后，以頻繁k+1項集的任意規(guī)模為k的子集必須在頻繁k項集中為剪枝原則進行剪枝.順序掃描事務(wù)數(shù)據(jù)庫，檢查k+1項候選集中的每個候選項，刪除支持度小于最小支持度的候選項.

步驟3：重復步驟2直至不再產(chǎn)生新的頻繁項集.

令最小支持度為2，表1中事務(wù)數(shù)據(jù)庫D，如圖 3所示，產(chǎn)生的頻繁一項集有{{M1},{M2},{M3},{M4}}，頻繁2項集有{{M1,M2}, {M2,M3} }.

圖3 AP算法求解D中頻繁項集過程Fig.3 Process of AP algorithm in database D

2.3 根據(jù)頻繁項生成直線設(shè)備布局方案

由于在上一步產(chǎn)生的頻繁項集中并不一定存在某個頻繁項是等于設(shè)備集的，因此需要在頻繁項集合中找到能覆蓋設(shè)備集的最小頻繁項集合.FMDM算法在此步中運用集合覆蓋的貪心算法對頻繁項集進行選擇，調(diào)用GREEDY_SET_COVER(M,F)形成初步候選布局方案.此步驟的目標是找到能覆蓋所有設(shè)備的頻繁項集，且被選頻繁項集的個數(shù)盡量小.貪心策略為：每次選擇能覆蓋最多尚未被覆蓋設(shè)備元素的頻繁項集.

示例如下，在上一步產(chǎn)生的頻繁項集F={{M1},{M2},{M3},{M4},{M1,M2},{M2,M3}}中進行選擇，調(diào)用GREEDY_SET_COVER(M,F)找到最小規(guī)模的子集X?F可以覆蓋集合M.

GREEDY_SET_COVER(M,F)

輸入：設(shè)備集M,D中的頻繁項集F

輸出：F的子集X

1.U=M

2.X=?

3.whileU≠?

4.select anQ∈Fthat maximizes |Q∩U|

5.U=U-Q

6.X=X∪{Q}

7.End while

8.ReturnX

算法GREEDY_SET_COVER(M,F)的時間復雜度為Ο(|F|min(|M|,|F| ) ).

按照GREEDY_SET_COVER(M,F)算法的描述，圖 2所示調(diào)度結(jié)果集在其頻繁項集F中找到的覆蓋集合設(shè)備集M的子集X為{{M1,M2}, {M3}, {M4}}.X即為初步的候選布局方案.

在初步候選方案X中的設(shè)備仍是無序的，下面對X中每個頻繁項內(nèi)的設(shè)備以及X中各頻繁項之間進行排序，以此確定每個設(shè)備的位置形成最終的布局方案.首先調(diào)整頻繁項內(nèi)設(shè)備順序，調(diào)整方案為將每個頻繁項內(nèi)的設(shè)備序列按其在事務(wù)數(shù)據(jù)庫中出現(xiàn)頻度非降序排序.例如，X中的頻繁項{M1,M2}，由于M1與M2的出現(xiàn)頻度相同，可隨機排列，在此例中取{M1,M2}這一順序.X中剩余兩個頻繁項均為一項集，無需調(diào)整.

下一步調(diào)整布局方案X中各頻繁項之間的順序.根據(jù)X中的頻繁項集，隨機產(chǎn)生一個頻繁項集序列，并利用事務(wù)數(shù)據(jù)庫計算該序列的編輯距離值，具體方法如下.

CACULATE_EDIT_DISTANCE(X,J,M)

輸入：集合X，工件加工工序集J，設(shè)備集M

輸出：設(shè)備序列A和對應(yīng)工件加工工序集J的編輯距離s

1.t=X.length

2.m=J.length，n=M.length

3.letA[1..n] be an new array

4.fori=1 tot

5.swapX[i] withX[RANDOM(i,t)]

6.End for

7.put the index of frequent items ofXinA

8.returnA

9.letD[1:n][1:n] be an new matrix

10.fori=1 ton

11.forj=1 ton

12.D[A[i]][A[j]]=|j-i|

13.End for

14.End for

15.letS=[1..m] be an new array

16.fori=1 tom

17.S[i]=0

18.If |Ji|=1 then

19.S[i]=0

20.End if

21.Else if |Ji|>1 then

22.fork=1 to |Ji|-1

23.S[i]=S[i]+C[Ji,k][Ji,k+1 ]

24.End for

25.End if

26.End for

27.s=0

28.forj=1 tom

29.s=s+S[i]

30.End for

31.returns

反復多次調(diào)用CACULATE_EDIT_DISTANCE(X,J,M)，選擇編輯距離s最小的輸出數(shù)組A即為所得.

m為待加工工序數(shù)，n為待布局的設(shè)備數(shù)量，CACULATE_EDIT_DISTANCE(X,J,M)整體的時間復雜度為Ο(max(m,n)×n).

下面舉例說明如何調(diào)整頻繁項集之間的布局順序.調(diào)用CACULATE_EDIT_DISTANCE算法，調(diào)整布局方案X中包含的3個頻繁項集之間的順序，產(chǎn)生隨機序列，以及根據(jù)加工工序計算這些隨機序列的編輯距離值.

(1){M1,M2},{M3},{M4} ，產(chǎn)生的設(shè)備序列為{M1,M2,M3,M〗4}，每個工序步驟的編輯距離為{0,1,1},{0,3},{0,1,2},{0,1}，此設(shè)備序列的編輯距離為9；

(2){M1,M2}, {M4},{M3}，產(chǎn)生的設(shè)備序列為{M1,M2,M4,M〗3}，每個工序步驟的編輯距離為{0,1,2},{0,2},{0,1,1},{0,1}，此設(shè)備序列的編輯距離為8；

(3){M3},{M1,M2},{M4}，產(chǎn)生的設(shè)備序列為{M3,M1,M2,M〗4}，每個工序步驟的編輯距離為{0,1,2},{0,2},{0,3,1},{0,1}，此設(shè)備序列的編輯距離為10；

(4){M3}, {M4},{M1,M2}，產(chǎn)生的設(shè)備序列為{M3,M4,M1,M2}，每個工序步驟的編輯距離為{0,1,3},{0,1},{0,1,2},{0,1}，此設(shè)備序列的編輯距離為9；

(5){M4},{M3},{M1,M2}，產(chǎn)生的設(shè)備序列為{M4,M3,M1,M〗2}，每個工序步驟的編輯距離為{0,1,2},{0,2},{0,1,3},{0,1}，此設(shè)備序列的編輯距離為10；

(6){M4},{M1,M2},{M3}，產(chǎn)生的設(shè)備序列為{M4,M1,M2,M3}，每個工序步驟的編輯距離為{0,1,1},{0,1},{0,3,2},{0,1}，此設(shè)備序列的編輯距離為9.

通過比較每個設(shè)備序列的編輯距離，距離最小的是方案2)為8，即最優(yōu)的設(shè)備序列為{M1,M2,M4,M3}.

3 測試結(jié)果

算法FMDM對求解過程中涉及的參數(shù)要求較低，而大部分的設(shè)備布局問題求解算法都對設(shè)備參數(shù)和過程中的物流參數(shù)要求極高，這是FMDM明顯優(yōu)于其他算法的地方，上述實例說明了FMDM的可行性.更重要的是，F(xiàn)MDM算法的結(jié)果可以作為經(jīng)典算法的初始解起到提高算法收斂速度，減少計算時間的作用.以下實驗將以FMDM的結(jié)果作為初始解來進行禁忌搜索算法，與經(jīng)典算法進行比較.

利用Python編寫相關(guān)程序，設(shè)最小支持度分別為2,3,3,3,4,4,4,4，使用來自單行設(shè)備布局研究算例庫的算例，在Intel(R) Core(TM) i5-2400 CPU3.10GHZ，內(nèi)存8G的PC上進行測試，F(xiàn)MDM作為禁忌搜索初始解與其他經(jīng)典算法進行比較，結(jié)果如表 2和圖 4所示.從圖 5和圖 6中可看出當設(shè)備的規(guī)模為中小型時，F(xiàn)MDM作為禁忌搜索初始解的算法比其他算法的收斂速度明顯提高，縮短了計算時間.

表2 算例求解對比結(jié)果Tab.2 Comparision result of different algorithms

圖4 算例求解對比結(jié)果Fig.4 Comparision result of different algorithms

圖5 FMDM+禁忌搜索與MIPS對比結(jié)果Fig.5 Comparision result of FMDM+Tabu search and MIPS

圖 6 FMDM+禁忌搜索與Amaral對比結(jié)果Fig.6 Comparision result of FMDM+Tabu search and Amaral

4 結(jié)語

基于數(shù)據(jù)挖掘的制造業(yè)工廠設(shè)備布局方法FMDM，通過清理柔性工廠工作調(diào)度結(jié)果并生成事物數(shù)據(jù)庫，使用Apriori算法挖掘事務(wù)數(shù)據(jù)庫中的頻繁項，根據(jù)頻繁項使用GREEDY_SET_COVER方法生成直線設(shè)備布局方案，利用事務(wù)數(shù)據(jù)庫調(diào)用CACULATE_EDIT_DISTANCE計算該方案的編輯距離值，反復多次選擇最優(yōu)方案.FMDM克服了經(jīng)典的求解單行直線型布局過程中需要提供各種參數(shù)的問題，基于設(shè)備等概率使用的限制，考慮了實際生產(chǎn)中多工件共享設(shè)備，多工件并發(fā)的情況，實現(xiàn)車間在建設(shè)或規(guī)劃初期對設(shè)備進行布局.FMDM算法結(jié)果作為經(jīng)典算法如禁忌搜索算法的初始解可提高算法的收斂速度.

[1] Marcello Braglia, Simone Zanoni, Lucio Zavanella. Layout design in dynamic environments: Strategies and quantitative indices[J]. International Journal of Production Research, 2003, 41(5):995-1016.

[2] 梁勤歐, 周曉艷. 基于免疫遺傳算法的設(shè)備布局問題研究[J]. 武漢理工大學學報(信息與管理工程版), 2011, 33(04): 643-646+655.

[3] 左興權(quán), 王春露, 趙新超. 一種結(jié)合多目標免疫算法和線性規(guī)劃的雙行設(shè)備布局方法[J].自動化學報, 2015, 41(3): 528-540.

[4] 鄭永前, 項德海. 基于單向環(huán)形方式的制造單元布局方法[J]. 計算機集成制造系統(tǒng), 2013, 19(06): 1224-1231.

[5] 邱勝海, 陳曙鼎, 王云霞,等.遺傳算法在車間設(shè)施布局優(yōu)化中的應(yīng)用[J]. 機械設(shè)計與制造工程, 2017, 46(2):80-83.

[6] 楊國俊, 陳 健, 孫思蒙, 等. 基于遺傳算法的車間布局優(yōu)化研究[J]. 機械研究與應(yīng)用, 2016, 29(1):12-14.

[7] 劉 瓊,張超勇,饒運清, 等. 改進遺傳算法解決柔性作業(yè)車間調(diào)度問題[J]. 工業(yè)工程與管理, 2009,14(2):59-66.

[8] Han Jia-wei, Kamber M. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 范 明, 孟小峰,譯. 北京：機械工業(yè)出版社, 2001: 158-166.

[9] LOVE R F, WONG J Y. On solving a one-dimensional space allocation problem with integer programming[J]. Information Processing and Operations Research (INFOR), 1976, 14(2): 139-143.

[10] AMARAL R S. On the exact solution of a facility layout problem[J]. European Journal of Operational Research, 2006, 173(2):508-518.

[11] AMARAL R S. An exact approach to the one-dimensional facility layout problem[J]. Operations Research, 2008,56(4):1026-1033.

FacilityLayoutMethodforManufacturingBasedonDataMining

SongZhongshan,ChenWenying,SunChong,TieJun

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074,China)

The algorithm for the design of a straight-line layout has been widely employed to solve facility layout problems. However, this algorithm requires sufficient parameters and demands equal probability of machines being used. This paper accordingly proposes an approach based on data mining to manufacturing facility layout, named as FMDM.FMDM firstly adopts the Apriori Algorithm for mining the existing production scheduling plan. Then a greedy algorithm is applied to the frequent item set, resulting in layout plans. Lastly, an algorithm is provided to select the best plan from these layout options. Experimental evidence shows that FMDM can be applied to a newly-built workshop′s facility layout planning without parameters and regardless of the probability of machines′ use. This approach helps to achieve multiple jobs on the shared device and concurrent production. In addition, the rate of convergence can be increased through inputting the result of FMDM to traditional algorithms.

data mining，Apriori algorithm，greedy algorithm，single straight line layout

2017-09-15

宋中山(1963-)，男，副教授，研究方向：數(shù)據(jù)挖掘和計算機網(wǎng)絡(luò)，E-mail：songzs@scuec.edu.cn

國家科技支撐計劃項目子課題(2015BAD29B01);中央高校基本科研業(yè)務(wù)費專項資金資助項目(CZY16002)

TP301

A

1672-4321(2017)04-0106-06