基于混合遺傳算法的車間調(diào)度方法研究與應用

摘  要

計算機集成制造系統(tǒng)(CIMS)在制造業(yè)的廣泛實施帶來了良好的經(jīng)濟效益，正成為當前國內(nèi)外各大中型企業(yè)研究和實施的熱點。管理自動化是CIMS的分系統(tǒng)，是現(xiàn)代制造工廠的重要促成部分，計算機輔助生產(chǎn)計劃、作業(yè)調(diào)度與控制是管理自動化的核心技術(shù)。生產(chǎn)計劃與調(diào)度系統(tǒng)作為實施CIMS工程中的一個重要組成部分，是CIMS功能結(jié)構(gòu)模型中不可缺少的一個層次，它對企業(yè)生產(chǎn)管理與控制系統(tǒng)有著重要的影響調(diào)度。因此，車間作業(yè)調(diào)度研究也成為廠大學者的研究課題，具有重要意義。這一問題研究因其建模復雜性、計算復雜性、動態(tài)多約束、多目標性等特點，是組合優(yōu)化問題范疇，被證明是典型NP困難問題，近幾年各種H能計算方法逐漸被引入到作業(yè)調(diào)度問題中，如遺傳算法、模擬退火算法、啟發(fā)式算法等。
遺傳算法(Genetic Algorithm GA)是演化計算方法中應用最廠泛之一，應用于全局搜索等參數(shù)優(yōu)化計算領(lǐng)域，也適用于車間作業(yè)調(diào)度問題。它作為一種非確定性的擬生態(tài)隨機優(yōu)化算法在過去20年中得到了廣泛的應用，由于其具有不依賴于問題模型的特性、全局最優(yōu)性、隨機轉(zhuǎn)移性而非確定性、隱含并行性等特點，因此遺傳算法更適合復雜問題的優(yōu)化比其他優(yōu)化技術(shù)相比存在顯著的優(yōu)勢，正越來越激起人們的廣泛研究與應用。
本文應用遺傳算法求解復雜的車間調(diào)度問題。首先在第一章緒論中論述了車間調(diào)度問題的重要性及其研究現(xiàn)狀、方法。緊接著在隨后的幾個章節(jié)分別介紹了遺傳算法的理論基礎(chǔ)，作業(yè)車間調(diào)度問題、流水車間調(diào)度問題、機器調(diào)度問題的描述、研究策略、及遺傳算法求解時的編碼方式和性能比較。在最后，簡要地論述了本論文課題的進一步研究方向及其研究方法和策略。

關(guān)鍵詞：生產(chǎn)調(diào)度，遺傳算法，啟發(fā)式，流水車間，作業(yè)車間

ABSTRACT

Computer Integrated Manufacturing System (CIMS) can greatly promote the synthesized economic profit of the enterprise when it is implemented widely in manufacturing fields, thus it has become the hotspot of research and implement in all kinds of enterprises. Management Automation System, one sub-system of CIMS, is an important part of modern manufacturing factory whose kernel technologies are CAPP, Job Shop Scheduling Problem (JSSP), etc, Which are vital and indispensable as a one part of enterprise produce system, JSPP affects it so much. So JSSP stirs many scholars' research. JSSP characters as its complicated model construct and calculation, dynamic multi-restriction, and multi-objective. It is assemble optimization problem and has been proved as NP-hard problem. Many intelligent computation methods such as simulated Anneal Algorithm, Genetic Algorithm, heuristic algorithm, are introduced into scheduling problem in recent years.
As a method in eva luative computer field, GA is applied widely in parameter optimization such as global search. When it's applied in JSSP, there are several distinct merits compared with other methods. As an uncertain stochastic optimal algorithm, GA is applied in all kinds of fields in the past 20 years. And because of its independence, global optimization, and implicit parallelism in complex problem solving, GA is developed and applied in many fields by more and more people.
In this paper, GA is applied to solve complicated shop floor scheduling problem. The paper is divided into seven chapters. In the introduction, it states the significance, recent actuality and research methods of job shop scheduling problem. Then the succeed five chapters include the presentation of GA, the typical descriptions of job shop, flow shop, machine scheduling earliness-tardiness and virtual scheduling and its research strategy. The performance is compared when using different GA coding mode. The simulation scheduling results of several samples show GA's feasibility, reliability and validity in solving JSSP problems. The last chapter is conclusion and expectation and prospect of the research subject.

Key words: Production scheduling, Genetic Algorithm, Flow Shop, Job Shop.
 

目   錄

摘  要 I
ABSTRACT II
1  引言 5
1.1 緒論 5
1.2 課題研究的目的和意義 5
1.3 國內(nèi)外研究現(xiàn)狀 6
1.4 課題的主要研究內(nèi)容 7
2  車間調(diào)度問題的描述 8
2.1 車間調(diào)度問題的描述 8
2.2 車間調(diào)度問題的特點 9
2.3 車間調(diào)度問題的優(yōu)化方法 9
2.4 車間調(diào)度問題的調(diào)度策略 11
    2.5 本章小結(jié)……………………………………………………………………………….12
3  遺傳算法的簡述 13
3.1 遺傳算法的定義 13
3.2 遺傳算法的生物學知識背景 14
3.2.1 達爾文生物進化論 14
3.2.2 孟德爾遺傳學說 14
        3.2.3 DNA-遺傳信息的載體………………………..………………………………… 15
3.3 遺傳算法的基本思想 15
3.4 遺傳算法的特點………………………………………………………………………..17
3.5 本章小結(jié)……………………………………………………………………………….17
4  經(jīng)典車間調(diào)度問題 18
4.1 流水車間調(diào)度問題 18
4.1.1 概述 18
4.1.2 精確算法 19
4.1.3 啟發(fā)式計算 20
4.2 作業(yè)車間調(diào)度問題 22
4.2.1 概述 23
4.2.2 古典作業(yè)車間調(diào)度模型 23
4.2.3 傳統(tǒng)啟發(fā)式 24
4.3 本章小結(jié) 27
5  基于遺傳算法的作業(yè)車間調(diào)度問題 28
5.1 車間調(diào)度系統(tǒng)設計 28
        5.1.1 系統(tǒng)設計中的關(guān)鍵性問題………………………………………………………28
        5.1.2 調(diào)度系統(tǒng)設計的基本思想………………………………………………………29
        5.1.3 車間管理系統(tǒng)設計的基本思想…………………………………………………29
5.2 車間調(diào)度系統(tǒng)設計 30
        5.2.1 界面設計…………………………………………………………………………30
        5.2.2 程序設計…………………………………………………………………………31
5.3 本章小結(jié)……………………………………………………………………………….34
6  總結(jié)與展望……………………………………………………………………………...35
6.1 總結(jié)…………………………………………………………………………………….35
6.2 展望…………………………………………………………………………………….35
參考文獻………………………………………………………….…………………………………………37
致謝……………………………………………………………………………………………...38