基于時(shí)間Petri網(wǎng)的自動(dòng)制造系統(tǒng)排產(chǎn)優(yōu)化方法

王藝翔,洪 良,田海霖,王曉華

(西安工程大學(xué) 電子信息學(xué)院,陜西 西安 710048)

0 引 言

由于自動(dòng)制造系統(tǒng)[1]中存在事件沖突性與并發(fā)性等特點(diǎn),當(dāng)前的算法和模型已無(wú)法滿足自動(dòng)制造系統(tǒng)的生產(chǎn)要求,因此,對(duì)排產(chǎn)的優(yōu)化顯得尤為重要.近年來(lái)對(duì)排產(chǎn)問題的研究,已經(jīng)取得了許多成果.Johnson在20世紀(jì)五十年代提出解決車間調(diào)度部分特殊問題的優(yōu)化算法[2],開啟了對(duì)調(diào)度問題的研究；Roslof提出了一種基于整數(shù)線性規(guī)劃的算法[3],但用該算法求解生產(chǎn)調(diào)度問題時(shí),隨著對(duì)象的增多和時(shí)間的推移會(huì)產(chǎn)生狀態(tài)空間爆炸的問題；文獻(xiàn)[4]將人工智能算法運(yùn)用到排程問題之中,提高了生產(chǎn)效率,但不能保證收斂到最優(yōu)解；文獻(xiàn)[5-7]對(duì)遺傳算法做了比較全面的總結(jié),遺傳算法可以對(duì)生產(chǎn)線上的個(gè)別工序進(jìn)行優(yōu)化,但局限于無(wú)法滿足多任務(wù)生產(chǎn)的情況.Petri網(wǎng)[8-10]在處理離散事件系統(tǒng)問題不僅可以描述系統(tǒng)的靜態(tài)行為,也可以描述系統(tǒng)的動(dòng)態(tài)行為[11],簡(jiǎn)單準(zhǔn)確地表示系統(tǒng)中的并發(fā)、資源共享、沖突、相互抑制以及非確定性等特征,圖像界面直觀清晰，這些特點(diǎn)都十分有利于自動(dòng)制造系統(tǒng)的建模. 文獻(xiàn)[12]應(yīng)用Petri網(wǎng)理論解決了傳統(tǒng)方法由于狀態(tài)空間爆炸造成的尋優(yōu)計(jì)算難題. 目前,Petri網(wǎng)理論已經(jīng)在大規(guī)模車間生產(chǎn)調(diào)度問題[13-16]中得到廣泛應(yīng)用,文獻(xiàn)[17-19]討論了利用時(shí)間Petri網(wǎng)對(duì)系統(tǒng)的建模和分析,給出了自動(dòng)制造系統(tǒng)生產(chǎn)過(guò)程的調(diào)度算法,但缺少對(duì)多條線路自動(dòng)制造系統(tǒng)的分析和優(yōu)化.

本文采用時(shí)間Petri網(wǎng)[20]建立系統(tǒng)模型,針對(duì)多線路自動(dòng)制造系統(tǒng),使用了減少緩沖器資源的策略,在添加控制器的基礎(chǔ)上引入時(shí)間函數(shù),解決沖突所帶來(lái)的設(shè)備等待時(shí)間過(guò)長(zhǎng)的問題,在節(jié)省緩沖器資源的同時(shí),提高系統(tǒng)的生產(chǎn)效率.

圖 1 一個(gè)基本的時(shí)間Petri網(wǎng)單元Fig.1 A basic unit of time Petri net

1 時(shí)間Petri網(wǎng)

Petri網(wǎng)(PN)是一個(gè)五元組,可表示為N=(P,T,F,W,M0),其中:P代表庫(kù)所的集合,庫(kù)所P用圓表示;庫(kù)所中包含的若干黑點(diǎn),稱為托肯(token);T代表變遷的集合,變遷t∈T用方框表示;F? (P×T) ∪ (T×P),稱為流關(guān)系或者有向弧的集合;W:(P×T) ∪ (T×P) →N,是一個(gè)映射,稱為Petri網(wǎng)N的權(quán)函數(shù),不進(jìn)行特殊標(biāo)注時(shí),默認(rèn)權(quán)函數(shù)為1;M0:P→N,是一個(gè)列向量,稱為Petri網(wǎng)N的初始標(biāo)識(shí),表示初始狀態(tài)下各庫(kù)所中的托肯數(shù). 一般用·p表示庫(kù)所p的輸入變遷集合,p·表示庫(kù)所p的輸出變遷集合,用·t表示變遷t的輸入庫(kù)所集合,t·表示的輸出庫(kù)所集合.PN的運(yùn)行規(guī)則是:變遷t在標(biāo)識(shí)M下是使能的,當(dāng)且僅當(dāng)?p∈·t:m(p)≥i(p,t). 變遷t的激發(fā)將從·t中轉(zhuǎn)移定量的托肯到t·中去,從而使Petri網(wǎng)的標(biāo)識(shí)發(fā)生變化.

自動(dòng)制造系統(tǒng)的工序通常和時(shí)間有關(guān),在基本網(wǎng)中加入時(shí)間元素來(lái)表示時(shí)間信息,構(gòu)成時(shí)間Petri網(wǎng)(TPN，timed petri nets).TPN分為3種,分別是給庫(kù)所中的托肯賦以持續(xù)時(shí)間、給變遷賦以延時(shí)時(shí)間、給有向弧賦以時(shí)間權(quán),本文采用第一種,庫(kù)所時(shí)間Petri網(wǎng)(TPPN,timed place petri nets).TPPN是一個(gè)六元組,TPPN=(P,T,F,W,M0,D),其中P,T,F,W,M0的定義與基本網(wǎng)定義相同,D={d1,d2,d3,…,dn},表示庫(kù)所中托肯的延遲時(shí)間.

2 問題描述

圖1是一個(gè)簡(jiǎn)單的自動(dòng)制造系統(tǒng),該系統(tǒng)表示兩條生產(chǎn)線同時(shí)開始工作,生產(chǎn)完成的部件由一個(gè)機(jī)械臂或小車來(lái)運(yùn)輸,用p1表示,兩條生產(chǎn)線屬于競(jìng)爭(zhēng)關(guān)系,隨時(shí)有可能產(chǎn)生沖突,造成系統(tǒng)死鎖．在加入控制器pc后,兩條生產(chǎn)線在緩沖器p1處的沖突問題得到解決,各庫(kù)所的延遲時(shí)間如表1所示.

一般情況下,為平衡兩條線路的生產(chǎn)任務(wù),緩沖器對(duì)于生產(chǎn)線上已生產(chǎn)完成的工件是依次輪流接收,

表 1 網(wǎng)模型中各庫(kù)所在系統(tǒng)中的含義

因此造成大量的等待時(shí)間,造成浪費(fèi)，如圖2所示，其中，縱坐標(biāo)“1”代表處于工作狀態(tài)，“0”代表處于空閑狀態(tài).由圖2可知，兩條線路均有大量的時(shí)間處于空閑狀態(tài).但是,對(duì)緩沖器進(jìn)行時(shí)間規(guī)劃后,生產(chǎn)效率大幅提升.這種優(yōu)化方式需要準(zhǔn)確預(yù)測(cè)上一組任務(wù)的完成時(shí)間,在本例中,首先計(jì)算緩沖器何時(shí)為空.已知兩條生產(chǎn)線路同時(shí)使用一個(gè)機(jī)器人作為緩沖器,通過(guò)計(jì)算時(shí)間,給生產(chǎn)線路和緩沖器賦予時(shí)間函數(shù),在固定時(shí)刻開始某一工件的生產(chǎn),緩沖器在特定的時(shí)刻與特定的生產(chǎn)線對(duì)接,如圖3所示,生產(chǎn)率成倍增長(zhǎng)甚至生產(chǎn)線2達(dá)到了100%.

圖 2 生產(chǎn)線1和生產(chǎn)線2的一般工作狀態(tài) 圖 3 添加任務(wù)時(shí)間后的工作狀態(tài) Fig.2 The work duration of line 1 and line 2 Fig.3 Work duration of line 1 and line 2 by adding task completion time

在實(shí)際生產(chǎn)中,系統(tǒng)要比上例中的單元復(fù)雜.以3個(gè)機(jī)床和2個(gè)移動(dòng)機(jī)器人的自動(dòng)制造系統(tǒng)為例. 3個(gè)機(jī)床M1,M2,M3負(fù)責(zé)加工工件,R1,R2表示2個(gè)移動(dòng)機(jī)器人把加工完成的工件運(yùn)輸?shù)较乱画h(huán)節(jié). 機(jī)床和移動(dòng)機(jī)器人的工作時(shí)間如表2所示,由于機(jī)床生產(chǎn)單個(gè)工件時(shí)間長(zhǎng)而機(jī)器人的運(yùn)輸時(shí)間較短,為了節(jié)省成本,不再使用移動(dòng)機(jī)器人與機(jī)床分別對(duì)接的形式.需要解決以下問題:

(1) 避免沖突時(shí)間發(fā)生,在系統(tǒng)中添加控制器；

(2) 提高該系統(tǒng)的生產(chǎn)效率,減少資源浪費(fèi).

表 2 工件經(jīng)過(guò)每個(gè)工序所需要的時(shí)間

圖 4 添加控制器后的Petri網(wǎng)模型Fig.4 The Petri net model of adding control place

添加控制器后的系統(tǒng)模型如圖4所示,經(jīng)過(guò)3個(gè)機(jī)床生產(chǎn)完成后的工件可以由機(jī)器人R1,R2中任意一個(gè)運(yùn)輸,以機(jī)床1為例,庫(kù)所p2中的托肯通過(guò)t2,t3轉(zhuǎn)移到p8或p10,同時(shí)在p1中產(chǎn)生新的托肯,代表機(jī)床1可以繼續(xù)加工工件. 網(wǎng)模型的初始狀態(tài)如圖所示,M0=(1,0,1,0,1,0,1,0,1,0,2)T.p8或者p10中的托肯經(jīng)過(guò)變遷t10或者t11同時(shí)在控制器中產(chǎn)生托肯,控制器中的最大托肯數(shù)為2,達(dá)到控制整個(gè)系統(tǒng)的目的. 通過(guò)控制器的協(xié)調(diào),系統(tǒng)可以有序的進(jìn)行工作,但通常情況下生產(chǎn)效率不夠高,出現(xiàn)了資源浪費(fèi)的情況. 因此,本文針對(duì)這種情況,給出了有效的算法.

3 算 法

在模型添加控制器后,生產(chǎn)過(guò)程中的某個(gè)工件進(jìn)入機(jī)床開始生產(chǎn)通常是在上一個(gè)工件已經(jīng)被機(jī)器人釋放之后. 實(shí)際上,當(dāng)機(jī)床將加工完成的工件送達(dá)機(jī)器人后,已經(jīng)可以開始繼續(xù)生產(chǎn)下一個(gè)工件. 利用這一思想,與兩個(gè)機(jī)器人工作時(shí)間相對(duì)較短的特點(diǎn)相結(jié)合,達(dá)到提高生產(chǎn)率的目的. 主要步驟如下:

(1) 找到所有的基本回路,該回路從控制器開始并最終回到控制器;

(2) 省略控制器的輸入弧,添加時(shí)間庫(kù)所;

(3) 計(jì)算控制器中控制機(jī)床和移動(dòng)機(jī)器人開始工作的具體時(shí)刻.

3.1 網(wǎng)模型基本回路判定算法

網(wǎng)模型中存在從某一節(jié)點(diǎn)出發(fā)最終回到該節(jié)點(diǎn),并且所有節(jié)點(diǎn)只出現(xiàn)一次的回路,稱回路上所有節(jié)點(diǎn)構(gòu)成的向量為有向回路,用si表示,有向回路構(gòu)成的集合Sc={si|i∈(0,j)}. 定義變遷集合Tc={tcm|tcm∈pc·,m∈(0,n)},pc表示控制器. 定義基本回路為所有包含tcm和pc的回路,用Se表示. 有向回路可能是多個(gè)基本回路的疊加,系統(tǒng)里面可能存在無(wú)數(shù)個(gè)有向回路,因此,需要從有向回路中提取出基本回路．基本回路表示能夠完成一個(gè)工件生產(chǎn)所經(jīng)過(guò)的最少元素的回路,經(jīng)過(guò)計(jì)算和比較,最優(yōu)回路在基本回路中產(chǎn)生. 已加入控制器的網(wǎng)模型中存在許多有向回路,從網(wǎng)模型中篩選出基本回路,可以判斷每個(gè)回路中所用到的工序,再計(jì)算得到回路所有工序占用的時(shí)間,進(jìn)行比較后確定最優(yōu)回路.

算法1:判定模型中存在的所有基本回路;

輸入:所有有向回路集合Sc;

輸出:所有基本回路的集合Se;

step 0:定義一個(gè)集合Se:=?,表示所有基本回路的集合;

step 1:for(i:=0;i≤j;i++)

for(m:=0;m≤n;m++)

ifsi中不包含tcm,Sc:=Sc{si};

step 2:while(Sc≠?)

從Sc中選擇一個(gè)si,Sc:=Sc{si};

ifsi中包含pc,Se:=Se∪{si};

step 3:輸出集合Se;

step 4:結(jié)束.

通過(guò)算法1,可以找到網(wǎng)模型(如圖4)中所有能夠完成工件生產(chǎn)的基本回路集合Se,計(jì)算得到每個(gè)基本回路完成工作的時(shí)間,根據(jù)算法的整體思想,省略基本回路中控制器的輸入弧,建立時(shí)間Petri網(wǎng),如圖5所示.繼續(xù)根據(jù)時(shí)間Petri網(wǎng)中庫(kù)所的延時(shí)時(shí)間D,通過(guò)算法2來(lái)計(jì)算得到最優(yōu)時(shí)間,判斷哪個(gè)回路是最優(yōu)回路,確定控制器中的具體時(shí)刻. 最優(yōu)回路即單位時(shí)間內(nèi)設(shè)備資源利用率最高,產(chǎn)出的工件最多的回路,工件在最優(yōu)回路上完成生產(chǎn)所消耗的時(shí)間稱為最優(yōu)時(shí)間.

圖 5 應(yīng)用本文算法建立時(shí)間Petri網(wǎng)模型Fig.5 The timed Petri net applying the algorithm

3.2 基本回路加工時(shí)間優(yōu)化算法

算法2:確定第k+1個(gè)工件的最優(yōu)回路所需時(shí)間,k+1表示第k個(gè)資源結(jié)束后的下一個(gè)資源;

輸入:工件在加工進(jìn)程上所需加工時(shí)間dn;工件在共享資源α中所需時(shí)間dα;工件在共享資源β中所需時(shí)間dβ;

輸出:最優(yōu)回路所需時(shí)間d0;

step 0:規(guī)定第一個(gè)工件使用第一個(gè)共享資源作為其最優(yōu)回路;

step 1:定義一個(gè)變量d0為第k+1個(gè)工件在最優(yōu)回路中所需時(shí)間;

step 2:switch(dα與dβ的比較,是否有共享資源閑置)

case(dα

case(dα=dβ,且此時(shí)共享資源α,β均閑置)則該工件占用共享資源α,d0:=dn+dα;

case(dα>dβ,且此時(shí)共享資源β閑置)則該工件占用共享資源β,d0:=dn+dβ;

case(此時(shí)無(wú)共享資源閑置)則開始等待,

step 3:輸出d0;

step 4:結(jié)束.

通過(guò)設(shè)計(jì)算法2,計(jì)算找出每個(gè)工序的最優(yōu)回路和最優(yōu)時(shí)間,通過(guò)控制器按照最優(yōu)排列順序工作,可以避免由系統(tǒng)的異步性產(chǎn)生的沖突,得到更加高效的排產(chǎn)結(jié)果.

4 計(jì)算結(jié)果

依據(jù)表2中所給出的各項(xiàng)工序所需要的時(shí)間,由算法1可以找到圖4模型中存在的所有基本回路,省略控制器的輸入弧,即[t10,p11],[t11,p11],建立TPN.應(yīng)用算法2,對(duì)比各條基本回路所用時(shí)間,計(jì)算出最優(yōu)排列順序,從而得到系統(tǒng)生產(chǎn)的最短時(shí)間. 圖6是加上傳統(tǒng)控制器時(shí)系統(tǒng)的排程結(jié)果,可以看出,雖然系統(tǒng)穩(wěn)定工作,但是排程上出現(xiàn)了大量空閑時(shí)間,造成了資源浪費(fèi).運(yùn)用本文算法計(jì)算結(jié)果如圖7所示,在同一條件下,整個(gè)系統(tǒng)的工作效率明顯提升,機(jī)床2的排程已經(jīng)達(dá)到了100%.在實(shí)際操作中,需要提前計(jì)算各環(huán)節(jié)的準(zhǔn)確時(shí)間,在系統(tǒng)開始工作之前,將時(shí)間函數(shù)輸入到控制器之中,要求系統(tǒng)按照計(jì)劃時(shí)間工作,才能達(dá)到本文中的效果.

圖 6 未優(yōu)化前的排產(chǎn)結(jié)果Fig.6 Production schedule before being optimized

圖 7 應(yīng)用本文算法的排產(chǎn)結(jié)果Fig.7 Production schedule applying the algorithm

5 結(jié)束語(yǔ)

在當(dāng)前對(duì)自動(dòng)制造系統(tǒng)排產(chǎn)的研究中,應(yīng)用添加控制器的方法避免了系統(tǒng)發(fā)生沖突和死鎖問題,但是生產(chǎn)效率沒有明顯提升.本文在自動(dòng)制造系統(tǒng)中建立時(shí)間Petri網(wǎng)模型,通過(guò)適當(dāng)?shù)挠?jì)算,在控制器中加入時(shí)間函數(shù),得到優(yōu)化后的時(shí)間排程,在實(shí)際生產(chǎn)中具有可操作性.