国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

設備故障條件下柔性作業(yè)車間重調(diào)度方法

2018-10-16 05:50:46博,張琳,張
計算機工程與應用 2018年19期
關鍵詞:右移工序工件

包 博,張 琳,張 搏

空軍工程大學 防空反導學院,西安 710051

1 引言

在實際生產(chǎn)環(huán)境中,各類不確定因素,如:加工設備故障、緊急件加入、物料供應短缺等,會導致車間工況變化,使得原調(diào)度方案不再可行,進而需要重新制定調(diào)度方案以進行后續(xù)生產(chǎn),即重調(diào)度[1-2]。設備故障是生產(chǎn)中最為普遍的一類不確定因素,針對車間調(diào)度中的設備隨機故障問題,學者們提出了許多行之有效的動態(tài)調(diào)度方法[3-5]。文獻[6]針對調(diào)度過程中的設備故障干擾,基于滾動時域優(yōu)化框架,提出改進的事件和周期混合驅(qū)動的動態(tài)調(diào)度方法。文獻[7]將多代理系統(tǒng)、遺傳算法與滾動窗口法有機地結合,提出了一種車間動態(tài)調(diào)度方法。文獻[8]分析車間生產(chǎn)環(huán)境復雜和生產(chǎn)過程中各種隨機擾動,提出車間動態(tài)重調(diào)度優(yōu)化方法。重調(diào)度方法在動態(tài)調(diào)度中顯示了較好的效果,重調(diào)度方法、策略逐漸成為了車間調(diào)度問題中的研究重點。文獻[9]針對機器故障條件下的混合流水車間重調(diào)度問題,提出了一種新的重調(diào)度模型。文獻[10]在開放式車間中,針對機器持續(xù)不可用干擾,提出了三種特定的重調(diào)度策略。文獻[11]提出了插入重調(diào)度和完全重調(diào)度策略,有效縮短了車間的加工時間。但相關研究主要存在兩方面不足:首先,重調(diào)度必然導致調(diào)度成本的增加,已有方法往往忽視了重調(diào)度成本而僅側(cè)重于調(diào)度效率。其次,已有重調(diào)度方法在運用多種重調(diào)度策略時,通常先選擇重調(diào)度策略進而在此策略下制定重調(diào)度方案,而這種方式難以確保重調(diào)度策略所得方案能夠適應該擾動景況。

針對設備隨機故障條件下的柔性作業(yè)車間調(diào)度問題,本文系統(tǒng)分析重調(diào)度成本,綜合運用部分右移重調(diào)度策略以及完全重調(diào)度策略,從而提出一種重調(diào)度方法。采用免疫遺傳算法實現(xiàn)模型的求解計算,并結合算例驗證方法的有效性。

2 問題描述

柔性作業(yè)車間調(diào)度,可簡單描述為:若干工件Ji(i=1,2,…,n)在設備 Mj(j=1,2,…,m)上進行加工;Oik表示工件的第k(k=1,2,…,l)道工序;工件可選擇加工設備 Mj開展工序Oik,表示為 pijk,Tijk表示 pijk對應的處理時間;工件嚴格依照工藝路線進行加工,每道工序可選擇若干設備執(zhí)行操作。在滿足特定約束條件下,需將工件的全部工序合理安排至機器設備上,并使調(diào)度方案達到最優(yōu)性能指標[12]。

結合上述分析,以最小化完工時間為目標,柔性作業(yè)車間調(diào)度問題可描述為數(shù)學模型:

其中,式(1)為目標函數(shù),eik是工序Oik的結束時刻,開始時刻為sik;式(2)表示每道工序僅選擇一臺設備執(zhí)行操作,xijk為0/1變量,為1時表示工序Oik選擇了機器Mj執(zhí)行操作;式(3)表示工序自身的時間約束關系;式(4)、(5)分別表示工件在工序上的時間約束和機器設備上各工序的時間約束,其中siu、eiu分別表示設備Mj上第u道工序的開始、結束時刻。

在實際的車間生產(chǎn)調(diào)度中,設備故障將使得生產(chǎn)無法按照原有的調(diào)度計劃繼續(xù)進行。設備故障的發(fā)生表現(xiàn)出隨機性,其隨機性可以從三個方面進行描述:故障發(fā)生設備的隨機性;故障發(fā)生時刻的隨機性;故障持續(xù)時間的隨機性。

3 重調(diào)度方法

重調(diào)度是在擾動發(fā)生后,重新編制調(diào)度方案,對調(diào)度計劃進行局部或全局調(diào)整。針對設備隨機故障,重調(diào)度方法要求能夠適應各種景況的設備故障干擾,在不同程度擾動下保證重調(diào)度效果。另外,在重調(diào)度過程中需要考慮調(diào)度成本的合理性。本文提出重調(diào)度方法,首先基于工件信息生成初始調(diào)度方案,當擾動發(fā)生,輸入擾動信息并通過重調(diào)度生成新方案。重調(diào)度的關鍵步驟包括構建重調(diào)度成本函數(shù)、設計重調(diào)度策略等[13]。

3.1 重調(diào)度成本

在重調(diào)度方案中,工序的開始加工時間偏移、工序加工設備的調(diào)整和以及相同工序在不同設備上的操作時間不相同,造成的物料調(diào)動量增加以及存儲時間變動等,使得重調(diào)度成本增加。本文基于工件與設備兩個層面,從時間偏差的角度,建立重調(diào)度成本函數(shù)。

提出假設:假設預調(diào)度方案為Q,即正在執(zhí)行的調(diào)度方案。擾動后經(jīng)重調(diào)度生成的調(diào)度方案為Q′,此時并不表示為最終所選擇的重調(diào)度方案。Q、Q′的任務完成時間分別表示為Z、Z′,工件工序Oik的開始時刻分別表示為 sik、s′ik,結束時刻分別表示為 eik、e′ik,工序Oik的工時分別為tik、t′ik,工序Oik選擇的操作設備分別表示為 pijk、p′ijk。

(1)工序開始時間偏差成本

工序由于開始時間的提前或延后,導致物料準備時間產(chǎn)生變動,使得運輸、儲存成本增加,因此采用開始時間偏差成本對此類重調(diào)度成本進行描述。

工序Oik在新舊方案中的開始加工時間偏差為:

工件總的偏差成本表示為:

(2)工時偏差成本

工時的增加,導致人工作業(yè)時間、設備使用時間增加,因此采用工序工時偏差成本對此類重調(diào)度成本進行描述。

工時增加量為:

工時偏差成本表示為:

(3)設備變更成本

工件工序操作設備的變更,將增加人力勞動及調(diào)運成本,因此采用設備變更成本對此類重調(diào)度成本進行描述。

工序Oik變更,則表示為:

設備變更成本表示為:

綜上,重調(diào)度成本函數(shù)表示為:

其中,ω1、ω2、ω3為3類重調(diào)度成本的權重系數(shù),ω1+ω2+ω3=1。權重系數(shù)表示3個子成本所占重調(diào)度成本的比重,權重系數(shù)由專家采用“德爾菲法”確定,經(jīng)過調(diào)查、征詢意見、匯總綜合、反饋、再調(diào)查這一反復過程。

重調(diào)度目標函數(shù)綜合考慮任務完工時間增量、重調(diào)度成本兩方面,表示為:

其中,有 μ1+μ2=1,μ1、μ2為兩類指標的權重系數(shù),同樣采用“德爾菲法”進行確定。

3.2 重調(diào)度策略

重調(diào)度將部分重調(diào)度策略與完全重調(diào)度策略相結合,利用兩者優(yōu)勢,以在不同擾動景況下,保證重調(diào)度方案的先進性。

3.2.1完全重調(diào)度

完全重調(diào)度是指對故障發(fā)生后的所有工件進行重新調(diào)度安排,它與靜態(tài)調(diào)度的根本區(qū)別在于每個機器的開始加工時間不同。完全重調(diào)度可保證重調(diào)度方案的優(yōu)化性,但會隨之產(chǎn)生額外較大的重調(diào)度成本。

完全重調(diào)度的基本步驟為:

步驟1確定重調(diào)度工序集合。重調(diào)度工序集合包含未開始的所有工序,以及因為設備故障導致中斷的工序。

步驟2確定每個機器的開始加工時間,機器的開始加工時間為故障發(fā)生后該機器的最早空閑時間。故障發(fā)生時,如果第 j臺機器正好處于空閑,則該機器的開始加工時間為0;如果第 j臺機器正在加工某道工序,且該工序的剩余加工時間為t,則該機器的開始加工時間為t。

步驟3基于優(yōu)化算法,對重調(diào)度工序集合中的工序進行優(yōu)化調(diào)度,形成重調(diào)度方案。

3.2.2部分右移重調(diào)度

部分右移重調(diào)度是指對受到設備故障直接或間接影響的工序執(zhí)行調(diào)整。該策略只對受影響工序的開始時間進行推遲處理,不改變工序次序和工序?qū)牟僮髟O備,避免了完全重調(diào)度帶來的額外成本過度增大的問題,但同時存在工序開始時間移動量較大的問題。

部分右移重調(diào)度的基本步驟為:

步驟1確定故障設備位置,并預估故障修復時間。

步驟2基于“二元分支”機理,從受到直接干擾的工序開始,分析確定出預調(diào)度方案中直接或間接的受影響的工序集合。

步驟3逐步后移調(diào)整工序計劃,直到滿足各類時間約束條件,形成重調(diào)度方案。

部分右移重調(diào)度具體操作方法可參見文獻[10]。

3.3 重調(diào)度流程

在整個調(diào)度過程中,預調(diào)度方案生成階段以最小化完成時間作為目標,而在重調(diào)度方案生成階段中,由于考慮了方案變動帶來的調(diào)度成本增加,因而兼顧最小化完成時間和最小化重調(diào)度成本兩方面目標。為保證重調(diào)度方案的質(zhì)量,重調(diào)度同時采用部分右移重調(diào)度和完全重調(diào)度兩種策略,在兩者形成的方案中選擇較優(yōu)方案。重調(diào)度流程如圖1所示。

圖1 重調(diào)度方法流程

重調(diào)度策略的基本步驟:

步驟1以最小化任務完成時間作為目標函數(shù)1,如式(1),基于智能優(yōu)化算法產(chǎn)生預調(diào)度方案。

步驟2依照預調(diào)度方案進行生產(chǎn),當擾動發(fā)生,轉(zhuǎn)至步驟3;否則,依照預調(diào)度方案繼續(xù)生產(chǎn)。

步驟3人工輸入擾動信息,包括故障位置、故障時刻、預計故障修復時間。

步驟4采用部分右移重調(diào)度形成方案A,并計算該方案對應目標函數(shù)2的函數(shù)值,重調(diào)度目標函數(shù)2如式(13);同時,依據(jù)目標函數(shù)2,采用完全重調(diào)度策略,基于智能優(yōu)化算法形成重調(diào)度方案B;比較重調(diào)度方案A、B的重調(diào)度目標函數(shù)值大小,選取兩者中較優(yōu)的方案作為重調(diào)度方案,更新預調(diào)度方案,轉(zhuǎn)至步驟2。

4 免疫遺傳算法

柔性作業(yè)車間調(diào)度問題是一類典型的NP難問題,學者們針對此類問題提出了許多求解算法,如禁忌搜索算法[14]、遺傳算法[15]、蟻群算法[16]、粒子群算法[17]等。遺傳算法在解決同類問題上顯示出較好的適用性,但存在迭代后期由于個體多樣性缺失從而易陷入局部最優(yōu)的問題。為克服遺傳算法在計算中的早熟收斂問題,提高算法的全局收索能力,本文將免疫系統(tǒng)與遺傳算法相結合,形成免疫遺傳算法,對問題進行求解計算。

基本流程如圖2所示。

4.1 染色體編碼

染色體同時對工件的工序加工順序和機器設備兩方面信息進行描述。本文采用雙層編碼結構對染色體進行編碼,染色體前半部分描述裝備的工序加工順序,后半部分描述工序所對應的加工設備。設染色體如:

圖2 算法流程

其中,xk(k=1,2,…,N)為工序的序號,yk(k=1,2,…,N)為工序所對應的加工設備。

染色體解碼需依據(jù)工序可選設備信息以及工序工時信息。對于染色體[1,2,1,2,3,3,2,1,3,3,1,2],不考慮具體工序工時,依據(jù)解碼規(guī)則,解碼過程如圖3所示。

圖3 染色體解碼示意圖

4.2 適應度函數(shù)

在預調(diào)度方案生成階段,目標函數(shù)為最小化任務完成時間。而在重調(diào)度方案生成階段中,目標函數(shù)綜合任務完成時間偏差以及重調(diào)度成本。

預調(diào)度方案制定時,依據(jù)目標函數(shù)1,適應度函數(shù)分別表示為:

重調(diào)度方案制定時,依據(jù)目標函數(shù)2,適應度函數(shù)分別表示為:

由于在初預調(diào)度方案制定、重調(diào)度方案制定中均采用免疫遺傳算法,區(qū)別僅在于適應度函數(shù),因此在后續(xù)步驟操作設計中,適應度函數(shù)均用 fv表示。

4.3 親和力、抗體濃度

抗體與抗原之間的親和力用于表示抗體對抗原的識別程度,針對本文中車間調(diào)度問題,親和力定義為:

相似度是指抗體與其他抗體的相似度。本文采用T0位連續(xù)方法計算抗體與抗體間的親和力,首先確定一個親和度判定閾值T0,當兩個個體有超過T0位或者連續(xù)T0位的編碼相同,則認為這兩種個體“相似”,否則認為“不相似”。此處借鑒變形的T0位連續(xù)方法來計算抗體間的親和度,即:

其中,ku,v為抗體u與抗體s中相同的位數(shù),L為抗體長度。

抗體的濃度是指群體中相似抗體所占的比例,表示為:

期望繁殖概率由親和力Av與抗體濃度Cv共同決定,表示為:

其中,α為0-1間常數(shù)。由上式可知,染色體適應度越好,期望繁殖概率越大;個體濃度越大,則期望繁殖概率越小。

4.4 選擇、交叉、變異

選擇操作采用輪盤賭的方法,依據(jù)概率選擇出染色體,染色體被選擇的概率為期望繁殖概率,如式(19)。

交叉操作可分為兩步:對兩個染色體在交叉點處進行基因互換;對交叉后的染色體進行局部調(diào)整,使得染色體滿足約束條件。交叉操作如:對兩個染色體進行交叉處理,假設交叉位置為3。在對交叉點處進行基因互換后,出現(xiàn)某些工件工序增加、或者減少的情況,對此,把工件工序多出的操作變?yōu)槿笔Р僮?,染色體后半部分不變,從而避免產(chǎn)生非法染色體:

變異操作首先在前半部分隨機選擇兩個變異點,然后將前半部分工件工序碼和后半部分機器設備碼的對應位置上的基因進行互換。例如,對某染色體選擇在位置2、3上進行交叉變異操作:

5 算例分析

假設某生產(chǎn)車間利用5組機器設備,對6個工件進行加工處理,每個工件均有5道工序。工件工序的可選操作設備以及對應的加工時間如表1所示([可選設備序號]/[對應時間(天)])。依據(jù)表中信息,制定調(diào)度方案。

表1 工序可選機器及對應時間

5.1 參數(shù)設置及生成預調(diào)度方案

采用MATLAB編碼完成上述調(diào)度算法,設置種群數(shù)為40,遺傳代數(shù)為50,交叉率為0.5,變異率為0.4,記憶庫容量為10,閾值T0為0.9,期望繁殖概率中參數(shù)α為0.5。運行該算法,得到一套預調(diào)度方案,如圖4甘特圖所示,圖中“a-b”表示裝備a的第b道工序。

圖4 預調(diào)度方案

從圖中可以清晰地了解到各道工序?qū)臋C器設備,以及開始、結束時間。在未發(fā)生擾動情況下,加工生產(chǎn)依照圖中調(diào)度方案執(zhí)行。

5.2 生成重調(diào)度方案

基于圖4預調(diào)度方案,假設第20天機器2上出現(xiàn)故障,工序O33中斷。專家預估故障修復時間為8天,現(xiàn)需要執(zhí)行重調(diào)度得到重調(diào)度方案。

采取本文重調(diào)度方法,依據(jù)“德爾菲法”確定重調(diào)度成本函數(shù)中指標權重 (ω1,ω2,ω3)=(0.1,0.4,0.5),重調(diào)度目標函數(shù)中指標權重(μ1,μ2)=(0.3,0.7),其他參數(shù)設置如5.1節(jié)不變。得到重調(diào)度方案如圖5,其中完全重調(diào)度的尋優(yōu)結果曲線如圖6。

圖5 重調(diào)度方案

圖6 重調(diào)度尋優(yōu)收斂曲線

在故障發(fā)生時刻,未開始進行處理的工件工序參與了重調(diào)度。從圖中結果可以看出,部分工序所選擇操作的機器發(fā)生了變化,由此可以判斷,在重調(diào)度中完全重調(diào)度所得到的調(diào)度結果優(yōu)于部分右移重調(diào)度的調(diào)度結果,因而該方法自動選擇了完全重調(diào)度策略所得到的重調(diào)度方案。

為了驗證上述分析判斷,即重調(diào)度中完全重調(diào)度所得到的調(diào)度結果優(yōu)于部分右移重調(diào)度的調(diào)度結果,依據(jù)部分右移重調(diào)度策略的算法規(guī)則得到相應的重調(diào)度方案,并計算重調(diào)度目標函數(shù)值。重調(diào)度方案甘特圖如圖7所示。

圖7 部分右移重調(diào)度方案

從圖中可以看出,工件工序并未改變操作設備,在開始、結束時間上發(fā)生了不同程度的后移。對比圖5可以發(fā)現(xiàn),采用右移重調(diào)度,完工時間推遲了8天;而采用完全重調(diào)度,完工時間僅推遲了2天,因而在完成時間這一指標上完全重調(diào)度所得方案表現(xiàn)較好。通過計算,部分右移重調(diào)度相應的重調(diào)度目標函數(shù)值為5.47,大于完全重調(diào)度相應的重調(diào)度目標函數(shù)值。分析可知,雖然完全重調(diào)度所得方案在執(zhí)行成本上表現(xiàn)較差,但綜合兩方面指標進行計算,完全重調(diào)度所得方案表現(xiàn)更優(yōu)。

5.3 設備故障景況分析

故障不同發(fā)生時間、不同修復時長都將對重調(diào)度效果造成影響,為探究不同擾動景況下重調(diào)度方法中兩種策略的表現(xiàn),通過對比實驗對兩種策略進行比較分析。

設置4組故障發(fā)生時間(5,15,25,35(天)),4組故障修復時間(2,4,6,8(天))。在16種景況下,分別采用完全重調(diào)度策略和部分右移重調(diào)度策略進行重調(diào)度實驗,分別計算出重調(diào)度目標函數(shù)值。16種景況均隨機重復10次,并計算平均值。

從圖8結果中可以看出,在晚期、微小擾動下,部分右移重調(diào)度策略往往得到更好的重調(diào)度結果,而在早期、擾動較大情況下,完全重調(diào)度通常能得到較好重調(diào)度結果。作為本文方法中的兩種策略,綜合使用兩種方法,彌補了單一方法的弊端,能夠?qū)崿F(xiàn)不同擾動情境下,盡可能保證重調(diào)度方案的先進性。

圖8 兩種策略重調(diào)度結果

6 結束語

本文針對設備隨機故障條件下的柔性作業(yè)車間調(diào)度問題進行了研究,提出了一種基于組合策略的重調(diào)度方法。在重調(diào)度方法中,對重調(diào)度成本進行了詳細分析并建立重調(diào)度成本函數(shù),綜合運用了兩種重調(diào)度策略,結合免疫算法對遺傳算法進行了改進,用于模型的求解計算。通過算例分析,驗證了方法的可行性和有效性。結果表明,不同擾動景況下各種策略表現(xiàn)存在差異,本文所提出方法能夠更好適應多種景況。在后續(xù)研究中,需要進一步挖掘設備故障的重調(diào)度策略,橫向上對其他不確定事件的重調(diào)度方法進行研究。

猜你喜歡
右移工序工件
120t轉(zhuǎn)爐降低工序能耗生產(chǎn)實踐
昆鋼科技(2022年2期)2022-07-08 06:36:14
華容道玩法大解密
大理石大板生產(chǎn)修補工序詳解(二)
石材(2020年4期)2020-05-25 07:08:50
土建工程中關鍵工序的技術質(zhì)量控制
考慮非線性誤差的五軸工件安裝位置優(yōu)化
太極拳養(yǎng)生八式(上)
少林與太極(2018年8期)2018-08-26 05:53:58
三坐標在工件測繪中的應用技巧
人機工程仿真技術在車門裝焊工序中的應用
焊接殘余形變在工件精密裝配中的仿真應用研究
焊接(2015年9期)2015-07-18 11:03:52
C語言位運算中鮮為人知的事
軟件工程(2014年5期)2014-09-24 11:53:38
鹿邑县| 黑龙江省| 梁平县| 永仁县| 嘉禾县| 云林县| 吉隆县| 慈溪市| 白朗县| 二连浩特市| 广南县| 墨江| 柏乡县| 上饶市| 新邵县| 海阳市| 柳江县| 江安县| 景宁| 和政县| 阆中市| 田林县| 蓬莱市| 定州市| 肃南| 青海省| 宁阳县| 泽州县| 井研县| 南昌市| 礼泉县| 喀喇沁旗| 青海省| 南陵县| 祁连县| 如皋市| 巴青县| 赣榆县| 朝阳县| 静乐县| 霍城县|