基于模糊規(guī)劃的flowxxx作業(yè)調(diào)度模型

基于模糊規(guī)劃的flowxxx作業(yè)調(diào)度模型

0生產(chǎn)調(diào)度問題的解決生產(chǎn)計(jì)劃包括對(duì)生產(chǎn)任務(wù)和產(chǎn)品產(chǎn)量需求的指定系統(tǒng)，并制定相應(yīng)的生產(chǎn)計(jì)劃來完成生產(chǎn)任務(wù)。系統(tǒng)、全面、合理的生產(chǎn)計(jì)劃體系不僅有利于提高公司的綜合管理水平，而且有助于為公司帶來顯著的經(jīng)濟(jì)效益。在以往的研究工作中,絕大多數(shù)調(diào)度模型都是把一些參數(shù)如加工時(shí)間、交貨期等認(rèn)為是確定性的.但是在處理實(shí)際的問題時(shí),有些調(diào)度參數(shù)很難用精確的數(shù)值表示,往往是不確定的.在企業(yè)的實(shí)際生產(chǎn)過程和調(diào)度過程中,會(huì)存在各種各樣的不確定因素,例如每一道生產(chǎn)工序中產(chǎn)品的處理量、處理時(shí)間、設(shè)備的清洗時(shí)間、原材料或中間產(chǎn)品的裝載時(shí)間、傳輸時(shí)間、中間存儲(chǔ)單元的存儲(chǔ)量、中間產(chǎn)品的穩(wěn)定存放時(shí)間等,以及生產(chǎn)中原材料或能源的短缺,都可能是不確定的.此外,生產(chǎn)過程中往往會(huì)發(fā)生一些事先無法預(yù)料的不預(yù)期事件,如生產(chǎn)設(shè)備的損壞、儀器儀表的故障、操作的失誤等等,這些不確定的因素往往會(huì)導(dǎo)致生產(chǎn)調(diào)度方案無法按預(yù)定的目標(biāo)正常執(zhí)行,因此需要采取特殊的方法處理.自從Zadeh提出模糊集合的理論以來,模糊數(shù)學(xué)的方法在自動(dòng)控制、模式識(shí)別等許多領(lǐng)域中獲得了廣泛的應(yīng)用.由于實(shí)際環(huán)境中有許多情況無法用精確的數(shù)學(xué)模型來表示,而模糊數(shù)學(xué)則可以用來表示不確定的或用典型的數(shù)學(xué)方法無法表達(dá)的問題,模糊優(yōu)化在區(qū)域發(fā)展規(guī)劃、資源分配、生產(chǎn)計(jì)劃與調(diào)度等諸多領(lǐng)域中,有著更加廣闊的前途.由于調(diào)度問題的計(jì)算量與問題規(guī)模呈指數(shù)關(guān)系,傳統(tǒng)的數(shù)學(xué)規(guī)劃無法解決較大規(guī)模的調(diào)度問題,人們開始尋求新的優(yōu)化調(diào)度方法,以遺傳算法、模擬退火算法等為代表的計(jì)算智能技術(shù)廣泛用于調(diào)度問題的研究,取得了一定的成果.從理論上來說,模擬退火法具有全局漸進(jìn)收斂性,而實(shí)際上初始溫度和退火方式的選擇比較困難.初始溫度越高,退火速度越慢,時(shí)間過長;反之,時(shí)間會(huì)縮短,卻容易陷入局部極小點(diǎn).而免疫算法和遺傳算法同屬進(jìn)化算法,但遺傳算法的收斂方向無法控制,其進(jìn)化算子是隨機(jī)的,沒有利用可能獲取的附加信息.且在進(jìn)化過程中,進(jìn)化與退化都有可能出現(xiàn).而近年來出現(xiàn)的免疫算法(IA),是受生物免疫系統(tǒng)的啟發(fā)而設(shè)計(jì)的一種具有全局搜索能力的優(yōu)化方法,具有多樣化的特點(diǎn),并可以有選擇,有目的地利用待求問題中的一些特征信息來抑制退化現(xiàn)象.因此,本文在免疫算法的基礎(chǔ)上,提出一種模糊免疫調(diào)度算法來解決不確定條件下的flowshop(流水車間作業(yè))調(diào)度問題,對(duì)免疫算法解決調(diào)度問題進(jìn)行了一定的嘗試和探索.1確定處理時(shí)間的不確定性Flowshop調(diào)度是一個(gè)資源分配問題,可以這樣描述:多個(gè)產(chǎn)品在不同的加工設(shè)備上進(jìn)行加工,所有的產(chǎn)品都經(jīng)過相同的處理單元和處理路徑,但不同產(chǎn)品在同一處理單元上的處理時(shí)間可能不同,也稱為多產(chǎn)品(multiproduction)生產(chǎn)過程.本文采用三角模糊數(shù)x(xL,xM,xU)來描述處理時(shí)間的不確定性,其隸屬度函數(shù)定義為:μx(c)={0?c≤xLc-xLxΜ-xL?xL＜c≤xΜxU-cxU-xΜ?xΜ＜c≤xU0?c＞xU1.1具有模糊的操作開始時(shí)間N——加工產(chǎn)品的批量集.N={1,2,…,i,…,n},即待加工的產(chǎn)品總數(shù)為n個(gè);M——處理單元集合.M={1,2,…,j,…,m},即處理設(shè)備有m臺(tái);?Τij——處理時(shí)間.即產(chǎn)品i在處理單元j上的加工時(shí)間,它包括裝配時(shí)間、傳輸時(shí)間、卸載時(shí)間、加工時(shí)間以及清洗時(shí)間等,是變化的不確定量,采用模糊數(shù)表示;?Sij——產(chǎn)品i在處理單元j上的操作開始時(shí)間,由于產(chǎn)品處理時(shí)間的不確定性,這里的操作開始時(shí)間也是不確定的;?Cij——產(chǎn)品i在處理單元j上的操作完成時(shí)間,是一個(gè)模糊數(shù);?Sie——產(chǎn)品i的最后一道工序的操作開始時(shí)間;?Τie——產(chǎn)品i的最后一道工序所對(duì)應(yīng)的操作時(shí)間.1.2數(shù)學(xué)模型Flowshop問題中不同產(chǎn)品的生產(chǎn)路徑都是相同的,所有的產(chǎn)品都可以在零時(shí)刻投入生產(chǎn),但是必須滿足下面的約束條件1第1道工序-1道工序見表1?Sij≥?Si(j-1)+?Τi(j-1)i∈Ν?j∈Μ(1)式(1)表示產(chǎn)品i的第j道工序必須在第j-1道工序完成后才能開始,即任何一道工序的加工開始時(shí)間必須大于等于該產(chǎn)品上一道工序的結(jié)束時(shí)間.2處理單元處理單元法?Sij≥?S(i-1)j+?Τ(i-1)ji∈Ν?j∈Μ(2)式(2)表示一個(gè)產(chǎn)品的生產(chǎn)必須在前一個(gè)產(chǎn)品在某一處理單元處理完畢后才能進(jìn)入該處理單元,即任一時(shí)刻該處理單元不能同時(shí)處理兩個(gè)不同的產(chǎn)品.3調(diào)度目標(biāo)的確定?Sij≥0i∈Ν?j∈Μ(3)式(3)說明產(chǎn)品的可以從零時(shí)刻開始加工.此外,所有產(chǎn)品在每個(gè)加工單元上的操作次序相同,產(chǎn)品之間沒有優(yōu)先性,一個(gè)設(shè)備不能同時(shí)處理多種產(chǎn)品,并且一種產(chǎn)品不能同時(shí)為多個(gè)設(shè)備處理,產(chǎn)品的加工過程中不允許中斷.在此基礎(chǔ)上可以有不同的優(yōu)化目標(biāo),如產(chǎn)品的生產(chǎn)周期最短、產(chǎn)品的流經(jīng)時(shí)間最短、產(chǎn)品交貨延誤時(shí)間最短、加工設(shè)備利用率最大、產(chǎn)品平均等待時(shí)間最短、加工制造費(fèi)用最低等,本文采用生產(chǎn)周期最短來作為調(diào)度目標(biāo),即Μin(makespam)=Μin(Μɑx?Sie+?Τie)1.3模糊極大x目標(biāo)函數(shù)的生成根據(jù)模糊數(shù)學(xué)的有關(guān)定義和擴(kuò)展定理,定義了兩種用于模糊調(diào)度問題的模糊運(yùn)算,用于求解不確定情況下的生產(chǎn)調(diào)度問題.設(shè)兩個(gè)模糊數(shù)為?x=(xL?xΜ?xU)和?у=(уL?уΜ?уU)模糊加法?x+?у=(xL+уL?xΜ+уΜ?xU+уU)模糊極大?x∨?у=(xL∨уL?xΜ∨уΜ?xU∨уU)由上式,可推知所求解的目標(biāo)函數(shù)Min(makespan):11j.1?Sij=0??Cij=?Sij+?Τij=?Τij(4)2當(dāng)i.1，j.1時(shí)?Sij=?Ci(j-1)?Cij=?Sij+?Τij=?Ci(j-1)+?Τij(5)3當(dāng)i.1和j.1時(shí)?Sij=?C(i-1)j??Cij=?Sij+?Τij=?C(i-1)j+?Τij(6)4當(dāng)i為1，j為1時(shí)?Sij=mɑx(?C(i-1)j??Ci(j-1))?Cij=?Sij+?Τij(7)5cie的理想解Min(makespan)=Μin(Μax?Sie+?Τie)=Μin(?Cie)=Μin(CLie?CΜie?CUie)(8)則模糊目標(biāo)規(guī)劃問題就化為多目標(biāo)規(guī)劃問題,由于CLie,CMie,CUie分別與模糊處理時(shí)間TLij,TMij,TUij分別相關(guān),求出多目標(biāo)規(guī)劃問題的最優(yōu)解即得到模糊規(guī)劃問題的解,它們分別表示規(guī)劃問題的最劣解、最可能解和最優(yōu)解,引用文獻(xiàn)中的“中間值最大隸屬度”的算法,將上述的多目標(biāo)規(guī)劃問題轉(zhuǎn)化為清晰的單目標(biāo)規(guī)劃模型,然后求解.首先,采用Zimmermann的方法求得?Cie的正、負(fù)理想解CΡΙSie和CΝΙSie,即CΡΙSk(k=1,2,3)和CΝΙSk(k=1,2,3)分別為:CΡΙS1=MinCLie,CΡΙS2=MinCMie,CΡΙS3=MinUie,CΝΙS1=MɑxCLie,CΝΙS2=MɑxCMie,CΝΙS3=MɑxCUie其中,CΡΙSie和CΝΙSie分別表示對(duì)?Cie單獨(dú)求解的情況下,可能取得的最優(yōu)解和最劣解,并由此確定對(duì)于?Cie的滿意程度的隸屬函數(shù)μCk(x),(k=1,2,3),即μCk(x)={0x＞CΝΙSiex-CΡΙSieCΝΙSie-CΡΙSie?CΡΙSie≤x≤CΝΙSie1x＜CΡΙSiek=1?2?3(9)然后,在上述基礎(chǔ)上的多目標(biāo)規(guī)劃模型可以轉(zhuǎn)化為單目標(biāo)規(guī)劃模型:Mɑx{ΓαL+(1-Γ)αU}s.t.αL≤μCk≤αU,k=1,2,3αU≤μC2αL,αU∈(10)其中,μCk(x),(k=1,2,3)是?Cie的滿意隸屬函數(shù),而αL是由μCk(x),(k=1,2,3)中的最小值確定的,αU是由μCk(x),(k=1,2,3)中的最大值確定的.在實(shí)際的決策過程中,常希望目標(biāo)值能在最可能的情況下具有最高的滿意程度,而不是在最劣和最優(yōu)情況下取得最大的滿意度,在最可能情況下的滿意度卻較小.所以在上述模型中,令μC2(x)即最可能情況下的滿意程度取得隸屬函數(shù)中的最大值,而最小值則在最劣和最優(yōu)情況下產(chǎn)生,這樣既考慮不同情況下的隸屬度,又能使結(jié)果在實(shí)際實(shí)施中有較好的適應(yīng)度.并且為了便于綜合決策,在模型中采用補(bǔ)與因子Γ來反映決策者在積極與消極決策間的傾向,Γ值越小,則αU在目標(biāo)函數(shù)中所占的比例越大,決策越積極;反之,則決策越消極,彌補(bǔ)了單純極大極小運(yùn)算無補(bǔ)的缺點(diǎn).2抗體的編碼與檢測(cè)免疫算法(immunealgorithm)是借鑒高度進(jìn)化、復(fù)雜的生物免疫系統(tǒng)的特點(diǎn)形成的一種演化算法.免疫算法最大的特點(diǎn)就是免疫記憶特性、抗體的自我識(shí)別能力和免疫的多樣性.它的自組織、自學(xué)習(xí)能力和強(qiáng)大的信息處理能力使得它在智能控制、模式識(shí)別、優(yōu)化設(shè)計(jì)和機(jī)器學(xué)習(xí)等很多領(lǐng)域都得到有效的應(yīng)用.它模擬生物抗體濃度自適應(yīng)調(diào)節(jié)的過程,即根據(jù)抗體的濃度自適應(yīng)地調(diào)節(jié)搜索方向和解群的分布,從而大大提高算法克服局部收斂的能力,可以將其應(yīng)用于調(diào)度問題中.下面是本文采用的改進(jìn)的模糊免疫調(diào)度算法(improvedimmunealgorithm,IIA)的主要內(nèi)容:由于調(diào)度問題是一類有序問題(sequencingproblemororderingproblem),即目標(biāo)函數(shù)值不僅與表示解的數(shù)值有關(guān),而且與其在編碼字符串中的位置有關(guān).對(duì)于這類問題,二進(jìn)制的編碼方法不直觀也增加了編碼與譯碼的時(shí)間與難度,所以采用字符編碼的方法來表示抗體.根據(jù)flowshop調(diào)度問題的特性,即同順序的生產(chǎn)方式,采用字符編碼表示加工產(chǎn)品的序號(hào),即以每個(gè)字符代表一個(gè)加工產(chǎn)品,編碼中每個(gè)產(chǎn)品只能出現(xiàn)一次,字符在編碼中出現(xiàn)的順序就是加工產(chǎn)品的生產(chǎn)順序.步驟1產(chǎn)生初始抗體.抗體和抗原分別對(duì)應(yīng)目標(biāo)函數(shù)和可行解,抗體是由不同的基因個(gè)體組成的.如果記憶細(xì)胞庫中的抗體為空,則初始抗體隨機(jī)產(chǎn)生;否則,從記憶細(xì)胞庫中提取記憶細(xì)胞,和產(chǎn)生的抗體一起組成抗體群;步驟2對(duì)抗體群中的各個(gè)抗體進(jìn)行評(píng)價(jià).免疫系統(tǒng)通過識(shí)別抗原的基因來產(chǎn)生不同的抗體,再通過識(shí)別抗體的基因來調(diào)節(jié)抗體的濃度.而抗體與抗原、以及抗體之間的匹配程度是用親和力描述的,所以首先計(jì)算親和力,然后計(jì)算抗體群中抗體的濃度和期望繁殖率,在此采用信息熵來表示抗體的多樣性;步驟3記憶單元更新.在上一步的基礎(chǔ)上,將與抗原的親和力較大的抗體加入到記憶單元中.由于記憶單元的數(shù)目有限,所以在記憶單元中用新加入的抗體取代與其親和力大的原有抗體;步驟4抗體的促進(jìn)和抑制.根據(jù)抗體群中每個(gè)抗體的期望繁殖率排序,期望繁殖率低的抗體將受到抑制.因此,與抗原親和力大的抗體和低密度的抗體生存幾率較大,得到促進(jìn),而高密度的抗體將受到抑制,體現(xiàn)了控制機(jī)制的多樣性;步驟5解群體的更新.對(duì)抗體群進(jìn)行選擇、交叉、變異操作可以得到新的群體,同時(shí)從記憶庫中取出記憶抗體,共同構(gòu)成新的解群體.這里采用2點(diǎn)交叉操作,即在一個(gè)父代個(gè)體中隨機(jī)選擇2點(diǎn)為交叉點(diǎn),2個(gè)交叉點(diǎn)將該個(gè)體分為3部分,交叉點(diǎn)兩邊的產(chǎn)品由父代遺傳給子代,其余的產(chǎn)品從另一個(gè)父代個(gè)體中獲得,但是該產(chǎn)品必須保證與已有產(chǎn)品不同,且順序與第2個(gè)父代相同.而變異操作是隨機(jī)在父代個(gè)體中選擇兩點(diǎn),作為變異點(diǎn),兩個(gè)變異點(diǎn)將父代分為了3部分,將變異點(diǎn)之間的產(chǎn)品依次后移一位,移出的一位填補(bǔ)前面的空白位,2點(diǎn)外的各位保持不變.通過這樣的操作,可以得到可行的產(chǎn)品序列,不會(huì)出現(xiàn)無效情況,即不合理的調(diào)度方案;步驟6如果達(dá)到終止條件,則結(jié)束運(yùn)算;否則,轉(zhuǎn)向步驟2執(zhí)行.3解群體的目標(biāo)值和調(diào)度結(jié)果在仿真試驗(yàn)中,以10個(gè)加工產(chǎn)品、5個(gè)處理單元的調(diào)度問題為例,表1是產(chǎn)品的不確定處理時(shí)間,用模糊數(shù)表示.表中括號(hào)內(nèi)的3個(gè)數(shù)分別表示加工時(shí)間為三角模糊數(shù)的3個(gè)端點(diǎn)的加工時(shí)間值,即依次表示了可能的最小加工時(shí)間、最可能加工時(shí)間和可能的最大加工時(shí)間.算法中解群體的規(guī)模popsize=40,記憶庫的規(guī)模memsize=20,最大的迭代次數(shù)gen-num=150,對(duì)問題進(jìn)行了多次仿真,當(dāng)Γ=0.3時(shí),得到的結(jié)果如圖1,圖2所示.圖1中,上面的曲線是解群體中的最優(yōu)值曲線,表示每代解群體中的最優(yōu)目標(biāo)值;中間曲線是記憶抗體目標(biāo)平均值曲線,對(duì)應(yīng)的是每次迭代運(yùn)算時(shí)記憶庫中所有記憶抗體個(gè)體目標(biāo)值的平均值;下面的曲線是解群體中抗體的目標(biāo)平均值曲線,表示每次迭代運(yùn)算所得到的目標(biāo)平均值.從圖中看到,隨著算法的不斷演化,目標(biāo)的最優(yōu)值和解群體的平均值越來越趨向于最優(yōu)并趨向穩(wěn)定,說明了算法的收斂性.由此可以確定對(duì)應(yīng)的產(chǎn)品的加工順序,以及產(chǎn)品的開始加工時(shí)間和完成時(shí)間,圖2就是調(diào)度結(jié)果的甘特圖.采用本文提出的算法,對(duì)于不同Γ情況下的調(diào)度結(jié)果見表2:由表中可以看出,Γ越小,雖然得到的三個(gè)makespan值都一樣,但目標(biāo)函數(shù)值越大,越趨向于1,其調(diào)度結(jié)果越好,決策越積極;反之,得到的目標(biāo)函數(shù)值越小,調(diào)度結(jié)果越差,決策越保守.當(dāng)Γ不斷從小到大,目標(biāo)函數(shù)值不斷下降,進(jìn)化曲線趨向于收斂,在各種情況下,算法都表現(xiàn)出了良好的收斂性,調(diào)度結(jié)果都具有較大的滿意度.為了驗(yàn)證算法的有效性,以10×5規(guī)模的調(diào)度問題為例,在解群體的規(guī)模、交叉率和變異率、以及一些參數(shù)的設(shè)置相同的情況下,用上述算法(IIA)和遺傳算法(