鄢超波 張雷

對(duì)于制造業(yè)來(lái)說(shuō),其產(chǎn)品主要來(lái)自于龐大的生產(chǎn)線系統(tǒng),生產(chǎn)線的效率(吞吐率) 越高,企業(yè)效益往往也就越好.然而生產(chǎn)線中的機(jī)器會(huì)發(fā)生隨機(jī)故障,當(dāng)生產(chǎn)線中某一臺(tái)機(jī)器發(fā)生故障時(shí),如果該機(jī)器沒(méi)有得到及時(shí)的維修,就有可能使得系統(tǒng)吞吐率下降,進(jìn)而導(dǎo)致企業(yè)利潤(rùn)減少.本文假設(shè)一臺(tái)機(jī)器故障時(shí),只能由已分配的某一名維修工人進(jìn)行維修,顯然如果為每臺(tái)機(jī)器都配備一名維修工人,那么所有的機(jī)器故障都會(huì)得到立即維修,企業(yè)的損失也就最小.然而,這樣會(huì)導(dǎo)致維修工人在大多數(shù)時(shí)間都處于空閑狀態(tài),極大地增加了企業(yè)的用人成本.如何在保證串行生產(chǎn)線系統(tǒng)吞吐率的情況下,使用盡可能少的維修工人來(lái)完成機(jī)器的維修任務(wù),本文稱這樣一個(gè)問(wèn)題為串行生產(chǎn)線中機(jī)器維修工人的任務(wù)分配問(wèn)題.

在生產(chǎn)線領(lǐng)域,已經(jīng)存在有大量的資料,文獻(xiàn)中主要通過(guò)排隊(duì)論[1]、分解[2]、仿真和近似[3?4]等方法來(lái)對(duì)生產(chǎn)線進(jìn)行研究.當(dāng)前生產(chǎn)線領(lǐng)域的研究方向主要是生產(chǎn)線的性能分析和優(yōu)化,例如生產(chǎn)線平衡問(wèn)題[5?6]和生產(chǎn)線中緩沖區(qū)大小分配問(wèn)題[7?8]等.然而,盡管在生產(chǎn)線這一領(lǐng)域已經(jīng)有了很多研究工作,但是根據(jù)文獻(xiàn)調(diào)研,目前還沒(méi)有相關(guān)文獻(xiàn)在研究串行生產(chǎn)線中機(jī)器維修工人的任務(wù)分配問(wèn)題.這也就是說(shuō),本文所研究的問(wèn)題是一個(gè)全新的問(wèn)題.對(duì)于這樣一個(gè)新問(wèn)題,有三類問(wèn)題與之具有一定相似性.第一類問(wèn)題是任務(wù)分配問(wèn)題[9],該問(wèn)題要求定義每一個(gè)任務(wù)分配給任意一個(gè)人的“成本”,然而在本文所研究的問(wèn)題中吞吐率是一個(gè)整體的性能指標(biāo),難以定義每一個(gè)機(jī)器的維修任務(wù)分配給任意一個(gè)工人的“成本”,所以不能應(yīng)用分配問(wèn)題的算法來(lái)求解本文的問(wèn)題.第二類問(wèn)題是裝箱問(wèn)題[10?11],該問(wèn)題要求將一定數(shù)量的物品放入容量相同的一些箱子中,使得所用的箱子數(shù)目最少,然而由于無(wú)法定義維修工人的“容量” (單個(gè)工人可以負(fù)責(zé)維修的機(jī)器數(shù)量),所以也不能直接應(yīng)用裝箱問(wèn)題的算法來(lái)求解本文的問(wèn)題.第三類問(wèn)題是并行機(jī)調(diào)度問(wèn)題和文獻(xiàn)[12]中提出的線邊緩沖區(qū)分配問(wèn)題(Line-side buffer assignment problem,LBAP),其中并行機(jī)調(diào)度問(wèn)題要求使用一定數(shù)量的機(jī)器完成一些相互獨(dú)立的任務(wù),使得完成時(shí)間最短,而LBAP 問(wèn)題則是要求在保證總裝線吞吐率的條件下,使用給定數(shù)量的司機(jī)完成物料傳送任務(wù).由于第三類問(wèn)題中的LBAP 問(wèn)題與本文所研究的新問(wèn)題非常類似,因此可以借鑒文獻(xiàn)[12] 中提出的帶回溯的序貫分配算法(Sequential assignment with backtracking,SAB),來(lái)求解本文所研究的問(wèn)題.該算法基于并行機(jī)調(diào)度問(wèn)題[13]中的最長(zhǎng)處理時(shí)間優(yōu)先(Longest processing time,LPT)算法[14?15]和回溯策略,是一種啟發(fā)式算法.

本文的貢獻(xiàn)在于:1) 本文提出了一個(gè)全新的問(wèn)題—串行生產(chǎn)線中機(jī)器維修工人的任務(wù)分配問(wèn)題,并對(duì)其進(jìn)行了建模;2) 合理地定義了機(jī)器的維修工作量,使得本文所研究的問(wèn)題可以類比為并行機(jī)調(diào)度問(wèn)題;3) 通過(guò)仿真實(shí)驗(yàn),驗(yàn)證了文獻(xiàn)[12] 中提出的SAB 算法,對(duì)本文所研究的問(wèn)題同樣適用,該方法在保證系統(tǒng)吞吐率的前提下,能夠有效減少企業(yè)的用人成本.

本文的結(jié)構(gòu)安排如下:第1 節(jié)介紹串行生產(chǎn)線,建立問(wèn)題模型和仿真模型;第2 節(jié)定義和量化機(jī)器以及工人的維修工作量,并對(duì)維修工人數(shù)量的下界進(jìn)行估計(jì);第3 節(jié)描述帶回溯的維修工人任務(wù)分配算法;第4 節(jié)進(jìn)行仿真實(shí)驗(yàn),驗(yàn)證本文方法的有效性;最后對(duì)本文的內(nèi)容和貢獻(xiàn)進(jìn)行總結(jié).

1 系統(tǒng)模型

1.1 串行生產(chǎn)線模型

串行生產(chǎn)線是指:將機(jī)器以串行方式連接起來(lái),并通過(guò)物料儲(chǔ)運(yùn)設(shè)備將工件從第一個(gè)機(jī)器輸送到與它相鄰的下一個(gè)機(jī)器的生產(chǎn)系統(tǒng),如圖1 所示,其中圓圈表示機(jī)器,方框表示物料儲(chǔ)運(yùn)設(shè)備(即緩沖區(qū)).在實(shí)際生產(chǎn)過(guò)程中,機(jī)器總是會(huì)發(fā)生隨機(jī)故障(即機(jī)器不可靠),這些故障造成的影響會(huì)沿著生產(chǎn)線向上游和下游的機(jī)器傳播.例如,當(dāng)圖1 中的機(jī)器m2發(fā)生故障時(shí),其下游的機(jī)器m3不久便會(huì)加工完緩沖區(qū)b2中的所有工件,然后進(jìn)入饑餓狀態(tài),同時(shí)機(jī)器m1則會(huì)在充滿緩沖區(qū)b1后進(jìn)入阻塞狀態(tài).如果此時(shí)機(jī)器m2仍然沒(méi)有被修復(fù),那么饑餓狀態(tài)會(huì)繼續(xù)向下游傳播直至最后一臺(tái)機(jī)器mM.類似的,阻塞狀態(tài)也會(huì)向上游傳播,這種饑餓或堵塞的情況越嚴(yán)重,串行生產(chǎn)線的吞吐率也就越低.

圖1 串行生產(chǎn)線Fig.1 A serial production line

為便于分析串行生產(chǎn)線,本文做出以下假設(shè):

1) 串行生產(chǎn)線的第一臺(tái)機(jī)器不會(huì)由于原料短缺而發(fā)生饑餓,最后一臺(tái)機(jī)器不會(huì)發(fā)生堵塞.

2) 機(jī)器mj加工一個(gè)工件所需的時(shí)間(即加工節(jié)拍) 為τj,j=1,2,···,M,且τj為一個(gè)常數(shù).

3)緩沖區(qū)bj的容量為Cj,j=1,2,···,M ?1,且Cj為非負(fù)整數(shù).

4) 操作相關(guān)故障(Operation-dependent failure,ODF):機(jī)器只有在加工工件時(shí)才會(huì)發(fā)生故障,在阻塞或饑餓時(shí)不會(huì)發(fā)生故障.

5) 加工后阻塞(Blocked after services,BAS):一臺(tái)機(jī)器如果處于工作狀態(tài),只要其上游緩沖區(qū)非空,就從中提取工件進(jìn)行加工;如果加工結(jié)束時(shí),下游緩沖區(qū)已滿,則該機(jī)器被阻塞而暫時(shí)無(wú)法加工下一個(gè)工件,直到下游緩沖區(qū)有可用空間為止.

6) 用連續(xù)概率分布描述機(jī)器的可靠性模型,即用連續(xù)概率分布刻畫機(jī)器的故障間隔時(shí)間和故障維修時(shí)間.如果機(jī)器的可靠性模型用負(fù)指數(shù)分布描述,則稱為指數(shù)可靠性模型;此時(shí),機(jī)器的故障率和維修率可以分別用λ和μ來(lái)表示.

1.2 問(wèn)題模型

圖2 給出了一個(gè)串行生產(chǎn)線中維修工人任務(wù)分配的例子,其中實(shí)線部分表示一個(gè)擁有4 臺(tái)機(jī)器的串行生產(chǎn)線系統(tǒng),虛線部分表示一個(gè)擁有2 名機(jī)器維修工人的維修排隊(duì)系統(tǒng).當(dāng)生產(chǎn)線中的某一臺(tái)機(jī)器發(fā)生故障后,該機(jī)器就會(huì)停止加工,并進(jìn)入到維修排隊(duì)系統(tǒng),維修完成之后,再返回生產(chǎn)線系統(tǒng).在圖2 中,機(jī)器m1和機(jī)器m2的維修任務(wù)分給了維修工人r1,而機(jī)器m3和機(jī)器m4的維修任務(wù)則分給了維修工人r2.顯然,當(dāng)改變維修工人的數(shù)量以及機(jī)器維修任務(wù)的分配方式時(shí),維修效率都可能會(huì)受到影響,從而導(dǎo)致生產(chǎn)線的吞吐率發(fā)生變化.那么如何合理分配機(jī)器的維修任務(wù),使得能夠用盡可能少的維修工人,滿足串行生產(chǎn)線的吞吐率要求,就成為了本文研究的核心內(nèi)容.

圖2 串行生產(chǎn)線中維修工人任務(wù)分配Fig.2 Repairman allocation in a serial production line

設(shè)N為維修工人數(shù)量,TP為串行生產(chǎn)線的吞吐率(系統(tǒng)穩(wěn)態(tài)運(yùn)行時(shí),最后一臺(tái)機(jī)器單位時(shí)間內(nèi)平均產(chǎn)出的工件數(shù)),要在滿足串行生產(chǎn)線吞吐率的條件下,最小化維修工人數(shù)量,則本文所研究的優(yōu)化問(wèn)題模型可表示為:

其中,A為任務(wù)分配方式,TP(A) 表示維修任務(wù)分配方式為A時(shí)系統(tǒng)的吞吐率,TP0表示系統(tǒng)所需滿足的吞吐率,A=(D1,D2,···,DN),Di表示第i個(gè)維修工人所負(fù)責(zé)機(jī)器的集合,D則代表所有機(jī)器的集合.

然而,由于優(yōu)化問(wèn)題P1 中維修工人的數(shù)量是不確定的,很難直接進(jìn)行任務(wù)分配,于是本文考慮將該優(yōu)化問(wèn)題轉(zhuǎn)化為多個(gè)判定問(wèn)題進(jìn)行求解.優(yōu)化問(wèn)題P1 對(duì)應(yīng)的判定問(wèn)題如下:

P2:給定維修工人數(shù)量N,判定是否存在一個(gè)維修任務(wù)分配方式A,使得系統(tǒng)能夠滿足以下約束條件:

求解多個(gè)判定問(wèn)題的過(guò)程也就相當(dāng)于在求解原優(yōu)化問(wèn)題,通過(guò)不斷減小維修工人數(shù)量N的值,最終便可以找到滿足系統(tǒng)吞吐率的最小維修工人數(shù)量.

1.3 串行生產(chǎn)線系統(tǒng)動(dòng)態(tài)仿真模型

在第1.2 節(jié)中,本文已經(jīng)給出了問(wèn)題的優(yōu)化模型以及轉(zhuǎn)化后的判定問(wèn)題模型,然而對(duì)于模型中串行生產(chǎn)線系統(tǒng)的吞吐率還沒(méi)有給出評(píng)估方法.考慮到串行生產(chǎn)線系統(tǒng)所具有的復(fù)雜性和隨機(jī)性,本節(jié)將通過(guò)借鑒文獻(xiàn)[12] 中的方法,建立串行生產(chǎn)線系統(tǒng)動(dòng)態(tài)模型,采用仿真的方法求解系統(tǒng)吞吐率.

在串行生產(chǎn)線中,系統(tǒng)的運(yùn)行主要是機(jī)器對(duì)工件的加工活動(dòng),對(duì)于串行生產(chǎn)線中的第k個(gè)工件來(lái)說(shuō),它在通過(guò)第j臺(tái)機(jī)器時(shí)的三個(gè)主要活動(dòng)時(shí)間點(diǎn)為:

1)(k):第k個(gè)工件從第j臺(tái)機(jī)器的上游緩沖區(qū)離開(kāi),到達(dá)第j臺(tái)機(jī)器的時(shí)間點(diǎn).

2)(k):第k個(gè)工件在第j臺(tái)機(jī)器中加工結(jié)束的時(shí)間點(diǎn).

3)(k):第k個(gè)工件從第j臺(tái)機(jī)器離開(kāi),到達(dá)第k臺(tái)機(jī)器的下游緩沖區(qū)的時(shí)間點(diǎn).

系統(tǒng)的動(dòng)態(tài)過(guò)程可表示如下:

式(8)～(10) 中,j=1,2,···,M,k=1,2,···,K,M為總的機(jī)器數(shù)量,K為總的工件數(shù)量,Cj為第j臺(tái)機(jī)器的下游緩沖區(qū)的容量,(k) 為第k個(gè)工件在第j個(gè)機(jī)器中的加工時(shí)間,(k) 的取值如下所示:

上式中,dj(k) 的值表示第k個(gè)工件在第j臺(tái)機(jī)器上加工時(shí)機(jī)器是否會(huì)發(fā)生故障,當(dāng)dj(k) 為0 時(shí),表示不會(huì)發(fā)生故障,其加工時(shí)間為該機(jī)器的加工節(jié)拍τj;當(dāng)dj(k) 為1 時(shí),表示會(huì)發(fā)生故障,其加工時(shí)間為該機(jī)器的加工節(jié)拍τj加上一個(gè)帶有隨機(jī)性的故障時(shí)間段(k),該故障時(shí)間段等于實(shí)際維修時(shí)間與等待維修時(shí)間的總和.其中,實(shí)際維修時(shí)間可以用滿足一定概率分布的隨機(jī)數(shù)代替,而等待維修時(shí)間則需要在仿真過(guò)程中根據(jù)維修工人實(shí)時(shí)的忙閑情況計(jì)算得到.對(duì)于dj(k) 的值,則可通過(guò)式(12) 進(jìn)行判斷:

仿真時(shí),設(shè)置初始條件如下:

通過(guò)遞推求解式(8)～(10),便可建立串行生產(chǎn)線的系統(tǒng)動(dòng)態(tài)仿真過(guò)程,通過(guò)統(tǒng)計(jì)系統(tǒng)穩(wěn)定生產(chǎn)時(shí)最后一臺(tái)機(jī)器的加工效率,則可得到系統(tǒng)吞吐率.

2 問(wèn)題結(jié)構(gòu)分析

2.1 維修工作量的定義和量化

針對(duì)判定問(wèn)題P2,本節(jié)首先定義和量化機(jī)器的維修工作量,并將該量化指標(biāo)作為求解判定問(wèn)題P2時(shí)的分配依據(jù);然后通過(guò)定義工人的維修工作量,推導(dǎo)出機(jī)器的維修工作量與工人的維修工作量之間的關(guān)系.

在生產(chǎn)系統(tǒng)中,一般用MTBF(Mean time between failure) 來(lái)表示機(jī)器的平均故障間隔,用MTTR(Mean time to repair) 來(lái)表示機(jī)器的平均修復(fù)時(shí)間.那么在系統(tǒng)穩(wěn)定運(yùn)行期間,第j臺(tái)機(jī)器的總維修時(shí)間可以表示如下:

式中,為第j臺(tái)機(jī)器在系統(tǒng)穩(wěn)定運(yùn)行時(shí)間T中故障的次數(shù).而第j臺(tái)機(jī)器在系統(tǒng)穩(wěn)定運(yùn)行期間,實(shí)際加工工件的總時(shí)間可以表示為:

加工的總工件數(shù)K為:

那么,也可以表示為:

聯(lián)立式(16)～(19) 則有:

定義第j臺(tái)機(jī)器的維修工作量為系統(tǒng)每加工一個(gè)工件時(shí),該機(jī)器平均所需要的維修時(shí)間,則有:至此,本文將機(jī)器的維修工作量,量化為了只與機(jī)器自身參數(shù)相關(guān)的一個(gè)指標(biāo),使得各個(gè)機(jī)器的維修工作量可以直接進(jìn)行比較.

對(duì)于維修工人來(lái)說(shuō),第i個(gè)維修工人的總維修時(shí)間為:

定義第i個(gè)維修工人的維修工作量為系統(tǒng)加工每一個(gè)工件時(shí),該工人平均花費(fèi)的維修時(shí)間,則有:

聯(lián)立式(19)～(23),則有:

在判定問(wèn)題P2 中,要求使用給定數(shù)量的維修工人對(duì)多個(gè)機(jī)器進(jìn)行維修,判定是否存在一種任務(wù)分配方式,使得系統(tǒng)能夠滿足吞吐率要求.這就類似于在并行機(jī)調(diào)度問(wèn)題中,要求采用給定數(shù)量的機(jī)器,完成多個(gè)加工任務(wù),判定是否可以找到一種任務(wù)分配方式使得任務(wù)總完成時(shí)間滿足要求.其中,判定問(wèn)題P2 中的“維修工人” 對(duì)應(yīng)于并行機(jī)調(diào)度問(wèn)題中的“機(jī)器”,“機(jī)器維修任務(wù)” 對(duì)應(yīng)于“加工任務(wù)”,而“機(jī)器維修工作量” 則對(duì)應(yīng)于“加工時(shí)間”.在并行機(jī)調(diào)度問(wèn)題中要求任務(wù)的加工時(shí)間滿足可加性,由式(24) 可知,在判定問(wèn)題P2 中機(jī)器維修的任務(wù)量也滿足可加性.考慮到判定問(wèn)題P2 與并行機(jī)調(diào)度問(wèn)題具有很強(qiáng)的相似性,所以本文在求解判定問(wèn)題P2時(shí),將借鑒并行機(jī)調(diào)度問(wèn)題中的經(jīng)典方法,即LPT算法.

2.2 維修工人數(shù)量的下界估計(jì)

針對(duì)判定問(wèn)題P2,當(dāng)給定的維修工人數(shù)量較少時(shí),可能不存在可行的分配方法.由此,本節(jié)將參考文獻(xiàn)[12] 中求解司機(jī)數(shù)量下界的方法,推導(dǎo)出維修工人數(shù)量的下界.在驗(yàn)證分配方式是否可行時(shí),當(dāng)給定的維修工人數(shù)量小于該下界,則不需要進(jìn)行仿真求解,直接判定不可行.

定義第i個(gè)維修工人的利用率Γi為系統(tǒng)穩(wěn)定運(yùn)行時(shí),一個(gè)單位時(shí)間中該工人的平均工作時(shí)間,則有:

結(jié)合式(20)～(22) 以及式(24)～(26),則有:

結(jié)合式(5) 和式(24),則有:

當(dāng)把所有機(jī)器的維修工作量乘以TP0時(shí),則有:

3 帶回溯的維修工人任務(wù)分配算法

由于本文所研究的判定問(wèn)題P2 與文獻(xiàn)[12] 中所研究的LBAP 問(wèn)題是同一類問(wèn)題,所以在求解判定問(wèn)題P2 時(shí),可以借鑒文獻(xiàn)[12] 中提出的SAB 算法.同時(shí),因?yàn)長(zhǎng)BAP 問(wèn)題與并行機(jī)調(diào)度問(wèn)題具有一定相似性,所以SAB 算法結(jié)合了并行機(jī)調(diào)度問(wèn)題的經(jīng)典解法,即LPT 算法(一種貪心算法),并在此基礎(chǔ)上引入了回溯策略,使得該算法能夠快速求得可行解,并且以概率1 收斂.另外,文獻(xiàn)[12] 中還將SAB 算法與遺傳算法進(jìn)行了對(duì)比,證明了在解決LBAP 問(wèn)題時(shí),SAB 算法的優(yōu)越性.在解決本文所研究的問(wèn)題時(shí),采用LPT 算法是因?yàn)榕卸▎?wèn)題P2與并行機(jī)調(diào)度問(wèn)題也具有很強(qiáng)的相似性,這一點(diǎn)在第2.1 節(jié)中已經(jīng)進(jìn)行了說(shuō)明.在并行機(jī)調(diào)度問(wèn)題中要使任務(wù)總完成時(shí)間盡可能減少,則需要使各個(gè)機(jī)器的任務(wù)量盡可能平均.那么同理,在判定問(wèn)題P2中,要提高生產(chǎn)線吞吐率,則需要平衡維修工人的忙閑程度,該步驟通過(guò)LPT 算法即可實(shí)現(xiàn).而引入回溯策略則有兩個(gè)原因:首先,由于串行生產(chǎn)線的吞吐率是由仿真得到的,而仿真是帶有一定誤差的,并不能完全代表真實(shí)值;其次,一般來(lái)說(shuō)維修工人的忙閑程度越平衡,系統(tǒng)吞吐率越高,但是由于串行生產(chǎn)線系統(tǒng)的復(fù)雜性和隨機(jī)性,導(dǎo)致維修工人的忙閑程度最平衡時(shí),并不表示系統(tǒng)吞吐率也一定最高,所以需要回溯來(lái)尋找更優(yōu)的可行解.

參考SAB 算法,本文約定如果在一個(gè)分配方案中,所有的機(jī)器都被分配給了維修工人,則稱這樣的一個(gè)分配為完全分配,否則稱之為部分分配.對(duì)于一個(gè)部分分配A來(lái)說(shuō),如果在此基礎(chǔ)上,再分配一臺(tái)機(jī)器,得到部分分配或者完全分配A′,則稱A為A′的父分配,稱A′為A的子分配.假設(shè)未分配的機(jī)器都不會(huì)發(fā)生故障,那么顯然,當(dāng)一個(gè)部分分配的系統(tǒng)吞吐率小于TP0,該部分分配的子分配也都不滿足吞吐率要求.通過(guò)這一性質(zhì),我們便可以在算法的步驟5) 中,引入回溯策略,確定下一步的搜索方向.

算法的具體步驟如下:

1) 初始化N=Nlean,并設(shè)置一個(gè)小的正數(shù)?,且0

2) 按照LPT 算法的思想進(jìn)行貪心分配,將機(jī)器維修工作量從大到小排序,逐個(gè)將未分配的機(jī)器中最大的機(jī)器,分配給當(dāng)前任務(wù)量最小的維修工人,記當(dāng)前分配方式為A.

3) 仿真得到當(dāng)前分配方式的吞吐率TP(A).如果TP(A)

4) 將N的值減1,按照步驟2) 中貪心分配的方法重新分配任務(wù),并更新當(dāng)前分配方案A,進(jìn)入步驟5).

5) 仿真得到當(dāng)前分配方案A的吞吐率TP(A),若TP(A)

6) 若在步驟5) 中找到可行解,則返回步驟4)尋找更優(yōu)的可行解,否則算法結(jié)束.

算法說(shuō)明:步驟1)～3),通過(guò)簡(jiǎn)單的貪心分配,可迅速獲得一個(gè)可行解,縮小搜索范圍;步驟4)～6)結(jié)合貪心分配和回溯策略,求解優(yōu)化問(wèn)題P1,其實(shí)質(zhì)是對(duì)于多個(gè)判定問(wèn)題P2 的求解.在步驟4)～6)中對(duì)于單個(gè)判定問(wèn)題求解時(shí),本文的算法與文獻(xiàn)[12]中的SAB 算法基本相同,其不同點(diǎn)僅在于本文的算法步驟中,去除了SAB 算法里可行解的可信度這一參數(shù).這是由于本文在求解吞吐率時(shí),仿真時(shí)間設(shè)定較長(zhǎng),吞吐率的精度已經(jīng)可以滿足實(shí)驗(yàn)要求,為了簡(jiǎn)化算法步驟,則去除了該參數(shù).

4 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文方法的有效性,第4.1 節(jié)將對(duì)一條具有8 臺(tái)機(jī)器的串行生產(chǎn)線進(jìn)行仿真實(shí)驗(yàn),并對(duì)仿真結(jié)果進(jìn)行定性分析.第4.2 節(jié)將仿真一條具有50 臺(tái)機(jī)器的串行生產(chǎn)線,其中機(jī)器的參數(shù)帶有一定隨機(jī)性,由此進(jìn)一步來(lái)驗(yàn)證本文方法的可靠性.

4.1 8 臺(tái)機(jī)器串行生產(chǎn)線仿真實(shí)驗(yàn)

本節(jié)采用一條具有8 臺(tái)機(jī)器的串行生產(chǎn)線,設(shè)定所有機(jī)器的可靠性模型為指數(shù)可靠性模型,機(jī)器之間的緩沖區(qū)容量均設(shè)為5 個(gè)工件,機(jī)器的加工節(jié)拍統(tǒng)一設(shè)置為1 (分鐘),?取值為0.15,機(jī)器的其他具體參數(shù)如表1 所示.

表1 機(jī)器參數(shù)Table 1 Machine parameters

對(duì)于這樣一條具有8 臺(tái)機(jī)器的串行生產(chǎn)線,本節(jié)首先對(duì)其分配8 個(gè)維修工人,使得所有的維修任務(wù)都能及時(shí)得到維修,通過(guò)仿真得到系統(tǒng)的最大吞吐率TPmax=0.8868.由于當(dāng)維修工人數(shù)量小于機(jī)器數(shù)量時(shí),其吞吐率必然小于等于為每一臺(tái)機(jī)器都分配一個(gè)維修工人時(shí)生產(chǎn)線系統(tǒng)的吞吐率,所以可以設(shè)定TP0=0.95×TPmax=0.8424,當(dāng)仿真求出的系統(tǒng)吞吐率大于等于TP0時(shí),即認(rèn)為該分配方式滿足系統(tǒng)要求.實(shí)驗(yàn)所得到的系統(tǒng)吞吐率和工人數(shù)量如表2 所示,同時(shí)表3 中給出了具體的維修工人任務(wù)分配方案.

表2 實(shí)驗(yàn)結(jié)果Table 2 Experimental results

表3 維修工人任務(wù)分配Table 3 Repairman task allocation

由表2 可知,當(dāng)回溯次數(shù)為0 時(shí),即就是只采用簡(jiǎn)單的貪心分配進(jìn)行求解時(shí),得出所需的維修工人數(shù)量為5.當(dāng)設(shè)置回溯次數(shù)為10,則得到了只需要4 個(gè)維修工人的分配方案,當(dāng)回溯次數(shù)增加到50 后,找到了維修工人數(shù)量為4 時(shí),吞吐率更大的可行解.實(shí)驗(yàn)結(jié)果表明:對(duì)于機(jī)器參數(shù)給定的小型串行生產(chǎn)線,本文的方法能夠快速地求解出一個(gè)比較好的解,同時(shí)隨著回溯次數(shù)的增加,找到更優(yōu)的可行解的可能性也隨之增加.

4.2 50 臺(tái)機(jī)器串行生產(chǎn)線仿真實(shí)驗(yàn)

在第4.1 節(jié)中,為了方便分析,采用了一條相對(duì)簡(jiǎn)單的具有8 臺(tái)機(jī)器的串行生產(chǎn)線,其中機(jī)器的維修率、故障率以及加工周期都是直接給定的.本節(jié)將采用一條具有50 臺(tái)機(jī)器的串行生產(chǎn)線進(jìn)行仿真實(shí)驗(yàn),仍舊設(shè)定所有機(jī)器的可靠性模型為指數(shù)可靠性模型,機(jī)器之間的緩沖區(qū)容量為5 個(gè)工件,?取值為0.15.但是,機(jī)器參數(shù)的設(shè)置更為隨機(jī),令50 臺(tái)機(jī)器的故障率λ、維修率μ和加工節(jié)拍τ分別為滿足(0,1)、(2,10) 和(0.8,1.2) 的均勻分布.

對(duì)于這樣一條具有50 臺(tái)機(jī)器的串行生產(chǎn)線,首先對(duì)其分配50 個(gè)維修工人,仿真得到TPmax=0.6930,設(shè)定TP0=0.95×TPmax=0.6584,然后按照算法步驟進(jìn)行求解,實(shí)驗(yàn)結(jié)果如表4 所示.

表4 50 臺(tái)機(jī)器實(shí)驗(yàn)結(jié)果Table 4 Experimental results of 50 machines

由表4 可知,當(dāng)只采用貪心分配時(shí),得到所需的工人數(shù)量為17,當(dāng)設(shè)置回溯次數(shù)為100 時(shí),得到了只需要15 個(gè)維修工人的分配方案,節(jié)省了2 個(gè)維修工人.實(shí)驗(yàn)結(jié)果表明:當(dāng)串行生產(chǎn)線的機(jī)器參數(shù)為帶有隨機(jī)性的值時(shí),本文的方法仍然能夠獲得較好的可行解;另外,隨著機(jī)器數(shù)量的增加,解空間的規(guī)模呈爆炸性增長(zhǎng),此時(shí)通過(guò)本文算法中的貪心分配仍可以迅速得到一個(gè)可行解,同時(shí)通過(guò)回溯機(jī)制通常也可以找到更優(yōu)的可行解.

5 結(jié)論

本文研究了串行生產(chǎn)線中機(jī)器維修工人的任務(wù)分配問(wèn)題,給出了一套系統(tǒng)化的解決方案.首先,本文構(gòu)建了所研究問(wèn)題的優(yōu)化模型,并將其轉(zhuǎn)換為多個(gè)判定問(wèn)題進(jìn)行求解,同時(shí)建立了串行生產(chǎn)線的仿真模型來(lái)求解系統(tǒng)吞吐率;然后,合理地定義了機(jī)器的維修工作量,使得判定問(wèn)題可以類比為并行機(jī)調(diào)度問(wèn)題,并估計(jì)了維修工人數(shù)量的下界;最后,采用一種基于LPT 算法和回溯策略的啟發(fā)式算法,對(duì)該問(wèn)題進(jìn)行了求解.實(shí)驗(yàn)結(jié)果表明,本文采用的方法在不同機(jī)器數(shù)量和不同機(jī)器參數(shù)的串行生產(chǎn)線中,都能較好地解決維修工人的任務(wù)分配問(wèn)題,在保證系統(tǒng)吞吐率的前提下,有效地減少了企業(yè)的用人成本.