【正文】 衷心感謝我的父母，是他們在物質(zhì)上和精神上始終默默地支持和鼓勵我，使我心無旁慮，一心求進。 白康老師的學(xué)識、嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度以及誨人不倦的教導(dǎo)使作者受益匪淺， 給予我以后工作的影響是我一生所取之不盡，用之不竭的力量源泉。 展望 由于車間調(diào)度實現(xiàn)和應(yīng)用是一個龐大的系統(tǒng)工程，另外由于時間和個人學(xué)識的限制，關(guān)于車間調(diào)度問題的研究，在理論和應(yīng)用上尚需做大量的工作，在以下幾個方面尚有待進一步深入： 1． 本文所研究的柔性作業(yè)車間調(diào)度問題主要針對不同工序 可以在多臺不同機床上加工然后尋找出各種不同目標(biāo)最優(yōu)調(diào)度的情況，在今后的研究中，可以將該柔性調(diào)度問題進一步拓展，考慮 多目標(biāo) 的情況，此類問題更具復(fù)雜性，但進一步集成了生產(chǎn)計劃與車間調(diào)度，是一個值得研究的方向。 工序選擇 加工機床及加工工時間 1 2 3 4 5 6 J1 Q11 2 3 4 Q12 3 2 4 Q13 1 4 5 J2 Q21 3 5 2 Q22 4 3 6 Q23 4 7 11 J3 Q31 5 6 Q32 4 3 5 Q33 13 9 12 J4 Q41 9 7 9 Q42 6 4 5 Q43 1 3 3 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 21 3 1 51 3 1 4 3 11 1 3 2 2 34 1 7 2 3 41 2 2 3 2 32 1 23 3 94 2 5M 1M 2M 3M 4M 5M 61 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 圖 時間進度合成 甘特 圖 表 工序路徑 工序選擇 工序選擇 加工機床及加工工時間 1 2 3 4 5 6 J1 Q11 3 Q12 2 Q13 1 J2 Q21 2 Q22 3 Q23 4 J3 Q31 5 Q32 3 Q33 9 J4 Q41 7 Q42 5 Q43 1 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 22 5 總結(jié)與展望 總結(jié) 本論文選擇作業(yè)車間的生產(chǎn)調(diào)度為研究和開發(fā)對象，以遺傳算法為基礎(chǔ)，綜合運用車間調(diào)度問題的基本理論，對具有路徑柔性的多目標(biāo)作業(yè)車間調(diào)度問題和作業(yè)車間動態(tài)調(diào)度問題進行了系統(tǒng)的研究。 表 4*6的柔性作業(yè)車間調(diào)度 算法執(zhí)行 100 次后，基因串收斂于總操作時間 Cmax =17 小時， 比文獻 [5] 中的 Cmax =18小時要優(yōu)。表格中的第一橫行數(shù)據(jù) 6 表示 6 臺機器對應(yīng)的編碼，下面的數(shù)字表示工件 Ji 的第 j 個操作在選定機器 Mi 上的加工時間。設(shè)群體規(guī)模為 n， 將父代與子代群體同時進行比較，選擇前 n個個體作為下一代群體。而對于第一層編碼則可以將父代 2的基因 (除子代中已有的子序列外 )直接拷貝到子代的相應(yīng)位置。由于編碼的特殊性 ， 交叉操作 需對兩部分分別進行。 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 18 表 第二字串編碼 工序 第一層編碼 第二層編碼 Q11 2 3 Q12 3 4 Q13 1 2 Q21 3 5 Q22 2 7 Q23 5 8 Q31 1 9 Q32 4 6 Q33 6 12 Q41 3 11 Q42 4 10 Q43 6 1 注： M1表示機器編碼 1，下同。 特別需要注意的是：由于第二子串編碼工序加工的先后順序是有講究的。 Q42={ M M M6}， Q43={ M M M6}。 Q13={ M M M3}， Q21={ M M M5}。對于基于活動種群的 FJSS問題不僅要尋找最佳的排序方案，選擇最合適的機器，還要考慮各機器和工人加工的成本因素，所以更增添了求解的復(fù)雜性。 第九步 比較各局部最優(yōu)解，得出全局最優(yōu)解，即最優(yōu)調(diào)度。 第五步 按變異概率 Pm隨機選擇個體，進行變異操作生成新個體。 F I S S 問 題 描 述確 定 決 策 變 量 、 約束建 立 優(yōu) 化 模 型個 體 表 現(xiàn) 型 （ 調(diào) 度方 案 ）目 標(biāo) 函 數(shù)編 碼 方 法編 碼 方 法 確 定 適 應(yīng) 度 轉(zhuǎn) 換 規(guī) 則全 體 基 因 型 適 應(yīng) 度設(shè) 計 遺 傳 算 子確 定 運 行 參 數(shù)遺 傳 算 法適 應(yīng) 度 函 數(shù)懲 罰 規(guī) 則 、 系 數(shù)權(quán) 值 分 配時 間 目 標(biāo)成 本 目 標(biāo) 圖 求解 FJSS 問題的遺傳算法主要構(gòu)造過程示意圖 運用基于活動種群的遺傳算法求解 FJSS模型的總體流程則表示如下： 第一步 設(shè)計問題的染色體，隨機生成種群規(guī)模為 P的初始可行解，即初始的可行調(diào)度。 (3) 互換變異 在染色體串中隨機的選擇兩個基因位，然后互換基因位上的值， 完成變異操作。若需要進行變異操作則將基因座上的原有基因值 （ 假設(shè)為 ） 0，則變異操作將該基因值變?yōu)?1；反之，若原有基因值為 1，則變異操作將該基因值變?yōu)?0。交叉算子與變異算子的相互配合，共同完成對搜索空間 的全局搜索和局部搜索，從而使得 GA能夠以良好的搜索性能完成最優(yōu)化問題的尋優(yōu)過程。 P1→(1100 ∣ 100) C1→(1100 ∣ 011) P2→(0011 ∣ 011) C2→(0011 ∣ 100) (2) 多點交叉 首先在相互配對的染色體中隨機確定多個交叉位置，然后對換相應(yīng)的子串。子代應(yīng)能夠部分或者全部地繼承父代的結(jié)構(gòu)特征和有效的基因。首先在父代種群中隨機選取 k個個體，然后令其中適配值或目標(biāo)值最好的個體為被選中的個體。設(shè)群體大小為 M，個體 i的適應(yīng)度為 Fi，則個體 i被選中的概率 Pi，為 Pi = ??Mi iiFF1 (2 6) 由上式可見，適應(yīng)度越高的個體被選中的概率越大；反之，適應(yīng)度越低的個體被選中的概率越小。 最常用的選擇方法是適應(yīng)度比例選擇、最優(yōu)個體保存選擇和錦標(biāo)賽選擇。但考慮到搜索效率和質(zhì)量，最好采用如下策略設(shè)定 [21]： 1) 根據(jù)問題固有知識，設(shè)法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此范圍內(nèi)設(shè)定初始種群。該系數(shù)有兩個作用：避免式 (25)產(chǎn)生被零除錯誤；可以將選擇方式從適應(yīng)值比例選擇調(diào)整到純粹隨機選擇 ( ??? )。理想解實際上無法達到，然而它可以成為評價可達到的非支配解的標(biāo)準(zhǔn)。采用妥協(xié)方法 [19]的基本思想是：通過 最大完成時間來確定后悔值 r，進而求得相應(yīng)染色體的適應(yīng)度。 c(X)為個體的目標(biāo)值， a0。遺傳算法在求高維、復(fù)雜優(yōu)化問題時通常采用實數(shù)編碼 [18]。 格雷碼是將二進制編碼通過一個轉(zhuǎn)換而得到的編碼。 3) 符合最小字符集編碼原則。這種缺陷造成了 Hamming懸崖將降低遺傳算子的搜索效率。二進制編碼類似生物染色體的組成，從而使算法易于用生物遺傳理論來解釋。 有效調(diào)度，如圖 。 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 11 (3)映射的唯一性從編碼空間到解空間的映射可以是 1對 1映射、 X對 1映射或 1對 X映射，顯然， 1對 1映射是最好的，而 1對 X映射是最不值得提倡的。 GA的一個顯著特點是它交替地在編碼空間和解空間中工作，它在編碼空間對染色體進行遺傳操作，而在解空間對解進行評估和選擇。 (6)選擇策略 (S) 通常有兩種選擇策略：其一為純選擇，即種群中每一個體根據(jù)其適應(yīng)度作比例選擇；其二為保優(yōu)策略，即先用純選擇作選擇，然后將最優(yōu)個體加入下一代種群，該策略可防止最優(yōu)解的遺失。對于最大化函數(shù)優(yōu)化問題，個體 x的適應(yīng)度可以定義為： u(x)=f(X)一 fmin (21) 其中 f(x)為其目標(biāo)值， fmin為問題的最小目標(biāo)值。 (4)代溝 (G) 代溝用于控制每代中種群被替換的比例。但是，變異概 率太小則不會產(chǎn)生新個體，概率太大則使GA成為隨機搜索。 一般建議的取值范圍是 。當(dāng)種群數(shù)目設(shè)得過小時，不能提供足夠的采樣點來搜索整個解空間，以致算法性能很差；當(dāng)種群數(shù)目設(shè)得過大時，盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但無疑會增加計算量，從而使收斂時間太長，算法效率偏低。終止準(zhǔn)則應(yīng)根據(jù)所求解問題的性質(zhì)，在優(yōu)化質(zhì)量和效率方面作合理均衡或側(cè)重。通常包括：初始化、選擇、交叉、變異和替換操作等。適應(yīng)度函數(shù)基本上依據(jù)優(yōu)化問題的目標(biāo)函數(shù)而定，當(dāng)適應(yīng)度函數(shù)確定以后，自然選擇規(guī)律是以適應(yīng)度函數(shù)值的大小決定的概率分布來確定哪些染色體適應(yīng)生存，哪些被淘汰，生存下來的染色體組成種群，形成一個可以繁殖下一代的群 體。 標(biāo)準(zhǔn)遺傳算法的主要步驟如描述下： (1) 確定問題的編碼方案。 (3) 群體的大小 (Population Size)：在群體中個體的數(shù)量為群體的大小。因為遺傳算法是一類基于 “產(chǎn)生 +測試 ”方式的迭代搜索 算法，盡管算法在一定條件具有全局收斂性，但算法的交叉、變異、選擇等操作一般都是在概率意義下隨機進行的，雖 然 保證了種群的群體進化性，但一定程度上不可避免退化現(xiàn)象的出現(xiàn)。 (5) 遺傳算法最善于搜索復(fù)雜地區(qū)，從中找出期望值高的區(qū)域和個體。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以 任意設(shè)定。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)，克服了早熟的缺點。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開來。此過程反復(fù)執(zhí)行，這構(gòu)成一代代的群體。 遺傳算法的基本思想 遺傳算法 (Geic Algorithms)的基本思想來源于分子遺傳學(xué)和生物進化論，其基本原理是，產(chǎn)生若干代表問題候選解的成員，并組成一個群 體，按照某一評價函數(shù)或算法對群體中的每個成員進行評估，評估結(jié)果代表解的良好性。它最早由美國密執(zhí)安大學(xué)的 Holland教授提出，起源于 60年代對自然和人工自適應(yīng)系統(tǒng)的研究 [12]． 70年代 De Gong基于 GA的思 想在計算機上進行大量的純數(shù)值函數(shù)優(yōu)化計算實驗 [13]。 Gantt 圖使車間的計劃安排情況一目了然，成為管理人員了解全局，安排車間進度的有效工具。 Gantt 圖 對于 m 臺機器 (Machine)(M1， M2， …， Mm)， n 個工件 (Job)(J1， J2， …， Jn)的加工過程，調(diào)度通常用 Gantt 圖表示。 調(diào)度目標(biāo)是為每道工序選擇最合適的機器，以及確定每臺機器上各工件工序的最佳加工順序及開工時間，使系統(tǒng)的某些性能指標(biāo)達到最優(yōu)。研 究具有路徑柔性的車間調(diào)度 (Flexible Job Shop Scheduling，簡稱 FJSS)問題具有重要的理論和應(yīng)用意義。 柔性車間作業(yè)調(diào)度問題 問題描述 一般的車間調(diào)度問題都是對于具體生產(chǎn)環(huán)境中復(fù)雜動態(tài)、多目標(biāo)、多約束調(diào)度的一種抽象和簡化，其首要問題是對調(diào)度問題進行建模。 由于大多數(shù)調(diào)度問題屬于一類 NP難組合問題，因此尋找具有多項式復(fù)雜性的最優(yōu)算法幾乎是不可能的。 ◆ 免疫算法 （ immunity algorithm） 。 ◆ 神經(jīng)網(wǎng)絡(luò) （ neural work， NN） 。 ◆ 閾值接受法 （ threshold accepting， TA）。 ◆ 禁忌 搜索 （ tabu search， TS） 。 華北電力大學(xué)本科畢業(yè)設(shè)計（論文） 4 ◆ 迭代改進法 （ iterative improvement） 。 ◆ 插入方法 （ insertion algorithm） 。 ◆ 優(yōu)先分配規(guī)則 （ priority dispatch rule） 。 ◆ 分支定 界 （ bound and branch） ◆ 數(shù)學(xué)方法 （ mathematical method） 。這種多目標(biāo)性導(dǎo)致調(diào)度的復(fù)雜性和計算量急劇增加。 (2) 動態(tài)隨機性 在實際的生產(chǎn)調(diào)度系統(tǒng)中存在很多隨機的和不確定的因素，比如作業(yè)到達時間的不確定性、作業(yè)的加工時間也有一定的隨機性，而且生產(chǎn)系統(tǒng)中常出現(xiàn)一些突發(fā)