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

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