【正文】 的研究。由于車間調度問題的復雜性，各種不同的具體問題往往有不同的解決方法。大量的研究促使車間調度領域取得了豐碩的成果，產生了很多重要的調度方法。隨著70年代后期調度理論研究的深入及各種交叉學科的發(fā)展，又涌現(xiàn)出了許多新的車間調度理論與方法，如：基于運籌學（OR）方法[6]、基于控制的方法、基于DEDS（離散事件動態(tài)系統(tǒng)）的解析模型方法、模擬退火法，啟發(fā)式算法[10]，禁忌搜索法[7]以及拉格朗日約束松弛法[8]等，代表著經典調度理論趨向成熟。90年代至今，隨著計算機應用技術的發(fā)展，各種方法在車間調度問題的研究中得到了充分的發(fā)揮，同時新的研究手段層出不窮，人工智能、人工神經網(wǎng)絡、基因遺傳算法的作業(yè)調度方法等被廣泛用于Jobshop調度問題的研究。Davis是最早把遺傳算法應用于車間調度問題的學者之一，他在使用GA求解車間調度的問題的研究中取得了近似最優(yōu)解。遺傳算法的優(yōu)越性主要表現(xiàn)在搜索過程中不易陷入局部最優(yōu)，即使在所定義的適應度函數(shù)不連續(xù)的情況下，也能以極大的概率找到最優(yōu)解[9]。此后，很多學者就遺傳算法在車間調度問題方面的應用做了大量研究。1992年，Koza將遺傳算法應用于計算機程序的優(yōu)化設計及自動生成，提出了Genetic Programming(簡稱GP)的概念，Koza成功地將他提出的遺傳編程方法應用到了人工智能、機器學習、符號處理等方面，進一步證明了遺傳算法在解決NP問題方面的有效性[11]。國內對于車間調度問題的研究起步比較晚，基本上是靠調度人員的經驗進行車間作業(yè)分配和調度。隨著遺傳算法在作業(yè)調度方面的應用，國內也掀起了一股應用遺傳算法研究車間作業(yè)調度問題的熱潮。目前,研究工作主要集中在清華大學等CIMS(Computer Integrated Manufacturing System)國家重點實驗室，這些實驗室的系統(tǒng)開發(fā)基本上還處于試用階段，距離開發(fā)出成熟的軟件系統(tǒng)還有很長一段距離，因此還需要投入大量的人力物力進行該方面的研究。 本文的研究內容本文針對先進制造環(huán)境下車間管理與調度的特點，分析了車間作業(yè)調度的特點，給出了遺傳算法求解車間作業(yè)調度的過程。通過研究與分析車間作業(yè)調度系統(tǒng)，給出了調度的數(shù)學模型，運用Matlab遺傳算法工具箱進行了仿真調度，并分析了結果。本文主要分五章，具體安排如下：第一章說明了課題的提出背景和研究意義，討論了車間調度的國內外研究現(xiàn)狀，最后給出了本文的研究內容和文章的結構安排。第二章詳細闡述了車間作業(yè)調度問題，分析了調度模型及模型描述，總結了車間調度的求解方法。第三章簡要說明了遺傳算法的產生、發(fā)展、特點及操作流程。重點研究了遺傳算法在車間作業(yè)調度優(yōu)化中的操作過程，包括了編碼方式、種群大小、交叉方式與概率、變異方法與概率等參數(shù)的選擇。第四章將實際的車間作業(yè)問題抽象成數(shù)學模型，并且設計遺傳算法的基本算子以及操作。第五章運用Matlab遺傳算法工具箱，通過編碼實現(xiàn)模擬作業(yè)調度。并且分析結果的可行性，運行時間以及目標值。第 34 頁 共 34 頁 2 車間作業(yè)調度算法 調度問題特點與分類調度問題的主要特點有:(1)建模、計算復雜性。車間中工件、機器、操作人員和搬運系統(tǒng)之間相互影響、相互制約。每個工件又要考慮它的加工時間、安裝時間和操作順序等因素，因而相當復雜，調度問題往往是通過等式或不等式等約束條件來計算的，屬于典型的NPhard問題。隨著問題規(guī)模的加大，計算量也急劇加工，所以調度問題往往沒有精確的解，通常是在解答過程中尋求其最優(yōu)解。在現(xiàn)有計算條件下，一般優(yōu)化方法對于車間調度問題是低效甚至是無能為力的。(2)動態(tài)隨機性調度中存在很多隨機性和不確定性。如機器故障、作業(yè)交貨期的變更，如工件到達時間的不確定性，實際工件的加工時間也有一定的隨機性。如機器故障、緊急任務插入、作業(yè)交貨期的變更等一些突發(fā)事件也增加了調度的難度和隨機性。(3)多約束性調度中受到很多約束條件的限制。車間的生產能力不僅會受到機床的制約，還會受到工人和輔助工具的制約，各道工序的先后關系不能顛倒，如緩存容量、資源數(shù)量、工件到期時間與操作順序等也是制約因素。此外，還有人為的附加因素，如機器負荷平衡等等約束條件。(4)多目標性調度的目標很多，目標之間往往又相互沖突。如基于作業(yè)交貨期的目標、基于作業(yè)完成時間的目標、基于生產成本的目標等。按照不同的分類標準，可分為6種類型:(l)開環(huán)車間和閉環(huán)車間。(2)單臺處理機、多臺并行機、Job—shop和Flow—shop。(3)基于調度費用和調度性能的指標。(4)確定性調度、隨機性調度。(5)靜態(tài)調度、動態(tài)事實調度。(6) 有序加工，無序加工?，F(xiàn)代車間調度類型往往是Jobshop、Flowshop型。 車間作業(yè)調度問題描述一般車間調度問題可以描述為:n個工件在m臺機器上加工，每個工件分為k道工序，每道工序可在不同的機器上加工。每一臺機器在每個時間只能加工某個工件的某道工序，只能在上道工序加工完成才能開始下一道工序的加工，前者稱為占用約束，后者稱為順序約束。調度的結果就是確定決策方案，決策內容包括分配決策(工件的加工順序)和時間決策(工件各工序的加工時間)以及路徑決策(工件工序的加工設備的分配)。生產車間出現(xiàn)調度問題主要原因是生產資源受到了制約。車間調度的問題是多個工件在有限的機器上加工，每臺機器在切換不同的工件加工時又需要一定的生產加工準備時間。切換加工的次數(shù)越多越有利于減少工件的庫存，但導致生產率的下降。如果車間有足夠多的機床設備和其它生產資源分配給每個工件或每條工藝加工路線，那么一切都會井然有序，也就不存在調度問題。但是，對于企業(yè)主來說，這樣必定會造成資源浪費和制造成本的增加，于是出現(xiàn)了工件和相應的工序數(shù)量多于生產資源的情況，也就出現(xiàn)了車間調度問題。因此，需要在庫存成本與切換加工次數(shù)頻率之間尋求一個動態(tài)的平衡。生產的柔性體現(xiàn)在設備的使用和設備的安排兩個方面，設備使用的柔性是指設備可用于多個零件的多道工序加工，設備安排的柔性是指工件的設備加工路徑，而不是固定或預先確定的。具有可選的路徑，可以通過將若干設備組作為一條或者多條生產線加工一種工件，使得該工件的生產率最大。典型的車間調度問題包括一個要完成的作業(yè)集(工件集)，每個作業(yè)由一個操作集(工序集)組成，各操作的加工需要生產資源(機器、人員、刀具和輔助資源)，并且必須按一些可行的工藝次序進行加工。車間調度就是對一個可用的加工機床集在時間和空間上進行加工任務集分配，以達到生產性能指標最優(yōu)化。每臺機床可加工工件的若干操作，并且在不同的機床上能加工的操作集可以不同。調度的目標是將作業(yè)合理地安排到各機床以及合理地使用其它生產資源，并合理安排作業(yè)的加工次序和加工時間，使約束條件被滿足，同時優(yōu)化其中的一些生產性能指標。 調度問題優(yōu)化算法目前的車間調度問題的算法研究有很多，歸納起來主要有:（1）確定性最優(yōu)化方法該方法主要通過對車間調度問題建立一個數(shù)學模型，采用基于枚舉思想的分枝定界或動態(tài)規(guī)劃法進行求解，分枝定界法有很多，其主要不同點在于分枝規(guī)則、定界機制和上界的產生等三個方面的差異。這類方法從理論上來說是能求得最優(yōu)解，但通常由于計算復雜性原因，不能獲得真正的實用。采用數(shù)學規(guī)劃的方法，表達清晰，易于在計算機上求解，但生產環(huán)境具有很多不確定的因素，存在建模不確定性和求解空間太大，造成計算困難，特別是不能反映特定調度領域的自然結構，所以很難應用經驗知識去處理調度問題。采用數(shù)學規(guī)劃的方法大致可以分為三類：簡單規(guī)則、復合規(guī)則、啟發(fā)式規(guī)則。（2）基于啟發(fā)式規(guī)則的調度方法最早的近似算法便是基于啟發(fā)式規(guī)則的調度算法(也稱調度規(guī)則)，其本質是給每一個生產任務和操作，并賦予優(yōu)先級，優(yōu)先級高的生產任務和操作優(yōu)先考慮。這類方法因調度規(guī)則易于實現(xiàn)，計算復雜度低，能夠用于動態(tài)實時調度系統(tǒng)中，許多年來一直受到廣泛關注和研究，并不斷涌現(xiàn)許多新的調度規(guī)則。如作業(yè)的平均等待時間、機床的平均利用率、作業(yè)總加工時間等。（3）基于知識的調度方法近年來受實際需要的推動，基于知識的智能調度系統(tǒng)和方法的研究取得了很大的進展，基于只是的調度方法是用專家系統(tǒng)自動產生調度或輔助人去調度，它是傳統(tǒng)的調度方法與基于知識的調度評價相結合的方法。在八十年代后期，幾位學者先后開展了基于調度系統(tǒng)處于不同狀態(tài)，采用不同的調度規(guī)則策略的動態(tài)調度方法的研究，其共同特點是:在支持某些活動發(fā)生的資源條件具備時(稱為決策點)，根據(jù)系統(tǒng)當時所處的屬性轉臺，決定采取何種規(guī)則(策略)，確定或選擇活動發(fā)生的順序和時間，即所謂的狀態(tài)指導的智能調度方法。（4）仿真調度方法由于制造系統(tǒng)的復雜性，很難用一個精確的解析模型來進行描述分析，而通過對仿真模型的運行收集數(shù)據(jù)，就能對實際系統(tǒng)進行性能，狀態(tài)方面的分析，從而能對系統(tǒng)采用合適的控制調度方法。該方法不可避免存在以下問題:a)缺乏理論意義。b)應用仿真進行生產調度的費用很高。c)仿真的準確性很大程度受編程人員的判斷和技巧的限制。（5）基于DEDS的解析模型方法現(xiàn)實中的制造系統(tǒng)往往是離散事件系統(tǒng)，因此可以用研究離散事件系統(tǒng)解析模型和方法探討車間調度問題，諸如排隊論、極大極小代數(shù)模型、Petri網(wǎng)等。比如，Petri網(wǎng)作為一種圖形建模工具可以形象地表示和分析FMS（柔性制造系統(tǒng)）中加工過程的并發(fā)和分布本質，以及多項作業(yè)共享資源時的沖突現(xiàn)象。Petri網(wǎng)具有很強地建模能力，對于描述系統(tǒng)的不確定性和隨機性也具有一定地優(yōu)越性，目前Petri網(wǎng)已經用于FMS建模和調度，但尚存在下列問題:l)節(jié)點語義的單義性，使得所攜帶的系統(tǒng)信息量不夠豐富。2)重用性差。Petri網(wǎng)是基于FMS中作業(yè)的加工流程建模，當作業(yè)需求或工藝稍微變動，必須改模型結構。3)很難對高級的調度規(guī)則建模。（6）啟發(fā)式圖搜索法在人工智能中啟發(fā)式圖搜索法是圖搜索的重要策略之一，在啟發(fā)式圖搜索法中最引人注目的A*算法，在圖搜索過程中A*算法能夠通過選擇合適的評價函數(shù)尋找達到目標結點的最佳路徑。在調度問題的離散圖模型基礎上，啟發(fā)式圖搜索法在調度領域得到應用。對于表述為整數(shù)規(guī)劃的調度問題，最初采用分枝界定法，而后其他的啟發(fā)式圖搜索法也被應用于解決調度問題。該方法主要需要解決搜索效率和降低內存使用問題，對大規(guī)模的問題需進一步探討。（7）模擬退火模擬退火法（SA）是將組合優(yōu)化問題與統(tǒng)計力學的熱平衡問題類比，通過模擬退火過程，可找到全局(或近似)最優(yōu)解。模擬退火法的改進算法有加溫退火法、記憶退火法。模擬退火法可以用于具有最小MakesPan指標的FlowShop排序問題。由于模擬退火法能以一定的概率接受差的能量值，因而有可能跳出局部極小，但它的收斂速度較慢，很難用于實時動態(tài)調度環(huán)境。（8）禁忌搜索法對于復雜的組合優(yōu)化問題，禁忌搜索也是一種通過領域搜索以獲取最優(yōu)解的方法，Gfover首次敘述了它的基本原理。該方法已經用于解決nowshop調度問題。（9）神經網(wǎng)絡優(yōu)化人工神經網(wǎng)絡(ANNs)是一種模擬人腦神經系統(tǒng)的結構和功能，運用大量的處理部件，經廣泛互連而組成的網(wǎng)絡系統(tǒng)。搜索網(wǎng)絡（Hopfield）模型可以求解各種有約束的優(yōu)化問題，隨機Hopfield也可以用于解決jobshop的調度問題。（10）拉格朗日(LR)松弛算法LR算法由于其在可行的時間里能對復雜的規(guī)劃問題提供較好的次優(yōu)解，并能對解的次優(yōu)性進行定量評估，近年來已成為解決復雜生產調度問題的一種重要方法。但同時LR算法的對偶問題存在搜索效率低，可行調度的構造有待于進一步研究等問題。由于調度問題的復雜性，其研究策略主要形成了以下幾種：①分解與成組策略：利用分解生產計劃或GT的調度策略可以大大降低問題的計算復雜性和規(guī)模，求得調度問題的較優(yōu)解，同時優(yōu)化系統(tǒng)的一些性能指標。②實時或動態(tài)重調度策略：車間制造過程的隨機性、不確定性需要不斷地進行重調度，以處理突發(fā)的事件。基于目前的研究，對于動態(tài)調度的具體策略有:周期調度，連續(xù)調度，事件驅動調度，周期與事件驅動混合調度，周期與連續(xù)調度混合的策略等。③生產計劃與調度集成策略：生產計劃、調度的集成研究具有全局優(yōu)化的特征，也符合先進制造模式的思想。④多目標權衡調度策略：實際調度問題往往是多目標的，而這些目標往往相互沖突。對此類多目標優(yōu)化問題，常用數(shù)學規(guī)劃中的約束法、評價函數(shù)法、分層序列法、功效函數(shù)法等。隨著各種特殊調度問題的攻克和新方法、新設備的出現(xiàn)，作業(yè)車間調度研究正在向動態(tài)、敏捷、多重入、多資源、智能化的方向發(fā)展。3 求解調度問題的遺傳算法 遺傳算法求解調度問題的優(yōu)越性遺傳算法（Genetic Algorithm, GA）是一類借鑒生物界“適者生存，優(yōu)勝劣汰”的遺傳機制演化而來的隨機化搜索算法。它基于自然界生物進化過程中優(yōu)勝劣汰、自然選擇、適者生存和物種遺傳的思想來搜索求解空間最優(yōu)解，是一種多參數(shù)、多群體同時進行的優(yōu)化方法，其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息，它尤其適用于處理傳統(tǒng)搜索方法難以解決的復雜非線性問題。由于它具有這些特點，從上世紀80年代以來，遺傳算法成為信息科學和運籌優(yōu)化領域的一個研究熱點，并在數(shù)據(jù)挖掘、生產調度、函數(shù)優(yōu)化、機器學習、