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

摘  要

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

關(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 國(guó)內(nèi)外研究現(xiàn)狀 6
1.4 課題的主要研究?jī)?nèi)容 7
2  車間調(diào)度問(wèn)題的描述 8
2.1 車間調(diào)度問(wèn)題的描述 8
2.2 車間調(diào)度問(wèn)題的特點(diǎn) 9
2.3 車間調(diào)度問(wèn)題的優(yōu)化方法 9
2.4 車間調(diào)度問(wèn)題的調(diào)度策略 11
    2.5 本章小結(jié)……………………………………………………………………………….12
3  遺傳算法的簡(jiǎn)述 13
3.1 遺傳算法的定義 13
3.2 遺傳算法的生物學(xué)知識(shí)背景 14
3.2.1 達(dá)爾文生物進(jìn)化論 14
3.2.2 孟德爾遺傳學(xué)說(shuō) 14
        3.2.3 DNA-遺傳信息的載體………………………..………………………………… 15
3.3 遺傳算法的基本思想 15
3.4 遺傳算法的特點(diǎn)………………………………………………………………………..17
3.5 本章小結(jié)……………………………………………………………………………….17
4  經(jīng)典車間調(diào)度問(wèn)題 18
4.1 流水車間調(diào)度問(wèn)題 18
4.1.1 概述 18
4.1.2 精確算法 19
4.1.3 啟發(fā)式計(jì)算 20
4.2 作業(yè)車間調(diào)度問(wèn)題 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)度問(wèn)題 28
5.1 車間調(diào)度系統(tǒng)設(shè)計(jì) 28
        5.1.1 系統(tǒng)設(shè)計(jì)中的關(guān)鍵性問(wèn)題………………………………………………………28
        5.1.2 調(diào)度系統(tǒng)設(shè)計(jì)的基本思想………………………………………………………29
        5.1.3 車間管理系統(tǒng)設(shè)計(jì)的基本思想…………………………………………………29
5.2 車間調(diào)度系統(tǒng)設(shè)計(jì) 30
        5.2.1 界面設(shè)計(jì)…………………………………………………………………………30
        5.2.2 程序設(shè)計(jì)…………………………………………………………………………31
5.3 本章小結(jié)……………………………………………………………………………….34
6  總結(jié)與展望……………………………………………………………………………...35
6.1 總結(jié)…………………………………………………………………………………….35
6.2 展望…………………………………………………………………………………….35
參考文獻(xiàn)………………………………………………………….…………………………………………37
致謝……………………………………………………………………………………………...38