【正文】 調(diào)度問題特點與分類調(diào)度問題的主要特點有:(1)建模、計算復(fù)雜性。每個工件又要考慮它的加工時間、安裝時間和操作順序等因素，因而相當(dāng)復(fù)雜，調(diào)度問題往往是通過等式或不等式等約束條件來計算的，屬于典型的NPhard問題。在現(xiàn)有計算條件下，一般優(yōu)化方法對于車間調(diào)度問題是低效甚至是無能為力的。如機器故障、作業(yè)交貨期的變更，如工件到達時間的不確定性，實際工件的加工時間也有一定的隨機性。(3)多約束性調(diào)度中受到很多約束條件的限制。此外，還有人為的附加因素，如機器負荷平衡等等約束條件。如基于作業(yè)交貨期的目標(biāo)、基于作業(yè)完成時間的目標(biāo)、基于生產(chǎn)成本的目標(biāo)等。(2)單臺處理機、多臺并行機、Job—shop和Flow—shop。(4)確定性調(diào)度、隨機性調(diào)度。(6) 有序加工，無序加工。 車間作業(yè)調(diào)度問題描述一般車間調(diào)度問題可以描述為:n個工件在m臺機器上加工，每個工件分為k道工序，每道工序可在不同的機器上加工。調(diào)度的結(jié)果就是確定決策方案，決策內(nèi)容包括分配決策(工件的加工順序)和時間決策(工件各工序的加工時間)以及路徑?jīng)Q策(工件工序的加工設(shè)備的分配)。車間調(diào)度的問題是多個工件在有限的機器上加工，每臺機器在切換不同的工件加工時又需要一定的生產(chǎn)加工準(zhǔn)備時間。如果車間有足夠多的機床設(shè)備和其它生產(chǎn)資源分配給每個工件或每條工藝加工路線，那么一切都會井然有序，也就不存在調(diào)度問題。因此，需要在庫存成本與切換加工次數(shù)頻率之間尋求一個動態(tài)的平衡。具有可選的路徑，可以通過將若干設(shè)備組作為一條或者多條生產(chǎn)線加工一種工件，使得該工件的生產(chǎn)率最大。車間調(diào)度就是對一個可用的加工機床集在時間和空間上進行加工任務(wù)集分配，以達到生產(chǎn)性能指標(biāo)最優(yōu)化。調(diào)度的目標(biāo)是將作業(yè)合理地安排到各機床以及合理地使用其它生產(chǎn)資源，并合理安排作業(yè)的加工次序和加工時間，使約束條件被滿足，同時優(yōu)化其中的一些生產(chǎn)性能指標(biāo)。這類方法從理論上來說是能求得最優(yōu)解，但通常由于計算復(fù)雜性原因，不能獲得真正的實用。采用數(shù)學(xué)規(guī)劃的方法大致可以分為三類：簡單規(guī)則、復(fù)合規(guī)則、啟發(fā)式規(guī)則。這類方法因調(diào)度規(guī)則易于實現(xiàn)，計算復(fù)雜度低，能夠用于動態(tài)實時調(diào)度系統(tǒng)中，許多年來一直受到廣泛關(guān)注和研究，并不斷涌現(xiàn)許多新的調(diào)度規(guī)則。（3）基于知識的調(diào)度方法近年來受實際需要的推動，基于知識的智能調(diào)度系統(tǒng)和方法的研究取得了很大的進展，基于只是的調(diào)度方法是用專家系統(tǒng)自動產(chǎn)生調(diào)度或輔助人去調(diào)度，它是傳統(tǒng)的調(diào)度方法與基于知識的調(diào)度評價相結(jié)合的方法。（4）仿真調(diào)度方法由于制造系統(tǒng)的復(fù)雜性，很難用一個精確的解析模型來進行描述分析，而通過對仿真模型的運行收集數(shù)據(jù)，就能對實際系統(tǒng)進行性能，狀態(tài)方面的分析，從而能對系統(tǒng)采用合適的控制調(diào)度方法。b)應(yīng)用仿真進行生產(chǎn)調(diào)度的費用很高。（5）基于DEDS的解析模型方法現(xiàn)實中的制造系統(tǒng)往往是離散事件系統(tǒng)，因此可以用研究離散事件系統(tǒng)解析模型和方法探討車間調(diào)度問題，諸如排隊論、極大極小代數(shù)模型、Petri網(wǎng)等。Petri網(wǎng)具有很強地建模能力，對于描述系統(tǒng)的不確定性和隨機性也具有一定地優(yōu)越性，目前Petri網(wǎng)已經(jīng)用于FMS建模和調(diào)度，但尚存在下列問題:l)節(jié)點語義的單義性，使得所攜帶的系統(tǒng)信息量不夠豐富。Petri網(wǎng)是基于FMS中作業(yè)的加工流程建模，當(dāng)作業(yè)需求或工藝稍微變動，必須改模型結(jié)構(gòu)。（6）啟發(fā)式圖搜索法在人工智能中啟發(fā)式圖搜索法是圖搜索的重要策略之一，在啟發(fā)式圖搜索法中最引人注目的A*算法，在圖搜索過程中A*算法能夠通過選擇合適的評價函數(shù)尋找達到目標(biāo)結(jié)點的最佳路徑。對于表述為整數(shù)規(guī)劃的調(diào)度問題，最初采用分枝界定法，而后其他的啟發(fā)式圖搜索法也被應(yīng)用于解決調(diào)度問題。（7）模擬退火模擬退火法（SA）是將組合優(yōu)化問題與統(tǒng)計力學(xué)的熱平衡問題類比，通過模擬退火過程，可找到全局(或近似)最優(yōu)解。模擬退火法可以用于具有最小MakesPan指標(biāo)的FlowShop排序問題。（8）禁忌搜索法對于復(fù)雜的組合優(yōu)化問題，禁忌搜索也是一種通過領(lǐng)域搜索以獲取最優(yōu)解的方法，Gfover首次敘述了它的基本原理。（9）神經(jīng)網(wǎng)絡(luò)優(yōu)化人工神經(jīng)網(wǎng)絡(luò)(ANNs)是一種模擬人腦神經(jīng)系統(tǒng)的結(jié)構(gòu)和功能，運用大量的處理部件，經(jīng)廣泛互連而組成的網(wǎng)絡(luò)系統(tǒng)。（10）拉格朗日(LR)松弛算法LR算法由于其在可行的時間里能對復(fù)雜的規(guī)劃問題提供較好的次優(yōu)解，并能對解的次優(yōu)性進行定量評估，近年來已成為解決復(fù)雜生產(chǎn)調(diào)度問題的一種重要方法。由于調(diào)度問題的復(fù)雜性，其研究策略主要形成了以下幾種：①分解與成組策略：利用分解生產(chǎn)計劃或GT的調(diào)度策略可以大大降低問題的計算復(fù)雜性和規(guī)模，求得調(diào)度問題的較優(yōu)解，同時優(yōu)化系統(tǒng)的一些性能指標(biāo)?；谀壳暗难芯?，對于動態(tài)調(diào)度的具體策略有:周期調(diào)度，連續(xù)調(diào)度，事件驅(qū)動調(diào)度，周期與事件驅(qū)動混合調(diào)度，周期與連續(xù)調(diào)度混合的策略等。④多目標(biāo)權(quán)衡調(diào)度策略：實際調(diào)度問題往往是多目標(biāo)的，而這些目標(biāo)往往相互沖突。隨著各種特殊調(diào)度問題的攻克和新方法、新設(shè)備的出現(xiàn)，作業(yè)車間調(diào)度研究正在向動態(tài)、敏捷、多重入、多資源、智能化的方向發(fā)展。它基于自然界生物進化過程中優(yōu)勝劣汰、自然選擇、適者生存和物種遺傳的思想來搜索求解空間最優(yōu)解，是一種多參數(shù)、多群體同時進行的優(yōu)化方法，其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息，它尤其適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜非線性問題。調(diào)度問題屬于NPplete問題，很難建立準(zhǔn)確的數(shù)值模型，由于調(diào)度規(guī)則是基于經(jīng)驗，故沒有普遍適用的規(guī)則存在，某一規(guī)則只能運用于一定的場合，應(yīng)用調(diào)度規(guī)則求得的解也只是問題的近優(yōu)解，很難保證其解的有效性。調(diào)度問題的多目標(biāo)優(yōu)化問題的，還有很多設(shè)計、工藝等方面的約束必須考慮，從而使多數(shù)的優(yōu)化方法在此問題前失效，然而遺傳算法由于其自然數(shù)序號的編碼方式串與調(diào)度方案的表現(xiàn)形式不謀而合，都是數(shù)字串，盡管還不完整，但也較容易地就解決了調(diào)度問題解空間與染色體編碼串空間的映射問題，另外，遺傳算法的特點也使它很適合于解算各種制造系統(tǒng)的調(diào)度問題。與傳統(tǒng)的搜索方法相比，遺傳算法具有如下特點:(1)搜索過程不直接作用在變量上，而是在參數(shù)集進行了編碼的個體。這使的遺傳算法能以較少的計算獲得較大的收益。采用概率的變遷規(guī)則來指導(dǎo)搜索方向，而不采用確定性搜索規(guī)則。 遺傳算法的自組織、自適應(yīng)和自學(xué)習(xí)性(智能性)決定遺傳算法可求解復(fù)雜問題。應(yīng)用遺傳算法時，根據(jù)具體問題的特性，進行編碼與適應(yīng)度設(shè)計之后，其余操作按常規(guī)算子自動運行即可，只等最后輸出最優(yōu)解個體，而不必關(guān)心求解的實際過程，所以遺傳算法非常便于處理那些輸入輸出之間因果關(guān)系復(fù)雜的問題。 遺傳算法簡介 遺傳算法概述遺傳算法是基于自然選擇，在計算機上模擬生物進化機制的尋優(yōu)搜索算法。這些概念如下所示：1. 串（String）：串是個體（Individual）的形式，在算法中為字符串，并且對應(yīng)于遺傳學(xué)中的染色體（Chromosome）。串是群體中的元素。4. 基因（Gene）：基因是串中的元素，基因用于表示個體的特征。它們的值稱為等位基因（Alleles）?；虿僮魇窃诖Y(jié)構(gòu)空間中進行的。6. 參數(shù)空間 SP：這是串空間在物理系統(tǒng)中的映射，它對應(yīng)于遺傳學(xué)中的表現(xiàn)型（Phenotype）的集合。對于優(yōu)化問題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)，遺傳算法對于適應(yīng)度函數(shù)并不要求可導(dǎo)等條件，只要求適應(yīng)度函數(shù)為可加以比較的非負函數(shù)。9. 選擇(Selection) ：以一定的概率從種群中選擇若干個體的操作。在遺傳算法中為通過交配原則產(chǎn)生一組新解的過程。 遺傳算法基本過程遺傳進化開始于隨機選擇遺傳種群，然后通過應(yīng)用遺傳算子，即繁殖算子，交叉算子和變異算子朝著優(yōu)化的方向進化。①編碼將問題的潛在解用一些參數(shù)表示，這些參數(shù)(基因)排列在一起形成一個特定的編碼(染色體)，代表一個個體，從而將問題的狀態(tài)空間與遺傳算法的碼空間相對應(yīng)，這很大程度上依賴于問題的性質(zhì)，并將影響遺傳操作的設(shè)計。二進制編碼將問題的解用一個二進制0和1字符串來表示，十進制編碼將問題的解用一個十進制串來表示。實數(shù)編碼解決了二進制和十進制編碼對算法精度和存儲量的影響，同時便于優(yōu)化中引入問題的相關(guān)信息，譬如梯度信息。鑒于組合優(yōu)化問題本身的性質(zhì)，其編碼方式需要特殊設(shè)計。根據(jù)求解問題特性來定義反應(yīng)個體對問題環(huán)境適應(yīng)能力和優(yōu)劣程度的測定函數(shù)。選擇操作按照個體的適值進行，適值高的個體擁有更多的被選中機會，因而有更大的存活概率，并將其優(yōu)良特性傳遞給后代。隨機遍歷抽樣((stoehastic universal sampling)。截斷選擇(truncation selection)。④交叉交叉算子是母體空間到個體空間的映射，記作Tc:S2→S交叉是最主要的遺傳運算，它同時對兩個染色體操作，交叉操作用于結(jié)合來自父染色體和母染色體的特征來產(chǎn)生新的子個體，在解空間中進行有效搜索，同時降低對有效模式的破壞概率。單點交叉即首先在雙親的染色體上隨機地選一個交叉位置，將交換位置的右段互相交換，從而形成兩個新的后代。以下以離散交叉為例介紹實數(shù)編碼的交叉方式。與二進制編碼單點交叉不同在于交換的對象的差異，前者是二進制串，后者是實空間的向量。⑤變異變異是一種基本運算，它在染色體上自發(fā)地產(chǎn)生隨機的變化。在遺傳算法中，變異可以提供初始種群中不含有的基因，或找回選擇過程中丟失的基因，為種群提供新的內(nèi)容。種群規(guī)模選擇較大時，可以同時處理更多的解，因而容易找到全局最優(yōu)解，其缺點是增加了每次迭代所需要的時間。叉率(記為Pc)定義為各代中交叉產(chǎn)生的后代數(shù)與種群中的個體數(shù)(Pop_Size)的比。 變異率(記為Pm)定義為種群中變異基因數(shù)中的百分比。若變異率太低，一些有用的基因就不能進入選擇，若太高，既隨機的變化太多，那么后代就可能失去雙親繼承下來的好特性，這樣算法就會失去從過去的搜索中學(xué)習(xí)的能力。另一種是把算法的運行時間作為停止準(zhǔn)則。當(dāng)由此監(jiān)控得到算法再進化己無法改進解的性能，此時停止計算。在遺傳算法中以各種形式融入模擬退火思想，從而使得遺傳算法在理論上具有全局收斂性，是一個有意義的研究方向。這種混合型遺傳算法不但模擬了生物種群的學(xué)習(xí)過程，而且事實上還模擬了種群的個體在其生命周期內(nèi)具有學(xué)習(xí)行為這一生物現(xiàn)象。(Parallel Genetic Algorithm)并行遺傳算法是在遺傳算法的實施中加入自然生物種群中的空間結(jié)構(gòu)因素，它的目的是可以在大規(guī)模并行機上運行，即使是序列式實施并行遺傳算法，也可克服經(jīng)典遺傳算法性能上的不足，從而提高算法的效率。島模型的實施方法是在幾個獨立按經(jīng)典遺傳算法方式運行的種群(稱為子種群)中加入遷移(Migration) )因素。島模型考慮的是種群的空間結(jié)構(gòu)，而細胞模型考慮的是一種群中個體的空間結(jié)構(gòu)。在混亂遺傳算法中，個體由其每個分量的位置與取值共同表示，位置可以不按次序排列，也并不是所有分量都在個體的表示中出現(xiàn)?；靵y遺傳算法的理論基礎(chǔ)、算法設(shè)計及實驗比較，均是有待探討的課題。(4）每道工序從開始到結(jié)束，不會被另外的工序所中斷。(6) 一個工件同一時間只能在一臺機器上加工，一臺機器同一時間只能加工一個工件，加工的開始時間為O。即一個調(diào)度是由m個工件的所有工序的排列組合，且m 臺機器上的排列又相互制約，必須遵循：各工件的某道工序加工時，它的前道工序已經(jīng)加工完成；（7）TS (a)表示在調(diào)度策略S 下，機器Ma上全部工序的完成時間（包括機器的執(zhí)行時間和等待時間），則調(diào)度S 的完成時間T（S）=max（TS (1)，TS ( 2)，?，TS ( m)）；（8）基于最短完成時間的JSP 問題的目標(biāo)函數(shù)為min（T（S），∨S），即尋找一個滿足約束的調(diào)度S，使得T(S)最小。遺傳算法通?？啥x為一個五元組GA=（C，F(xiàn)，PO，O，Para），式中C 表示個體（染色體）的編碼方法；F 表示個體的適應(yīng)度評價函數(shù)；PO表示問題的初始解群；O表示一組基本的遺傳操作，包括選擇算子、交叉算子和變異算子；Para 表示一組遺傳算法的參數(shù)，包括群體規(guī)模N、交叉概率Pc 和變異概率Pm等。下面給出遺傳算法求解JSP 的具體實現(xiàn)。遺傳算法的編碼技術(shù)必須考慮染色體的合法性、可行性、有效性以及問題解空間的表征的完全性。本文采用基于工序的編碼，利用十進制直接的表達方式。在染色體編碼中，給定所有同一工件的的工序指定相同的符號，即工件編號，根據(jù)它們在給定染色體中出現(xiàn)的先后順序就可以確認是第幾道工序。不難看出染色體的任意排列總能產(chǎn)生可行調(diào)度，而且可以肯定這種編碼方式一定含有最優(yōu)調(diào)度方案。也就是在一個給定的合理的染色體的基礎(chǔ)上，產(chǎn)生兩個隨機數(shù)作為交換位置，再交換兩位置之間的基因，進而產(chǎn)生新的染色體。適應(yīng)度函數(shù)F（*）的值可以從目標(biāo)函數(shù)T（*）經(jīng)轉(zhuǎn)換得到。每次進行適應(yīng)度比較的種群規(guī)模為2*N，每次選擇N個適應(yīng)度最高的個體遺傳給下一代?？紤]到染色體表現(xiàn)型的實際意義, 采用單親單子兩點隨機交叉操作產(chǎn)生子代。 變異算子變異操作在本問題中相對而言比較簡單。 遺傳算法流程在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務(wù)就是對群體的個體按照它們對環(huán)境適應(yīng)度(適應(yīng)度評估)施加一定的操作，從而實現(xiàn)優(yōu)勝劣汰的進化過程。遺傳算法和傳統(tǒng)