基于基因轉(zhuǎn)錄的機(jī)加工車間主動(dòng)調(diào)度研究

吳正佳 龔 穩(wěn) 孟榮華 涂晶鑫 董元發(fā),2

(1.三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院,湖北 宜昌 443002;2.機(jī)器人與智能系統(tǒng)宜昌市重點(diǎn)實(shí)驗(yàn)室,湖北 宜昌443002)

生產(chǎn)過程中不確定的擾動(dòng)事件,如緊急訂單插入、交貨期更改、設(shè)備突然失效等,隨時(shí)可能導(dǎo)致車間生產(chǎn)紊亂甚至中斷,給企業(yè)帶來損失.故研究擾動(dòng)因子已成為機(jī)加工車間穩(wěn)健作業(yè)的核心任務(wù).近年來,許多專家針對此問題做了諸多研究.Zakaria等[1]提出了基于設(shè)備空閑時(shí)間來有效地應(yīng)對插單和機(jī)器故障;Vieira等[2]針對重調(diào)度,提出了一種新的重調(diào)度系統(tǒng);Al-Hinai等[3]通過改進(jìn)的遺傳算法來研究隨機(jī)機(jī)器故障下FJSP魯棒調(diào)度問題;Lu等[4]通過最短路徑問題解決最小化加工時(shí)間的單一目標(biāo)函數(shù)的單機(jī)魯棒調(diào)度問題;Ranjbar等[5]研究了有關(guān)隨機(jī)加工時(shí)間和已知客戶交貨期的魯棒并行機(jī)調(diào)度問題;劉明周[6]等采用主動(dòng)和被動(dòng)重調(diào)度規(guī)則進(jìn)行響應(yīng)擾動(dòng),建立了重調(diào)度優(yōu)化集.綜上所述,機(jī)加工穩(wěn)健作業(yè)問題研究現(xiàn)狀存在著以下幾點(diǎn)不足:

1)在調(diào)度策略上大多采用魯棒性調(diào)度,雖然考慮了不確定性事件,但是不確定性因素過于單一,適用的范圍很小,且此調(diào)度方案對突發(fā)時(shí)間的響應(yīng)能力較差,犧牲了調(diào)度系統(tǒng)的效率,難以融入實(shí)際生產(chǎn)中.

2)目前的研究重點(diǎn)著重于車間的顯性擾動(dòng)研究,忽略了隱性擾動(dòng)的危害.而研究車間的隱性擾動(dòng),通過擾動(dòng)因子之間的耦合可以提前預(yù)測隱性擾動(dòng),采用有效解決方法,可以提高車間調(diào)度系統(tǒng)的穩(wěn)定性.

3)現(xiàn)有研究方式多為假設(shè)反應(yīng)式調(diào)度,缺少主動(dòng)式調(diào)度的研究,而運(yùn)用好主動(dòng)式調(diào)度可以有效增加車間調(diào)度的魯棒性及減少車間的調(diào)度產(chǎn)生次數(shù).

上述描述突出了現(xiàn)有研究現(xiàn)狀下,缺少對車間主動(dòng)調(diào)度問題的研究.車間主動(dòng)調(diào)度問題非常復(fù)雜,因?yàn)閿_動(dòng)因子、設(shè)備故障和調(diào)度策略,在生產(chǎn)車間都是相互影響的.在擾動(dòng)發(fā)生之前,對車間生產(chǎn)調(diào)度系統(tǒng)進(jìn)行微調(diào)度,避免完全重新調(diào)度,同時(shí)節(jié)約成本,是主動(dòng)調(diào)度的主要思想.基于上述車間主動(dòng)調(diào)度問題,本文提出了生物學(xué)中基因的概念,以解決隱性因子不易表達(dá)的困難,同時(shí)借鑒基因轉(zhuǎn)錄與翻譯的概念,對隱性因子進(jìn)行研究,使多種不確定事件進(jìn)行耦合,便于主動(dòng)調(diào)度的實(shí)施.

1 問題描述

1.1 機(jī)加工車間調(diào)度問題描述

n個(gè)工件,m臺(tái)機(jī)器,每個(gè)工序可以在多臺(tái)機(jī)床中任意選擇一臺(tái)進(jìn)行加工,不同工件的工序加工路徑可以不相同.工件集為J={J1,J2,…,Jn};每個(gè)工件包含一道或多道工序數(shù),工件i的工序集合為Oi={Oi1,Oi2,…,Oij};工件i的第j道工序可供選擇的機(jī)器的集合為Mij={Mij1,Mij2,…,Mijk};工件i的第j道工序在機(jī)器k上的加工時(shí)間集合為pij={pij1,pij2,…,pijk}.

加工作業(yè)調(diào)度問題約束條件如下:

1)所有工件最早加工時(shí)間為零,加工開始前機(jī)器都是空閑的;

2)工件在加工過程中不能中斷,除非有擾動(dòng)事件發(fā)生;

3)工件的某工序在同一時(shí)刻只能占有一臺(tái)設(shè)備,同樣每臺(tái)設(shè)備在某個(gè)時(shí)刻只能為一個(gè)工件所用;

4)不同工件沒有優(yōu)先級規(guī)則;

5)工件的加工工序順序固定、不能調(diào)換,只有當(dāng)前一工序加工完成后才能開始下一工序的加工;工序的準(zhǔn)備時(shí)間忽略不計(jì);

6)出現(xiàn)擾動(dòng)時(shí),不受其影響的正在加工的工件繼續(xù)加工,直到該工序完成.

在建立模型時(shí),需用特定的符號來描述車間中工序和機(jī)器的狀態(tài)信息,見表1.

表1 魯棒性測度建模符號含義

據(jù)此,本文的調(diào)度模型為

式(1)為工件最大完工時(shí)間;式(2)為機(jī)器能力約束;式(3)為工序約束,式(4)為開工時(shí)間.

1.2 主動(dòng)調(diào)度方案的魯棒性測度建模

當(dāng)初始調(diào)度方案受實(shí)時(shí)與預(yù)測擾動(dòng)事件影響時(shí),對初始調(diào)度方案稍做修改,形成主動(dòng)調(diào)度方案.調(diào)度方案的性能魯棒性測度為:

初始調(diào)度方案的穩(wěn)定性魯棒性測度為:

當(dāng)實(shí)時(shí)與預(yù)測事件影響初始調(diào)度時(shí),形成響應(yīng)的主動(dòng)調(diào)度方案,其目標(biāo)是最小化擾動(dòng)時(shí)間對初始調(diào)度方案的影響.影響方案的魯棒性測度表示為:

2 生產(chǎn)車間擾動(dòng)因子分析

生產(chǎn)車間擾動(dòng)事件的本質(zhì)是由擾動(dòng)因子之間的相互作用產(chǎn)生的[7].擾動(dòng)因子與調(diào)度策略之間的關(guān)系如圖1所示.擾動(dòng)因子分為隱性擾動(dòng)因子和顯性擾動(dòng)因子,而隱性擾動(dòng)因子可以通過隱性擾動(dòng)因子之間的耦合關(guān)系轉(zhuǎn)變?yōu)轱@性擾動(dòng)因子.

圖1 擾動(dòng)因子與調(diào)度策略關(guān)系圖

2.1 生產(chǎn)車間的擾動(dòng)因子分類

在目前的主動(dòng)調(diào)度研究過程中,擾動(dòng)因子分類是第一步.本文主要從設(shè)備類,物料類,產(chǎn)品類,訂單類4個(gè)方面展開研究,總結(jié)出如圖2所示的常見生產(chǎn)擾動(dòng)現(xiàn)象原因分類圖.

圖2 因子分類圖

2.2 擾動(dòng)因子的相關(guān)關(guān)系

在車間中,一般能觀察到的多為顯性擾動(dòng),但隱性擾動(dòng)也是十分重要的一部分[8].本文的主要思想為:顯性因子不能自發(fā)地進(jìn)行擾動(dòng),如要發(fā)生擾動(dòng)則必須由一個(gè)或多個(gè)隱性擾動(dòng)之間耦合對其進(jìn)行驅(qū)動(dòng),使顯性因子進(jìn)行擾動(dòng).故隱性擾動(dòng)也是間接影響了車間調(diào)度策略.隱性擾動(dòng)因子之間的關(guān)系可以分為促進(jìn)作用和抑制作用,促進(jìn)作用是指當(dāng)兩個(gè)隱性擾動(dòng)因子進(jìn)行耦合時(shí),能夠增加耦合轉(zhuǎn)變?yōu)轱@性擾動(dòng)因子的幾率,相反的抑制作用是指降低耦合轉(zhuǎn)變幾率.若因子X促進(jìn)因子Y轉(zhuǎn)變,則因子X為因子Y的促進(jìn)子,否則稱為抑制子.當(dāng)因子X調(diào)節(jié)因子Y時(shí),在網(wǎng)絡(luò)中可以用關(guān)系X→Y表示.單位時(shí)間內(nèi)生成因子Y的數(shù)量是因子X的活化狀態(tài)函數(shù),用希爾函數(shù)表述.對于促進(jìn)因子而言,希爾函數(shù)從0開始,逐漸逼近最大的飽和水平,希爾函數(shù)具體的形式可以表示為:

對于抑制因子來說,希爾函數(shù)是一個(gè)S形遞減函數(shù).該函數(shù)曲線形狀可表示為如下形式:

為了使系統(tǒng)具有一般性,本文讓所有的節(jié)點(diǎn)參數(shù)相同.

2.3 擾動(dòng)因子耦合圖的建立

基于上述理論,可以將隱性擾動(dòng)因子構(gòu)建為一個(gè)有向網(wǎng)絡(luò)漸變圖,如圖3所示.

圖3 有向隱性網(wǎng)絡(luò)漸變圖

其中綠線代表促進(jìn)作用,紅線代表抑制作用.在車間未開始加工時(shí)(t=0時(shí)刻),無論什么生產(chǎn)元素的隱性擾動(dòng)因子都是處于未被激活的狀態(tài),如圖3(a)所示;在加工開始后,可能出現(xiàn)如圖3(b)所示的已經(jīng)激活的隱性擾動(dòng)關(guān)系圖;通過耦合后得到如圖3(c)所示的漸變圖.

2.4 閾值的設(shè)定

隨著擾動(dòng)個(gè)數(shù)的增加,以及耦合程度的增加,對單個(gè)生產(chǎn)要素的影響程度是不一樣的.如圖3所示,4個(gè)節(jié)點(diǎn)以及6條邊都有賦值,代表了此點(diǎn)或邊對這個(gè)4節(jié)點(diǎn)隱性擾動(dòng)網(wǎng)絡(luò)的影響程度,故這個(gè)4節(jié)點(diǎn)網(wǎng)絡(luò)的節(jié)點(diǎn)代數(shù)和決定了網(wǎng)絡(luò)的耦合程度.若耦合值α小于閾值δ,則對其進(jìn)行添加抑制或者促進(jìn)因子使生產(chǎn)恢復(fù)穩(wěn)態(tài);若耦合值α大于閾值δ,則產(chǎn)生的擾動(dòng)很大.

3 車間的基因表達(dá)過程

鑒于上述分析得出,擾動(dòng)因子分為顯性擾動(dòng)和隱性擾動(dòng).顯性擾動(dòng)是通過隱性擾動(dòng)之間的耦合產(chǎn)生的,類似于生物學(xué)中遺傳信息的轉(zhuǎn)錄.故本文將車間的擾動(dòng)類比于生物學(xué)中的中心性法則進(jìn)行研究.生物中心性法則表達(dá)如圖4所示.

圖4 中心性法則示意圖

將車間表達(dá)成3層結(jié)構(gòu):把隱藏的隱性擾動(dòng)因子信息耦合轉(zhuǎn)錄出來,成為易觀察的顯性擾動(dòng),顯性擾動(dòng)因子對生產(chǎn)調(diào)度產(chǎn)生影響,通過求解表達(dá)出新的調(diào)度策略.生產(chǎn)車間中的中心法則如圖5所示.

圖5 生產(chǎn)車間的中心法則圖

故在生產(chǎn)車間加工生產(chǎn)的過程中,通過分析擾動(dòng)因子與車間調(diào)度策略之間的關(guān)系,然后進(jìn)一步分析擾動(dòng)因子中顯性擾動(dòng)因子與隱性擾動(dòng)因子之間的耦合關(guān)系,得出顯性擾動(dòng)轉(zhuǎn)化的安全閾值.所有的隱性擾動(dòng)因子視為DNA,它們之間的耦合形成顯性擾動(dòng),此時(shí)就對原有調(diào)度方案形成了擾動(dòng),擾動(dòng)大則需產(chǎn)生新的調(diào)度方案.

而本文的主動(dòng)調(diào)度思想則是在隱性擾動(dòng)耦合成為顯性擾動(dòng)的過程中,對其進(jìn)行添加抑制或者促進(jìn)因子,使得隱性因子的耦合值低于閾值(α＜δ),則維持原調(diào)度方案;若隱性因子的耦合值高于閾值(α≥δ),即產(chǎn)生的擾動(dòng)很大,在可以調(diào)控的范圍之內(nèi),則采用主動(dòng)調(diào)度方案.本文根據(jù)專家經(jīng)驗(yàn)設(shè)定閾值δ=0.8.基因抑制流程圖如圖6所示.

圖6 基因抑制流程圖

4 主動(dòng)調(diào)度方案

4.1 主動(dòng)調(diào)度框架

加工過程中,擾動(dòng)不可避免.當(dāng)車間出現(xiàn)異常的擾動(dòng)時(shí),首先判斷異常類型,確定受影響的工件、工序和機(jī)器,更新調(diào)度參數(shù),產(chǎn)生新的動(dòng)態(tài)調(diào)度方案,并執(zhí)行新調(diào)度方案;為避免調(diào)度中時(shí)間的浪費(fèi),減小異常擾動(dòng)給制造加工系統(tǒng)帶來的損失,在異常擾動(dòng)發(fā)生之前,根據(jù)加工過程中RFID采集的實(shí)時(shí)數(shù)據(jù)與歷史數(shù)據(jù),對將來可能發(fā)生的異常擾動(dòng)進(jìn)行預(yù)測,采取必要的預(yù)防維護(hù)措施,避免擾動(dòng)的發(fā)生,確定受影響工件與工序,更新調(diào)度參數(shù),形成主動(dòng)調(diào)度方案.本文的調(diào)度目標(biāo)為最小化異常擾動(dòng)對初始調(diào)度方案的影響.加工作業(yè)的主動(dòng)調(diào)度框架流程圖如圖7所示.

圖7 主動(dòng)調(diào)度框架流程圖

4.2 主動(dòng)調(diào)度策略

通過RFID標(biāo)簽技術(shù),實(shí)現(xiàn)從原材料出庫經(jīng)過機(jī)床加工以及產(chǎn)品入庫整個(gè)加工過程的監(jiān)測,在物料經(jīng)過的各個(gè)加工工位都配置有RFID感知節(jié)點(diǎn),以達(dá)到實(shí)時(shí)感知到達(dá)工件的ID號、時(shí)間、位置等數(shù)據(jù),形成工件的實(shí)時(shí)狀態(tài)矩陣S=(aij)(1≤i≤m,1≤j≤4).

式中:i表示工件序號;j表示工位序號;aij=0,表示工件在該工位加工情況正常;aij=1,表示加工情況異常.

主動(dòng)調(diào)度采用基于預(yù)測事件驅(qū)動(dòng)的重調(diào)度策略.該調(diào)度方式根據(jù)制造車間現(xiàn)場采集的加工過程實(shí)時(shí)數(shù)據(jù)以及歷史數(shù)據(jù),預(yù)測擾動(dòng)事件的發(fā)生,并在擾動(dòng)事件開始之前,預(yù)先安排處理,如更換刀具等.

滾動(dòng)調(diào)度策略是常用的動(dòng)態(tài)調(diào)度策略[7],在滾動(dòng)調(diào)度策略中需要定義一個(gè)工件窗口,在重調(diào)度時(shí)刻,只調(diào)度該時(shí)刻工件窗口中的工件,滾動(dòng)調(diào)度工件窗口示意圖如圖8所示.

圖8 滾動(dòng)調(diào)度工件窗口示意圖

5 計(jì)算實(shí)例

以B車間為例,B車間有6個(gè)工件,每個(gè)工件均有3道工序,每道工序可以選擇可加工該工件的機(jī)器中的任意1臺(tái)進(jìn)行加工,每道工序在各個(gè)機(jī)器的加工時(shí)間確定,各個(gè)工件每道工序可選擇的加工機(jī)器見表2,各工序在對應(yīng)機(jī)器上的加工時(shí)間見表3.

表2 工序加工可選機(jī)器設(shè)備

表3 工序在對應(yīng)機(jī)器上的加工時(shí)間 (單位:s)

利用Matlab編程,使用遺傳算法[9],基本參數(shù)根據(jù)規(guī)模與復(fù)雜度,設(shè)定種群規(guī)模為500,最大迭代次數(shù)為500,交叉率為0.7,變異率為0.3.得到初始的調(diào)度方案為圖9所示:在加工開始進(jìn)行時(shí)按照此加工方案進(jìn)行操作,最小完工時(shí)間為712 s.此方案未考慮車間的其他運(yùn)行情況因素(如物料運(yùn)送時(shí)間或者考慮維護(hù)時(shí)間),是一個(gè)理想化的方案.

圖9 調(diào)度甘特圖

若考慮到擾動(dòng)時(shí),當(dāng)t=326 s時(shí)刻,RFID對工件實(shí)時(shí)監(jiān)測返回的異常狀態(tài)矩陣如下:

說明在t=326 s時(shí)刻,O62=1表示第6個(gè)工件在第2道工序工位加工情況異常.甘特圖9得到O62在M3上進(jìn)行加工.則通過RFID預(yù)警檢查在工作狀態(tài)下的O62可能發(fā)生的擾動(dòng)因子,能否使得O62在隱性擾動(dòng)的情況下增加抑制或者促進(jìn)因子,使之隱性因子之間的耦合影響不超過閾值.故分析得知,O62存在的隱性擾動(dòng)見表4.

表4 存在的隱性擾動(dòng)

得到隱性擾動(dòng)網(wǎng)絡(luò)如圖10(a)所示,耦合后的網(wǎng)絡(luò)圖如圖10(b)所示.

圖10 隱性擾動(dòng)因子耦合圖

由希爾濃度關(guān)系,取h=2,k=0.3,對各點(diǎn)進(jìn)行賦值,計(jì)算出耦合值為:α=0.84＞0.8,故無法通過增加抑制或者促進(jìn)因子使得擾動(dòng)維持在隱性擾動(dòng)水平.故需要采用主動(dòng)調(diào)度方案使得原始調(diào)度方案維持穩(wěn)定.

以擾動(dòng)因子3(緩沖區(qū)堵塞)進(jìn)行說明,針對后續(xù)影響工序,采取調(diào)度方案時(shí)的目標(biāo)為工件完工時(shí)間和魯棒性測度和最小.對初始的調(diào)度方案局部調(diào)整,很快可以得到最優(yōu)目標(biāo)值為795.6,以使得出現(xiàn)擾動(dòng)時(shí)間對初始調(diào)度方案影響最小.如圖11所示:為應(yīng)對加工O62出現(xiàn)的緩沖區(qū)堵塞的擾動(dòng)時(shí)間,只是將O62后面的工序O13,O53采取了右移重調(diào)度,其他的加工工序保持不變,避免了緩沖區(qū)堵塞對O13,O53的影響,同時(shí)也確保了對初始調(diào)度計(jì)劃影響最小.

圖11 主動(dòng)調(diào)度方案甘特圖

6 結(jié) 論

在生產(chǎn)車間中,生產(chǎn)調(diào)度經(jīng)常會(huì)隨著擾動(dòng)的發(fā)生而變化.針對目前車間調(diào)度研究的薄弱環(huán)節(jié),本文研究了擾動(dòng)因子之間的關(guān)系,并借助基因生物學(xué)中的動(dòng)力學(xué)模型,研究擾動(dòng)因子之間的關(guān)系,以達(dá)到對擾動(dòng)事件的一個(gè)實(shí)時(shí)預(yù)測;采取主動(dòng)調(diào)度的方法,使得生產(chǎn)調(diào)度系統(tǒng)在不需要產(chǎn)生新的調(diào)度方案之前消除擾動(dòng),使生產(chǎn)調(diào)度系統(tǒng)趨于穩(wěn)態(tài).最后通過經(jīng)典的調(diào)度問題證明了方法的可行性.主要成果如下:1)建立了設(shè)備相關(guān)的隱性與顯性擾動(dòng)因子關(guān)系,且量化了隱性因子之間的耦合關(guān)系;2)針對實(shí)時(shí)調(diào)度問題的求解,設(shè)計(jì)了主動(dòng)調(diào)度的框架,引入了前后兩個(gè)不同單目標(biāo)進(jìn)行優(yōu)化調(diào)度,并用經(jīng)典的調(diào)度實(shí)例進(jìn)行了應(yīng)用分析.