[發(fā)明專利]一種基于元胞機(jī)的大型零件柔性作業(yè)車(chē)間的動(dòng)態(tài)調(diào)度方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201210034023.5
• 申請(qǐng)日: 2012-02-15
• 公開(kāi)（公告）號(hào): CN102608916A
• 公開(kāi)（公告）日: 2012-07-25
• 發(fā)明（設(shè)計(jì)）人: 陳勇;吳云翔;邱曉杰;盛家君;潘益菁
• 申請(qǐng)（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類(lèi)號(hào): G05B13/04
• 分類(lèi)號(hào): G05B13/04
• 代理公司: 杭州天正專利事務(wù)所有限公司 33201
• 代理人: 王兵;王利強(qiáng)

1.一種基于元胞機(jī)的大型零件柔性作業(yè)車(chē)間的動(dòng)態(tài)調(diào)度方法，其特征在于：包括如下步驟：

1)建立元胞機(jī)的網(wǎng)格模型：將整個(gè)車(chē)間設(shè)定為一個(gè)包含移動(dòng)粒子的二維網(wǎng)格系統(tǒng)，每個(gè)網(wǎng)格作為一個(gè)元胞代表一個(gè)加工工位或緩存，每個(gè)工位某一時(shí)刻只能加工一個(gè)零件，緩存區(qū)的工件排隊(duì)等待，設(shè)定所述大型零件柔性作業(yè)車(chē)間共有n個(gè)工位組，每組包含的工位個(gè)數(shù)m(n)只與工位組別號(hào)n有關(guān)，一般不等，每一工位組包含的工位個(gè)數(shù)和與其對(duì)應(yīng)的緩存組的緩存?zhèn)€數(shù)相，，移動(dòng)粒子表示隨機(jī)到達(dá)系統(tǒng)的工件，

2)元胞狀態(tài)描述設(shè)計(jì)：根據(jù)元胞狀態(tài)函數(shù)任意一緩存元胞t+1時(shí)刻的狀態(tài)可用以下數(shù)學(xué)形式表示

SC(2n+1)jt+1=f[SC(2n+1)jt,(SC(2n)mt,SC(2n+1)mt,SC(2n+2)jt)]---(1)]]>

式(1)中：

f——局部狀態(tài)轉(zhuǎn)換規(guī)則即作業(yè)調(diào)度規(guī)則；

——緩存元胞C_(2n+1)j上游工位組所有工位元胞t時(shí)刻的狀態(tài)集合；

(m≠j)——緩存元胞C_(2n+1)j所在緩存組其他元胞C(_2n+1)mt時(shí)刻的狀態(tài)集合；

——緩存元胞C_(2n+1)j下游工位組中與其對(duì)應(yīng)的工位元胞C_(2n+2)jt時(shí)刻的狀態(tài)，

同樣，任意工位元胞t+1時(shí)刻的狀態(tài)表示為：

SC(2n)jt+1=f[SC(2n)jt,(SC(2n-1)jt,SC2n+1t)]---(2)]]>

式(2)中：

——工位元胞C_(2n)j上游工位組中與其對(duì)應(yīng)的緩存元胞C_(2n-1)jt時(shí)刻的狀態(tài)；

——工位元胞C_(2n)j下游緩存組所有緩存元胞t時(shí)刻的狀態(tài)集合，

緩存元胞t時(shí)刻的狀態(tài)屬性表示為：

Scbt(wct,wco,wcl,lq,wq)---(3)]]>

式(3)中：

——緩存元胞C_(2n+1)j在t時(shí)刻的狀態(tài)；

w_ct——緩存元胞的在制品空間總?cè)萘浚o態(tài)屬性，單位unit；

w_co——緩存元胞中已被占用的容量，動(dòng)態(tài)屬性，0≤w_co≤w_ct；

w_cl——該緩存元胞未被占用的容量，動(dòng)態(tài)屬性，w_cl＝w_ct-w_co；

lq——隊(duì)列長(zhǎng)度，動(dòng)態(tài)屬性，表示緩存元胞中等待加工的工件個(gè)數(shù)；

w_q——等待時(shí)間，動(dòng)態(tài)屬性，等于緩存元胞的工件隊(duì)列中最后一個(gè)加工工件需要等待的時(shí)間，單位day，(wl為零件對(duì)應(yīng)的工序所需的加工能力)，

pe——加工效率，靜態(tài)屬性，選擇代表工序，取一天能完成幾道代表工序作為加工效率，每個(gè)工位的pe多數(shù)不等；

工位元胞t時(shí)刻的狀態(tài)屬性表示為：

Scst(st,pe,T,ss,sct,sco,scl)---(4)]]>

式(4)中：

——工位元胞C_(2n)j在t時(shí)刻的狀態(tài)；

st——所屬工位組，靜態(tài)屬性，st∈{C_2n}，n為正整數(shù)；

T——工位一個(gè)調(diào)度周期內(nèi)總共能用于加工的時(shí)間，靜態(tài)屬性，單位天/d；

s_s——工位忙閑狀態(tài)，動(dòng)態(tài)屬性，s_s∈{0，1，2}，0空閑，1忙碌，2故障；

s_ct——工位一個(gè)調(diào)度周期內(nèi)的總加工能力，靜態(tài)屬性，s_ct＝pe×T，單位unit；

s_co——工位已被占用的加工能力，也即工位的負(fù)荷量，動(dòng)態(tài)屬性，等于已加工和正在加工的工件，對(duì)應(yīng)緩沖元胞的隊(duì)列中待加工的工件，這三部分零件需要的加工能力值的總和，0≤s_co≤s_ct；

s_cl——工位元胞剩余的加工能力，動(dòng)態(tài)屬性，s_cl＝s_ct-s_co，

3)初始條件和邊界條件設(shè)定：工件粒子t時(shí)刻的狀態(tài)屬性，表達(dá)式如下：

Spt(pt,pf,np,fst,wl,sn,dp,qn,ta)---(5)]]>

式中：

——Status?ofParticle，粒子p_k在t時(shí)刻的狀態(tài)，k∈N⁺，工件編號(hào)；

p_t——Procedures?in?Total，粒子所需加工的工序總數(shù)，靜態(tài)屬性；

p_f——Procedures?Finished，粒子已經(jīng)完成的工序數(shù)，動(dòng)態(tài)屬性；

np——Next?Procedure，粒子的下一道工序編號(hào)，動(dòng)態(tài)屬性；

fst——Following?Station?Type，粒子完成當(dāng)前工序后所要進(jìn)入的下一工位組，動(dòng)態(tài)屬性；

wl——Workload，該粒子下一道工序所需要的工位的加工能力，動(dòng)態(tài)屬性，單位是unit；

s_n——Space?Needed，該粒子所需要占用的空間，靜態(tài)屬性，對(duì)應(yīng)緩存區(qū)的w_cl；

dp——Delivery?Priority，工件加工優(yōu)先級(jí)，靜態(tài)屬性，由工件的交貨期決定，交貨期越緊優(yōu)先級(jí)越高，對(duì)應(yīng)的dp數(shù)值越大，dp取正整數(shù)；

qn——Sequence?Number?of?the?Queue，隊(duì)列排序中的序號(hào)，動(dòng)態(tài)屬性，qn取正整數(shù)；

t_a——Arrive?Time，到達(dá)元胞的時(shí)間，分為到達(dá)緩存元胞的時(shí)間(也即開(kāi)始排隊(duì)的時(shí)間)和到達(dá)工位元胞的時(shí)間(也即開(kāi)始加工的時(shí)間)，動(dòng)態(tài)屬性，

整個(gè)模型系統(tǒng)的初始和入口邊界條件定義成各粒子進(jìn)入系統(tǒng)的節(jié)拍，出口邊界條件是供應(yīng)鏈下游工廠對(duì)產(chǎn)品的接受能力；

4)確定模型自組織演化規(guī)則：大型零件柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題的優(yōu)化目標(biāo)概括為3點(diǎn)：(1)各道工序完工時(shí)間早；(2)各工位負(fù)荷率高，空閑少；(3)同一工位組中所有工位負(fù)荷平衡，根據(jù)柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度的特點(diǎn)將本模型的自組織演化規(guī)則歸納為三條，表1所示，

表1

4)模型演化過(guò)程，具體包括：

工位選擇：工位選擇規(guī)則R_p→c：某一工件到達(dá)，首先判斷其下個(gè)目標(biāo)工位組中工位的忙、閑或故障狀態(tài)；然后根據(jù)處于同一狀態(tài)的工位的數(shù)量，優(yōu)先選擇加工效率高也即pe數(shù)值大的工位，或者是能夠最早完成本工序的工位，即比較(w_q+wl÷pe)的值，選擇值最小的對(duì)應(yīng)的工位；再判斷工件在時(shí)間、空間上是否能被其目標(biāo)工位元胞和目標(biāo)緩存元胞所容納，也即比較s_cl和wl的大小，以及w_cl和s_n的大小，如果s_cl≥wl且w_cl≥s_n，工件進(jìn)入工位，否則，工件暫時(shí)進(jìn)入后備緩存區(qū)，待仿真鐘前進(jìn)一個(gè)時(shí)步再調(diào)度時(shí)重新判斷；

工件排序：工件排序規(guī)則R_c→p主要結(jié)合FCFS(先到先服務(wù))原則及工件的加工優(yōu)先級(jí)確定工件的加工順序，首先，根據(jù)到達(dá)時(shí)刻t_a排序，t_a越小的工件排在越前面；然后從隊(duì)末往前工件兩兩比較優(yōu)先級(jí)dp的大小，若后面工件的dp值大于前面工件的dp值，則將兩工件的隊(duì)列位置及隊(duì)列序號(hào)qn互換，直到前面工件的dp值不小于后面工件的dp值為止，輸出隊(duì)列順序，更新緩存元胞及各粒子的狀態(tài)屬性值，

任務(wù)觸發(fā)：任務(wù)觸發(fā)規(guī)則R_ta的激活需要滿足兩個(gè)條件：(1)目標(biāo)工位元胞空閑，s_s＝0；(2)待加工工件位于隊(duì)列的最前端，qn＝1，條件滿足時(shí)，工件進(jìn)入目標(biāo)工位，目標(biāo)工位被占據(jù)，置其忙碌，s_s＝1，緩存元胞隊(duì)列長(zhǎng)度lq＝lq-1，隊(duì)列中等待的所有粒子的隊(duì)列序號(hào)qn減1，前進(jìn)一位，產(chǎn)生加工開(kāi)始時(shí)間，同時(shí)更新t_a，加工完畢后安排加工結(jié)束事件，閑置工位，工件離開(kāi)，最后返回總控程序，

演化規(guī)則為：工位選擇規(guī)則R_p→c是以第j道工序加工完成為起點(diǎn)，第j+1道工序加工完成為終點(diǎn)的這段時(shí)間(w_q+wl÷pe)為衡量標(biāo)準(zhǔn)，選擇(w_q+wl÷pe)最小的工位作為第j+1道工序的加工工位，工件排序規(guī)則R_c→p則是按照先到先服務(wù)規(guī)則結(jié)合工件加工優(yōu)先級(jí)決定的。

2.如權(quán)利要求1所述的一種基于元胞機(jī)的大型零件柔性作業(yè)車(chē)間的動(dòng)態(tài)調(diào)度方法，其特征在于：所述步驟4)中，采用遺傳算法對(duì)元胞機(jī)的演化規(guī)則進(jìn)行優(yōu)化，過(guò)程如下：

設(shè)一個(gè)工位組和其對(duì)應(yīng)的緩存組為一個(gè)單元，每一個(gè)時(shí)步內(nèi)，每個(gè)單元的調(diào)度機(jī)制相同，轉(zhuǎn)化為一個(gè)個(gè)靜態(tài)柔性調(diào)度問(wèn)題，最優(yōu)目標(biāo)有3個(gè)：(1)各道工序完工時(shí)間早；(2)各工位負(fù)荷率高，空閑少；(3)同一工位組中所有工位負(fù)荷平衡，下面，利用遺傳算法對(duì)工位選擇規(guī)則R_p→c和工件排序規(guī)則R_c→p進(jìn)行編碼；

元胞機(jī)各調(diào)度單元每個(gè)時(shí)步內(nèi)的模型描述為：n個(gè)工件粒子要在包含m個(gè)同類(lèi)工位的工位組中進(jìn)行加工，m個(gè)工位分別對(duì)應(yīng)m個(gè)緩存，每個(gè)工位的加工效率不同，每個(gè)工件在此工位組中只需完成一道工序，每道工序根據(jù)實(shí)際要求可供選擇的工位是工位組中的某幾個(gè)或全部，每道工序在不同的工位上加工所需的時(shí)間不一，設(shè)：

工件粒子集P＝{p₁，p₂，p₃，......，p_n}；

工位集s＝{s₁，s₂，s₃，......，s_m}；

緩存集B＝{b₁，b₂，b₃，......，b_m}；

工序O_ij表示第i個(gè)工件的第j道工序，本模型研究范圍內(nèi)每個(gè)工件只有唯一一道工序，也即每個(gè)工件對(duì)應(yīng)的j只有一個(gè)；

第x個(gè)工位組的加工時(shí)間矩陣T，其中T_ijxy表示第i個(gè)工件的第j道工序在第x個(gè)工位組的第y個(gè)工位上加工所需要的時(shí)間；

設(shè)備維修時(shí)間信息，每臺(tái)設(shè)備的故障率為λ_y；

子目標(biāo)權(quán)重w₁，w₂，w₃，

所有工序總加工時(shí)間最短，即為了配合其余兩個(gè)子目標(biāo)，使之相對(duì)統(tǒng)一，對(duì)其進(jìn)行如下處理，使子目標(biāo)1轉(zhuǎn)化為最大值，且不至于過(guò)分接近于0，

F1=Σi=1nminTiyΣi=1n(TiAi)y∈{1,2,...,m}---(6)]]>

式(6)中，分子表示的是所有工件都選擇加工時(shí)間最短的工位進(jìn)行加工時(shí)總的加工時(shí)間，是理想狀況的最小值；分母表示每個(gè)可行解的實(shí)際總加工時(shí)間，0＜F₁≤1，T_i是一系列包含m個(gè)元素的行矩陣，每個(gè)元素對(duì)應(yīng)一個(gè)T_ijxy，對(duì)于每個(gè)單元調(diào)度可簡(jiǎn)寫(xiě)為T(mén)_iy；

A_i則是一系列包含m個(gè)元素的列矩陣，每個(gè)元素a_iy∈{0，1}，其中y對(duì)應(yīng)的就是工位序號(hào)y∈{1，2，...m}，

各工位負(fù)荷率高，轉(zhuǎn)化為所有工位總利用率F₂高：

F2=Σi=1n(TiAi)Σy=1m(T(1-λy))---(7)]]>

式(7)中，T是每個(gè)仿真步長(zhǎng)所代表的實(shí)際時(shí)間，仿真開(kāi)始之前進(jìn)行設(shè)定，仿真過(guò)程中不發(fā)生變化；λ_y是對(duì)應(yīng)工位組中每臺(tái)設(shè)備的故障率，

同一工位組中所有工位負(fù)荷平衡，平衡率F₃最大，根據(jù)

有

F3=Σi=1n(TiAi)Cmax×m---(8)]]>

式(8)中，C_max為負(fù)荷最大的工位所耗費(fèi)的加工時(shí)間，m為此工位組的工位總數(shù)，

通過(guò)權(quán)重加合法得到元胞機(jī)的每個(gè)離散單元在每個(gè)時(shí)步內(nèi)的調(diào)度總目標(biāo)函數(shù)：

F＝max(w₁F₁+w₂F₂+w₃F₃)，即

F=max(w1×Σi=1nminTiyΣi=1n(TiAi)+w2×Σi=1n(TiAi)Σy=1m(T(1-λy))+w3×Σi=1n(TiAi)Cmax×m)---(9)]]>

加工約束條件如下：

1)資源約束，

a)同一臺(tái)設(shè)備同一時(shí)刻只能加工一個(gè)工件；

b)同一工件的同一道工序只能被一臺(tái)設(shè)備加工；

c)每個(gè)工件的每道工序一旦開(kāi)始加工就不能停止，

2)工藝約束，

a)不同工件的工序之間沒(méi)有先后約束；

b)同一工件的工序之間有先后約束，

3)權(quán)重約束，

a)每個(gè)子目標(biāo)的權(quán)重介于0和1之間：0≤w_i≤1i∈{1，2，3}；

b)所有子目標(biāo)的權(quán)重之和為

獲取初始種群：以min(w_q+wl÷pe)為工位選擇標(biāo)準(zhǔn)獲得的工位選擇方案，及根據(jù)FCFS規(guī)則結(jié)合工件加工優(yōu)先級(jí)獲得的工件排序方案分別對(duì)應(yīng)編碼中的工位選擇染色體和工序排序染色體，獲得遺傳算法的初始解；

將目標(biāo)函數(shù)設(shè)為適應(yīng)度函數(shù)，有

fit(F)=F=0.4×Σi=1nminTiyΣi=1n(TiAi)+0.3×Σi=1n(TiAi)Σy=1m(T(1-λy))+0.3×Σi=1n(TiAi)Cmax×m---(10)]]>

采用按比例的適應(yīng)度分配方法，利用比例于各個(gè)個(gè)體適應(yīng)度的概率決定其子代保留的可能性，若某個(gè)個(gè)體i，其適應(yīng)度為f_i，則其被選取的概率表示為，

Pi=fiΣi=1Mfi---(11)]]>

選擇方法采用輪盤(pán)賭選擇法，將個(gè)體適應(yīng)度按比例轉(zhuǎn)化為選中概率，有幾個(gè)個(gè)體就將輪盤(pán)分成幾個(gè)扇區(qū)；

交叉：所述染色體分為兩個(gè)部分，第一部分染色體工位選擇部分直接采用雙切點(diǎn)交叉法，對(duì)應(yīng)部分兩兩交叉；第二部分的染色體——工件排序染色體中，由于每道工序只能出現(xiàn)一次，如果采用兩條染色體兩兩交叉，產(chǎn)生的新染色體不是和父代染色體相同就是不合法；

變異：第一部分染色體的變異，采用在工位選擇染色體的基因串中隨機(jī)選擇一個(gè)位置，在此工序的工位集中隨機(jī)選擇一個(gè)與其不相等的整數(shù)，替換當(dāng)前基因，這樣得到的解可以保證是可行解，第二部分染色體的變異采用基因位置互換的方法，即從工序排序染色體中隨機(jī)選擇兩個(gè)位置的基因，將其位置進(jìn)行互換，這樣可以保證同一條工序排序染色體中不會(huì)出現(xiàn)相同的數(shù)字，也即解可行，

一個(gè)世代的簡(jiǎn)單進(jìn)化過(guò)程包括獲取初始種群、適應(yīng)度函數(shù)、選擇、交叉、變異操作，然后根據(jù)一個(gè)世代的簡(jiǎn)單進(jìn)化過(guò)程反復(fù)迭代，直到滿足終止條件，此時(shí)得到的染色體可視為經(jīng)遺傳算法尋優(yōu)后得到的元胞自動(dòng)機(jī)演化的最優(yōu)規(guī)則。3、如權(quán)利要求2所述的一種基于元胞機(jī)的大型零件柔性作業(yè)車(chē)間的動(dòng)態(tài)調(diào)度方法，其特征在于：所述交叉操作中，工序排序部分染色體的交叉選用POX交叉法，設(shè)有父代染色體Parent1和Parent2，POX產(chǎn)生子代染色體Children1和Children2，具體流程如下：

1)隨機(jī)劃分工件集{1，2，3，...，n}為兩個(gè)非空子集J1和J2；

2)復(fù)制Parent1包含在J1的工件到Children1，Parent2包含在J1的工件到Children2，保留它們的位置；

3)復(fù)制Parent2包含在J2的工件到Children1，Parent1包含在J2的工件到Children2，保留它們的順序。