【正文】 含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機構(gòu)的學位或?qū)W歷而使用過的材料。 關(guān)鍵詞 ： 作業(yè) 車間調(diào)度； 遺傳算法；改進染色體編碼 ； 生產(chǎn)周期 遼寧科技大學本科生畢業(yè)設計 第 II 頁 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ù)學模型和優(yōu)化算法的基礎(chǔ)上，將一種改進的自適應遺傳算法應用在作業(yè)車間調(diào)度中。 作業(yè) 車間調(diào)度問題是計算機集成制造系統(tǒng) (CIMS)工程中的一個重要組成部分，它對企業(yè)的生產(chǎn)管理和控制系統(tǒng)有著重要的影響。在當今的競爭環(huán)境下，如何利用計算機技術(shù)實現(xiàn)生產(chǎn)調(diào)度計劃優(yōu)化，快速調(diào)整資源配置，統(tǒng)籌安排生產(chǎn)進度，提高設備利用率已成為許多加工企業(yè)面臨的重大課題。該算法是將 sigmoid 函數(shù)的變形函數(shù)應用到自適應遺傳算法中，并將作業(yè)車間調(diào)度問題中的完工時間大小作為算法的評價指標，實現(xiàn)了交叉率和變異率隨著完工時間的非線性自適應調(diào)整，較好地克服了標準遺傳算法在解決作業(yè)車間調(diào)度問題時的“早熟”和穩(wěn)定性差的缺點，以及傳統(tǒng)的線性自適應遺傳算法收斂速度慢的缺點。 geic algorithm。對本研究提供過幫助和做出過貢獻的個人或集體，均已在文中作了明確的說明并表示了謝意。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。 涉密論文按學校規(guī)定處理。遺傳算法的蓬勃發(fā)展正體現(xiàn)了科學發(fā)展的這一特點和趨勢。 由于一般車間調(diào)度問題的復雜性，各種不同的具體問題往往有許多不同的算法來解決，例如經(jīng)典的啟發(fā)式算法，傳統(tǒng)的搜索方法等。 作業(yè) 車間調(diào)度問題表述 作業(yè)車間調(diào)度（ jobshop）問題可以表述為：設有 N個工件在 M臺機器上加工，根據(jù)工件加工工藝的要求，每個工件使用 機器的順序及其每道工序所花時間已給定，調(diào)度問題的目標就是如何選擇加工順序使得總的加工時間最短最優(yōu)。它可分為精確求解方法和近視求解方法。 車間作業(yè)是指利用車間資源 (如機床、刀具、夾具等 )完成的某項任務。一個工件在一臺機器上的加工程序稱為一道“工序”，相應的加工時間稱為該工序的“加工時間”。它所要解決的問題就是確定每臺機器上不同工件的加工順序，以及每個工件的所有工序的起始加工時間，以最優(yōu)化某個性能指標。 2. 不考慮工件加工的優(yōu)先權(quán)，即工件之間沒有優(yōu)先約束關(guān)系限制的 。 6. 緩沖區(qū)容量為無窮大。 P（ i， j） 表 示 i工件的第 j 道工序。 MJ （ i， j）表示 i工件的第 j 道工序的機器號， (, )MJi? 表示 i工件的所有工序按優(yōu)先順序加工的各機器號的排列。同樣地，如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿 。事實上，工件排列陣就是調(diào)度的一種表示形式。調(diào)度問題從生產(chǎn)成本方面來考慮，其優(yōu)化目標有 :庫存最少、在制品最少、設備利用率最高等 。第一章簡要介紹了車間調(diào)度問題和求解調(diào)度問題的基本方法 ；第 遼寧科技大學本科生畢業(yè)設計 第 5 頁 二章介紹了遺傳算法的基本理論；第三章用遺傳算法來解決車間調(diào)度問題 ,其中介紹了常用的幾種編碼方式 ,在比較的情況下提出本文主要用基于操作的編碼方式 .還有提出了幾種主要的遺傳算子。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號串形式，對群體反復進行基于遺傳學的操作（遺傳，交叉和變異），根據(jù)預定的目標適應度函數(shù)對每個個體進行評價，依據(jù)適者生存，優(yōu)勝劣汰的進化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。進化是發(fā)生在編碼染色體上，通過對染色體的譯碼部分生成生物體，但下面幾個關(guān)于進化理論的一般特性已被廣大人們所接受。 。自然選擇決定了群體中那些個個體能存活并繁殖，有性生殖保證了后代基因中的混合與重組。 遺傳算法的 模式定理 選擇操作是遺傳算法中體現(xiàn)“適者生存”的關(guān)鍵一環(huán)，它能控制高適應度的模式成指數(shù)級增長。 交換操作是有規(guī)則的信息交換，它能創(chuàng)建新的模式結(jié)構(gòu)，但又最低限度地破壞選擇操作過程所選擇的高適應度的模式。 通過變異操作對個體串中單個位置進行代碼替換，替換的概率為變異概率 Pm，則該位置不發(fā)生變異的概率為 1Pm。 模式定理保證了較優(yōu)的模式 (遺傳算法的較優(yōu)解 )的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理提供了數(shù)學基礎(chǔ)。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在 。 遺傳算法的收斂性分析 遺傳算法要實現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。 影響 選擇操作使高適應度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。概率太小時，交叉操作很少進行，從而會使搜索停滯不前，造成算法的不收斂。由馬爾可夫鏈推導出來的一些結(jié)論 :基本遺傳算法收斂于最優(yōu)解的概率為 1,使用保留最優(yōu)個體策略的遺傳算法收斂于最優(yōu)解的概率為 1。隱含并行性為遺傳算法的高效性提供了理論依據(jù)。 (crossover rate) 交換概率 Pc 用于控制交換操作的頻率。增加種群多樣性具有重要意義。 窗口 (scaling window) 該參數(shù)用于作出由目標值到適應度函數(shù)值的調(diào)整。這種機制意味著搜索過程可以跳出局部最優(yōu)點，能很好地將局部搜索和全局搜索協(xié)調(diào)起來，達到全局最優(yōu)點。 ，容易形成通用算法程序。 ，用遺傳算法求最優(yōu)解比較困難，因為染色體種群很可能過 早地 斂，而 對以后變化了的數(shù)據(jù)不再產(chǎn)生變化。 ，但交叉和變異的重要性存在爭議。 ，優(yōu)化問題要具體情況具體分析。通過不斷的選擇，使有利于生存發(fā)展的變異遺傳下去，積累下來，使變異和遺傳向著適應環(huán)境的方向發(fā)展。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn) （ 即基因型 ） 是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。 隨著應用領(lǐng)域的擴展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向 ［ 9］ ：一是基于遺傳算法的機器學習，這一新的研究課題把遺傳算法從歷來離散的搜索空間 的優(yōu)化搜索算法擴展到具有獨特的規(guī)則生成功能的嶄新的機器學習算法 ［ 10］ 。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機體系結(jié)構(gòu)的研究都是十分重要的。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點。此后， Holland 指導學生完成了多篇有關(guān)遺傳算法研究的論文。 Holland 在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極其重要的模式理論 （ schema theory） 。盡管 De Jong 和 Hollstien 一樣主要側(cè)重于函數(shù)優(yōu)化的應用研究，但他將 遼寧科技大學本科生畢業(yè)設計 第 14 頁 選擇、交叉和變異操作進一步完善和系統(tǒng)化，同時又提出了諸如代溝 （ generation gap）等新的遺傳操作技術(shù)。 1989 年， Holland 的學 生 出版了專著《搜索、優(yōu)化和機器學習中的遺傳算法》 （ Geic Algorithms in Search , Optimization, and Machine Learning） 。此外，以遺傳算法的理論基礎(chǔ)為中心的學術(shù)會議還有 Foundations of Geic Algorithms，該會也是從 1990 年開始隔年召開一次。 1994 年，他又出版了《遺傳程序設計，第二冊 :可重用程序的自動發(fā)現(xiàn)》深化了遺傳程序設計的研究，使程序設計自動化展現(xiàn)了新局面。《 Advanced Computational Intelligence》雜志即將發(fā)刊，由模糊集合創(chuàng)始人 教授為名譽主編。一般的學習系統(tǒng)要求具有隨時間推移逐步調(diào)整有關(guān)參數(shù)或者改變自身結(jié)構(gòu)以更加適應環(huán)境，更好達到目標的能力。 今后幾年，拓廣更加多樣的應用領(lǐng)域，將是 GA 發(fā)展的主流。這對 GA 的實際應用關(guān)系重大 。 研究過程中的幾個關(guān)鍵問題 設備死鎖現(xiàn)象 初始解群是問題的起點，解決設備死鎖問題必須從初始解群開始。遺傳算法的工作基礎(chǔ)是選擇適當?shù)姆椒ū硎緜€體和問題的解 (作為進化的個體 )。 表 加工時間和工藝約束 項目 工件 操作序列 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 個機器上加工（以下同），則對機器加工順序的工藝約束，