【基于遺傳算法的作業(yè)車間調度與仿真探究10000字（論文）】

基于遺傳算法的作業(yè)車間調度與仿真探究目錄摘要 [2]（FlexibleJobShopSchedulingProblem,FJSP）是傳統(tǒng)的Job-Shop調度問題的擴展，在上一大節(jié)所提到的作業(yè)車間的靜態(tài)調度問題中，工件的每一道工序只能在一臺確定的機床上加工，柔性作業(yè)車間調度問題是在這個問題的基礎之上，增加的調度的靈活性，使得每道工序可以在多臺機床上加工，并且在不同的機床上所需要的加工時間也不盡相同。所以對于柔性作業(yè)車間調度問題，機器約束減小，可行解的搜索范圍加大，使得問題也更加復雜。柔性作業(yè)車間調度問題的問題描述即為：m臺機器加工n種工件，每個工件有一道或者多道工序，工件的工序已經(jīng)確定；每道工序可以在不同的機器上加工，并且在不同的機器上加工的時間也不同。需要我們進行合理的安排調度，為每個工件每道工序選擇最合適的機器，確定每臺機器上的工件的工序的最佳加工順序，使得我們所要達到的性能指標最優(yōu)。其約束條件如下：1.同一時刻一臺機器只能加工一個零件；2.每個工件在某一時刻只能在一臺機器上加工，中途操作不能中斷；3.同一工件的工序有先后約束，不同工件的工序沒有先后約束；4.各個工件具有相同的優(yōu)先級。在此我們提出以下具體問題進行研究：表4.1FJSP例題1工件工序加工機器及時間M1M2M3M4M5M6M7M8J1O11535330109O121005839962O2157398090O22085267109O23010056417O24108964700J3O31100076524O320106489100O33145601007J4O4131659784O4212117810569O43462103957J5O51367890100O52100749860O5309874270O54119067536J6O61671469010O62110999764O63105910110100J7O71542670100O720909119105O73089386010J8O81285904010O82747890100O8399085671O8490371580（二）柔性作業(yè)車間調度問題的算法實現(xiàn)柔性作業(yè)車間調度問題是在傳統(tǒng)的作業(yè)車間調度問題的基礎之上所提出來的，因此在求解的思路上也大同小異，盡管在編碼解碼以及交叉等操作方面有所改動，但總體思路不變，只需按照前面所提到的流程思想繼續(xù)進行算法的編寫即可。1.編碼和解碼柔性作業(yè)車間調度問題相較于傳統(tǒng)的作業(yè)車間調度問題不僅僅要確定工序的加工順序，還要為每道工序選擇一臺合適的機器，因此像作業(yè)車間的靜態(tài)調度問題一樣僅僅使用基于工序的編碼方式不能得到問題的解。因此本文將其編碼分為兩部分組成，相當于每個個體擁有的是兩條染色體，第一部分仍然是基于工序的編碼，用來確定工序加工的先后順序；第二部分是基于機器分配的編碼，用來選擇加工每道工序的加工機器。例如以下一個個體：P1:131312322145233455其中第二行表示的是每一個工件的每一道工序分別在哪一臺機器上加工，如工件1的三道工序分別在機器1/4/5上加工。這樣表示的好處在于在接下來的交叉操作中，基于機器分配編碼基因中可以只使得同一個工件的同一個工序進行交換，這樣一來就能保證了所產(chǎn)生的子代的可行性。2.初始化種群較于作業(yè)車間靜態(tài)調度問題，柔性作業(yè)車間調度問題的種群初始化時要尤其注意個體的可行性，因為現(xiàn)在每一個個體擁有兩條染色體，在基于工序的編碼基礎之上，再通過將給出的工件的每一道工序的可加工機器作為一種約束，進而來產(chǎn)生初始化的種群個體。3.適應度計算適應度的計算也同傳統(tǒng)的作業(yè)車間調度問題一樣，將個體基因解碼之后將染色體轉化為調度方案，計算其加工時間，仍然選取適應度函數(shù)為加工時間的倒數(shù)。4.交叉操作由于現(xiàn)在的每個個體擁有了兩條染色體，在生物學上不同的染色體所控制的是不同的性狀，個體之間的基因交換僅限于控制相同性狀的染色體之間的基因交換，所以我們把基于工序編碼基因的染色體和基于機器分配編碼基因的染色體分別進行交叉，且由于這倆染色體所描述的信息的特性不同，所以對其進行的交叉操作采用不同的交叉方式。（1）基于工序編碼基因的交叉同靜態(tài)作業(yè)車間調度問題一樣，仍選擇IPOX交叉因子，其操作過程同3.2.4所述，在此不再贅述。（2）基于機器分配編碼基因的交叉對于機器分配編碼基因，在此選取了MPX交叉因子的方法。MPX交叉父代染色體中工序選定的機器，工序的加工順序保留到子代，其交叉過程如下所述：首先產(chǎn)生一個由0，1組成的長度同機器分配編碼基因相同的集稱為Z；對于父代P1和P2，其產(chǎn)生的子代C1和C2，若Z在某一處為0，則P1,C1;P2,C2在該處的值一一對應，反之若Z在某一處為1，則P1,C2;P2,C1在該處的值一一相對應。例如：P1:124561235125P2：426354221135010100010110則C1:124361225135C2:426554231125由于是同一工序的加工機器交換，所以產(chǎn)生的子代必定會是可行解。5.變異操作在此變異操作的目的為改善算法的局部搜索能力和維持群體多樣性，同時也防止出現(xiàn)早熟現(xiàn)象，對于兩種基因編碼在此采取不同的兩種變異方式。（1）基于工序編碼基因的變異同3.2.5所述。（2）基于機器分配編碼基因的變異鑒于在柔性作業(yè)車間調度問題中每一道工序都可以有多臺機器完成，故在此可隨機選擇一道工序，查閱這道工序可被加工的機器，并綜合考慮加工時間最短的那臺機器，實現(xiàn)變異操作。6.選擇操作同3.2.6所述。（三）FJSP仿真結果及分析同樣根據(jù)以上分析我們搭建了MATLAB模型來進行仿真，通過多次仿真得到以下結果：圖4.1FJSP第一次仿真甘特圖圖4.2FJSP第二次仿真甘特圖圖4.3FJSP第三次仿真甘特圖對比圖4.1，圖4.2，圖4.3所給出的甘特圖，F(xiàn)JSP所給出的問題模型更為的復雜，因此在求解上所具有的可能性也更多，仿真三次所得到的三個加工方案的最優(yōu)解并不相同，且不同方案之間也是有著較大的差別，故在FJSP問題上還有待繼續(xù)深入研究?？梢娤鄬τ谧鳂I(yè)車間的靜態(tài)調度問題，柔性作業(yè)車間調度問題更為復雜，可行解也更多，但已能基本實現(xiàn)要求，給出相應的解決問題的基本方案。五、總結與展望車間調度問題作為制造系統(tǒng)的核心，是企業(yè)提升競爭力的重要途徑，本文簡要的分析了車間調度問題，并且簡述了遺傳算法的基本原理。基于MATLAB仿真，研究了基于遺傳算法的JSP和FJSP兩個車間調度問題實例，更加深入的說明了調度問題的特點，表明了智能算法在解決傳統(tǒng)經(jīng)典問題上的可能性。本文僅僅是簡單的闡述了兩個經(jīng)典的車間調度問題，并且簡要的介紹了遺傳算法，然而車間調度問題并不是僅限于此，遺傳算法也可以通過與其他算法相結合，或者增添新的過程處理機制來實現(xiàn)更為優(yōu)秀的效果，作為一種通用的算法，遺傳算法有望應用在其他領域去解決一些其他問題。盡管目前為止對車間調度問題的研究已經(jīng)有了幾十年的歷史，也提出了眾多新穎新奇且實用的算法，但仍沒有一套系統(tǒng)的理論和方法來解決有關車間調度的這一類問題，且對車間調度問題的研究仍停留在理論上，與實際應用之間還存在著較大的差距，有待專家學者們繼續(xù)深入研究。參考文獻劉宏磊,張佳歡,謝添.作業(yè)車間調度問題(JSP)研究綜述報告[J].裝備制造技術,2015(12):235-237.AsmaFekih,HatemHadda,ImedKacem,AtidelB.HadjAlouane.AhybridgeneticTabusearchalgorithmforminimisingtotalcompletiontimeinaflexiblejob-shopschedulingproblem[J].EuropeanJournalofIndustrialEngineering,2021,14(6).PruetthaNanakorn,KonlakartnMeesomklin.ANovelPenaltySchemeinGeneticAlgorithmsForStructuralDesignOptimization[J].ASEANJournalonScienceandTechnologyforDevelopment,2000,17(2).王玨,唐青青.以培育新優(yōu)勢實現(xiàn)中國制造業(yè)轉型升級[J].西北大學學報(哲學社會科學版),2021,51(03):69-79.金晶,蘇勇.一種改進的自適應遺傳算法[J].計算機工程與應用,2005(18):64-69.張海濤.基于遺傳算法的車間作業(yè)調度問題研究[D].沈陽理工大學,2016.劉連成,陸淑珍,劉悅辰.整數(shù)規(guī)劃法在優(yōu)化模擬生產(chǎn)實習中的應用[J].襄陽職業(yè)技術學院學報,2014,13(01):11-14.DavidA.Plaisted.AHeuristicAlgorithmforSmallSeparatorsinArbitraryGraphs[J].SIAMJournalonComputing,2006,19(2).張煜東,吳樂南,王水花.專家系統(tǒng)發(fā)展綜述[J].計算機工程與應用,2010,46(19):43-47.周飛燕,金林鵬,董軍.卷積神經(jīng)網(wǎng)絡研究綜述[J].計算機學報,2017,40(06):1229-1251.朱祥磊.加速AI分布式訓練研究和實踐[J].電信技術,2019(12):28-31.黎靜華,韋化.求解機組組合問題的領域搜索法[J].中國電機工程學報,2008(13):33-40.王明.基于改進遺傳算法的作業(yè)車間調度問題研究[D].安徽工程大學,2019.呂文軍.基于BOM的柔性作業(yè)車間調度方法與信息系統(tǒng)研究[D].重慶大學,2016.韓明.遺傳算法在作業(yè)車間調度問題中的應用[D].吉林大