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