【正文】 遺傳算法與局部搜索方法有機(jī)結(jié)合起來，是改進(jìn)遺傳算法性能的一個(gè)卓有成效的方法。 遺傳算法執(zhí)行策略遺傳算法在執(zhí)行策略方面的下面幾方面工作值得注意:模擬退火（Simulated Annealing)是一種基于熱力學(xué)理論的優(yōu)化方法，并有著完善的全局收斂理論。第三種準(zhǔn)則有一定的自適應(yīng)性，例如根據(jù)算法的評(píng)價(jià)的一些規(guī)則。2. 終止規(guī)則遺傳算法的終止準(zhǔn)則通常有三種，一種是將某一個(gè)固定的最大代數(shù)作為停止算法的標(biāo)準(zhǔn)。變異率控制了新基因?qū)敕N群的比例。較高的交叉率可達(dá)到更大的解空間，但會(huì)因搜索不必要的解空間而耗費(fèi)大量的計(jì)算時(shí)間，從而降低停在非最優(yōu)解上的機(jī)會(huì)。迭代代數(shù)，即算法進(jìn)化代數(shù)，代數(shù)的大小直接關(guān)系到解的質(zhì)量和計(jì)算速度。Vl=[l0010011]在給定點(diǎn)變異后變?yōu)?V1*=[10011011]在遺傳操作中需注意的幾點(diǎn)問題:1. 參數(shù)及其選取種群規(guī)模記為Pop_Size，即種群中個(gè)體(染色體)的個(gè)數(shù)。一種簡單的變異方法是替換一個(gè)或多個(gè)基因。如若選擇交換第k個(gè)分量以后的所有分量，則兩個(gè)后代為sz =( v1（1），v2(1)，…，vk（1），vk+1（2），…vm（2）)sw =( v1（2），v2(2)，…，vk（2），vk+1（1），…vm（1）)組合優(yōu)化中的置換編碼遺傳算法通常采用部分映射交叉、次序交叉、循環(huán)交叉、基于位置的交叉，群交叉等操作。為了便于解釋，下面設(shè)解向量s1= (v1（1），v2(1)，…，vm（1）)和s1=( v1（2），v2（2），…，vm（2）)是兩個(gè)父解向量，sz={ s1 s2，…sm }和sw=( s1 ，s2，…sn)是通過雜交獲得的兩個(gè)后代。實(shí)數(shù)編碼遺傳算法的交叉操作類似于二進(jìn)制編碼遺傳算法。點(diǎn)式交叉算子分為單點(diǎn)交叉和多點(diǎn)交叉。錦標(biāo)賽選擇(tournament selection)。局部選擇(local selection)。通常有以下的算法可供選擇:輪盤賭選擇(roulette wheel selection)記種群規(guī)模為n，個(gè)體Vi的適值為(fvi)，則個(gè)體Vi被選擇的概率為然后，根據(jù)這些概率構(gòu)造一個(gè)轉(zhuǎn)輪，旋轉(zhuǎn)轉(zhuǎn)輪n次，每次選一個(gè)染色體加入新的種群。③選擇選擇即是在一個(gè)種群中選擇一個(gè)個(gè)體，它是隨機(jī)映射Ts:SN→S選擇操作的目的是為了避免當(dāng)前群體中有效基因的損失，使高性能的個(gè)體得以更大的概率生存，從而提高全局收斂性和計(jì)算效率。②適值函數(shù)即個(gè)體空間S到正實(shí)數(shù)空間的映射，適值函數(shù)f為 f:S→R+遺傳算法在搜索進(jìn)化過程中一般不需要其它外部信息，僅用適應(yīng)度函數(shù)值來評(píng)估個(gè)體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。實(shí)數(shù)編碼直接在解的表現(xiàn)型上進(jìn)行遺傳操作，目前在高維復(fù)雜優(yōu)化問題中得到廣泛應(yīng)用，并取得了較好效果。實(shí)數(shù)編碼將問題的解用一個(gè)實(shí)數(shù)來表示。針對(duì)優(yōu)化問題的編碼技術(shù)主要有二進(jìn)制編碼、十進(jìn)制編碼、實(shí)數(shù)編碼等。下面對(duì)關(guān)鍵參數(shù)與操作的設(shè)計(jì)做簡單介紹。(Mutation)：在細(xì)胞進(jìn)行復(fù)制時(shí)可能以很小的概率產(chǎn)生某些復(fù)制差錯(cuò)，從而使DNA發(fā)生某種變異，產(chǎn)生新的染色體，這些新的染色體表現(xiàn)出新的性狀。(crossover) ：有性生殖生物在繁殖下一代時(shí)兩個(gè)同源染色體之間通過交叉而重組，即在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個(gè)新的染色體。8. 編碼、解碼操作：遺傳算法必須包含兩個(gè)必需的數(shù)據(jù)轉(zhuǎn)換操作，即把搜索空間中的參數(shù)或解轉(zhuǎn)換成遺傳空間中的染色體或個(gè)體，稱為編碼操作，反之，稱為譯碼操作。7. 適應(yīng)度（Fitness）函數(shù)：適應(yīng)度表示某個(gè)體對(duì)于環(huán)境的適應(yīng)程度。串結(jié)構(gòu)空間對(duì)應(yīng)于遺傳學(xué)中的基因型（Genotype）的集合。5. 串結(jié)構(gòu)空間 SS：在串中，基因任意組合所構(gòu)成的串的集合。例如，有一個(gè)串 S = 1001，則其中的元素 1，0，0，1 分別稱為基因。3. 群體規(guī)模（Population Size）：群體中個(gè)體的數(shù)目成為群體個(gè)數(shù)，也稱為群體規(guī)?；蛉后w大小。2. 群體（Population）：一定數(shù)量的個(gè)體組成了群體，或叫種群。由于遺傳算法是自然遺傳學(xué)與計(jì)算機(jī)科學(xué)相互結(jié)合滲透的產(chǎn)物，因此在遺傳算法中借用了許多自然進(jìn)化的概念。基于遺傳算法以上的特點(diǎn)，本文選用遺傳算法作為求解優(yōu)化問題的有效方法。(5)黑箱式結(jié)構(gòu)。(4)對(duì)搜索空間沒有任何特殊要求(如連通性、凸性等)，只利用適應(yīng)性信息，不需要導(dǎo)數(shù)等其他輔助信息，適應(yīng)范圍更廣。(3)遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來進(jìn)行的，從而增加了其搜索過程的靈活性。(2)搜索過程是從一組解迭代到另一組解，采用同時(shí)處理群體中多個(gè)個(gè)體的方法，降低了陷入局部最優(yōu)解的可能性，并易于并行化。遺傳算法作為一種快捷、簡便、容錯(cuò)性強(qiáng)的算法，在各類結(jié)構(gòu)對(duì)象的優(yōu)化過程中顯示出明顯的優(yōu)勢。經(jīng)過幾十年的發(fā)展，遺傳算法已經(jīng)在數(shù)據(jù)挖掘、生產(chǎn)調(diào)度、函數(shù)優(yōu)化、圖象處理等領(lǐng)域得到成功的應(yīng)用，并顯示出其良好的性能，特別是在求解復(fù)雜優(yōu)化問題上的巨大潛力，使得幾乎所有領(lǐng)域的研究人員都嘗試過遺傳算法在各自專業(yè)領(lǐng)域的應(yīng)用，如:人工生命、神經(jīng)網(wǎng)絡(luò)、組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、系統(tǒng)辨識(shí)等等。由于它具有這些特點(diǎn)，從上世紀(jì)80年代以來，遺傳算法成為信息科學(xué)和運(yùn)籌優(yōu)化領(lǐng)域的一個(gè)研究熱點(diǎn)，并在數(shù)據(jù)挖掘、生產(chǎn)調(diào)度、函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)、圖像處理等多個(gè)領(lǐng)域得到廣泛應(yīng)用，被認(rèn)為是21世紀(jì)有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)之一。3 求解調(diào)度問題的遺傳算法 遺傳算法求解調(diào)度問題的優(yōu)越性遺傳算法（Genetic Algorithm, GA）是一類借鑒生物界“適者生存，優(yōu)勝劣汰”的遺傳機(jī)制演化而來的隨機(jī)化搜索算法。對(duì)此類多目標(biāo)優(yōu)化問題，常用數(shù)學(xué)規(guī)劃中的約束法、評(píng)價(jià)函數(shù)法、分層序列法、功效函數(shù)法等。③生產(chǎn)計(jì)劃與調(diào)度集成策略：生產(chǎn)計(jì)劃、調(diào)度的集成研究具有全局優(yōu)化的特征，也符合先進(jìn)制造模式的思想。②實(shí)時(shí)或動(dòng)態(tài)重調(diào)度策略：車間制造過程的隨機(jī)性、不確定性需要不斷地進(jìn)行重調(diào)度，以處理突發(fā)的事件。但同時(shí)LR算法的對(duì)偶問題存在搜索效率低，可行調(diào)度的構(gòu)造有待于進(jìn)一步研究等問題。搜索網(wǎng)絡(luò)（Hopfield）模型可以求解各種有約束的優(yōu)化問題，隨機(jī)Hopfield也可以用于解決jobshop的調(diào)度問題。該方法已經(jīng)用于解決nowshop調(diào)度問題。由于模擬退火法能以一定的概率接受差的能量值，因而有可能跳出局部極小，但它的收斂速度較慢，很難用于實(shí)時(shí)動(dòng)態(tài)調(diào)度環(huán)境。模擬退火法的改進(jìn)算法有加溫退火法、記憶退火法。該方法主要需要解決搜索效率和降低內(nèi)存使用問題，對(duì)大規(guī)模的問題需進(jìn)一步探討。在調(diào)度問題的離散圖模型基礎(chǔ)上，啟發(fā)式圖搜索法在調(diào)度領(lǐng)域得到應(yīng)用。3)很難對(duì)高級(jí)的調(diào)度規(guī)則建模。2)重用性差。比如，Petri網(wǎng)作為一種圖形建模工具可以形象地表示和分析FMS（柔性制造系統(tǒng)）中加工過程的并發(fā)和分布本質(zhì)，以及多項(xiàng)作業(yè)共享資源時(shí)的沖突現(xiàn)象。c)仿真的準(zhǔn)確性很大程度受編程人員的判斷和技巧的限制。該方法不可避免存在以下問題:a)缺乏理論意義。在八十年代后期，幾位學(xué)者先后開展了基于調(diào)度系統(tǒng)處于不同狀態(tài)，采用不同的調(diào)度規(guī)則策略的動(dòng)態(tài)調(diào)度方法的研究，其共同特點(diǎn)是:在支持某些活動(dòng)發(fā)生的資源條件具備時(shí)(稱為決策點(diǎn))，根據(jù)系統(tǒng)當(dāng)時(shí)所處的屬性轉(zhuǎn)臺(tái)，決定采取何種規(guī)則(策略)，確定或選擇活動(dòng)發(fā)生的順序和時(shí)間，即所謂的狀態(tài)指導(dǎo)的智能調(diào)度方法。如作業(yè)的平均等待時(shí)間、機(jī)床的平均利用率、作業(yè)總加工時(shí)間等。（2）基于啟發(fā)式規(guī)則的調(diào)度方法最早的近似算法便是基于啟發(fā)式規(guī)則的調(diào)度算法(也稱調(diào)度規(guī)則)，其本質(zhì)是給每一個(gè)生產(chǎn)任務(wù)和操作，并賦予優(yōu)先級(jí)，優(yōu)先級(jí)高的生產(chǎn)任務(wù)和操作優(yōu)先考慮。采用數(shù)學(xué)規(guī)劃的方法，表達(dá)清晰，易于在計(jì)算機(jī)上求解，但生產(chǎn)環(huán)境具有很多不確定的因素，存在建模不確定性和求解空間太大，造成計(jì)算困難，特別是不能反映特定調(diào)度領(lǐng)域的自然結(jié)構(gòu)，所以很難應(yīng)用經(jīng)驗(yàn)知識(shí)去處理調(diào)度問題。 調(diào)度問題優(yōu)化算法目前的車間調(diào)度問題的算法研究有很多，歸納起來主要有:（1）確定性最優(yōu)化方法該方法主要通過對(duì)車間調(diào)度問題建立一個(gè)數(shù)學(xué)模型，采用基于枚舉思想的分枝定界或動(dòng)態(tài)規(guī)劃法進(jìn)行求解，分枝定界法有很多，其主要不同點(diǎn)在于分枝規(guī)則、定界機(jī)制和上界的產(chǎn)生等三個(gè)方面的差異。每臺(tái)機(jī)床可加工工件的若干操作，并且在不同的機(jī)床上能加工的操作集可以不同。典型的車間調(diào)度問題包括一個(gè)要完成的作業(yè)集(工件集)，每個(gè)作業(yè)由一個(gè)操作集(工序集)組成，各操作的加工需要生產(chǎn)資源(機(jī)器、人員、刀具和輔助資源)，并且必須按一些可行的工藝次序進(jìn)行加工。生產(chǎn)的柔性體現(xiàn)在設(shè)備的使用和設(shè)備的安排兩個(gè)方面，設(shè)備使用的柔性是指設(shè)備可用于多個(gè)零件的多道工序加工，設(shè)備安排的柔性是指工件的設(shè)備加工路徑，而不是固定或預(yù)先確定的。但是，對(duì)于企業(yè)主來說，這樣必定會(huì)造成資源浪費(fèi)和制造成本的增加，于是出現(xiàn)了工件和相應(yīng)的工序數(shù)量多于生產(chǎn)資源的情況，也就出現(xiàn)了車間調(diào)度問題。切換加工的次數(shù)越多越有利于減少工件的庫存，但導(dǎo)致生產(chǎn)率的下降。生產(chǎn)車間出現(xiàn)調(diào)度問題主要原因是生產(chǎn)資源受到了制約。每一臺(tái)機(jī)器在每個(gè)時(shí)間只能加工某個(gè)工件的某道工序，只能在上道工序加工完成才能開始下一道工序的加工，前者稱為占用約束，后者稱為順序約束?，F(xiàn)代車間調(diào)度類型往往是Jobshop、Flowshop型。(5)靜態(tài)調(diào)度、動(dòng)態(tài)事實(shí)調(diào)度。(3)基于調(diào)度費(fèi)用和調(diào)度性能的指標(biāo)。按照不同的分類標(biāo)準(zhǔn)，可分為6種類型:(l)開環(huán)車間和閉環(huán)車間。(4)多目標(biāo)性調(diào)度的目標(biāo)很多，目標(biāo)之間往往又相互沖突。車間的生產(chǎn)能力不僅會(huì)受到機(jī)床的制約，還會(huì)受到工人和輔助工具的制約，各道工序的先后關(guān)系不能顛倒，如緩存容量、資源數(shù)量、工件到期時(shí)間與操作順序等也是制約因素。如機(jī)器故障、緊急任務(wù)插入、作業(yè)交貨期的變更等一些突發(fā)事件也增加了調(diào)度的難度和隨機(jī)性。(2)動(dòng)態(tài)隨機(jī)性調(diào)度中存在很多隨機(jī)性和不確定性。隨著問題規(guī)模的加大，計(jì)算量也急劇加工，所以調(diào)度問題往往沒有精確的解，通常是在解答過程中尋求其最優(yōu)解。車間中工件、機(jī)器、操作人員和搬運(yùn)系統(tǒng)之間相互影響、相互制約。并且分析結(jié)果的可行性，運(yùn)行時(shí)間以及目標(biāo)值。第四章將實(shí)際的車間作業(yè)問題抽象成數(shù)學(xué)模型，并且設(shè)計(jì)遺傳算法的基本算子以及操作。第三章簡要說明了遺傳算法的產(chǎn)生、發(fā)展、特點(diǎn)及操作流程。本文主要分五章，具體安排如下：第一章說明了課題的提出背景和研究意義，討論了車間調(diào)度的國內(nèi)外研究現(xiàn)狀，最后給出了本文的研究內(nèi)容和文章的結(jié)構(gòu)安排。 本文的研究內(nèi)容本文針對(duì)先進(jìn)制造環(huán)境下車間管理與調(diào)度的特點(diǎn)，分析了車間作業(yè)調(diào)度的特點(diǎn)，給出了遺傳算法求解車間作業(yè)調(diào)度的過程。隨著遺傳算法在作業(yè)調(diào)度方面的應(yīng)用，國內(nèi)也掀起了一股應(yīng)用遺傳算法研究車間作業(yè)調(diào)度問題的熱潮。1992年，Koza將遺傳算法應(yīng)用于計(jì)算機(jī)程序的優(yōu)化設(shè)計(jì)及自動(dòng)生成，提出了Genetic Programming(簡稱GP)的概念，Koza成功地將他提出的遺傳編程方法應(yīng)用到了人工智能、機(jī)器學(xué)習(xí)、符號(hào)處理等方面，進(jìn)一步證明了遺傳算法在解決NP問題方面的有效性[11]。遺傳算法的優(yōu)越性主要表現(xiàn)在搜索過程中不易陷入局部最優(yōu)，即使在所定義的適應(yīng)度函數(shù)不連續(xù)的情況下，也能以極大的概率找到最優(yōu)解[9]。90年代至今，隨著計(jì)算機(jī)應(yīng)用技術(shù)的發(fā)展，各種方法在車間調(diào)度問題的研究中得到了充分的發(fā)揮，同時(shí)新的研究手段層出不窮，人工智能、人工神經(jīng)網(wǎng)絡(luò)、基因遺傳算法的作業(yè)調(diào)度方法等被廣泛用于Jobshop調(diào)度問題的研究。大量的研究促使車間調(diào)度領(lǐng)域取得了豐碩的成果，產(chǎn)生了很多重要的調(diào)度方法。6070年代都是利用混合或純整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃和分枝定界法解決一些有代表性的問題，并開始重視調(diào)度復(fù)雜性的研究。 國內(nèi)外研究現(xiàn)狀綜述車間作業(yè)調(diào)度問題是一個(gè)經(jīng)典而又傳統(tǒng)的問題，對(duì)于它的研究始于20世紀(jì)50年代。因此，合理的生產(chǎn)調(diào)度是生產(chǎn)系統(tǒng)的高效運(yùn)行的前提，生產(chǎn)調(diào)度可以保證:生產(chǎn)計(jì)劃的有效實(shí)施；高效低耗地使用生產(chǎn)資源；均衡生產(chǎn)，減少在制品的資金占用；縮短產(chǎn)品生產(chǎn)周期、確保產(chǎn)品交貨期、降低生產(chǎn)成本，以適應(yīng)多變的市場需求。制造系統(tǒng)生產(chǎn)管理的核心就是車間生產(chǎn)調(diào)度，生產(chǎn)管理任務(wù)順利實(shí)施與完成，最終要靠合理的生產(chǎn)調(diào)度來保證。車間作業(yè)調(diào)度是一個(gè)交叉的研究領(lǐng)域，以數(shù)學(xué)為基礎(chǔ)，涉及運(yùn)籌學(xué)、計(jì)算機(jī)、控制工程和工業(yè)設(shè)計(jì)等多門學(xué)科。當(dāng)前在自動(dòng)化程度較高的生產(chǎn)系統(tǒng)中，使生產(chǎn)過程合理、高效運(yùn)行的調(diào)度問題變得非常復(fù)雜，需要建立有效的計(jì)算機(jī)調(diào)度控制策略、因此調(diào)度問題的研究具有重要的現(xiàn)實(shí)意義。計(jì)算機(jī)集成制造系統(tǒng)(CIMS)能給企業(yè)帶來巨大的綜合經(jīng)濟(jì)效益，因此國內(nèi)、外各大中型企業(yè)都研究與實(shí)施計(jì)算機(jī)集成制造系統(tǒng)。然而，當(dāng)前的產(chǎn)品的加工工藝復(fù)雜度相當(dāng)高，在調(diào)度任務(wù)規(guī)模較大且動(dòng)態(tài)多變的環(huán)境中，手工調(diào)度表現(xiàn)的非常低效甚至無法實(shí)現(xiàn)調(diào)度。一個(gè)調(diào)度方案就是按照作業(yè)內(nèi)在邏輯的先后順序條件將所有工序安排到機(jī)器上的一種方案。 課題的現(xiàn)實(shí)與理論意義車間作業(yè)調(diào)度問題(JobShop Scheduling Problem，JSP)的求解目標(biāo)是尋求某種最優(yōu)策略，找到的調(diào)度方案能將加工作業(yè)安排到車間制造機(jī)器上，并且使加工作業(yè)能夠最高效的完成。有關(guān)資料表明，在制造過程中95％的時(shí)間消耗在非切削過程中。在這