【正文】 1scHPPl??? ? () 綜合考慮選擇操作，模式 H 在下一代中的數(shù)量可以用下式來綜合估計 : _( ) ( )( , 1 ) ( , ) ( 1 )1cf H Hm H t m H t p lf ?? ? ? ?? () 從上式可以看出，模式的平均適應度高于群體平均適應度，并且具有短 定義距的模式，將在下一代中成指數(shù)級的增長。 ，變異可以使生物體子代 的染色體不同于它們父代的染色體，通過結(jié)合兩個父代染色體的物質(zhì)，重組過程可以在子代中產(chǎn)生有很大差異的染色體。 生產(chǎn) 調(diào)度問題存在多種優(yōu)化目標或者綜合優(yōu)化目標，調(diào)度問題的優(yōu)化目標通常從兩個方面來考慮 :生產(chǎn)成本和生產(chǎn)時間。我們定義以下基本數(shù)學符號 ［ 6］ ： J:所有工件的集合， 12{ , , }nJ J J J? ； M:所有機器的集合， 12{ , , }mM M M M? ； ijP： 工件 Ji 的工序集合， 12{ , , }i i i i ij j j j pP P P P?； P:所有工序的集合，此為 12m ax{ , , }nn P P P? 矩陣。在此基礎上，可對車間作業(yè)調(diào)度問題進行一般性的描述 :假定有多個工件，要經(jīng)過多臺機器加工。目前的調(diào)度算法大多只關(guān)心工件的調(diào)度問題，而對其它資源分配問題則研究相對不多，將二者 結(jié)合起來研究應該是值得注意的問題，目前已有不少學者開始關(guān)注該問題。盡我所知，除文中特別加以標注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機構(gòu)的學位或?qū)W歷而使用過的材料。在當今的競爭環(huán)境下，如何利用計算機技術(shù)實現(xiàn)生產(chǎn)調(diào)度計劃優(yōu)化，快速調(diào)整資源配置，統(tǒng)籌安排生產(chǎn)進度，提高設備利用率已成為許多加工企業(yè)面臨的重大課題。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。 作業(yè) 車間調(diào)度問題表述 作業(yè)車間調(diào)度（ jobshop）問題可以表述為：設有 N個工件在 M臺機器上加工，根據(jù)工件加工工藝的要求，每個工件使用 機器的順序及其每道工序所花時間已給定，調(diào)度問題的目標就是如何選擇加工順序使得總的加工時間最短最優(yōu)。它所要解決的問題就是確定每臺機器上不同工件的加工順序，以及每個工件的所有工序的起始加工時間，以最優(yōu)化某個性能指標。 MJ （ i， j）表示 i工件的第 j 道工序的機器號， (, )MJi? 表示 i工件的所有工序按優(yōu)先順序加工的各機器號的排列。第一章簡要介紹了車間調(diào)度問題和求解調(diào)度問題的基本方法 ；第 遼寧科技大學本科生畢業(yè)設計 第 5 頁 二章介紹了遺傳算法的基本理論；第三章用遺傳算法來解決車間調(diào)度問題 ,其中介紹了常用的幾種編碼方式 ,在比較的情況下提出本文主要用基于操作的編碼方式 .還有提出了幾種主要的遺傳算子。自然選擇決定了群體中那些個個體能存活并繁殖，有性生殖保證了后代基因中的混合與重組。 模式定理保證了較優(yōu)的模式 (遺傳算法的較優(yōu)解 )的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理提供了數(shù)學基礎。概率太小時，交叉操作很少進行，從而會使搜索停滯不前，造成算法的不收斂。增加種群多樣性具有重要意義。 ，用遺傳算法求最優(yōu)解比較困難，因為染色體種群很可能過 早地 斂，而 對以后變化了的數(shù)據(jù)不再產(chǎn)生變化。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn) （ 即基因型 ） 是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。此后， Holland 指導學生完成了多篇有關(guān)遺傳算法研究的論文。此外，以遺傳算法的理論基礎為中心的學術(shù)會議還有 Foundations of Geic Algorithms，該會也是從 1990 年開始隔年召開一次。 今后幾年，拓廣更加多樣的應用領(lǐng)域，將是 GA 發(fā)展的主流。 表 加工時間和工藝約束 項目 工件 操作序列 1 2 3 操作時間 J1 J2 J3 3 1 3 3 5 2 2 3 3 機器 J1 J2 J3 M1 M1 M2 M2 M3 M1 M3 M2 M3 對于上表 3個工件在 3個機器上加工的例子，假設染色體為 {2 1 2 3 1 1 3 2 3}， Oijk 表示第 i個工件的第 j 個工序在第 k 個機器上加工（以下同），則對機器加工順序的工藝約束，該染色體對應的有序操作表為 [O211 O111 O223 O312 O122 O133 O321 O232 O333]，即首先安排第二個工件的第一個操作步驟，然后安排第一個工件的第一個操作步驟，第二項任務的第二個操作步驟， ? 以次類推。因為每個工件有三道工序，所以每個工件在一個染色體中剛好出現(xiàn)三次。從生物學角度講 ,適應度相當于“生存競爭 ,適者生存”的生物生存能力 ,在遺傳過程中具有重要意義。評價值 (目標函數(shù) )較小的個體有較高的概率生存 ,即在下一代群體中再次出現(xiàn)。 pc 交叉概率用于控制交叉操作的頻率。重復 STEP1， STEP2， STEP3， STEP4，直到種群滿。 前面兩種編碼方式比較復雜，下面我們用基于操作的編碼方式來解此車間調(diào)度問題： 把調(diào)度編碼為工序的序列，每個基因代表一道工序，給所有同一工件的工序指定相同的符號，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務相應順序的操作。 圖 設備死鎖示意圖 在圖 中，分屬工件 1 和工件 2 的總共四個工序都處于循環(huán)等待其前面工序或前道工序結(jié)束加工的狀態(tài)之中，從而使設備 1 和設備 2 處于空轉(zhuǎn)狀態(tài)，即產(chǎn)生了所謂的死鎖現(xiàn)象。 遺傳算法主要應用在機器學習 中。 進入八十年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應用研究都成了十分熱門的課題。所謂人工生命即是用計算機模 擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應、進化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進化規(guī)劃 （ Evolution Programming,EP） 以及進化策略 （ Evolution Strategy,ES）等進化計算理論日益結(jié)合。 遺傳算法的 進展 地球上自出現(xiàn)生命至今已有 30 多億年的歷史，從低級生物到高級生命再至擁有智慧的人類，這是一個漫長的生物進化過程。 ，而不是對參數(shù)本身，因此遺傳算法具有靈活性高的特點。 (population size) 種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時，不能提供足夠多的個體，致使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。 通常，種群太小則不能提供足夠的采樣點，以致算法性能很差 。但是如果其中一方個體不具有模式 H， 則有可能會引起另一個個體模式的改變。 ，哪些適應性好地個體的染色體經(jīng)常比差的個體的染色體有更多的繁殖機會。即 jM? 使得目標函數(shù) ()jfM 取值最小 (或最大 )，且與 MJ 相容，則稱 jM? 為車間作業(yè)調(diào)度問題在此目標函數(shù)下的最優(yōu)解。 假設有 n個工件，要在 m臺機器上加工，每個工件有 Pi 道工序，每臺機器上總共要加工 Lj 道工序。而在本文中，為了研究方便，我們將這項任務限定為加工一批工件。 雖然對其研究已有幾十年的 歷史 但至今尚未形成一套系統(tǒng)的方法和理論，理論研究與實際應用之間還存在著較大距離。 production cycl 遼寧科技大學本科生畢業(yè)設計 第 III 頁 畢業(yè)設計（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設計（論文），是我個人在指導教師的指導下進行的研究工作及取得的成果。 近年來遺傳算法得到了很大的發(fā)展，應用遺傳算法來解決車間調(diào)度問題早有研究。本人完全意識到本聲明的法律后果由本人承擔。 前提假設 ［ 3］ ： 1. 每一臺機器每次只能加工一個工件，每一個工件在機器上的加工被成為一道工 遼寧科技大學本科生畢業(yè)設計 第 2 頁 序。 車間作業(yè)調(diào)度問題研究的假設條件及數(shù)學模型 車間作業(yè)調(diào)度問題研究的假設條件 在研究一般的車間作業(yè)調(diào)度問題中往往需要明確兩類重要假設條件 : :工件的任一工序必須在其前道工序完成后才能開始，并保證同一工件不會同時在兩臺機器上 加工，反映了工件不同工序間的時序關(guān)系 。注意 : 如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0填滿 。并且以四個工件四個機器問題進行舉例 ,說明了用遺傳算法解決車間調(diào)度問題的可行性 。比起那些僅包 含 單個親本的基因拷貝和依靠偶然變異來改進的后代，這種由基因重組產(chǎn)生的后代進化要 快得多。 由模式定理可知，具有低階、短定 義距以及平均適應度高于群體平均適應度的模式在后代中呈指數(shù)級增長。 變異操作是對種群 模式的擾動，有利于增加種群的多樣性。通常選取一個較低的變異概率。對于這個問題，研究者提出了一些方法增加基因的多樣性，從而防止過早的收斂。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。 1971年， 在他的博士論文中首次把遺傳算法用于函數(shù)優(yōu)化。這些國際會議論文，集中反映了遺傳算法近些年來的最新發(fā)展和動向。這也是本世紀高新技術(shù)迅速發(fā)展帶有規(guī)律性的特點，即面向應用。進而相應的調(diào)度如圖 （我們用 Gantte圖表示一個調(diào)度）。例如， 遼寧科技大學本科生畢業(yè)設計 第 19 頁 在以上給定的染色體中出現(xiàn)三個 2 表示工件 j2 的三道工序，第一個 2 對應工件 j2 的第一道工序在機器 1 上加工，第二個 2 對應工件 j2 的第二道工序在機器 2 上加工，第三個2 對應工件 j2 的第三道工序在機器 3 上加工。 適應度函數(shù)就是目標函數(shù)，在用遺傳算法解決車間調(diào)度問題里，定義個體的適應度函數(shù)為在 M 臺機器上排序加工完 N 個工件所需的時間，根據(jù)染色體編碼的思想提出的適應度算法如下： STEP1:定義 ti(n)為每個工件的可加工時間，初始化向量為零向量。一種常用的選擇方法是按比例選擇 ,即若個體 i適應值 (目標函數(shù) )是 fi,則個體在群體中復制 (再生 )的子代個數(shù)在群體中的比例將為 : /iiff? 。當然，在優(yōu)化過程中種群數(shù)目是允許變化的，也可以將較大規(guī)模的種群分解成若干子種群進行優(yōu)化。產(chǎn)生的 chrom 為一個個體。 () 對染色體的解釋為 ：在第一臺機器上首先應該安排第二項工件的操作，其次是第一項工件的操作，第三項工件的操作；在第二臺機器上首先應該安排第三項工件的操作，然后是第一、二項任務的操作，以此類推。本研究的設備死鎖不在同一臺機器上而是在不同的機器上產(chǎn)生死鎖現(xiàn)象，所謂的設備死鎖現(xiàn)象如圖所示，其 中括號內(nèi)的兩個數(shù)據(jù)，意義為（工件號，工序號）。目前，關(guān) 于遺傳算法研究的熱潮仍在持續(xù)，越來越多的從事不同領(lǐng)域的研究人員已經(jīng)或正在置身于有關(guān)遺傳算法的研究或應用之中 現(xiàn)在隨著科學技術(shù)的日益發(fā)展，遺傳算法有了突飛猛進的發(fā)展， 不僅 遼寧科技大學本科生畢業(yè)設計 第 15 頁 理論研究十分活躍，而在越 來越多的領(lǐng)域得到發(fā)展。可以認為， De Jong 的研究工 作為遺傳算法及其應用打下了堅實的基礎，他所得出的許多結(jié)論，迄今仍具有普遍的指導意義。四是遺傳算法和另一個稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所以在使用遺傳算法的同時，也可以嘗試其它算法，互相補充，甚至根本不用遺傳算法。 ，遺傳算法的初始種群本身就帶有大量與最優(yōu)解甚遠的信息，通過選擇、交換、變異操作，能迅速排除與最優(yōu)解相差極大的串，這是一個強烈的濾波過程，并且是一個并行濾波機制。 基本遺傳 算法參數(shù)說明 對遺傳算法性能有影響的參數(shù)主要有 :種群數(shù)目 N、交換概率 Pc、變異概率 Pm、代溝 G、尺度窗口 W、和選擇策略 S 等。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。假設交換操作是采用的單點隨機雜交方式，隨機選取雜交的起始位置，交叉概率為 Pc，兩個具有相同模式 H 的個體發(fā)生交換，即雜交操作，不會改變模式 H。 ，而不是發(fā)生在它們所編碼地生物個體上。 由此，我們可以給出一般性的車間作業(yè)調(diào)度數(shù)學模型的 定義 : 如 果 對 應 于 一 個確 定 的 jM? ，滿足 * 1 2( ) m i n { ( ) , ( ) , ( ) }nj j j jf M f M f M f M? 或* 1 2( ) m a x { ( ) , ( ) , ( ) }nj j j jf M f M f M f M? 。 車間作業(yè) 調(diào)度問題的數(shù)學模型 建立車間作業(yè)調(diào)度問題的數(shù)學模型，是我們研究該