改進(jìn)的粒子群算法在動(dòng)態(tài)車間調(diào)度問題研究

改進(jìn)的粒子群算法及其在Job-Shop問題中的應(yīng)用ImprovedParticleSwarmOptimizationandItsApplicationin第2章作業(yè)車間調(diào)度2.1引言作業(yè)車間的調(diào)度問題是工業(yè)生產(chǎn)當(dāng)中原料采購、生產(chǎn)制造、企業(yè)管理的核心環(huán)節(jié)，高效的作業(yè)車間調(diào)度系統(tǒng)已成為智能化工業(yè)不可缺少的部分。由于企業(yè)生產(chǎn)制造不比實(shí)驗(yàn)室，面臨更多的不可抗力因素，并且作業(yè)車間調(diào)度問題本身屬于不確定問題，很難找到最為有效、唯一的調(diào)度算法求解車間調(diào)度問題。故此，促使眾多科研人員不斷更新新的更加智能優(yōu)化算法用來求解車間調(diào)度問題，降低企業(yè)成本，提高企業(yè)效率，增強(qiáng)企業(yè)競爭力。2.2車間調(diào)度問題2.2.1調(diào)度問題分類根據(jù)以往的研究結(jié)果，大體可以把車間調(diào)度問題分為兩類：（1）根據(jù)調(diào)度方法不同，可以分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度。靜態(tài)調(diào)度中調(diào)度的任務(wù)是離線進(jìn)行分配的，即在工件在加工之前，先把調(diào)度任務(wù)分配好，加工時(shí)間和工序在加工過程中不允許改變，加工機(jī)器不允許故障，是在一種理想情況下進(jìn)行的調(diào)度任務(wù)；動(dòng)態(tài)調(diào)度中調(diào)度的任務(wù)是線上進(jìn)行的，可以根據(jù)加工實(shí)際情況調(diào)整加工順序，例如增加訂單、取消訂單、機(jī)器故障等缺陷，動(dòng)態(tài)調(diào)度更加符合實(shí)際生產(chǎn)需求。（2）根據(jù)加工工序不同，可以分為流水車間調(diào)度和作業(yè)車間調(diào)度。流水車間調(diào)度是指多個(gè)工件在多臺(tái)機(jī)器上加工，其每個(gè)工件的每道工序相同；作業(yè)車間調(diào)度是在流水車間調(diào)度基礎(chǔ)上，每個(gè)工件的每道工序不同，作業(yè)車間調(diào)度更加符合實(shí)際生產(chǎn)需求。2.2.2問題描述作業(yè)車間調(diào)度問題可以看成是以時(shí)間為參考量的最佳性能指標(biāo)集。具體描述如下：一批N個(gè)待加工工件在M臺(tái)機(jī)器上準(zhǔn)備進(jìn)行加工，在一定的限制條件下，通過調(diào)度系統(tǒng)，對(duì)加工工件及加工機(jī)器合理安排，在保證產(chǎn)品質(zhì)量的情況下，最短時(shí)間完成加工任務(wù)，從而降低企業(yè)的生產(chǎn)成本，提高生產(chǎn)效率。作業(yè)車間調(diào)度中一般限制條件如下：每個(gè)工件加工工序不能改變；每個(gè)工件加工時(shí)間確定，加工機(jī)器確定，且中途不能更改；同一時(shí)間一臺(tái)機(jī)器只能加工一個(gè)工件；無特殊指定，工件加工優(yōu)先級(jí)一樣。表2.1車間調(diào)度問題中常見數(shù)學(xué)模型符號(hào)數(shù)學(xué)符號(hào)含義N待加工工件總個(gè)數(shù)；J加工工件集合；M加工機(jī)器集合；M加工時(shí)間，Mt={MM運(yùn)轉(zhuǎn)時(shí)間，Mr={2.2.3調(diào)度問題表示方法作業(yè)車間調(diào)度問題有多種表示方法，最為常見的有析取圖描述法、甘特圖表示法等等。本文以甘特圖表示法為例，甘特圖表示法是以活動(dòng)列表和時(shí)間刻度表示出特定項(xiàng)目順序與持續(xù)時(shí)間關(guān)系，橫坐標(biāo)表示時(shí)間刻度，縱坐標(biāo)表示項(xiàng)目刻度，在車間調(diào)度問題中，縱坐標(biāo)表示加工機(jī)器，以矩形框的形式表示加工進(jìn)程，同時(shí)矩形框長短表示加工時(shí)間刻度，甘特圖表示法以簡單、醒目、易懂等特點(diǎn)，在調(diào)度問題中能直觀地反應(yīng)加工順序和進(jìn)程關(guān)系而被廣泛使用。表2.2以3×3車間調(diào)度問題為例，其甘特圖如圖2.1。表2.23×3作業(yè)車間調(diào)度問題加工時(shí)間、加工機(jī)器矩陣工件加工時(shí)間J469J53-J645加工機(jī)器JMMMJMM-JMMM工件J1需要經(jīng)過3道加工工序，由圖加工時(shí)間矩陣可知第1道工序所需時(shí)間為4，第2道工序所需時(shí)間為6，第3道工序所需時(shí)間為9；在加工機(jī)器矩陣可知工件J1第1道工序在M1機(jī)器上加工，同理可知，其第2、3道工序分別在M2、M3圖2.1實(shí)例最優(yōu)解甘特圖2.2.4調(diào)度問題求解方法車間調(diào)度問題一經(jīng)提出，國內(nèi)外科研人員便對(duì)其開展研究工作，早期科研人員因?yàn)槊鎸?duì)較為簡單的調(diào)度系統(tǒng)，采取比較簡單的方法，針對(duì)簡單調(diào)度系統(tǒng)，大都數(shù)為精確求解算法；隨著工業(yè)的發(fā)展，遇到的車間調(diào)度問題規(guī)模越來越大，問題本身越來越復(fù)雜，簡單求解算法不再適用復(fù)雜的車間調(diào)度問題，科研人員轉(zhuǎn)而研究更多近似優(yōu)化算法如圖2.2。圖2.2求解車間調(diào)度問題方法分類在實(shí)際的生產(chǎn)調(diào)度問題中，調(diào)度規(guī)模一般較大，難以適用精確求解算法，或需要花費(fèi)較大代價(jià)求解最優(yōu)值，相比之下，求解近似最優(yōu)解較為容易，在大多數(shù)情況下已經(jīng)能夠滿足車間調(diào)度需求，獲得較為滿意的解。因此，近似求解方法越來越受到研究人員的青睞。近似求解算法總體可分為人工智能法和鄰域搜索法，人工智能法是模擬人或自然界某些生物思維過程和生活習(xí)慣的行為算法。算法主要包括粒子群算法、神經(jīng)網(wǎng)絡(luò)算法、蟻群算法等；鄰域搜索法是較為通用的近似算法，其算法核心是將當(dāng)前最優(yōu)解進(jìn)行迭代臨近搜索，以達(dá)到最優(yōu)解目的，由于鄰域搜索步伐較小，其算法容易陷入局部極值，單獨(dú)依靠鄰域搜索算法很難達(dá)到全局搜索的目的，因此，鄰域搜索算法大多數(shù)與全局搜索算法配合使用，以達(dá)到全局搜索的效果。鄰域搜索算法主要包括遺傳算法、模擬退火算法、混沌算法等。神經(jīng)網(wǎng)絡(luò)算法(Neural

networkalgorithm)是依據(jù)人類腦部組織結(jié)構(gòu)和運(yùn)行機(jī)制研究后提出來的智能算法，具有并行處理、分布式信息存儲(chǔ)、自組織自學(xué)習(xí)能力等特點(diǎn)。該算法長期被用作動(dòng)態(tài)、不確定因素的車間調(diào)度問題。1990年，Rabelo等人最早利用神經(jīng)網(wǎng)絡(luò)算法求解車間調(diào)度問題。蟻群算法(antcolonyoptimization)最早由MarcoDorigo在1992年提出，模擬自然界螞蟻覓食行為演化而來的概率型算法，王碩提出參數(shù)自適應(yīng)蟻群算法求解車間調(diào)度問題，蟻群算法雖適應(yīng)能力強(qiáng)，但其也存在參數(shù)較多，不易控制，收斂速度慢等缺點(diǎn)。遺傳算法(GeneticAlgorithm)是通過模擬自然進(jìn)化過程搜索最優(yōu)解而形成的仿生優(yōu)化算法。由于優(yōu)化不依賴迭代，具有很強(qiáng)的魯棒性和全局搜索能力，從而廣發(fā)應(yīng)用于路徑規(guī)劃、車間調(diào)度等各個(gè)領(lǐng)域。模擬退火算法(Simulatedannealingalgorithm)思想來源于固體退火降溫過程的模擬，是一種較強(qiáng)的局部搜索算法，1983年Kirkpatrick等人將該算法應(yīng)用于調(diào)度系統(tǒng)中，取得了較大成就，而后不斷應(yīng)用于車間調(diào)度系統(tǒng)中。模擬退火算法憑借其較強(qiáng)的局部搜索能力，與其他全局搜索算法有機(jī)結(jié)合，在車間調(diào)度問題上被廣泛應(yīng)用。2.3本章小結(jié)本章詳細(xì)闡述了車間調(diào)度系統(tǒng)的理論知識(shí)，從車間調(diào)度問題分類、問題描述、問題表示方法、求解方法等角度全面闡述車間調(diào)度問題，對(duì)后面動(dòng)態(tài)車間調(diào)度問題的解決奠定了基礎(chǔ)。

第3章混合粒子群算法研究3.1引言粒子群優(yōu)化算法是通過模擬自然界中鳥群覓食行為抽象出來的群智能優(yōu)化算法，現(xiàn)已被廣泛應(yīng)用到作業(yè)車間調(diào)度、路徑最優(yōu)化選取、神經(jīng)網(wǎng)絡(luò)治療等多個(gè)領(lǐng)域。本章結(jié)合實(shí)際應(yīng)用過程中的問題及粒子群算法特點(diǎn)，提出一種混合粒子群算法。3.2標(biāo)準(zhǔn)粒子群算法標(biāo)準(zhǔn)粒子群算法是在1995年由R.Eberhart和J.Kennedy兩位研究學(xué)者提出來的，是一種群智能優(yōu)化算法，通過自然界中鳥群覓食行為抽象出來的優(yōu)化算法，它把實(shí)際問題遍歷區(qū)域看成搜索空間，將鳥群中的個(gè)體看作單獨(dú)粒子，搜索空間中每個(gè)粒子均有自己的初始位置和初始速度，當(dāng)鳥群中發(fā)現(xiàn)有覓食食物時(shí)，搜索空間中的每一個(gè)粒子受自身和其他粒子影響，重新賦予位置及速度，以此類推，通過多次迭代搜索，直至找到目標(biāo)位置。粒子群算法是一種并行算法，其原理簡單易懂，參數(shù)少，目前已經(jīng)用于最優(yōu)路徑選取、作業(yè)車間調(diào)度、神經(jīng)網(wǎng)絡(luò)治療等領(lǐng)域。3.2.1粒子群算法的數(shù)學(xué)模型由N個(gè)粒子組成的一個(gè)群體，在D維的搜素空間中，xi表示第iVit+1=ωXit+1=Xi在粒子速度更新公式中，ω為慣性權(quán)重，Vi為粒子速度，c1、c2為學(xué)習(xí)因子，γ1、γ2為[0,1]區(qū)間隨機(jī)數(shù)，為調(diào)節(jié)系數(shù)，Vit、Xit分別表示粒子i在第t次迭代更新后粒子的速度與位置，Pit、P3.2.2粒子群算法基本操作步驟標(biāo)準(zhǔn)粒子群算法處理優(yōu)化問題操作步驟如下：步驟一：初始化粒子。在D維搜索空間中隨機(jī)初始化種群粒子N，并賦予每個(gè)粒子初始速度v。步驟二：適應(yīng)度函數(shù)評(píng)價(jià)機(jī)制。對(duì)搜索空間中每個(gè)粒子進(jìn)行適應(yīng)度評(píng)價(jià)機(jī)制，判斷粒子當(dāng)前最優(yōu)解位置。步驟三：迭代更新。通過迭代更新和適應(yīng)度函數(shù)判斷，更新每個(gè)粒子位置及迭代速度，更新當(dāng)前最優(yōu)位置及全局最優(yōu)位置。步驟四：找出最優(yōu)解。依據(jù)尋優(yōu)精度，判斷是否結(jié)束尋優(yōu)過程。如達(dá)到尋優(yōu)精度或迭代次數(shù)，符合條件，找到最優(yōu)解，結(jié)束尋優(yōu)算法；如沒有達(dá)到尋優(yōu)精度或迭代次數(shù)，返回步驟二，繼續(xù)驗(yàn)證適應(yīng)度函數(shù)，進(jìn)行迭代尋優(yōu)更新。適應(yīng)度函數(shù)一般為目標(biāo)函數(shù)，根據(jù)求解問題的不同而不同，適應(yīng)度值越高，代表所得解越好，越接近目標(biāo)位置，一般使用f(開始開始粒子初始化適應(yīng)度函數(shù)評(píng)價(jià)更新個(gè)體極值及全局極值更新粒子速度及位置達(dá)到最大精度或最大迭代次數(shù)結(jié)束NY圖3.1粒子群算法流程圖3.3混合粒子群算法PSO算法盡管具有原理簡單、參數(shù)少、容易實(shí)現(xiàn)等諸多優(yōu)點(diǎn)，但是由于每次迭代更新需要通過自身認(rèn)知和社會(huì)其他粒子影響的共同作用下進(jìn)行的，進(jìn)而導(dǎo)致使粒子容易陷入局部最優(yōu)區(qū)域而找不到全局最優(yōu)解。本文對(duì)粒子群算法進(jìn)行如下改進(jìn)：添加局部搜索算法，提高算法搜索精度，動(dòng)態(tài)調(diào)節(jié)種群多樣性，從根源消除算法容易陷入局部極值的缺點(diǎn)。3.3.1局部搜索算法鑒于PSO算法搜索精度低，容易陷入局部極值等缺點(diǎn)，因此提高局部搜索精度、增強(qiáng)種群多樣性成為提高優(yōu)化算法得整體思路，在優(yōu)化算法中，慣性權(quán)重值得引入，使得算法在搜索初期對(duì)搜索空間中所有粒子進(jìn)行全局大范圍搜索，體現(xiàn)了智能算法得全局性，隨著更新迭代的進(jìn)行，逐步搜索到某一局部區(qū)域，算法只會(huì)在局部內(nèi)進(jìn)行搜索，而無法跳出當(dāng)前局部搜索空間，這一現(xiàn)象被稱為陷入局部極值。在粒子迭代過程中，搜索空間中設(shè)定有多個(gè)局部極值，在PSO算法中，粒子更新會(huì)同時(shí)收到自身慣性及周圍粒子影響進(jìn)行搜索，進(jìn)而隨機(jī)性陷入某一個(gè)局部極值無法跳出。本文引入模擬退火機(jī)制，實(shí)現(xiàn)局部搜索的精確搜索，引入變異策略，增強(qiáng)種群多樣性，跳出局部最優(yōu)概率。3.3.2退火機(jī)制模擬退火機(jī)制可理解為三個(gè)階段：（1）加溫。假定固態(tài)物體內(nèi)部粒子原先處于不平衡狀態(tài)，當(dāng)把固態(tài)物體加熱，內(nèi)部粒子會(huì)因?yàn)闇囟鹊纳叨x相對(duì)穩(wěn)定的狀態(tài)，直到液化固態(tài)物體，內(nèi)部粒子打破原來狀態(tài)，達(dá)到相對(duì)均勻。（2）平衡。當(dāng)外界不再加熱，物體由于自身溫度高于外界溫度，將與外界進(jìn)行溫度置換，物體內(nèi)部粒子能量減少，當(dāng)物體與外界溫度一致時(shí)，此時(shí)物體內(nèi)部能量最少，系統(tǒng)達(dá)到平衡。（3）冷卻。當(dāng)進(jìn)一步將物體冷卻，系統(tǒng)內(nèi)能量進(jìn)一步減少，物體內(nèi)部粒子相對(duì)穩(wěn)定，系統(tǒng)達(dá)到穩(wěn)定。模擬退火算法具有很好的局部搜索能力，主要因?yàn)樗梢越邮鼙犬?dāng)前解更差的解，在模擬退火算法初期，隨著溫度的升高，算法不接受或小概率接受最優(yōu)解，逐漸到算法后期，隨著溫度降低，最優(yōu)解接受概率較高，可以容納比當(dāng)前最優(yōu)解較差的解，有利于算法跳出局部極值。模擬退火算法思想如下：(1)產(chǎn)生可行鄰域解。模擬退火算法是鄰域搜索算法，利用Metropolis接受機(jī)制，有幾率產(chǎn)生比當(dāng)前全局最優(yōu)粒子差的鄰域解，使算法有概率跳出局部極值。設(shè)優(yōu)化目標(biāo)函數(shù)為f(x)，當(dāng)前迭代次數(shù)時(shí)全局最優(yōu)解為f(x1)，產(chǎn)生鄰域解為f(p由此公式可以看出，當(dāng)df<0時(shí)，一定會(huì)產(chǎn)生新的鄰域解，即還有達(dá)到局部最優(yōu)狀態(tài)；當(dāng)df≥0時(shí)，算法以exp?dfT概率接受鄰域解，即當(dāng)前全局最優(yōu)解好于鄰域解時(shí)，產(chǎn)生概率p是溫度T(2)初溫及降溫設(shè)定。初溫設(shè)定一般較大，能夠使得所有轉(zhuǎn)移狀態(tài)都被接受，但也不宜過大，否則算法搜索時(shí)間過長，本文取T0=1000作為初始溫度。其降溫公式為：Tt=T0(3)終止溫度。當(dāng)模擬退火算法內(nèi)、外循環(huán)在每一次迭代沒有產(chǎn)生新的更新狀態(tài)或已經(jīng)達(dá)到設(shè)定的溫度下限，即看成完成尋優(yōu)任務(wù)，終止循環(huán)。3.3.3編碼與解碼優(yōu)化問題中粒子編碼就是所求優(yōu)化問題得所有解得表達(dá)方式。編碼得選取直接影響粒子群算法得優(yōu)化性能，需符合調(diào)度方案，可以映射調(diào)度問題得解空間，能夠適應(yīng)粒子群算法中位置、速度得迭代更新。在車間調(diào)度問題中，粒子編碼可以選取得種類很多，可從工件、工序、機(jī)器等進(jìn)行編碼，比較編碼復(fù)雜性和時(shí)間復(fù)雜度來說，本文選取工序編碼方式進(jìn)行。解碼是相對(duì)于編碼而言的，簡單概括編碼是將具體問題抽象化，建立數(shù)學(xué)模型，便于求解，解碼是將所得數(shù)據(jù)還原具體問題當(dāng)中，從而進(jìn)行評(píng)估、選擇。現(xiàn)有3個(gè)工件需要加工，每個(gè)工件需要加工3道工序，采用工序編碼，下圖給出一組可行解。131321223圖3.23×3問題可行解編碼如圖所示，圖中1、2、3代表工業(yè)生產(chǎn)中工件編碼，在可行解編碼中出現(xiàn)的位置代表加工的有效順序，以第一件工件為例，出現(xiàn)的位置分別為1號(hào)、3號(hào)、6號(hào)位，即代表工件1分別在對(duì)應(yīng)的位置進(jìn)行工序1、工序2、工序3得加工工作，以此類推，圖1只是給出一個(gè)可行編碼解，代表工件加工順序優(yōu)先級(jí)。3.3.4交叉與變異交叉與變異操作是遺傳算法得重要手段，是通過生物進(jìn)化而得來的準(zhǔn)則。交叉操作是指子代中繼承父代有利基因，淘汰不利基因；變異是將原有基因序列某一片段進(jìn)行修改，進(jìn)而增強(qiáng)子代基因，通過交叉變異操作可以提高子代基因種類。由粒子群公式可以看出，粒子迭代后速度更新由自身與群體其他粒子均有影響，正是因?yàn)橛杀旧須v史最優(yōu)粒子和全局最優(yōu)粒子得影響下，保持向全局最優(yōu)粒子靠攏，從而實(shí)現(xiàn)子代更新迭代。由此可知，交叉操作是父代在參考群體搜索經(jīng)驗(yàn)當(dāng)中進(jìn)行的，子代在繼承父代有利基因外，還將繼承群體經(jīng)驗(yàn)中交叉變異后的有利基因，這樣增加了跳出局部極值得概率。粒子群算法不能動(dòng)態(tài)實(shí)現(xiàn)種群更新，本文引入交叉變異操作提高粒子群算法種群動(dòng)態(tài)更新。（1）交叉操作。選定需要進(jìn)行交叉操作的兩個(gè)父代粒子x1、x2，將x1粒子隨機(jī)選中和保留粒子的基因位，并記錄選中基因個(gè)數(shù)，在x2粒子隨機(jī)選中與x1粒子選中基因相同的對(duì)應(yīng)基因位，并保留其所在基因，復(fù)制到新一代y粒子當(dāng)中，將x1粒子中未選中基因按照順序重新插入到y(tǒng)粒子中，所得新的基因序列即為交叉操作所得粒子。交叉操作示意圖：圖3.3交叉示意圖（2）變異操作。在粒子群算法中引入變異操作，也是提高種群多樣性的有效途徑，引導(dǎo)算法指向更高的適應(yīng)度函數(shù)進(jìn)化，在鄰域搜索算法中，引入變異操作，使粒子產(chǎn)生鄰域解，增強(qiáng)種群多樣性，有易于跳出當(dāng)前迭代極值，實(shí)現(xiàn)全局搜索。在基于工序編碼的車間調(diào)度問題當(dāng)中，變異操作是隨機(jī)選擇父代中一個(gè)粒子基因片段的不同基因位進(jìn)行互換，需要強(qiáng)調(diào)的是，一個(gè)基因片段可以互相調(diào)換多組基因位，如果調(diào)換位置基因位相同，則父代基因與變異后子代基因相同，則實(shí)質(zhì)上沒有進(jìn)行變異。以3×3車間調(diào)度問題為背景對(duì)其變異過程如圖3.4所示：圖3.4變異示意圖3.4靜態(tài)車間調(diào)度求解混合粒子群算法根據(jù)車間調(diào)度問題提出，為了驗(yàn)證混合粒子群算法在車間調(diào)度問題中的應(yīng)用，首先采用靜態(tài)車間調(diào)度問題，采用MATLAB測(cè)試軟件進(jìn)行模擬仿真實(shí)驗(yàn)，驗(yàn)證結(jié)果。3.4.1建立數(shù)學(xué)模型確定車間調(diào)度問題的輸入輸出是建立數(shù)學(xué)模型的關(guān)鍵，我們以工件個(gè)體及加工時(shí)間為輸入對(duì)象，輸出則以甘特圖表示最佳調(diào)度流程，經(jīng)過限制條件、智能算法優(yōu)化、最終達(dá)到求解最優(yōu)值。車間調(diào)度問題輸入輸出模型圖如下：圖3.5車間調(diào)度問題輸入輸出模型圖3.4.2仿真實(shí)驗(yàn)本文選取較為常見的FT06實(shí)例進(jìn)行仿真測(cè)試實(shí)驗(yàn)，F(xiàn)T06實(shí)例描述為一批待加工6個(gè)工件，6臺(tái)加工機(jī)器，每個(gè)工件需要加工6道工序，求解如何加工工件順序使得加工時(shí)間最少，效率最高。具體工件及加工時(shí)間如下表：表3.1FT06車間調(diào)度數(shù)據(jù)表工件機(jī)器號(hào)/加工時(shí)間13/11/32/64/76/35/622/83/55/106/101/104/433/54/46/81/92/15/742/51/53/54/35/86/953/92/35/56/41/34/162/34/36/91/105/43/1FT06實(shí)例問題目前達(dá)到的最好解為55。利用混合粒子群算法求解的FT06問題得出甘特圖如圖3.6，圖中以工件加工總消耗時(shí)間為橫坐標(biāo)，以工件編號(hào)為縱坐標(biāo)，以矩形框表示工件加工順序。為了進(jìn)一步驗(yàn)證混合粒子群算法在實(shí)例當(dāng)中收斂性、魯棒性，同時(shí)選取了DPSO、GA算法進(jìn)行模擬對(duì)比實(shí)驗(yàn)，在FT06實(shí)例問題上三種算法分別求解10次，每種算法迭代200次，選取每一次迭代全局最優(yōu)解平均值做出如圖3.7所示，圖中以每種算法迭代次數(shù)為橫坐標(biāo)，以每次迭代中全局最優(yōu)值平均值為縱坐標(biāo)。從圖中可以看出，混合粒子群算法在收斂速度和收斂效果上都比DPSO、GA算法要好。圖3.6甘特圖6×6車間調(diào)度輸出圖圖3.7三種算法收斂性比較圖3.5本章小結(jié)本章首先介紹了標(biāo)準(zhǔn)粒子群算法的基本原理，數(shù)學(xué)模型和操作流程，依據(jù)粒子群算法參數(shù)特點(diǎn)對(duì)其容易陷入局部極值缺陷進(jìn)行改進(jìn)，提出局部范圍精度搜索，引入交叉變異策略，提出鄰域值操作方法，提高種群多樣性，從而跳出局部極值，增強(qiáng)算法魯棒性，最后通過靜態(tài)車間調(diào)度問題，引入具體實(shí)例，以混合粒子群算法及SPSO、GA算法進(jìn)行可行性實(shí)驗(yàn)測(cè)試，對(duì)比得出混合粒子群算法無論在收斂速度及收斂精度上都取得較好效果。

第4章混合粒子群算法在動(dòng)態(tài)車間調(diào)度問題中的應(yīng)用4.1引言目前對(duì)車間調(diào)度算法的研究大多數(shù)都是針對(duì)靜態(tài)車間調(diào)度問題，是在固定工件個(gè)數(shù)、固定加工工序、固定加工時(shí)間等一系列外界條件下進(jìn)行的，但是在實(shí)際的工業(yè)生產(chǎn)中，工件加工往往不能遵循預(yù)先設(shè)定好的程序持續(xù)進(jìn)行，由此動(dòng)態(tài)車間調(diào)度被越來越多的人接受和采用，動(dòng)態(tài)車間調(diào)度是在靜態(tài)車間調(diào)度問題基礎(chǔ)上提出來的，增加了由企業(yè)內(nèi)部和外部環(huán)境帶來的加工風(fēng)險(xiǎn)，例如：加工機(jī)器損壞、加工原料緊缺、客戶加急訂單、取消現(xiàn)有訂單等等，這些突然情況導(dǎo)致無法延用原來固定不變的優(yōu)化算法。因此對(duì)動(dòng)態(tài)車間調(diào)度問題研究，更貼合實(shí)際應(yīng)用。4.2動(dòng)態(tài)車間調(diào)度問題4.2.1問題描述以往研究的車間調(diào)度問題對(duì)條件的設(shè)定一般是固定的，例如加工的工件個(gè)數(shù)、加工所需的機(jī)器特定，每個(gè)工件加工時(shí)所需時(shí)間一經(jīng)確定將不再更改，在調(diào)度算法開始前所有工件都已準(zhǔn)備就緒等等，這類已經(jīng)確定好的調(diào)度問題被稱為靜態(tài)調(diào)度問題，而實(shí)際生產(chǎn)過程中，由于自身不可抗力因素或外部環(huán)境因素影響，導(dǎo)致無法按照指定原有計(jì)劃進(jìn)行，這類生產(chǎn)調(diào)度問題被稱為動(dòng)態(tài)車間調(diào)度問題。簡而言之，動(dòng)態(tài)車間調(diào)度是在靜態(tài)車間調(diào)度問題上增添突發(fā)事件而產(chǎn)生的，即動(dòng)態(tài)車間調(diào)度系統(tǒng)是靜態(tài)車間調(diào)度系統(tǒng)基礎(chǔ)上添加突發(fā)事件等不可抗力因素形成的，如圖4.1。圖4.1動(dòng)態(tài)車間調(diào)度與靜態(tài)車間調(diào)度關(guān)系圖4.2.2動(dòng)態(tài)調(diào)度模型分類在實(shí)際生產(chǎn)環(huán)境中，由于自身或外界不可抗力因素導(dǎo)致需要進(jìn)行動(dòng)態(tài)調(diào)節(jié)原有調(diào)度事件成為動(dòng)態(tài)事件。根據(jù)Suresh等人對(duì)動(dòng)態(tài)車間調(diào)度問題中動(dòng)態(tài)事件的研究，一般分為以下三種動(dòng)態(tài)事件。（1）工件突發(fā)事件。該事件包含由于工件問題導(dǎo)致的不可繼續(xù)進(jìn)行的突發(fā)事件，例如工件原材料缺損、工件加工過程中作廢、工件優(yōu)先級(jí)變化等等。（2）工序突發(fā)事件。該事件包含加工工序操作階段導(dǎo)致無法進(jìn)行的事件。例如某件工序加工延時(shí)、加工質(zhì)量不合格重新加工等。（3）機(jī)器突發(fā)事件。該事件主要由于機(jī)器損壞導(dǎo)致加工無法正常進(jìn)行的突發(fā)事件。針對(duì)以上幾種動(dòng)態(tài)突發(fā)事件，在實(shí)際生產(chǎn)過程中可能同時(shí)或多個(gè)出現(xiàn)，本文在研究中為了簡化操作，只考慮單一突發(fā)事件情況。4.2.3動(dòng)態(tài)調(diào)度窗口當(dāng)生產(chǎn)調(diào)度系統(tǒng)發(fā)生動(dòng)態(tài)事件時(shí)，打破原有調(diào)度規(guī)則，我們把產(chǎn)生動(dòng)態(tài)事件時(shí)調(diào)度窗口稱為動(dòng)態(tài)調(diào)度窗口，如圖4.2重調(diào)度動(dòng)態(tài)窗口，橫坐標(biāo)為生產(chǎn)加工時(shí)間，縱坐標(biāo)為加工機(jī)器，在ti時(shí)刻，由于發(fā)生動(dòng)態(tài)調(diào)度，機(jī)器不再執(zhí)行原有調(diào)度程序算法，暫停執(zhí)行，此時(shí)如圖4.2所示，M1、M2、M3已加工完成部分工件，M1圖4.2重調(diào)度動(dòng)態(tài)窗口4.2.4動(dòng)態(tài)調(diào)度策略一般當(dāng)突發(fā)事件發(fā)生時(shí)，動(dòng)態(tài)調(diào)度策略大體分為兩類：突發(fā)事件調(diào)度，即一旦有突發(fā)事件，系統(tǒng)會(huì)自動(dòng)響應(yīng)，進(jìn)行重調(diào)度算法；周期性調(diào)度，系統(tǒng)每隔指定時(shí)間重調(diào)度算法。本文采用突發(fā)事件重調(diào)度策略，即生產(chǎn)調(diào)度系統(tǒng)在執(zhí)行調(diào)度方案時(shí)，以遵照最開始調(diào)度方案進(jìn)行調(diào)度工作，在調(diào)度開始之前，設(shè)定所有調(diào)度系統(tǒng)中原材料及加工機(jī)器均已準(zhǔn)備好，一旦發(fā)生重調(diào)度，會(huì)對(duì)現(xiàn)有資源進(jìn)行重新整理分配，圖4.3是根據(jù)事件驅(qū)動(dòng)重調(diào)度策略進(jìn)行重調(diào)度示意圖，調(diào)度系統(tǒng)會(huì)實(shí)時(shí)監(jiān)測(cè)有無突發(fā)事件，一旦檢測(cè)成功，將觸發(fā)調(diào)度系統(tǒng)，啟動(dòng)重調(diào)度算法。圖4.3事件驅(qū)動(dòng)重調(diào)度示意圖4.3動(dòng)態(tài)調(diào)度問題求解基于突發(fā)事件的動(dòng)態(tài)調(diào)度策略，可以及時(shí)對(duì)系統(tǒng)采取重調(diào)度處理。利用動(dòng)態(tài)調(diào)度窗口可知，當(dāng)發(fā)生重調(diào)度時(shí)可看做成一個(gè)靜態(tài)調(diào)度結(jié)束，另一個(gè)靜態(tài)調(diào)度開始，故而可以把動(dòng)態(tài)調(diào)度問題看成是多個(gè)靜態(tài)調(diào)度問題的結(jié)合，如全程僅存在一個(gè)靜態(tài)調(diào)度即沒有發(fā)生過重調(diào)度事件，因此，動(dòng)態(tài)調(diào)度問題求解可看成一個(gè)或多個(gè)靜態(tài)調(diào)度求解問題。4.3.1數(shù)學(xué)模型修正當(dāng)調(diào)度系統(tǒng)發(fā)生重調(diào)度時(shí)，相當(dāng)于又開啟一項(xiàng)新的靜態(tài)調(diào)度，新開啟的靜態(tài)調(diào)度與最開始的靜態(tài)調(diào)度初始狀態(tài)不同，重調(diào)度時(shí)機(jī)器的狀態(tài)和加工的工件狀態(tài)不一樣，在進(jìn)行粒子群算法重調(diào)度之前，需要進(jìn)行數(shù)學(xué)模型修正。（1）利用加工時(shí)間修正。由于突發(fā)事件是隨機(jī)的，所以當(dāng)啟動(dòng)動(dòng)態(tài)調(diào)度窗口時(shí)，工件可能會(huì)處于三種狀態(tài)，未加工工件將不再進(jìn)行加工工作；正在加工工件為不打斷問題連續(xù)性，將繼續(xù)加工至完成；已加工完成工件退出加工流程。（2）利用機(jī)器修復(fù)時(shí)間修正。當(dāng)啟用動(dòng)態(tài)調(diào)度窗口時(shí)，機(jī)器同樣可能處于三種狀態(tài)，機(jī)器處于空閑狀態(tài)，將暫停加工工作；機(jī)器正在加工過程中，為不打斷問題連續(xù)性，將繼續(xù)加工至完成；機(jī)器處于故障狀態(tài)，設(shè)定機(jī)器預(yù)計(jì)修復(fù)時(shí)間，則重調(diào)度中機(jī)器響應(yīng)時(shí)間為預(yù)計(jì)修復(fù)時(shí)間。如圖3.3重調(diào)度數(shù)學(xué)模型修正。如圖3.4所示，3臺(tái)機(jī)器分別進(jìn)行工件加工工作，當(dāng)t=15時(shí)機(jī)器2發(fā)生故障，預(yù)計(jì)修復(fù)時(shí)間為5，則機(jī)器1在t=15時(shí)，處于空閑狀態(tài)，可以立即進(jìn)行重調(diào)度；機(jī)器2在預(yù)計(jì)修復(fù)時(shí)間結(jié)束后可啟用重調(diào)度，即t=20；機(jī)器3當(dāng)前正在加工工件，為不打斷問題連續(xù)性，當(dāng)工件加工完成時(shí)t=22，可參與重調(diào)度。綜上所述，機(jī)器可利用時(shí)間矩陣為Tr圖4.4機(jī)器修復(fù)模型4.3.2動(dòng)態(tài)事件處理根據(jù)混合粒子群算法及動(dòng)態(tài)調(diào)度窗口技術(shù)對(duì)動(dòng)態(tài)車間調(diào)度問題進(jìn)行求解，本文分別對(duì)加急訂單、取消訂單、機(jī)器故障三種突發(fā)事件進(jìn)行討論，一般解決步驟如下：（1）根據(jù)數(shù)學(xué)修正模型，確定重調(diào)度時(shí)刻（2）根據(jù)重調(diào)度，判定工件加工時(shí)間、加工機(jī)器、機(jī)器可利用三種調(diào)度模型狀態(tài)（3）根據(jù)調(diào)度模型，開啟重調(diào)度。本節(jié)以3×3模型調(diào)度實(shí)例講解在緊急訂單、取消訂單、機(jī)器故障三種不同情況下發(fā)生突發(fā)事件處理辦法。初始調(diào)度時(shí)，機(jī)器可利用狀態(tài)矩陣為TrJt=245利用混合粒子群算法進(jìn)行優(yōu)化后得出在初始調(diào)度系統(tǒng)中最優(yōu)粒子排序?yàn)椋篠=3圖4.5初始調(diào)度系統(tǒng)最優(yōu)解甘特圖假設(shè)在T=3時(shí)刻發(fā)生動(dòng)態(tài)事件，按以下三種情況分別討論。（1）加急訂單。調(diào)度系統(tǒng)在t=3時(shí)刻發(fā)生重調(diào)度，假設(shè)新增加急訂單為4號(hào)工件，其工件加工時(shí)間矩陣為T4=3，5，6，加工機(jī)器矩陣為M4=3，2，1，如圖4.5所示，在t=3時(shí)刻，1號(hào)機(jī)器正在加工1號(hào)工件，t=4時(shí)刻加工完成；2號(hào)機(jī)器正在加工2號(hào)工件，在圖4.6加工時(shí)間、加工機(jī)器變化矩陣圖其中0代表無需加工操作，再根據(jù)Tr（2）取消訂單。假設(shè)t=3時(shí)刻取消工件3訂單，調(diào)度系統(tǒng)為節(jié)約加工材料，立即取消加工操作，則機(jī)器可利用矩陣為TrJt3=450（3）機(jī)器故障。在生產(chǎn)得實(shí)際工作當(dāng)中，機(jī)器故障引發(fā)動(dòng)態(tài)事件占所有動(dòng)態(tài)事件很大概率，假設(shè)在t=3時(shí)刻機(jī)器2發(fā)生故障，預(yù)計(jì)修復(fù)時(shí)間為4，即t=3時(shí)刻機(jī)器2不再進(jìn)行加工工作，為了避免加工工件損壞，我們考慮在故障機(jī)器沒有進(jìn)行加工完成得工件都需重新加工當(dāng)前工序，根據(jù)訂單加急原理，機(jī)器可利用矩陣為TrJt3=4504.4仿真實(shí)驗(yàn)本節(jié)將利用混合粒子群算法求解動(dòng)態(tài)車間調(diào)度問題，繼續(xù)采用FT06實(shí)例進(jìn)行驗(yàn)證。前面已經(jīng)對(duì)FT06在靜態(tài)調(diào)度情況下進(jìn)行仿真實(shí)驗(yàn)，本節(jié)仍然以最短加工時(shí)間為優(yōu)化目標(biāo)，討論在加急訂單、取消訂單、機(jī)器故障三種情況下混合粒子群算法在動(dòng)態(tài)車間調(diào)度問題求解。按照FT06實(shí)例，則有工件加工時(shí)間矩陣及機(jī)器加工矩陣如下：Jt=136（1）加急訂單。假設(shè)在t=20時(shí)刻，新增加急訂單7號(hào)工件，加工時(shí)間矩陣為T7=6，3，8，5，4，9圖4.6加急訂單甘特圖（2）訂單取消。假設(shè)t=30時(shí)刻，取消工件4、5加工工序，啟動(dòng)重調(diào)度，利用混合粒子群算法求解最優(yōu)解為52，甘特圖如圖4.7。圖4.7訂單取消甘特圖（3）機(jī)器故障。假設(shè)t=26時(shí)刻，機(jī)器4故障，預(yù)計(jì)修復(fù)時(shí)間為9，利用混合粒子群算法求解最優(yōu)解為57，甘特圖如圖4.8。圖4.8機(jī)器故障甘特圖根據(jù)以往用遺傳算法求解動(dòng)態(tài)車間調(diào)度問題，本文將混合粒子群算法與遺傳算法在動(dòng)態(tài)車間調(diào)度問題進(jìn)行比較，得出如下結(jié)果：4.5本章小結(jié)本章對(duì)動(dòng)態(tài)車間調(diào)度問題進(jìn)行詳細(xì)研究，從動(dòng)態(tài)車間調(diào)度問題分類，分析調(diào)度問題中動(dòng)態(tài)事件數(shù)學(xué)建模類型，提出動(dòng)態(tài)調(diào)度窗口，列舉加急訂單、取消訂單、機(jī)器故障三種突發(fā)事件，結(jié)合混合粒子群算法進(jìn)行仿真模擬實(shí)驗(yàn)，最后與遺傳算法進(jìn)行比較分析，驗(yàn)證混合粒子群算法在動(dòng)態(tài)車間調(diào)度過程中取得較好效果。

第5章總結(jié)與展望5.1總結(jié)制造業(yè)是我國經(jīng)濟(jì)發(fā)展和經(jīng)濟(jì)繁榮得關(guān)鍵，為我國經(jīng)濟(jì)發(fā)展提供強(qiáng)大動(dòng)力，提升制造業(yè)產(chǎn)品多元化、提高生產(chǎn)效率、提升質(zhì)量是進(jìn)一步提高我國制造業(yè)生產(chǎn)智能化得關(guān)鍵一步。一個(gè)好的生產(chǎn)調(diào)度系統(tǒng)會(huì)大幅提升生產(chǎn)效率，降低生產(chǎn)成本，因此，研究車間調(diào)度問題具有實(shí)際應(yīng)用價(jià)值。本文詳細(xì)介紹了粒子群算法基本原理、參數(shù)設(shè)置、操作流程等，并與其他智能算法混合形成新的智能算法，應(yīng)用于車間流水調(diào)度問題當(dāng)中，從穩(wěn)定性、尋優(yōu)精度等角度提高算法性能?，F(xiàn)將本文研究工作總結(jié)如下：（1）詳細(xì)闡述車間調(diào)度問題的分類、問題描述、表示方法及求解方法，介紹車間調(diào)度當(dāng)前研究現(xiàn)狀及存在問題。（2）介紹標(biāo)準(zhǔn)粒子群算法基本原理、參數(shù)設(shè)置、數(shù)學(xué)模型及其在車間調(diào)度問題中的計(jì)算步驟，并依據(jù)粒子群算法及車間調(diào)度問題特點(diǎn)，提出在粒子群算法基礎(chǔ)上增加交叉變異、引入退火機(jī)制的混合粒子群算法，從而增強(qiáng)種群多樣性，提高局部搜索能力，引入除自身及全局其他粒子對(duì)其影響的額外信息參考點(diǎn)，提高算法搜索能力。（3）使用MATLAB軟件模擬測(cè)試混合粒子群算法在靜態(tài)車間調(diào)度系統(tǒng)中的應(yīng)用，使用FT06實(shí)例對(duì)其混合粒子群算法收斂性、魯棒性進(jìn)行驗(yàn)證，并與其他優(yōu)化算法進(jìn)行比較，驗(yàn)證混合粒子群算法具有較強(qiáng)的搜索能力及收斂性能。（4）從動(dòng)態(tài)車間調(diào)度問題的分類、動(dòng)態(tài)調(diào)度窗口、動(dòng)態(tài)調(diào)整策略及數(shù)學(xué)模型修復(fù)等方面介紹動(dòng)態(tài)車間調(diào)度問題重難點(diǎn)，采用動(dòng)態(tài)調(diào)度窗口及動(dòng)態(tài)調(diào)度策略修正重調(diào)度所用資源，分別在加急訂單、取消訂單、機(jī)器故障三種突發(fā)情況下重啟調(diào)度系統(tǒng)，并將仿真結(jié)果與蟻群算法進(jìn)行對(duì)比分析，驗(yàn)證混合粒子群算法在動(dòng)態(tài)車間調(diào)度問題中性能。實(shí)驗(yàn)結(jié)果證明，混合粒子群算法相比其他算法尋優(yōu)能力更強(qiáng)，精度更高，在實(shí)際生產(chǎn)過程中應(yīng)變能力更好。5.2展望動(dòng)態(tài)車間調(diào)度問題是一項(xiàng)相對(duì)復(fù)雜的工程問題，由于時(shí)間和知識(shí)水平的限制，對(duì)于此項(xiàng)問題研究還不夠深入，還有很多需要優(yōu)化改進(jìn)的地方，需要進(jìn)一步研究：本文設(shè)定優(yōu)化目標(biāo)為單一優(yōu)化目標(biāo)，即最優(yōu)目標(biāo)為單一個(gè)體，而在實(shí)際生產(chǎn)過程中，往往要綜合考慮產(chǎn)品性能、加工成本、生產(chǎn)效率等等，目標(biāo)生產(chǎn)不僅僅為單一目標(biāo)，需要進(jìn)一步研究多目標(biāo)優(yōu)化效果。在混合粒子群算法中本文采取兩種優(yōu)化算法混合取得的效果，可以考慮多種優(yōu)化算法混合，進(jìn)一步提升算法魯棒性。在針對(duì)動(dòng)態(tài)車間調(diào)度問題中，忽略不同生產(chǎn)時(shí)期對(duì)產(chǎn)品的不同要求，不具有隨時(shí)隨地調(diào)節(jié)生產(chǎn)時(shí)間、生產(chǎn)精度等，算法具有一定強(qiáng)制性，一旦設(shè)定參數(shù)值將整個(gè)周期不能更改。

參考文獻(xiàn)[1]越民義,韓繼業(yè).N個(gè)零件在M臺(tái)機(jī)床上加工順序問題[J].中國科學(xué):1975,5:462-470.[2]何霆,劉飛,馬玉林.車間生產(chǎn)調(diào)度問題研究[J].機(jī)械工程學(xué)報(bào):2000,36(05):97-02.[3]Gavett,J.Threeheuristicrulesforsequencingjobstoasingleproductionfacility[D].ManagementScience,1965,11(08):166-176.[4]GereWS.Heuristicsinjobshopscheduling[D].ManagementScience:1966,13(08):167-190.[5]MA.Cruz-Chavez.Neighborhoodgenerationmechanismappliedinsimulatedtojobannealingshopschedulingproblems[J].InternationalJournalofSystemsScience:2015,46(15):2673-2685.[6]T.M.Willems.Implementingheuristicsasanoptimizationcriterioninneuralnetworksforjob-shopscheduling[J].JournalofIntelligentManufacturing:1996,6(12):377-387.[7]K.KurbelA.Comparisonofjob-shopschedulingtechniques:Simulatedannealing,geneticalgorithms,andmathematicaloptimization[J].1995,37:581-593.[8]Liu,SQ.MetaheuristicsforminimizingthemakespanoftheDynamicshopschedulingproblem[J].AdvancesInEngineeringSoftware,2004,36(7):199-205.[9]HoogeveenH.WoegingerGJ.Averydifficultschedulingproblemwithcommunicationdelays[J].OperationsResearchLetters:2001,29(5),241-245.[10]鞠全勇，朱劍英.基于混合遺傳算法的動(dòng)態(tài)車間調(diào)度系統(tǒng)的研究[J].中國機(jī)械工程:2007,1(1):40-43.[11]ZhangRui,WuCheng.Ahybridimmunesimulatedannealingalgorithmforthejobshopschedulingproblem[J].AppliedSoftComputingJournal:2010,10(14):79-89.[12]R.Eberhart,J.Kennedy.ANewOptimizerUsingParticleSwarmTheory[C].InProceedingsof6thInternationalSymposiumonMicroMachineandHumanScience:1995:39-43.[13]彭虎,田俊峰,鄧長壽.求解約束優(yōu)化問題的動(dòng)態(tài)鄰域粒子群算法[J].計(jì)算機(jī)應(yīng)用研究:2011,28(07):2476-2478.[14]KennedyJ,EberhartR.Adiscretebinaryversionoftheparticleswarmalgorithm[C].ProceedingoftheWordMulticonferenceonSystematics,CyberneticsandInformatics.1997:104-4019.[15]JohnsonS.Optimaltwoandthreestageproductionscheduleswithsetuptimesincluded[J].NavalResearchLogisticsQuarterly,1954,21:61-68.[16]趙志剛,蘇一丹.帶自變異算子的粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2006