《求解流水車(chē)間調(diào)度問(wèn)題的差分進(jìn)化算法設(shè)計(jì)》8700字（論文）

求解流水車(chē)間調(diào)度問(wèn)題的差分進(jìn)化算法設(shè)計(jì)目錄TOC\o"1-2"\h\u264641緒論 281041.1課題來(lái)源與背景 2154351.2本文主要研究?jī)?nèi)容與意義 3189092差分進(jìn)化算法 468862.1差分進(jìn)化算法的含義 435852.2差分進(jìn)化算法的流程 5183662.3差分進(jìn)化算法的意義 6205532.4本章小結(jié) 621933零等待流水車(chē)間 6205963.1引言 6131293.2NWFSP基本概念和模型 7300153.3優(yōu)化指標(biāo)和計(jì)算 8251303.4本章小結(jié) 9277674求解調(diào)度問(wèn)題的差分進(jìn)化算法設(shè)計(jì) 9240884.1引言 932124.2求解NWFSP問(wèn)題的算法 1062374.3算法具體部分的設(shè)計(jì) 1130284.4本章小結(jié) 1259805仿真實(shí)驗(yàn)與結(jié)果分析 127435.1引言 1256475.2算例介紹 1368295.3算例仿真 14215715.4本章小結(jié) 1731016總結(jié)與展望 17179056.1總結(jié) 1717266.2展望 17摘要：隨著我國(guó)制造業(yè)經(jīng)濟(jì)的迅速發(fā)展，各部門(mén)對(duì)制造業(yè)的要求也逐漸變高，制造業(yè)企業(yè)只有在生產(chǎn)加工方式，部門(mén)管理等方面進(jìn)行改革創(chuàng)新，才能面對(duì)當(dāng)今供不應(yīng)求的局面。解決調(diào)度問(wèn)題就是改革制造業(yè)的突破口，調(diào)度問(wèn)題主要研究的就是如何合理的分配資源。本文主要講解了零等待流水車(chē)間的調(diào)度問(wèn)題，以最大完成時(shí)間和總流程時(shí)間作為優(yōu)化指標(biāo)來(lái)研究，使讀者更容易理解，文章整體結(jié)構(gòu)更加清晰。此外本文還將用到差分進(jìn)化算法來(lái)解決零等待流水車(chē)間的調(diào)度問(wèn)題，通過(guò)介紹差分進(jìn)化算法的原理和流程，結(jié)合優(yōu)化指標(biāo)，求取最優(yōu)解。我們希望能夠在實(shí)現(xiàn)算法的基礎(chǔ)之上針對(duì)大規(guī)模、各種類型的算例進(jìn)行優(yōu)化設(shè)計(jì)，并對(duì)文中所選算例進(jìn)行仿真實(shí)驗(yàn)，針對(duì)仿真數(shù)據(jù)及結(jié)果做出進(jìn)一步詳盡的分析，有效的驗(yàn)證差分進(jìn)化算法在零等待作業(yè)車(chē)間調(diào)度中的作用與意義。關(guān)鍵詞：差分進(jìn)化算法；零等待；總流程時(shí)間1緒論1.1課題來(lái)源與背景目前各項(xiàng)企業(yè)在迅速發(fā)展變化的市場(chǎng)中依舊能夠保持競(jìng)爭(zhēng)地位的關(guān)鍵環(huán)節(jié)是車(chē)間調(diào)度，原油工業(yè)則是一開(kāi)始就提出流水車(chē)間的調(diào)度問(wèn)題，在化工原料方面加工、食品安全加工、混凝土類制品的生產(chǎn)以及制藥工程加工等行業(yè)中都有著諸多的應(yīng)用，可以說(shuō)是非常方便了。所以說(shuō)發(fā)現(xiàn)更快更好的調(diào)度技術(shù)以及使用方法有著至關(guān)重要的作用。在調(diào)度的研究過(guò)程中難度毋庸置疑是相當(dāng)大的，因?yàn)檎麄€(gè)工程所涉及到的問(wèn)題都是需要考慮的問(wèn)題，它不僅受著來(lái)自諸多方面的約束，并且每一個(gè)環(huán)節(jié)的變動(dòng)都會(huì)影響調(diào)度的結(jié)果。因此，在當(dāng)今這個(gè)時(shí)代，制造業(yè)的發(fā)展猶如雨后春筍，技術(shù)也不例外，和制造業(yè)并相發(fā)展，人們開(kāi)始越來(lái)越重視調(diào)度問(wèn)題的研究和解決，不僅如此，企業(yè)如果想要提高工作效率，尤為重要的一點(diǎn)就是調(diào)度的優(yōu)化。隨著科技與現(xiàn)代技術(shù)不斷地如日中天與提升，更多的工廠與企業(yè)開(kāi)始關(guān)注并重視流水車(chē)間調(diào)度問(wèn)題，其中占據(jù)重要地位的不得不說(shuō)零等待流水車(chē)間。下面來(lái)我們將大致的介紹一下零等待流水車(chē)間的主要流程，當(dāng)工件在完成整個(gè)流水線上，每當(dāng)它完成了一個(gè)加工步驟，那么下一個(gè)步驟要隨即進(jìn)行，在這一整個(gè)過(guò)程中工件根本沒(méi)有停歇的機(jī)會(huì)，尤其是在非這樣不行的時(shí)候，第一臺(tái)工作的車(chē)間機(jī)器，它的工作必需延遲開(kāi)始，以此來(lái)滿足本文所述的零等待的要求。若是機(jī)器的數(shù)量為兩個(gè)及以上，對(duì)與流水車(chē)間問(wèn)題而言，那么它屬于強(qiáng)NP-hard問(wèn)題。由此可見(jiàn)，能夠接受的計(jì)算時(shí)間范圍內(nèi)，零等待流車(chē)間調(diào)度問(wèn)題中有且只有小規(guī)模的流水車(chē)間才能獲得目標(biāo)最優(yōu)解。當(dāng)我們?cè)谘芯苛愕却魉?chē)間問(wèn)題的時(shí)候，不難發(fā)現(xiàn)，它不僅可以有效的縮短了加工過(guò)程所必不可少的時(shí)間，而且大幅度減少了上一個(gè)步驟與下一個(gè)步驟之間的等待時(shí)間，并且很大程度上的的提高了工作效率。由此可見(jiàn)，研究和進(jìn)一步拓展零等待流水車(chē)間的調(diào)度問(wèn)題對(duì)企業(yè)乃至個(gè)人都有著相當(dāng)大的影響和意義，同樣的對(duì)于此問(wèn)題的進(jìn)一步研究也引來(lái)了更多科研人員的廣泛關(guān)注與重視。大部分的研究開(kāi)發(fā)人員都會(huì)選擇把最大完成時(shí)間(makespan,)作為優(yōu)化指標(biāo)來(lái)研究調(diào)度問(wèn)題。我們不妨學(xué)習(xí)一下，同樣的做法，分別把最大完工時(shí)間和總時(shí)間當(dāng)做最終結(jié)果所需優(yōu)化的指標(biāo)。在研究零等待流水車(chē)間的總流程問(wèn)題時(shí)，我們將會(huì)通過(guò)差分進(jìn)化算法（DE）來(lái)將車(chē)間調(diào)度進(jìn)一步優(yōu)化，并且提供出能夠提高工作效率的加工按序，大幅提高企業(yè)與工廠的工作效率，使企業(yè)的利潤(rùn)達(dá)到最大化，我相信這些研討對(duì)企業(yè)和現(xiàn)代化社會(huì)的發(fā)展都具有重要且深遠(yuǎn)的意義。1.2本文主要研究?jī)?nèi)容與意義本文主要將會(huì)是通過(guò)差分進(jìn)化算法（DE）來(lái)認(rèn)識(shí)并解決零等待流水車(chē)間總流程時(shí)間調(diào)度問(wèn)題，大家可能還不了解該算法的定義，我們可以把它與同樣可以解決調(diào)度問(wèn)題的其余算法相比，差分進(jìn)化算法（DE）是一種效率極高，所涉局域極廣的算法，在解決零等待流水車(chē)間總流程時(shí)間調(diào)度問(wèn)題中同樣能夠發(fā)揮它高效的特點(diǎn)。本文所緊要講述零等待流水車(chē)間總流程時(shí)間調(diào)度問(wèn)題、差分進(jìn)化算法（DE）的流程和步驟，以及通過(guò)差分進(jìn)化算法（DE）解決NWFSP問(wèn)題的算法設(shè)計(jì)和各算例的算法仿真。上面已經(jīng)提到過(guò)，我們打算將最大完成時(shí)間和總流經(jīng)時(shí)間作為指標(biāo)來(lái)研究本文中所涉及到的調(diào)度問(wèn)題。在這里，需要注意幾個(gè)點(diǎn)：（1）零等待流水車(chē)間是探索本文的前提（2）必須通過(guò)差分進(jìn)化算法（DE）進(jìn)一步開(kāi)展車(chē)間調(diào)度的優(yōu)化（3）盡可能地把最大完成時(shí)間和總流程時(shí)間降至最低（4）提高企業(yè)以及工廠的生產(chǎn)效率，為企業(yè)謀取最大利潤(rùn)。各章節(jié)的主要內(nèi)容如下：第一章：緒論。能夠讓讀者更快更好的搞清楚本課題的來(lái)源以及背景，描述了本文主要講述的內(nèi)容以及該論文所表達(dá)的意義，更好的為下文做鋪墊。第二章：差分進(jìn)化算法。詳盡地介紹了該算法的含義，內(nèi)容，流程等，并且細(xì)致地描繪了如何運(yùn)用此算法來(lái)解決車(chē)間調(diào)度類的問(wèn)題。分別詳略得當(dāng)?shù)闹v解了車(chē)間調(diào)度和流水車(chē)間調(diào)度的概念，并且著重強(qiáng)調(diào)了零等待流水車(chē)間的有關(guān)內(nèi)容，包括概念、模型和優(yōu)化指標(biāo)等等。第三章：零等待流水車(chē)間。精細(xì)地向讀者闡述了零等待的內(nèi)含以及流水車(chē)間調(diào)度的概念，并著重介紹了零等待流水車(chē)間的概念含義以及我們所規(guī)定的優(yōu)化指標(biāo)的一系列計(jì)算。第四章：求解調(diào)度問(wèn)題的差分進(jìn)化算法設(shè)計(jì)。本章節(jié)通過(guò)進(jìn)一步對(duì)算法的介紹和過(guò)度，引用相關(guān)的例子，使讀者能夠自己動(dòng)腦，去更好的理解本文所講的主要方法。第五章：仿真實(shí)驗(yàn)與結(jié)果分析。對(duì)于上文中所提到的諸多相關(guān)算例，我們選取其中一部分進(jìn)行了仿真實(shí)驗(yàn)，我們通過(guò)圖表的形式讓讀者更直觀的體會(huì)和理解。第六章：總結(jié)與展望。作者對(duì)本文所寫(xiě)的內(nèi)容陳情并總結(jié)，表達(dá)作者對(duì)此類問(wèn)題的想法、建議與期望。本論文通過(guò)探究差分進(jìn)化算法（DE）來(lái)進(jìn)一步解決零等待流水車(chē)間總流程時(shí)間調(diào)度問(wèn)題。通過(guò)理論上的詳盡細(xì)致的描繪和分析，通過(guò)觀察與計(jì)算獲得解決此問(wèn)題的算法，并且使用計(jì)算機(jī)上的軟件進(jìn)行仿真實(shí)驗(yàn)，也可以選擇把流水車(chē)間的實(shí)例運(yùn)用差分進(jìn)化算法（DE）進(jìn)行仿真，得到最終的結(jié)果。差分進(jìn)化算法在車(chē)間流水線上的應(yīng)用有著深遠(yuǎn)影響與意義，因此企業(yè)可以通過(guò)此方法降低工件生產(chǎn)過(guò)程中的等待時(shí)間，大幅提高企業(yè)的工作效率，從而使企業(yè)在當(dāng)今競(jìng)爭(zhēng)力不斷增強(qiáng)的社會(huì)中取得一席之地。2差分進(jìn)化算法2.1差分進(jìn)化算法的含義差分進(jìn)化算法（DifferentialEvolutionAlgorithm,DE）是一種效率極高，涉及領(lǐng)域非常廣的算法，種群整體的啟發(fā)式搜索算法是它的基礎(chǔ)，這個(gè)種群里的每個(gè)個(gè)體都會(huì)有一個(gè)與之對(duì)應(yīng)的解向量。在進(jìn)化流程這一方面，差分進(jìn)化算法與遺傳算法也可以說(shuō)有著非常多的相似點(diǎn)了，兩者就像兄弟一樣，他們各自都包含這變異，雜交以及選擇這三個(gè)基本操作，那么關(guān)鍵來(lái)了，兩者之間最大的區(qū)別就是：對(duì)于操作的具體方法而言，兩者只能說(shuō)是大不相同了。如果你想要的更加明確的逼近效果，那么你就一定要選擇差分進(jìn)化算法了。差分進(jìn)化算法（DifferentialEvolutionAlgorithm,DE）是由科學(xué)家雷納斯托恩和肯尼恩普萊斯在1995年的時(shí)候最先提出的，人們把他的功能大部分定義在了求解實(shí)數(shù)優(yōu)化的問(wèn)題上，在很大程度上，我們也可以說(shuō)他是一種演化算法，它的優(yōu)點(diǎn)非常之多，由于結(jié)構(gòu)清晰易懂，流程很簡(jiǎn)單，人們想要完成它很容易。不僅如此，差分進(jìn)化算法的收斂速度極快，并且具有非常強(qiáng)的魯棒特性，所以它能夠在電磁領(lǐng)域，數(shù)字濾波器的構(gòu)造以及模式識(shí)別系統(tǒng)等方面具有非常廣泛的應(yīng)用。早在1996年，當(dāng)年的第一屆國(guó)際演化計(jì)算（ICEO）競(jìng)賽，比賽大致是在日本的名古屋進(jìn)行的，那次比賽就已發(fā)現(xiàn)并證明：差分進(jìn)化算法是世界上速度最快的算法。差分進(jìn)化算法（DifferentialEvolutionAlgorithm,DE）一般情況下都是通過(guò)使用浮點(diǎn)矢量來(lái)進(jìn)行編碼，從而生成種群個(gè)體，在進(jìn)行該算法來(lái)取得最優(yōu)解的過(guò)程中，第一步，我們首先要做的是要從父代個(gè)體中選擇兩個(gè)不同的個(gè)體進(jìn)行向量作差，從而就能夠得到差分矢量；第二步，選擇另外一個(gè)個(gè)體（不可同于第一步）與該差分矢量進(jìn)行求和，從而能夠生成實(shí)驗(yàn)個(gè)體；第三步，將父代個(gè)體與第二步中所得的實(shí)驗(yàn)個(gè)體進(jìn)行交叉操作；第四步也是最后一步，在父代個(gè)體與子代個(gè)體之間進(jìn)行選擇操作，把符合要求的個(gè)體保存到下一個(gè)群體中。2.2差分進(jìn)化算法的流程圖1差分進(jìn)化算法流程圖差分進(jìn)化算法（DE）的主要操作都是通過(guò)突變和選擇這兩個(gè)過(guò)程來(lái)實(shí)現(xiàn)的，這其中突變過(guò)程又包含了突變和選擇交叉兩部分，這兩部分的操作多數(shù)情況下被用于開(kāi)發(fā)工程和拓展系統(tǒng)，選擇過(guò)程主要是用于精確地選擇出能夠被進(jìn)一步利用的信息進(jìn)行接下來(lái)的操作。2.3差分進(jìn)化算法的意義差分進(jìn)化算法中數(shù)據(jù)很多，引用起來(lái)也十分復(fù)雜，所以相比與基于傳統(tǒng)微積分的方法，差分進(jìn)化算法有著更多的優(yōu)點(diǎn)，比如說(shuō)差分進(jìn)化算法的效率非常之高，并且局域廣闊，它不但具有著自我組織和適應(yīng)的特點(diǎn)，還可以自我學(xué)習(xí)。差分進(jìn)化算法整體而言，操作起來(lái)十分簡(jiǎn)潔方便，通俗易懂，對(duì)于測(cè)試各種的臨床實(shí)驗(yàn)問(wèn)題表現(xiàn)也是尤為突出，目前已成為現(xiàn)代進(jìn)化算法的研究熱點(diǎn)。2.4本章小結(jié)本章描述了差分進(jìn)化算法的含義，基本屬性，特點(diǎn)以及運(yùn)算方式，運(yùn)算流程，最后講述了差分進(jìn)化算法在實(shí)驗(yàn)及企業(yè)工廠中都具有非常重要的地位。近幾年來(lái)，差分進(jìn)化算法已成為現(xiàn)代進(jìn)化算法的研究熱點(diǎn)。3零等待流水車(chē)間3.1引言對(duì)于解決零等待流水車(chē)間調(diào)度問(wèn)題（NWFSP），至關(guān)重要就是“零等待”這個(gè)條件，那么問(wèn)題來(lái)了，什么叫“零等待”？“零等待”是指工件在生產(chǎn)流水線上，上一個(gè)步驟與下一個(gè)步驟之間沒(méi)有停頓，而在普通流水車(chē)間調(diào)度問(wèn)題上則是缺少了“零等待”這個(gè)約束條件，這也是兩者最大的不同之處。本章主要目的就在于解釋清楚零等待流水車(chē)間調(diào)度（NWFSP）的基本概念，以及向讀者們介紹它的數(shù)學(xué)模型和優(yōu)化指標(biāo)。對(duì)于零等待流水車(chē)間調(diào)度問(wèn)題（NWFSP）的優(yōu)化指標(biāo)，上文提過(guò)不止一次，我們接下來(lái)將主要描述最大完工時(shí)間（）和總流經(jīng)時(shí)間的計(jì)算。本章節(jié)將通過(guò)對(duì)以上兩個(gè)參數(shù)作為指標(biāo)來(lái)研究零等待流水車(chē)間調(diào)度問(wèn)題（NWFSP），目的就在于使用該算法大幅度提高企業(yè)工廠的工作效率，竭盡所能的減少產(chǎn)品完成所需要的時(shí)間，在近現(xiàn)代化工業(yè)生產(chǎn)中起到至關(guān)重要的作用。3.2NWFSP基本概念和模型經(jīng)過(guò)研究流水車(chē)間或者參考文獻(xiàn)書(shū)籍，網(wǎng)絡(luò)查閱等等，我們不難發(fā)現(xiàn)，零等待流水車(chē)間的調(diào)度問(wèn)題其實(shí)就可以描述為一個(gè)簡(jiǎn)單地問(wèn)題：有x個(gè)工件和y臺(tái)機(jī)器，當(dāng)這全部的工件分別在y臺(tái)機(jī)器上工作時(shí)，關(guān)鍵的一步在于x個(gè)工件在各自的機(jī)器上的加工順序要保證一致。某一個(gè)時(shí)刻是，每個(gè)工件只能在一臺(tái)機(jī)器加工，與此同時(shí)一臺(tái)機(jī)器在這一時(shí)刻也只能加工這一個(gè)工件；在這個(gè)過(guò)程中我們需要注意，我們還有一個(gè)約束條件——“零等待”，也就意味著一個(gè)工件在相鄰的兩臺(tái)機(jī)器之間工作時(shí)沒(méi)有片刻停頓的時(shí)間，必須連續(xù)加工。工件在每個(gè)機(jī)器上的加工時(shí)間已知。所研究的問(wèn)題是如何安排各工件的生產(chǎn)序列，我們所想要取得的是最小的優(yōu)化指標(biāo)。我們第一步要做的就是給模型中所能出現(xiàn)的變量定義值：x表示了產(chǎn)品的總數(shù)值；y表示了機(jī)器的總數(shù)值； 表示了該機(jī)器上的工作時(shí)間；表示了最大完成時(shí)間；表示了總流程時(shí)間；表示了該工件的完成時(shí)間。我們研究零等待流水車(chē)間調(diào)度的問(wèn)題時(shí)，大多數(shù)情況下會(huì)選擇使用混合整數(shù)規(guī)劃模型和有向圖模型來(lái)解決。由于時(shí)間有限，我們接下來(lái)會(huì)主要闡述混合整數(shù)規(guī)劃模型的方法，零等待流水車(chē)間的模型由下圖所示：首先，規(guī)定決策量 接下來(lái)一一列舉這其中的約束條件： （1） （2） （3） （4） （5） （6） （7）3.3優(yōu)化指標(biāo)和計(jì)算對(duì)于任何問(wèn)題的研究，我們都要制指定一個(gè)參考物，也就是本節(jié)所講述的優(yōu)化指標(biāo)，我們對(duì)于零等待流水車(chē)間總流程時(shí)間調(diào)度問(wèn)題的研究當(dāng)中，將會(huì)把最大完成時(shí)間（）和總流經(jīng)時(shí)間作為優(yōu)化指標(biāo)，并且詳盡描述最大完成時(shí)間和流經(jīng)總時(shí)間是如何計(jì)算的。（1）最大完成時(shí)間的計(jì)算方法零等待作為此加工過(guò)程的約束條件，兩個(gè)相鄰的工件與工件之間存在一個(gè)開(kāi)工時(shí)間差，將兩工件記為i-1和i，開(kāi)工時(shí)間差記為,則開(kāi)工時(shí)間差的計(jì)算式很容易可以獲得：（8）設(shè)常數(shù)π時(shí)刻，由此可得：QUOTEi=1n-1Ei，圖2調(diào)度甘特圖（2）總流程時(shí)間的計(jì)算方式通過(guò)了之前的計(jì)算，我們大致計(jì)算出了上文所提到的開(kāi)工時(shí)間差。我們可以根據(jù)這些推論求得總流經(jīng)時(shí)間的計(jì)算公式：（10）3.4本章小結(jié)針對(duì)這個(gè)課題，我們研究到這里，應(yīng)該已經(jīng)對(duì)它有了充分的理解，本章又詳盡的描述了零等待流水車(chē)間的含義，基本概念，模型，優(yōu)化指標(biāo)以及計(jì)算方法，同時(shí)，也對(duì)優(yōu)化指標(biāo)進(jìn)行了詳細(xì)的闡述，便于讀者理解，提供了相關(guān)的計(jì)算式，方便讀者對(duì)此類問(wèn)題進(jìn)行更深入的研究。4求解調(diào)度問(wèn)題的差分進(jìn)化算法設(shè)計(jì)4.1引言通過(guò)對(duì)于相關(guān)問(wèn)題的查閱，已經(jīng)對(duì)內(nèi)容進(jìn)行了總結(jié)和收集，本章節(jié)我想通過(guò)用各種實(shí)際算例來(lái)驗(yàn)證差分進(jìn)化算法（DE），要想通過(guò)實(shí)例來(lái)證明，我們就必須借助一些外力，對(duì)此我們打算使用c++語(yǔ)言來(lái)進(jìn)行編程的編寫(xiě)，進(jìn)一步實(shí)現(xiàn)算法設(shè)計(jì)。第二章中具體介紹了差分進(jìn)化算法的含義，基本屬性，特點(diǎn)以及運(yùn)算方式和流程，我們將會(huì)在這個(gè)前提下，把差分進(jìn)化算法進(jìn)一步描述，用具體事例來(lái)進(jìn)行證明，通過(guò)對(duì)算法的設(shè)計(jì)使讀者更好的了解，并將算法的設(shè)計(jì)步驟及應(yīng)用進(jìn)行到具體的程序當(dāng)中。4.2求解NWFSP問(wèn)題的算法對(duì)于解決零等待流水車(chē)間總流程時(shí)間調(diào)度問(wèn)題，我們上文一提到所規(guī)定的兩個(gè)優(yōu)化指標(biāo)——最大完工時(shí)間()和總流經(jīng)時(shí)間（），在這個(gè)基礎(chǔ)之上在進(jìn)行研究更加的得心用手。在這里我們要清楚，“如何用目標(biāo)函數(shù)編碼來(lái)實(shí)現(xiàn)這兩個(gè)參數(shù)的優(yōu)化目標(biāo)”是我們首要思考的問(wèn)題，而且在算法的過(guò)程當(dāng)中，判斷排列之間你是否可以相互取代也應(yīng)該通過(guò)比較最大完成時(shí)間和總流經(jīng)時(shí)間來(lái)實(shí)現(xiàn)的。當(dāng)然，我們的宗旨是要用差分進(jìn)化算法（DE）來(lái)解決全文所遇到的問(wèn)題。通過(guò)使用差分進(jìn)化算法解決零等待流水車(chē)間問(wèn)題操作步驟如下所述：步驟1：最先進(jìn)入種群初始化狀態(tài)，獲取Y個(gè)z維實(shí)數(shù)解向量。步驟2：計(jì)算出種群中每個(gè)個(gè)體的適應(yīng)值，并一一進(jìn)行判斷，判斷每個(gè)個(gè)體是否滿足終止條件，若滿足則輸出最優(yōu)結(jié)果，若不滿足則進(jìn)行以下操作。步驟3：將步驟2中不滿足終止條件的個(gè)體進(jìn)行變異操作，這個(gè)過(guò)程通俗來(lái)說(shuō)就是把兩個(gè)向量的向量差乘上變異算子，再與第三個(gè)向量相加得到新的變異向量。步驟4：為了增加干擾向量的多樣性，我們選擇引入交叉操作。這個(gè)過(guò)程中不可避免引入新變量CR，又名交叉算子。如果隨機(jī)產(chǎn)生的數(shù)值小于CR或者與之相等,那么就將變異后的種群放入下面的操作當(dāng)中，如果不是就將原來(lái)的種群放入接下來(lái)的操作當(dāng)中。步驟5：選擇操作很重要，它直接決定了種群中的向量是否能成為下一代的一員，這里需要注意的是試驗(yàn)向量只與一個(gè)個(gè)體進(jìn)行比較，而不是所有個(gè)體。選擇出的結(jié)果將再次進(jìn)行是否滿足終止條件的判斷。圖3流程圖4.3算法具體部分的設(shè)計(jì)（1）初始化階段對(duì)于整個(gè)過(guò)程最開(kāi)始的階段，初始排列是不可少的，我們可以通過(guò)差分進(jìn)化算法（DE）來(lái)產(chǎn)生。接下來(lái)使用for循環(huán)計(jì)算出所有工件的加工時(shí)間，將他們用sumtime整理出來(lái)，使得數(shù)據(jù)清晰，結(jié)果明確，讓人一眼便知結(jié)果。再次使用排列功能，以從大到小的排列次序?qū)⒐ぜ图庸r(shí)間依次排列清晰。把依次排好的排列放進(jìn)一個(gè)new函數(shù)中，求取最終結(jié)果，從而得到初始排列。最終獲得最優(yōu)排列。（2）差分進(jìn)化算法階段經(jīng)過(guò)了初始化階段，我們需要通過(guò)差分進(jìn)化算法解決零等待流水車(chē)間總流程時(shí)間的問(wèn)題，下面將展示差分進(jìn)化算法的步驟：{ 經(jīng)過(guò)初始化階段對(duì)變量進(jìn)行優(yōu)化，得到初始值，首先通過(guò)for循環(huán)計(jì)算出所有工件的加工時(shí)間，保證所有工件加工完畢，用冒泡序列對(duì)其進(jìn)行處理，就可以得到初始調(diào)度向量。for((j=0;j<product-1;j++){for(k=2;k<=machine;k++){for(h=2;h<=k;h++){比較temp與temp3值的大小關(guān)系可得=0，再次進(jìn)行for循環(huán)}}得到該運(yùn)算過(guò)程中的最大完成時(shí)間}將所得結(jié)果重復(fù)上述for循環(huán)可得cmax+=d.at(j)*(product-2-j)獲得總流程時(shí)間}4.4本章小結(jié) 本章當(dāng)中算法設(shè)計(jì)這部分是很難理解的一個(gè)難點(diǎn)，它非?？简?yàn)邏輯思維的轉(zhuǎn)換能力。在這里我們也把前兩章的內(nèi)容也進(jìn)行了充分地聯(lián)合，希望便于讀者的理解，對(duì)于算法設(shè)計(jì)的整體思想，以及算法設(shè)計(jì)的步驟，流程，我們可以去網(wǎng)絡(luò)上查看周刊，進(jìn)一步理解。本章的最后我們對(duì)分析的結(jié)果進(jìn)行了簡(jiǎn)單地解釋。5仿真實(shí)驗(yàn)與結(jié)果分析5.1引言上文中已經(jīng)提到過(guò)具體事例，那么第五章將會(huì)把這幾個(gè)典型的算例一一進(jìn)行測(cè)試。我們所使用的仿真系統(tǒng)——內(nèi)存為8G，Win10的操作系統(tǒng)，所用到的仿真軟件——VisualC++6.0。經(jīng)過(guò)對(duì)多組數(shù)據(jù)結(jié)果的分析和探究，求出最優(yōu)解，然后通過(guò)matlab畫(huà)出甘特圖，方便我們更清楚的得出結(jié)論。5.2算例介紹零等待流水車(chē)間總流程時(shí)間調(diào)度問(wèn)題可以說(shuō)成另外一個(gè)問(wèn)題，因?yàn)樗械乃憷际菄@一個(gè)問(wèn)題展開(kāi)的，經(jīng)過(guò)研究發(fā)現(xiàn)此類調(diào)度問(wèn)題一般情況下都是用“x個(gè)工件要在y臺(tái)機(jī)器上加工”來(lái)描述的，當(dāng)然我們也可以這樣理解——每個(gè)工件都有y道工序進(jìn)行加工。這里需要特別注意每個(gè)工件要在不同的機(jī)器上進(jìn)行加工，我們現(xiàn)在所研究的問(wèn)題，其主要目標(biāo)就是確定每臺(tái)機(jī)器上面工件的加工次序和開(kāi)工時(shí)間，我們只有求解出此數(shù)值才能實(shí)現(xiàn)最終目標(biāo)——獲得最優(yōu)實(shí)數(shù)解。當(dāng)我們探究零等待流水車(chē)間這類問(wèn)題時(shí)，我們必不可少的一個(gè)步驟——仿真實(shí)驗(yàn)，那我們拿什么來(lái)做仿真實(shí)驗(yàn)?zāi)?？這里就會(huì)引出本節(jié)重中之重的內(nèi)容——仿真算例的介紹。仿真算例大家都不會(huì)陌生，最為經(jīng)典的la問(wèn)題和abz問(wèn)題應(yīng)該也在很多文獻(xiàn)上看到過(guò)，對(duì)此我們就不多做介紹。經(jīng)過(guò)大量的實(shí)驗(yàn)研究，以及翻閱書(shū)籍和文獻(xiàn)，我們可以從中得知，這些算例得出了一些參考和值。實(shí)際生活中的算例都包含著大量的數(shù)據(jù)，每一個(gè)算例就相當(dāng)于一個(gè)小數(shù)據(jù)庫(kù)，如果一一來(lái)計(jì)算，不管是時(shí)間上，還是統(tǒng)計(jì)性能問(wèn)題上，都是很難實(shí)現(xiàn)的，所以在第五章中我將會(huì)選取其中的3組數(shù)據(jù)進(jìn)行運(yùn)算處理，分別為la10、abz5、la25，這兩組算例中的工件在設(shè)備上的處理時(shí)間如表1、表2、表3所示。其中表示第i個(gè)工件，表示第j臺(tái)設(shè)備。表1算例la10的加工時(shí)間G1G2G3G4G5H158449866H28997967784H37788813989H45721311573H54840497071H63482801233H7917555179H86247733511H96475509094H106720171271H115293682966H12705893777H1327826310103H148756362648H157632361512表2算例abz5的加工時(shí)間G1G2G3G4G527357747696H38668866766H491646210155H56988819993H64798646781H75888999796H89765835272H99488828667H105098816857表3算例la25的加工時(shí)間G1G2G3G4G5H11676173977H23983865989H36681454917H44486972260H55673764338H68071325274H79765782292H88986646168H94477124531H10632485333H112050771118H128573726076H131588143740H143291348388H1598702839925.3算例仿真上述三組數(shù)據(jù)abz5、la10、la25是我們從數(shù)據(jù)庫(kù)中選取出來(lái)的，機(jī)器數(shù)和工件數(shù)都比較少，容易計(jì)算和繪制甘特圖。我們將對(duì)這三組算例分別進(jìn)行以總流程時(shí)間為指標(biāo)的仿真實(shí)驗(yàn)。首先對(duì)abz5進(jìn)行仿真實(shí)驗(yàn)，由于該組數(shù)據(jù)中工件數(shù)較少，我們使用C++程序即可得出結(jié)果，最優(yōu)解如表4所示。表4abz5算例仿真運(yùn)行結(jié)果次數(shù)最優(yōu)序列最優(yōu)解1[74196281053]2170觀察該組仿真結(jié)果，我們進(jìn)行分析和比較，可以得到最優(yōu)總流程時(shí)間為2170，相對(duì)應(yīng)的最優(yōu)工序?yàn)閇74196281053]，我們將仿真所得到的的結(jié)果用甘特圖的形式展示出來(lái)。圖4abz5算例最優(yōu)工序仿真甘特圖然后我們對(duì)la10算例進(jìn)行仿真實(shí)驗(yàn)和甘特圖的繪制，所的結(jié)果如表4，圖5所示。表4la10算例仿真運(yùn)行結(jié)果次數(shù)最優(yōu)序列最優(yōu)解1[654139711015811122314]1290通過(guò)以上結(jié)果我們可以得出該算例的最優(yōu)總流程時(shí)間為1290，最優(yōu)序列為[654139711015811122314]，根據(jù)這些我們繪制出甘特圖。圖5la10算例最優(yōu)工序仿真甘特圖最后我們將la25算例進(jìn)行仿真實(shí)驗(yàn)和甘特圖的繪制