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

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

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

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

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

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

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

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

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

1 問(wèn)題描述

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

圖1 單行線型布局的物流運(yùn)動(dòng)方式Fig.1 Logistics movement of Single Straight line layout

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

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

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

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

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

在單行線型布局中常見(jiàn)的物流運(yùn)動(dòng)方式有以下4種：重復(fù)運(yùn)動(dòng)(在一臺(tái)設(shè)備上重復(fù)加工)；順次運(yùn)動(dòng)(按照加工順序依次在設(shè)備上加工)；迂回運(yùn)動(dòng)(跳過(guò)其中一臺(tái)或幾臺(tái)設(shè)備進(jìn)行加工)；返回運(yùn)動(dòng)(先在后面的設(shè)備上加工再在前面的設(shè)備上加工).

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

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

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

2 解決方案

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

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

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

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

FJSP結(jié)果的一個(gè)元組如圖 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}，對(duì)應(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ù)庫(kù)D，如表 1所示.

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

2.2 使用Apriori算法挖掘頻繁項(xiàng)

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

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

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

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

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

圖3 AP算法求解D中頻繁項(xiàng)集過(guò)程Fig.3 Process of AP algorithm in database D

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

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

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

GREEDY_SET_COVER(M,F)

輸入：設(shè)備集M,D中的頻繁項(xiàng)集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)的時(shí)間復(fù)雜度為Ο(|F|min(|M|,|F| ) ).

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

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

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

CACULATE_EDIT_DISTANCE(X,J,M)

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

輸出：設(shè)備序列A和對(duì)應(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

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

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

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

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

(4){M3}, {M4},{M1,M2}，產(chǎn)生的設(shè)備序列為{M3,M4,M1,M2}，每個(gè)工序步驟的編輯距離為{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}，每個(gè)工序步驟的編輯距離為{0,1,2},{0,2},{0,1,3},{0,1}，此設(shè)備序列的編輯距離為10；

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

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

3 測(cè)試結(jié)果

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

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

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

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

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

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

4 結(jié)語(yǔ)

基于數(shù)據(jù)挖掘的制造業(yè)工廠設(shè)備布局方法FMDM，通過(guò)清理柔性工廠工作調(diào)度結(jié)果并生成事物數(shù)據(jù)庫(kù)，使用Apriori算法挖掘事務(wù)數(shù)據(jù)庫(kù)中的頻繁項(xiàng)，根據(jù)頻繁項(xiàng)使用GREEDY_SET_COVER方法生成直線設(shè)備布局方案，利用事務(wù)數(shù)據(jù)庫(kù)調(diào)用CACULATE_EDIT_DISTANCE計(jì)算該方案的編輯距離值，反復(fù)多次選擇最優(yōu)方案.FMDM克服了經(jīng)典的求解單行直線型布局過(guò)程中需要提供各種參數(shù)的問(wèn)題，基于設(shè)備等概率使用的限制，考慮了實(shí)際生產(chǎn)中多工件共享設(shè)備，多工件并發(fā)的情況，實(shí)現(xiàn)車間在建設(shè)或規(guī)劃初期對(duì)設(shè)備進(jìn)行布局.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è)備布局問(wèn)題研究[J]. 武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版), 2011, 33(04): 643-646+655.

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

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

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

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

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

[8] Han Jia-wei, Kamber M. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 范 明, 孟小峰,譯. 北京：機(jī)械工業(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ù)挖掘和計(jì)算機(jī)網(wǎng)絡(luò)，E-mail：songzs@scuec.edu.cn

國(guó)家科技支撐計(jì)劃項(xiàng)目子課題(2015BAD29B01);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(CZY16002)

TP301

A

1672-4321(2017)04-0106-06