【正文】 含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過的材料。 關(guān)鍵詞 ： 作業(yè) 車間調(diào)度； 遺傳算法；改進(jìn)染色體編碼 ； 生產(chǎn)周期 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 II 頁(yè) Solving jopshop scheduling problem based on geic algorithm Abstract Simply speaking, the job shop scheduling problem(JSP) is the equipment resources optimization question. Job Shop Scheduling Problem as an important part of Computer IntegratedManufacturing System (CIMS) engineering is indispensable, and has vital effect onproduction management and control system. In the petion ecvironment nowadays, how touse the assignments quickly and to plan production with due consideration for all concernedhas bee a great subject for many recent years,the geic algorithms obtained great development it was used to solve the job shop scheduling problem paper discusses the chromosome code method in detail based on the geic algorithms and make the improvement on it. Through the research on mathematics model of JSP and optimized algorithm, theimproved adaptive geic algorithm (IAGA) obtained by applying the improved sigmoidfunction to adaptive geic algorithm is proposed. And in IAGA for JSP, the fitness ofalgorithm is represented by pletion time of jobs. Therefore, this algorithm making thecrossover and mutation probability adjusted adaptively and nonlinearly with the pletiontime, can avoid such disadvantages as premature convergence, low convergence speed andlow stability. Experimental results demonstrate that the proposed geic algorithm does notget stuck at a local optimum easily, and it is fast in convergence, simple to be implemented. the job shop scheduling system based on IAGA and GASH is designed andrealized, and the functions and operations of the system modules are introduced detailedly. In the end ,according to the code with improved carries on the geic algorithms desing, this paper offer one improved geic algorithms about soloving to the job shop scheduling problem, and the simulated example has indicated that this algorithm is valid. Keywords: jop shop scheduling。 在研究了作業(yè)車 間調(diào)度問題數(shù)學(xué)模型和優(yōu)化算法的基礎(chǔ)上，將一種改進(jìn)的自適應(yīng)遺傳算法應(yīng)用在作業(yè)車間調(diào)度中。 作業(yè) 車間調(diào)度問題是計(jì)算機(jī)集成制造系統(tǒng) (CIMS)工程中的一個(gè)重要組成部分，它對(duì)企業(yè)的生產(chǎn)管理和控制系統(tǒng)有著重要的影響。在當(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è)面臨的重大課題。該算法是將 sigmoid 函數(shù)的變形函數(shù)應(yīng)用到自適應(yīng)遺傳算法中，并將作業(yè)車間調(diào)度問題中的完工時(shí)間大小作為算法的評(píng)價(jià)指標(biāo)，實(shí)現(xiàn)了交叉率和變異率隨著完工時(shí)間的非線性自適應(yīng)調(diào)整，較好地克服了標(biāo)準(zhǔn)遺傳算法在解決作業(yè)車間調(diào)度問題時(shí)的“早熟”和穩(wěn)定性差的缺點(diǎn)，以及傳統(tǒng)的線性自適應(yīng)遺傳算法收斂速度慢的缺點(diǎn)。 geic algorithm。對(duì)本研究提供過幫助和做出過貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說明并表示了謝意。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。 涉密論文按學(xué)校規(guī)定處理。遺傳算法的蓬勃發(fā)展正體現(xiàn)了科學(xué)發(fā)展的這一特點(diǎn)和趨勢(shì)。 由于一般車間調(diào)度問題的復(fù)雜性，各種不同的具體問題往往有許多不同的算法來解決，例如經(jīng)典的啟發(fā)式算法，傳統(tǒng)的搜索方法等。 作業(yè) 車間調(diào)度問題表述 作業(yè)車間調(diào)度（ jobshop）問題可以表述為：設(shè)有 N個(gè)工件在 M臺(tái)機(jī)器上加工，根據(jù)工件加工工藝的要求，每個(gè)工件使用 機(jī)器的順序及其每道工序所花時(shí)間已給定，調(diào)度問題的目標(biāo)就是如何選擇加工順序使得總的加工時(shí)間最短最優(yōu)。它可分為精確求解方法和近視求解方法。 車間作業(yè)是指利用車間資源 (如機(jī)床、刀具、夾具等 )完成的某項(xiàng)任務(wù)。一個(gè)工件在一臺(tái)機(jī)器上的加工程序稱為一道“工序”，相應(yīng)的加工時(shí)間稱為該工序的“加工時(shí)間”。它所要解決的問題就是確定每臺(tái)機(jī)器上不同工件的加工順序，以及每個(gè)工件的所有工序的起始加工時(shí)間，以最優(yōu)化某個(gè)性能指標(biāo)。 2. 不考慮工件加工的優(yōu)先權(quán)，即工件之間沒有優(yōu)先約束關(guān)系限制的 。 6. 緩沖區(qū)容量為無窮大。 P（ i， j） 表 示 i工件的第 j 道工序。 MJ （ i， j）表示 i工件的第 j 道工序的機(jī)器號(hào)， (, )MJi? 表示 i工件的所有工序按優(yōu)先順序加工的各機(jī)器號(hào)的排列。同樣地，如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿 。事實(shí)上，工件排列陣就是調(diào)度的一種表示形式。調(diào)度問題從生產(chǎn)成本方面來考慮，其優(yōu)化目標(biāo)有 :庫(kù)存最少、在制品最少、設(shè)備利用率最高等 。第一章簡(jiǎn)要介紹了車間調(diào)度問題和求解調(diào)度問題的基本方法 ；第 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 5 頁(yè) 二章介紹了遺傳算法的基本理論；第三章用遺傳算法來解決車間調(diào)度問題 ,其中介紹了常用的幾種編碼方式 ,在比較的情況下提出本文主要用基于操作的編碼方式 .還有提出了幾種主要的遺傳算子。它將問題域中的可能解看作是群體的一個(gè)個(gè)體或染色體，并將每一個(gè)體編碼成符號(hào)串形式，對(duì)群體反復(fù)進(jìn)行基于遺傳學(xué)的操作（遺傳，交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià)，依據(jù)適者生存，優(yōu)勝劣汰的進(jìn)化規(guī)則，不斷得到更優(yōu)的群體，同時(shí)以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個(gè)體，求得滿足要求的最優(yōu)解。進(jìn)化是發(fā)生在編碼染色體上，通過對(duì)染色體的譯碼部分生成生物體，但下面幾個(gè)關(guān)于進(jìn)化理論的一般特性已被廣大人們所接受。 。自然選擇決定了群體中那些個(gè)個(gè)體能存活并繁殖，有性生殖保證了后代基因中的混合與重組。 遺傳算法的 模式定理 選擇操作是遺傳算法中體現(xiàn)“適者生存”的關(guān)鍵一環(huán)，它能控制高適應(yīng)度的模式成指數(shù)級(jí)增長(zhǎng)。 交換操作是有規(guī)則的信息交換，它能創(chuàng)建新的模式結(jié)構(gòu)，但又最低限度地破壞選擇操作過程所選擇的高適應(yīng)度的模式。 通過變異操作對(duì)個(gè)體串中單個(gè)位置進(jìn)行代碼替換，替換的概率為變異概率 Pm，則該位置不發(fā)生變異的概率為 1Pm。 模式定理保證了較優(yōu)的模式 (遺傳算法的較優(yōu)解 )的數(shù)目呈指數(shù)增長(zhǎng)，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長(zhǎng)，從而使遺傳算法找到全局最優(yōu)解的可能性存在 。 遺傳算法的收斂性分析 遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。 影響 選擇操作使高適應(yīng)度個(gè)體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。概率太小時(shí)，交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前，造成算法的不收斂。由馬爾可夫鏈推導(dǎo)出來的一些結(jié)論 :基本遺傳算法收斂于最優(yōu)解的概率為 1,使用保留最優(yōu)個(gè)體策略的遺傳算法收斂于最優(yōu)解的概率為 1。隱含并行性為遺傳算法的高效性提供了理論依據(jù)。 (crossover rate) 交換概率 Pc 用于控制交換操作的頻率。增加種群多樣性具有重要意義。 窗口 (scaling window) 該參數(shù)用于作出由目標(biāo)值到適應(yīng)度函數(shù)值的調(diào)整。這種機(jī)制意味著搜索過程可以跳出局部最優(yōu)點(diǎn)，能很好地將局部搜索和全局搜索協(xié)調(diào)起來，達(dá)到全局最優(yōu)點(diǎn)。 ，容易形成通用算法程序。 ，用遺傳算法求最優(yōu)解比較困難，因?yàn)槿旧w種群很可能過 早地 斂，而 對(duì)以后變化了的數(shù)據(jù)不再產(chǎn)生變化。 ，但交叉和變異的重要性存在爭(zhēng)議。 ，優(yōu)化問題要具體情況具體分析。通過不斷的選擇，使有利于生存發(fā)展的變異遺傳下去，積累下來，使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn) （ 即基因型 ） 是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。 隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個(gè)引人注目的新動(dòng)向 ［ 9］ ：一是基于遺傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來離散的搜索空間 的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法 ［ 10］ 。這一研究不僅對(duì)遺傳算法本身的發(fā)展，而且對(duì)于新一代智能計(jì)算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。此后， Holland 指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研究的論文。 Holland 在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對(duì)遺傳算法的理論研究和發(fā)展極其重要的模式理論 （ schema theory） 。盡管 De Jong 和 Hollstien 一樣主要側(cè)重于函數(shù)優(yōu)化的應(yīng)用研究，但他將 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 14 頁(yè) 選擇、交叉和變異操作進(jìn)一步完善和系統(tǒng)化，同時(shí)又提出了諸如代溝 （ generation gap）等新的遺傳操作技術(shù)。 1989 年， Holland 的學(xué) 生 出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》 （ Geic Algorithms in Search , Optimization, and Machine Learning） 。此外，以遺傳算法的理論基礎(chǔ)為中心的學(xué)術(shù)會(huì)議還有 Foundations of Geic Algorithms，該會(huì)也是從 1990 年開始隔年召開一次。 1994 年，他又出版了《遺傳程序設(shè)計(jì)，第二冊(cè) :可重用程序的自動(dòng)發(fā)現(xiàn)》深化了遺傳程序設(shè)計(jì)的研究，使程序設(shè)計(jì)自動(dòng)化展現(xiàn)了新局面?！?Advanced Computational Intelligence》雜志即將發(fā)刊，由模糊集合創(chuàng)始人 教授為名譽(yù)主編。一般的學(xué)習(xí)系統(tǒng)要求具有隨時(shí)間推移逐步調(diào)整有關(guān)參數(shù)或者改變自身結(jié)構(gòu)以更加適應(yīng)環(huán)境，更好達(dá)到目標(biāo)的能力。 今后幾年，拓廣更加多樣的應(yīng)用領(lǐng)域，將是 GA 發(fā)展的主流。這對(duì) GA 的實(shí)際應(yīng)用關(guān)系重大 。 研究過程中的幾個(gè)關(guān)鍵問題 設(shè)備死鎖現(xiàn)象 初始解群是問題的起點(diǎn)，解決設(shè)備死鎖問題必須從初始解群開始。遺傳算法的工作基礎(chǔ)是選擇適當(dāng)?shù)姆椒ū硎緜€(gè)體和問題的解 (作為進(jìn)化的個(gè)體 )。 表 加工時(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ī)器加工順序的工藝約束，