《基于遺傳算法的作業(yè)車間調(diào)度問題實證研究》10000字（論文）

[18]（FlexibleJobShopSchedulingProblem,FJSP）是傳統(tǒng)的Job-Shop調(diào)度問題的擴展，作業(yè)車間的靜態(tài)調(diào)度問題中工件要在確定的機器上加工；而本節(jié)所研究的柔性作業(yè)車間調(diào)度，有多臺機器可以對某一個工件的某一道工序進行加工，并且他們的加工時間也不相同，如此一來就指數(shù)倍的增加了可行解的數(shù)量，大大增加了求解的難度。柔性作業(yè)車間調(diào)度問題的問題描述即為：一個作業(yè)車間中有m臺機器，現(xiàn)需要在這m臺機器上加工n個工件，這n個工件中每個工件都需要若干道的加工工序，每道工序只能在某幾臺特定的機器上才能加工，并且在這幾臺不同的機器上加工所需要的加工時間也不一樣；每個工件只有完成前一道工序才可以繼續(xù)進行下一道工序，要求合理的對工件的加工順序及加工機器進行調(diào)度分配，使得加工時間能夠達到最短。其約束條件如下：1.每個工件只有完成上一道工序才可以進行下一道工序；2.每個工件的每道工序在不同機器上加工的優(yōu)先級都相同；3.各個工件的各道工序在同一臺機器上的加工優(yōu)先級都相同；4.每臺機器在同一時刻只能加工一個工件的一道工序；5.每個工件在同一時刻只能被一臺機器加工一道工序；6.不考慮機器損壞及加工人意愿。在此我們提出以下具體問題進行研究：表4.1FJSP例題1工件工序加工機器及時間M1M2M3M4M5M6M7M8J1114432108712806654761308075357J221483670100220744859723080546282499769600J3318009668232095778903323470908J441425688924210128795684338595427J55146561009052809657605307958760541010089648J66158524809621208895736398813120110J7717535801107208081289673010849708J8813768050128284375012083880876318480452670（二）柔性作業(yè)車間調(diào)度問題的算法實現(xiàn)柔性作業(yè)車間調(diào)度問題是在傳統(tǒng)的作業(yè)車間調(diào)度問題的基礎(chǔ)之上所提出來的，因此在求解的思路上也大同小異，盡管在編碼解碼以及交叉等操作方面有所改動，但總體思路不變，只需按照前面所提到的流程思想繼續(xù)進行算法的編寫即可。1.編碼和解碼在作業(yè)車間的靜態(tài)調(diào)度問題中每個個體只有一條染色體，代表的是工件的加工順序。在柔性作業(yè)車間的調(diào)度問題中，由于我們放寬了加工機器對于工件加工的約束，使得我們可行解的范圍增大，因此我們在JSP基礎(chǔ)之上為每一個個體增加了一條染色體。第一條染色體同靜態(tài)調(diào)度中個體的染色體一樣代表工件的加工工序，而第二條染色體表示的是每一個工件的每一個工序的加工機器，這樣就能夠完整的表現(xiàn)出工件的加工方案。例如以下一個個體：P1:131312322145233455其中第二行表示的是每一個工件的每一道工序分別在哪一臺機器上加工，如工件1的三道工序分別在機器1/4/5上加工。這樣表示的好處在于在接下來的交叉操作中，基于機器分配編碼基因中可以只使得同一個工件的同一個工序進行交換，這樣一來就能保證了所產(chǎn)生的子代的可行性。2.初始化種群柔性作業(yè)車間調(diào)度問題的種群初始化時要尤其注意個體的可行性，因為現(xiàn)在每一個個體擁有兩條染色體，在基于工序的編碼基礎(chǔ)之上，再通過將給出的工件的每一道工序的可加工機器作為一種約束，進而來產(chǎn)生初始化的種群個體。3.適應度計算適應度的計算也同傳統(tǒng)的作業(yè)車間調(diào)度問題一樣，將個體基因解碼之后將染色體轉(zhuǎn)化為調(diào)度方案，計算其加工時間，仍然選取適應度函數(shù)為加工時間的倒數(shù)。4.交叉操作由于現(xiàn)在的每個個體擁有了兩條染色體，在生物學上不同的染色體所控制的是不同的性狀，個體之間的基因交換僅限于控制相同性狀的染色體之間的基因交換，所以我們把基于工序編碼基因的染色體和基于機器分配編碼基因的染色體分別進行交叉，且由于這倆染色體所描述的信息的特性不同，所以對其進行的交叉操作采用不同的交叉方式。（1）基于工序編碼基因的交叉同靜態(tài)作業(yè)車間調(diào)度問題一樣，仍選擇IPOX交叉因子，其操作過程同3.2.4所述，在此不再贅述。（2）基于機器分配編碼基因的交叉對于機器分配編碼基因，在此選取了MPX交叉因子的方法。它能夠?qū)庸ろ樞蚝图庸C器分別進行交叉，其交叉過程如下所述：首先產(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.變異操作在此變異操作的目的為改善算法的局部搜索能力和維持群體多樣性，也能夠防止算法過早收斂，對于兩種基因編碼在此采取不同的兩種變異方式。（1）基于工序編碼基因的變異同3.2.5所述。（2）基于機器分配編碼基因的變異鑒于在柔性作業(yè)車間調(diào)度問題中每一道工序都可以有多臺機器完成，故在此可隨機選擇一道工序，查閱這道工序可被加工的機器，并綜合考慮加工時間最短的那臺機器，實現(xiàn)變異操作。6.選擇操作同3.2.6所述。（三）FJSP仿真結(jié)果及分析同樣根據(jù)以上分析我們搭建了MATLAB模型來進行仿真，通過多次仿真得到以下結(jié)果：圖4.1FJSP第一次仿真甘特圖圖4.2FJSP第二次仿真甘特圖圖4.3FJSP第三次仿真甘特圖對比圖4.1，圖4.2，圖4.3所給出的甘特圖，F(xiàn)JSP所給出的問題模型更為的復雜，因此在求解上所具有的可能性也更多，仿真三次所得到的三個加工方案的最優(yōu)解并不相同，且不同方案之間也是有著較大的差別，故在FJSP問題上還有待繼續(xù)深入研究。可見相對于作業(yè)車間的靜態(tài)調(diào)度問題，柔性作業(yè)車間調(diào)度問題更為復雜，可行解也更多，但已能基本實現(xiàn)要求，給出相應的解決問題的基本方案。五、總結(jié)與展望車間調(diào)度問題作為制造系統(tǒng)的核心，是企業(yè)提升競爭力的重要途徑，本文簡要的分析了車間調(diào)度問題，并且簡述了遺傳算法的基本原理。基于MATLAB仿真，研究了基于遺傳算法的JSP和FJSP兩個車間調(diào)度問題實例，更加深入的說明了調(diào)度問題的特點，表明了智能算法在解決傳統(tǒng)經(jīng)典問題上的可能性。本文僅僅是簡單的闡述了兩個經(jīng)典的車間調(diào)度問題，并且簡要的介紹了遺傳算法，然而車間調(diào)度問題并不是僅限于此，遺傳算法也可以通過與其他算法相結(jié)合，或者增添新的過程處理機制來實現(xiàn)更為優(yōu)秀的效果，作為一種通用的算法，遺傳算法有望應用在其他領(lǐng)域去解決一些其他問題。盡管目前為止對車間調(diào)度問題的研究已經(jīng)有了幾十年的歷史，也提出了眾多新穎新奇且實用的算法，但仍沒有一套系統(tǒng)的理論和方法來解決有關(guān)車間調(diào)度的這一類問題，且對車間調(diào)度問題的研究仍停留在理論上，與實際應用之間還存在著較大的差距，有待專家學者們繼續(xù)深入研究。參考文獻肖艷伶.金融科技創(chuàng)新對實體經(jīng)濟發(fā)展的影響研究[J].河北農(nóng)機,2021(04):94-95.王玨,唐青青.以培育新優(yōu)勢實現(xiàn)中國制造業(yè)轉(zhuǎn)型升級[J].西北大學學報(哲學社會科學版),2021,51(03):69-79.PruetthaNanakorn,KonlakartnMeesomklin.ANovelPenaltySchemeinGeneticAlgorithmsForStructuralDesignOptimization[J].ASEANJournalonScienceandTechnologyforDevelopment,2000,17(2).金晶,蘇勇.一種改進的自適應遺傳算法[J].計算機工程與應用,2005(18):64-69.張海濤.基于遺傳算法的車間作業(yè)調(diào)度問題研究[D].沈陽理工大學,2016.劉連成,陸淑珍,劉悅辰.整數(shù)規(guī)劃法在優(yōu)化模擬生產(chǎn)實習中的應用[J].襄陽職業(yè)技術(shù)學院學報,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)絡(luò)研究綜述[J].計算機學報,2017,40(06):1229-1251.朱祥磊.加速AI分布式訓練研究和實踐[J].電信技術(shù),2019(12):28-31.黎靜華,韋化.求解機組組合問題的領(lǐng)域搜索法[J].中國電機工程學報,2008(13):33-40.劉宏磊,張佳歡,謝添.作業(yè)車間調(diào)度問題(JSP)研究綜述報告[J].裝備制造技術(shù),2015(12):235-237.王明.基于改進遺傳算法的作業(yè)車間調(diào)度問題研究[D].安徽工程大學,2019.韓明.遺傳算法在作業(yè)車間調(diào)度問題中的應用[D].吉林大學,2015.張超勇,饒運清,劉向軍,李培根.基于POX交叉的遺傳算法求解Job-Shop調(diào)度問題[J].中國機械工程,2004(23):83-87.王芳,邱玉輝.一種引入輪盤賭選擇算子的混合粒子群算法[J].西南師范大學學報(自然科學版),2006(03):93-96.何燕.基于遺傳算法的車間調(diào)度優(yōu)化及其仿真[D].武漢理工大學,2006.AsmaFekih,HatemHad