基于Plant Simulation的作業(yè)調(diào)度仿真研究

□ 汪致賓

(珠海格力電器股份有限公司，廣東 珠海 519000)

1 引言

單品類東西在當(dāng)今世界經(jīng)濟(jì)融合發(fā)展的進(jìn)程中并不能滿足所有消費(fèi)者的需求，各企業(yè)必須針對(duì)不同消費(fèi)者群體制造不同的產(chǎn)品以求生存，但是不同種類的產(chǎn)品各生產(chǎn)制造環(huán)節(jié)具有較大的差異 ；與此同時(shí)，各市場(chǎng)需求風(fēng)云變幻，日常生產(chǎn)制造異常不可控等因素均會(huì)給企業(yè)在車間作業(yè)調(diào)度中帶來(lái)較大的問(wèn)題，而當(dāng)前的車間作業(yè)調(diào)度模式無(wú)法較好地解決各類異常狀況。

2 傳統(tǒng)單線作業(yè)調(diào)度

2.1 PFSP(Permutation Flow Shop Problem,PFSP)問(wèn)題的描述與假設(shè)

2.1.1 問(wèn)題的描述

PFSP問(wèn)題屬于一類經(jīng)典的NP-hard生產(chǎn)作業(yè)調(diào)度問(wèn)題。在實(shí)際生產(chǎn)中同一機(jī)器需連續(xù)對(duì)許多的在制品進(jìn)行加工處理，同時(shí)每個(gè)在制品需要在多臺(tái)機(jī)器上進(jìn)行加工處理，并且如果機(jī)器不同時(shí)各在制品所需的加工處理時(shí)間是不同的，因此確定各在制品在不同機(jī)器上加工處理的先后順序會(huì)對(duì)其最終加工時(shí)間結(jié)果具有較大的影響。根據(jù)并行機(jī)的類別，經(jīng)典的PFSP可以劃分為以下三類：相同并行機(jī)混合流水線[1]；均勻并行機(jī)混合流水線[2]；不相關(guān)并行機(jī)混合流水線[3]?？紤]到實(shí)際生產(chǎn)作業(yè)中的工藝約束和加工作業(yè)環(huán)境，在過(guò)去一段時(shí)間，大量學(xué)者都對(duì)PFSP問(wèn)題進(jìn)行了橫向和縱向的研究，同時(shí)提出了不同的PFSP作業(yè)調(diào)度問(wèn)題和模型。該問(wèn)題具體說(shuō)明如下：

n個(gè)加工任務(wù)(N=J1,J2,…,Jn)，三類產(chǎn)品X、Y、Z需在m臺(tái)機(jī)器(M=M1,M2,…,Mm)上完成加工，每個(gè)加工任務(wù)都包括操作集合J={Oi1,Oi2,Ojm}，加工任務(wù)Jj在第Mi臺(tái)機(jī)器上需要的加工時(shí)間記為Pi,j(i=1,2,…,m;j=1,2,…,n)。PFSP問(wèn)題通過(guò)n/m/P/Cmax來(lái) 表述，也就是n個(gè)加工任務(wù)/m臺(tái)設(shè)備/置換流水線調(diào)度/最大完成時(shí)間。

加工順序π={π1,π2,…，πn}，n個(gè)加工任務(wù)會(huì)依次經(jīng)過(guò)臺(tái)機(jī)器。任務(wù)πj在機(jī)器m上加工完成時(shí)間表示為C(πj,m)。按照加工次序π={π1,π2,…,πn}，PFSP問(wèn)題的加工完成時(shí)間如下所示：

C(π1)=Pπ,1

(1)

C(πj,1)=C(πj-1,1)+Pπ,1,j=2,…;n

(2)

C(π1,i)=C(π1,i-1)+Pπ,j,i=2,…,m

(3)

Cπj,j=max{C(πj-1,1),C(πj,i-1)+Pπ,1,J=2,…，m}

(4)

Makespan定義為：Cmax(π)=C(πn,m)。其中，Makespan指的是最大加工完成時(shí)間。PFSP問(wèn)題的目的是尋求該排列的最優(yōu)解：

π*∶Cmax(π*)≤C(πn,m),?π∈∏。

2.1.2 PFSP問(wèn)題的假設(shè)

為了確保不少于一個(gè)特性指標(biāo)可以得到最優(yōu)解，PFSP問(wèn)題的首要目的即是確定好n個(gè)加工任務(wù)在各臺(tái)機(jī)器上的最佳加工次序。故對(duì)于此問(wèn)題有如下假設(shè)：①所有工件在每臺(tái)機(jī)器設(shè)備上均有指定的加工次序；②單臺(tái)機(jī)器設(shè)備在加工處理工件時(shí)具有時(shí)間上的唯一性；③每個(gè)工件的加工任務(wù)在每臺(tái)機(jī)器設(shè)備上進(jìn)行加工處理時(shí)具有時(shí)間上的唯一性；④各加工工序具有隨機(jī)自主性；⑤每個(gè)工序處理順序和準(zhǔn)備時(shí)間不會(huì)相互影響，同時(shí)準(zhǔn)備時(shí)間屬于加工時(shí)間一部分；⑥所有的加工任務(wù)在該系統(tǒng)中機(jī)器設(shè)備上的加工順序是一致的；⑦每臺(tái)機(jī)器均持續(xù)可用；⑧如某臺(tái)機(jī)器已在加工處理該任務(wù)則在完成前均不能夠停滯亦不能有別的在制品插入進(jìn)行加工處理。

2.2 Palmer啟發(fā)式算法

對(duì)于一般的車間作業(yè)調(diào)度問(wèn)題，可以通過(guò)分支定界法來(lái)保證得到普通問(wèn)題的最優(yōu)解。在現(xiàn)實(shí)生產(chǎn)作業(yè)中若需要對(duì)較大規(guī)模的問(wèn)題進(jìn)行求解時(shí)采用分支定界法以求得到普通問(wèn)題的最優(yōu)解需花費(fèi)大量的時(shí)間來(lái)完成，因而其代價(jià)較大。要想通過(guò)較低的計(jì)算量即可得到較為滿意的結(jié)果，可使用更為實(shí)用的啟發(fā)式方法。Palmer啟發(fā)式算法研究的是按照斜度指標(biāo)給工件完成排序，其公式如下(5)所示：

(5)

上述公式，表示機(jī)器設(shè)備的數(shù)量；tij指工件Ji在所指定機(jī)器設(shè)備Mj上需要的處理時(shí)間。

2.3 建模與仿真

①如圖1建立模型。

圖1 Palmer仿真模型圖

②工件X、Y、Z分別于M1、M2、M3上的所需的加工處理時(shí)間如表1所示。

表1 各工件處理加工明細(xì)表

③各工件生成如公式(6)所示：

λ(t)=0.4+0.3*sin[(i*pi)/15]

(6)

④工件X、Y、Z數(shù)量均為33。

⑤該系統(tǒng)模型參數(shù)完成設(shè)置后，不借助Palmer方法而是直接點(diǎn)擊運(yùn)行EventController，讓其以隨意的加工作業(yè)順序完成各項(xiàng)任務(wù)，以此得到的最大流程時(shí)間如圖2所示為12天21小時(shí)47分鐘52秒。

圖2 正常調(diào)度甘特圖

⑥設(shè)置系統(tǒng)使用Palmer啟發(fā)式算法并對(duì)模型進(jìn)行運(yùn)行，得到如圖3所示的最大流程時(shí)間為12天17小時(shí)40分鐘34秒，與圖2對(duì)比可看出Palmer啟發(fā)式算法降低約4個(gè)小時(shí)。

圖3 Palmer甘特圖

⑦對(duì)M2的失效選項(xiàng)卡參數(shù)進(jìn)行重新設(shè)置，使其失效24小時(shí)。

⑧重新點(diǎn)擊運(yùn)行EventController，得到如圖4所示的最大流程時(shí)間為13天18小時(shí)30分鐘53秒，與圖2-3對(duì)比可見顯著提高約25小時(shí)。

圖4 機(jī)器失效Palmer算法作業(yè)調(diào)度甘特圖

⑨整個(gè)系統(tǒng)在M2失效時(shí)在制品數(shù)變動(dòng)如圖5所示。

圖5 機(jī)器失效Palmer算法在制品變化圖

從上述三種仿真模型結(jié)果可知Palmer啟發(fā)式算法盡管可以減少最大流程時(shí)間，但是若機(jī)器設(shè)備出現(xiàn)故障而同時(shí)有多類加工件需要加工處理時(shí)會(huì)提高該系統(tǒng)的最大流程時(shí)間，延遲該批生產(chǎn)訂單的交付周期，不僅如此，該系統(tǒng)中的在制品數(shù)量亦顯著提高。

3 基于局部信息的自主決策作業(yè)調(diào)度

3.1 問(wèn)題描述

在獲得相關(guān)局部信息的同時(shí)，各智能物流對(duì)象還需根據(jù)該信息完成相關(guān)決策；另一方面，各物流對(duì)象獲得的局部信息中包含著大量的干擾信息，使得各物流對(duì)象所做的每一個(gè)下一步驟具有更高的普適性。在智能調(diào)度中，各在制品工件本身可以自主確定使用某臺(tái)機(jī)器完成加工作業(yè)。而對(duì)于不同類型的在制品工件所需的處理時(shí)間各不相同這一狀況亦需作為參考，本文中具體的各類產(chǎn)品所需加工處理時(shí)間見表2。

本文討論的基于隊(duì)列長(zhǎng)度估計(jì)(Queue Length Estimator,QLE)的自主作業(yè)調(diào)度，其工件或產(chǎn)品計(jì)為X、Y、Z。各類產(chǎn)品在自己產(chǎn)線上所需要的加工時(shí)間是最短的，而如果該產(chǎn)品想要變更產(chǎn)線的話，則其加工處理時(shí)間會(huì)更長(zhǎng)。同時(shí)假定變更產(chǎn)線的決策通過(guò)該工件自身以得到的緩沖區(qū)局部信息來(lái)完成的。所以該產(chǎn)品在考慮是否變更生產(chǎn)線時(shí)會(huì)計(jì)算其它產(chǎn)線的加工處理時(shí)間會(huì)比其自身產(chǎn)線所需加工時(shí)間更長(zhǎng)這一情況。在每一臺(tái)機(jī)器設(shè)備上，該產(chǎn)品自主計(jì)算對(duì)比切換機(jī)器設(shè)備所需處理時(shí)間和它自己設(shè)備所需處理時(shí)間，而后選擇加工完成時(shí)間更少的機(jī)器設(shè)備。如圖6所示。

圖6 流程圖示例

3.2 建模與仿真

①如圖7建立模型。

圖7 QLE仿真模型圖

②如表2所示明確X、Y、Z在M11、M12、M13、M21、M22、M23、M31、M32、M33上所需加工處理時(shí)間，且它們數(shù)量都是99件。

表2 QLE工件加工時(shí)間表

③對(duì)相關(guān)參數(shù)進(jìn)行設(shè)置后，點(diǎn)擊運(yùn)行EventController，如圖8所示得到的最大流程時(shí)間是7天4小時(shí)25分鐘。

圖8 基于QLE作業(yè)調(diào)度甘特圖

④對(duì)M22失效選項(xiàng)卡進(jìn)行重新設(shè)置，讓它失效24小時(shí)。

⑤重新點(diǎn)擊運(yùn)行EventController得到如圖9所示的最大流程時(shí)間為7天11小時(shí)30分鐘，對(duì)比M22未失效時(shí)最大流程時(shí)間提高了約7小時(shí)。

圖9 機(jī)器失效QLE作業(yè)調(diào)度甘特圖

⑥如圖10所示為M22失效狀況下該模型系統(tǒng)中的制品數(shù)量變化情況。

圖10 機(jī)器失效下QLE在制品變化圖

在系統(tǒng)中某臺(tái)機(jī)器出現(xiàn)異常無(wú)法完成加工作業(yè)時(shí)，Palmer算法模型中的在制品數(shù)量快速的增加，而且長(zhǎng)時(shí)間未見減少；QLE可以對(duì)機(jī)器出現(xiàn)異常無(wú)法完成加工作業(yè)的突發(fā)狀況進(jìn)行較快的反應(yīng)，QLE模型中的在制品數(shù)量盡管在一定時(shí)間內(nèi)出現(xiàn)增加，但是在較短時(shí)間內(nèi)就減少到了平均值，整個(gè)模型系統(tǒng)受到較低的影響，對(duì)于機(jī)器異常無(wú)法完成加工作業(yè)的突發(fā)情況具有更好的響應(yīng)。

與Palmer算法的作業(yè)調(diào)度對(duì)比，基于隊(duì)列長(zhǎng)度估計(jì)的多類型產(chǎn)品作業(yè)調(diào)度在機(jī)器能夠正常作業(yè)和某一臺(tái)機(jī)器發(fā)生異常無(wú)法進(jìn)行加工作業(yè)24h這兩類的最大流程時(shí)間下，其均可在很大程度上減少最大流程時(shí)間，機(jī)器異常無(wú)法進(jìn)行加工作業(yè)對(duì)整個(gè)模型系統(tǒng)的正常運(yùn)行具有更低的影響。

4 總結(jié)和展望

4.1 本文的主要結(jié)論

本文以Plant Simulation為工具，獲得下述結(jié)論。

①Palmer算法盡管對(duì)解決PFSP問(wèn)題具有一定程度的效果，然而其效用是有限的，如模型所示若某臺(tái)機(jī)器出現(xiàn)異常無(wú)法作業(yè)時(shí)，Palmer算法更是無(wú)法發(fā)揮效用。

②不論機(jī)器是否出現(xiàn)異常無(wú)法進(jìn)行加工作業(yè)，QLE模型中的作業(yè)調(diào)度方法對(duì)整個(gè)系統(tǒng)在最大作業(yè)時(shí)間方面具有更好的影響，整個(gè)系統(tǒng)具有更強(qiáng)的魯棒性。

4.2 研究展望

總體而言，使用QLE這種基于局部信息的自主作業(yè)調(diào)度方式，各類工件均能夠根據(jù)實(shí)際情況自行調(diào)整，對(duì)于突發(fā)狀況能夠做出較好的反應(yīng)。對(duì)于該方向的深入研究具有一定的促進(jìn)作用。鑒于本文篇幅有限，基于局部信息的自主作業(yè)調(diào)度能夠在工件完成加工的終止時(shí)間、類別優(yōu)先級(jí)等方向上來(lái)做深入的研究，同時(shí)在制品變化量、滯留等待時(shí)間等亦是可作為研究比較的指標(biāo)。另外本文所提到的加工作業(yè)時(shí)間、準(zhǔn)產(chǎn)線間的切換時(shí)間、準(zhǔn)備時(shí)間等同樣可以做深入的研究。