基于Plant Simulation的作業調度仿真研究

□ 汪致賓

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

1 引言

單品類東西在當今世界經濟融合發展的進程中并不能滿足所有消費者的需求，各企業必須針對不同消費者群體制造不同的產品以求生存，但是不同種類的產品各生產制造環節具有較大的差異 ；與此同時，各市場需求風云變幻，日常生產制造異常不可控等因素均會給企業在車間作業調度中帶來較大的問題，而當前的車間作業調度模式無法較好地解決各類異常狀況。

2 傳統單線作業調度

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

2.1.1 問題的描述

PFSP問題屬于一類經典的NP-hard生產作業調度問題。在實際生產中同一機器需連續對許多的在制品進行加工處理，同時每個在制品需要在多臺機器上進行加工處理，并且如果機器不同時各在制品所需的加工處理時間是不同的，因此確定各在制品在不同機器上加工處理的先后順序會對其最終加工時間結果具有較大的影響。根據并行機的類別，經典的PFSP可以劃分為以下三類：相同并行機混合流水線[1]；均勻并行機混合流水線[2]；不相關并行機混合流水線[3]。考慮到實際生產作業中的工藝約束和加工作業環境，在過去一段時間，大量學者都對PFSP問題進行了橫向和縱向的研究，同時提出了不同的PFSP作業調度問題和模型。該問題具體說明如下：

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

加工順序π={π1,π2,…，πn}，n個加工任務會依次經過臺機器。任務πj在機器m上加工完成時間表示為C(πj,m)。按照加工次序π={π1,π2,…,πn}，PFSP問題的加工完成時間如下所示：

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指的是最大加工完成時間。PFSP問題的目的是尋求該排列的最優解：

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

2.1.2 PFSP問題的假設

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

2.2 Palmer啟發式算法

對于一般的車間作業調度問題，可以通過分支定界法來保證得到普通問題的最優解。在現實生產作業中若需要對較大規模的問題進行求解時采用分支定界法以求得到普通問題的最優解需花費大量的時間來完成，因而其代價較大。要想通過較低的計算量即可得到較為滿意的結果，可使用更為實用的啟發式方法。Palmer啟發式算法研究的是按照斜度指標給工件完成排序，其公式如下(5)所示：

(5)

上述公式，表示機器設備的數量；tij指工件Ji在所指定機器設備Mj上需要的處理時間。

2.3 建模與仿真

①如圖1建立模型。

圖1 Palmer仿真模型圖

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

表1 各工件處理加工明細表

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

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

(6)

④工件X、Y、Z數量均為33。

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

圖2 正常調度甘特圖

⑥設置系統使用Palmer啟發式算法并對模型進行運行，得到如圖3所示的最大流程時間為12天17小時40分鐘34秒，與圖2對比可看出Palmer啟發式算法降低約4個小時。

圖3 Palmer甘特圖

⑦對M2的失效選項卡參數進行重新設置，使其失效24小時。

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

圖4 機器失效Palmer算法作業調度甘特圖

⑨整個系統在M2失效時在制品數變動如圖5所示。

圖5 機器失效Palmer算法在制品變化圖

從上述三種仿真模型結果可知Palmer啟發式算法盡管可以減少最大流程時間，但是若機器設備出現故障而同時有多類加工件需要加工處理時會提高該系統的最大流程時間，延遲該批生產訂單的交付周期，不僅如此，該系統中的在制品數量亦顯著提高。

3 基于局部信息的自主決策作業調度

3.1 問題描述

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

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

圖6 流程圖示例

3.2 建模與仿真

①如圖7建立模型。

圖7 QLE仿真模型圖

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

表2 QLE工件加工時間表

③對相關參數進行設置后，點擊運行EventController，如圖8所示得到的最大流程時間是7天4小時25分鐘。

圖8 基于QLE作業調度甘特圖

④對M22失效選項卡進行重新設置，讓它失效24小時。

⑤重新點擊運行EventController得到如圖9所示的最大流程時間為7天11小時30分鐘，對比M22未失效時最大流程時間提高了約7小時。

圖9 機器失效QLE作業調度甘特圖

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

圖10 機器失效下QLE在制品變化圖

在系統中某臺機器出現異常無法完成加工作業時，Palmer算法模型中的在制品數量快速的增加，而且長時間未見減少；QLE可以對機器出現異常無法完成加工作業的突發狀況進行較快的反應，QLE模型中的在制品數量盡管在一定時間內出現增加，但是在較短時間內就減少到了平均值，整個模型系統受到較低的影響，對于機器異常無法完成加工作業的突發情況具有更好的響應。

與Palmer算法的作業調度對比，基于隊列長度估計的多類型產品作業調度在機器能夠正常作業和某一臺機器發生異常無法進行加工作業24h這兩類的最大流程時間下，其均可在很大程度上減少最大流程時間，機器異常無法進行加工作業對整個模型系統的正常運行具有更低的影響。

4 總結和展望

4.1 本文的主要結論

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

①Palmer算法盡管對解決PFSP問題具有一定程度的效果，然而其效用是有限的，如模型所示若某臺機器出現異常無法作業時，Palmer算法更是無法發揮效用。

②不論機器是否出現異常無法進行加工作業，QLE模型中的作業調度方法對整個系統在最大作業時間方面具有更好的影響，整個系統具有更強的魯棒性。

4.2 研究展望

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