基于改進遺傳算法的車間作業(yè)調(diào)度問題研究

徐冬+簡正豪

摘 要：隨著科學技術(shù)的不斷進步，當下現(xiàn)代工業(yè)也在迅猛發(fā)展中，企業(yè)的生產(chǎn)也朝著多類型、少批量、高要求等水平發(fā)展，這使得企業(yè)在自身生產(chǎn)作業(yè)計劃安排和各部分工作規(guī)劃上難度增加。高效的展開車間調(diào)度能夠有效降低企業(yè)在工作過程中出現(xiàn)的操作問題，并能為企業(yè)帶來更優(yōu)質(zhì)的工程競爭。本文就針對眼下在作業(yè)車間調(diào)度中出現(xiàn)的問題以及基于遺傳算法的改進措施展開相關(guān)探究和討論。

關(guān)鍵詞：遺傳算法；車間作業(yè)調(diào)度；工廠運營管理；編碼與解碼

DOI：10.16640/j.cnki.37-1222/t.2017.19.035

0 前言

作業(yè)車間調(diào)度問題在很多現(xiàn)代工廠運營管理中都有發(fā)生，這也是制造系統(tǒng)的一大重點和難點。進行工廠車間調(diào)度是為了結(jié)合工廠生產(chǎn)的實際情況以及生產(chǎn)的具體任務展開對各個單位和各條流水線上工作任務、工作時間的安排，從而以最優(yōu)良的調(diào)度策略為工廠生產(chǎn)系統(tǒng)提供最高的經(jīng)濟效益。這對整個項目來說都有著重要意義。但是由于對每個工廠任務的要求不同，每次調(diào)度的方法和研究對象也有差異，這使得調(diào)度存在隨機性和不確定性，這給了實際規(guī)劃一定挑戰(zhàn)，對生產(chǎn)順利展開埋下了一定障礙。且隨著車間生產(chǎn)在產(chǎn)品制作和操作中涉及到的工種類不斷增多，在互聯(lián)網(wǎng)平臺支持下的管理能夠根據(jù)實際需要自動匹配出最佳的操作方式，并以較為便捷和高效的模式合理配置，從而發(fā)揮出數(shù)控機床在生產(chǎn)過程中的最大經(jīng)濟效益。因此研究有效的調(diào)度方式以及優(yōu)化對應生產(chǎn)技術(shù)是實現(xiàn)當下先進制造和高效生產(chǎn)的重要關(guān)鍵。

1 遺傳算法概述

其中，遺傳算法是較為普及的一種優(yōu)化算法，全稱是Genetic Programming（遺傳編程）。遺傳算法里的具體思想就是，為了解決目標問題，設計一個小的DSL，然后遺傳算法要演化的就是這門DSL的程序，就需要實現(xiàn)這個DSL的解釋器，以及評估程序質(zhì)量的fitness function和實現(xiàn)交叉/變異等操作的算子。如果你的算法里有自適應參數(shù)，那么可以用遺傳算法幫助你來調(diào)參。有些遺傳算法本身有自適應參數(shù)的，還可以用遺傳算法來優(yōu)化遺傳算法。在編碼技術(shù)和遺傳操作上來講都比較簡單易學，且在算法編程中具有一定的靈活性，所被制約的因素可以被忽略，能夠在一定范圍內(nèi)多條件并存，相對于當下工廠調(diào)度現(xiàn)狀而言，這種并存的技術(shù)就顯得十分關(guān)鍵且必要。一方面，運用遺傳算法能夠展開對車間的全局搜索，通過全局搜索在多樣的方案選擇中結(jié)合實際要求選擇出最佳的解決方案，另外，遺傳算法具有隱形并存性，可以極大減少運算求解的時間，對提高車間調(diào)度質(zhì)量以及方案效率有很多幫助。下面就對遺傳算法在車間調(diào)度中的具體解決方案施行展開相關(guān)研究和說明。

2 問題描述

例如說某個車間一共有a臺機器，這a臺機器需要加工b個工件，而每個工件又有n個工序，每個工序需用時t，那么在限定的時間氛圍內(nèi)每個機器只能加工一個工件，不同工序之間的順序可以打亂，但是要求工序要完成齊全，那么問怎么劃分各個工序以及機器所做工件時長才能時工件完成整個任務所需的總時間最短？

3 遺傳算法的設計

3.1 編碼與解碼

在遺傳算法中就可采用按工序的實數(shù)編碼，像是生物基因?qū)W中的染色體DNA編碼與解碼。將每一道工序給予一定數(shù)字編號，比如說123...然后按照預先對車間工序展開流程調(diào)度方案研究，比如說是有三道工序要在三臺機器上運作，工序一用1表示，機器一用1表示，在編碼中工序就有211123233 ，機器使用順序有112332213，對該編碼解碼，也就是表示第一次出現(xiàn)的2道工序是在第1臺機器上加工，第2次出現(xiàn)的第2道工序是在第3臺機器上加工.....以此展開對車間生產(chǎn)中各個工序與機器使用的規(guī)劃和處理。在編碼與解碼的過程中，就好比是提前給車間流程劃定流程，并用數(shù)列表示，然后再將該數(shù)列轉(zhuǎn)化成對應的工序與設備。通過這種編碼與解碼的方式從而優(yōu)化對車間調(diào)度的流程設計，使得整體更加方便和快捷。

3.2 種群生成

在遺傳算法中很多都運用到了生物遺傳學知識，比如說在生物進化初期，早期是由遺傳的一小部分群體不斷進化，并在選擇中占據(jù)優(yōu)勢，由此成為種群的大多數(shù)而最終存活。相應的在調(diào)度方案中就可以優(yōu)化算法展開，在眾多算法中選擇出某個超級個體，以此保證整個車間運作能夠順利且高效的展開。具體的操作步驟首先需判斷種群的容納程度，也就是某一調(diào)度問題的整個算法容量有多少，確定容量后，還需要對各個條件的淘汰率進行統(tǒng)計。然后計算每個算法的最大適應度，也就是針對當下在車間生產(chǎn)中的具體要求，能夠在滿足各項條件的同時適用性最強。并采取隨機抽查檢驗的策略，測定該種算法的適用值是多少，然后在多個調(diào)度條例中選擇最佳的算法。此外，為了提高算法的多樣性，還能在算法適度檢驗中不斷優(yōu)化算法編程，讓算法能夠與其他算法有更多交叉和選擇的機會，能夠整合多個算法的優(yōu)勢展開。

3.3 遺傳操作

在遺傳算法的車間調(diào)度中，選用通過遺傳操作，先選擇出適應值最高的算法，然后以該算法為基準，并交叉和其他算法一并檢驗和整理加強，由此優(yōu)化第一條適應性較強的算法。在確定選擇后的算法，再將其進行交叉操作，交叉也是為了優(yōu)化該原始算法的算法精確度，在交叉中也會引起算法的變異，像是變異互換變異等，若出現(xiàn)變異的情況則說明算法在實際使用中是難以確保其穩(wěn)定性的，因此要進行反饋和重新編程。

4 總結(jié)

綜上所述，本文介紹了遺傳算法的具體操作方式以及在車間調(diào)度中的實踐方法，通過分析作業(yè)車間調(diào)度問題的特性，針對該特性確定了遺傳算法的優(yōu)勢，采用遺傳算法的并用性和全局性，在面對選擇多、變動大的前提條件下，使用遺傳算法無不能夠提高運算的效率和準確率，使得運算有更多的發(fā)揮空間，對車間的經(jīng)濟效益提升也有一定幫助。

參考文獻：

[1]李輝，陳根社.機床控制系統(tǒng)設計的遺傳特征結(jié)構(gòu)配置方法[A].2011年中國智能自動化學術(shù)會議暨智能自動化專業(yè)委員會成立大會論文集（下冊）[C].2011.

[2]彭宏，歐慶鈴，歐永斌.具有退火選擇的遺傳算法的收斂速度估計[A].2012年中國智能自動化學術(shù)會議論文集（下冊）[C].2012.endprint