目 錄
摘要……………………………………………………………………………………….…………………...1
前言……………………………………………………………………………………….………………….2
1遺傳算法的簡介……………………………………………………………………..….….......…………3
1.1遺傳算法的原理…………………………………………………………………….…………………...3
1.2遺傳算法的設計…………………………..……….………………………………….…..…………..….4
2 Turbo C的特點及簡介……………….....….…………………………....…….…..….…………….…......5
2.1 C 語言的產生與發展……………….…………………………………....……….….…...…………5
2.2 C 語言的特點……………………….………………………………….……...…....…….…………5
2.3 Turbo C 概述…………………………………………………………..…….………….……………..5
3 JSSP問題的描述及簡單分析…………………………………………….…………….….……….....…..7
3.1 JSSP的數學模型及其參變量…………………….. …………………………..………….……….…..7
4基於遺傳算法的車間作業調度的實現技術………………………………………..…....……….………9
4.1 JSSP的遺傳算法應用及處理………………………………………..…....……….………………….9
4.2 JSSP的遺傳算法的實現………………………………………..…....……….………………………11
5 適用於車間作業調度的遺傳算法描述…………………………..…....……….……………………….16
5.1 總體算法的描述…………………………………………………………..…….………….………16
5.2 仿真實驗及結果…………………………………………………………..…….………….………16
結論……………………………………………………………………………………..…………………..19
參考文獻………………………………………………………………..…………….………..…….20
致謝詞…………………………………………………………………….............................................21
附錄………………………………………………………....................……….………..22
應用遺傳算法解決車間作業調度問題
摘要
車間調度問題簡單來說就是設備資源優化配置問題。近年來遺傳算法得到了很大的發展，應用遺傳算法來解決車間調度問題早有研究。本文在已有算法基礎上詳細討論了染色體編碼方法並對其進行了改進。最後根據改進的編碼進行遺傳算法的設計，本文提出了1種求解車間作業調度問題的改進的遺傳算法，並給出仿真算例表明了該算法的有效性。
關鍵詞：車間作業調度;遺傳算法;改進遺傳算法染色體編碼
Genetic algorithms for Job Shop Scheduling Problem
Abstract
simply speaking, the job shop scheduling problem is the equipment resources optimization question. In recent years, the genetic algorithms obtained great development, it was used to solve the job shop scheduling problem early. This paper discusses the chromosome code method in detail based on the genetic algorithms and make the improvement on it. In the end, according to the code which improved carries on the genetic algorithms design, this paper offer one improved genetic algorithms about soloving to the job shop scheduling problem, and the simulated example has indicated that this algorithm is valid.
Key words: job shop scheduling ;genetic algorithms ; Improvement genetic algorithms chromosome code
前言
隨着社會不斷向前發展，競爭的加劇，製造業中普遍面臨的許多問題不斷地突現出來。如何在有限的生產資料條件下，以最短的生產週期、最小的成本將產品製造出來以滿足客戶的需求是每1個製造商不斷追求的目標。如何運用有限的資源，降低產品的生產成本，縮短產品的'製造週期，保證按時交貨，提高企業信譽，贏得更多的客戶，成爲製造廠商在競爭中生存的1個重要的條件。有效的利用現有的資源，合理的制定企業和車間生產計劃，是達到這個目標的關鍵。
由於車間調度問題不僅是1個典型的NP難題，也是至今爲止所有組合優化問題中最難問題之1，所以得到了廣泛的關注。早在20世紀50年代早期就有很多關於調度問題的研究文獻。在計算機出現以前，作業車間調度問題(Job Shop Scheduling Problem，簡稱爲JSSP或JSS問題)是用手工計算完成的。但是由於問題本身複雜、計算量大，手工操作可靠性差、調度方案優化性能不好，跟不上產品的多變性要求又容易受隨機因素的干擾，使資源和生產能力得不到充分的發揮和利用，生產車間效率不高。即使隨着計算機的出現和發展，調度問題也沒有得到很好的解決，因爲問題的規模和實時性要求也在不斷提高。通常用於求解JSSP的技術與方法主要分爲兩類，1類是近似求解方法，1類是最優化求解方法。用近似方法求解時，可以很快地得到問題的解，但它們不能保證所得到的解是最優的；用最優化方法求解這1問題時，它們可以得到全局最優解，但它們只能解決小規模的，而且速度很慢。
鑑於JSSP在實際應用中的重要地位，論文的具體安排如下:
第1：本文將對車間作業調度問題的基本概念、數學模型、表示方法及其基本理論進行闡述。在深入對問題進行剖析的基礎上，借鑑自然進化思想機理，對JSSP的求解問題進行探索性研究。旨在爲求解JSSP問題提供新的解決思路。而本文主要的研究重點放在基本遺傳算法，求解JSSP的研究上的編碼問題。同時給出以最小化生產週期(minimum makespan)爲目標函數的問題JSSP模型，並還給出了關於問題的複雜性描述。
第2：對遺傳算法在JSSP應用中的編碼問題、解碼問題以及JSSP的遺傳算子設計進行了深入的分析，參照了西安電子科技大學姜迪剛，葉尚輝共同編寫的論文《基於遺傳算法的車間調度作業》，針對1個生產週期最小化的優化目標進行實現。
最後，對本文進行了總結並對以後的研究工作給出了1些建議和展望。
1 遺傳算法的簡介
1.1 遺傳算法原理
遺傳算法(Genetic Algorithms) 是1種大致基於進化論優勝劣汰、適者生存的物種遺傳思想的搜尋算法。透過變異和重組當前1致的最好假設來生成後續的假設，每1步，更新被稱爲當前羣體的1組假設，方法是透過使用目前適應度最高的假設的後代替代羣體的某個部分。遺傳算法的普及主要考慮以下因素:
(1) 在生物系統中，進化被認爲是1種成功的自適應方法，且具有更好的健壯性；
(2) 遺傳算法搜尋的假設空間中，假設的各個部分相互作用，每1部分對總的假設適應度的影響難以建模；
(3) 遺傳算法易於並行化。遺傳算法的不同實現在細節上有所不同，但他們都具有以下的共同結構:算法迭代更新1個假設池，這個假設池稱爲羣體。在每1次迭代中，根據適應度函數評估羣體中的所有成員，然後從當前羣體中用概率方法選取適應度最高的個體產生新1代羣體。在這些被選中的個體中，1部分保持原樣地進入下1代羣體，其他的被用作產生後代個體的基礎。其中應用像交叉和變異這樣的遺傳方法。其中的重點在於如何表示解空間、遺傳算子的設計和適應度函數的計算。
