基于遺傳算法的模糊車間作業(yè)調(diào)度問題的研究

摘   要

在現(xiàn)今全球化制造時代，更加客戶化的產(chǎn)品需求和更短的產(chǎn)品生命周期要求更加先進(jìn)生產(chǎn)管理技術(shù)，車間作業(yè)調(diào)度技術(shù)是生產(chǎn)管理技術(shù)的核心技術(shù)。有效的車間作業(yè)調(diào)度技術(shù)，可以增強(qiáng)車間資源優(yōu)化配置能力，提高企業(yè)的生產(chǎn)效率，減少生產(chǎn)損耗，使企業(yè)在經(jīng)濟(jì)全球化的競爭中處于領(lǐng)先地位。然而以往人們多將目光投在確定性車間作業(yè)調(diào)度問題上，但現(xiàn)實(shí)生產(chǎn)中，受多種隨機(jī)因素的影響，加工時間和交貨期往往都是模糊的，所以，本文在現(xiàn)有理論的基礎(chǔ)上，研究了模糊車間作業(yè)調(diào)度問題。
本文首先在綜合國內(nèi)外關(guān)于車間作業(yè)調(diào)度問題研究狀況的基礎(chǔ)上，考慮目前車間作業(yè)運(yùn)作的實(shí)際情況，對車間作業(yè)調(diào)度理論問題進(jìn)行了深入系統(tǒng)的研究。其次考慮了車間作業(yè)調(diào)度問題復(fù)雜性與離散機(jī)械加工的特點(diǎn)，本文提出用遺傳算法來優(yōu)化車間調(diào)度問題。分析了遺傳算法的基本理論，包括遺傳算法的概念、操作流程、操作算子等，在此基礎(chǔ)上重點(diǎn)探討了幾種目前看來最有效的鄰域搜索算法。然后，比較分析了多種編碼方式、遺傳操作的優(yōu)劣，設(shè)計(jì)了一種適用于車間作業(yè)調(diào)度問題的動態(tài)自適應(yīng)遺傳算法。此算法融入了保優(yōu)策略和反復(fù)交叉變異策略，并且可以自適應(yīng)調(diào)整交叉概率和變異概率。進(jìn)而，又采用模糊數(shù)來表示工序加工時間和交貨期，定義了客戶滿意度來表示產(chǎn)品完成時間令客戶滿意的程度，利用模糊數(shù)的運(yùn)算、評價準(zhǔn)則和所設(shè)計(jì)的遺傳算法，定義并研究了多目標(biāo)模糊車間作業(yè)調(diào)度問題。
通過遺傳算法在車間作業(yè)調(diào)度中的研究，在實(shí)際的車間生產(chǎn)中運(yùn)用遺傳算法進(jìn)行作業(yè)優(yōu)化，可以更大地提高車間的加工管理水平，使企業(yè)獲得更大的生產(chǎn)效益。

關(guān)鍵字:車間調(diào)度，遺傳算法，模糊車間作業(yè)調(diào)度，多目標(biāo)函數(shù)

ABSTRACT

The trends of increased demands for more customized products and increasing product life cycles in this global manufacturing era point at the need to more advanced production management. Job-shop Schedule technology is the core technology of production management. Effective Job-shop schedule technology can boost the collocation of corporation resources. It also can improve productivity and reduce cost. This will enhance the capacity of the corporation and make the corporation the leader in the competition. Nevertheless, scholars often focus on certain job-shop scheduling problem in the past, but because it is affected by many uncertain factors in reality, this dissertation researches about fuzzy job-shop scheduling problem based-on existing theories.
On the basis of the technical review on the domestic and foreign research, this thesis has an extensive and systematic study on the job-shop scheduling combining the actual job-shop operation. Based on the complexity of Job-shop scheduling problem and the characteristics of machining, this thesis develops genetic algorithm to optimize job-shop scheduling problem. On the basis of dissertation of the fundamental conception, principle and operators of genetic algorithm, this thesis designs algorithm to apply it to job-shop scheduling optimization in detail. And several important neighbor-region searching algorithms which are the most effective intelligent methods until now are discussed. The advantages and disadvantages of different coding, genetic operations are compared and analyzed. Then the dynamic adaptive GA is designed towards solving job-shop scheduling problem. The strategy of "hold best result" and "repeated crossover and mutation" are united into GA and the possibility of crossover and mutation can be adjusted automatically according to the results of optimization. The processing time of operation and duedate are represented by fuzzy numbers and the satisfaction degree of customers is presented for showing the degree that the completion time is satisfying with customers. Then using the operations and eva luation criterions of fuzzy numbers, multi-objective fuzzy job-shop scheduling problem is defined and studied.
According to the research of genetic algorithm on job-shop scheduling problem, the use of genetic algorithm to actual job shop can highly improve the level of shop management and attain more profits.

Keywords: Job-shop Scheduling, Genetic Algorithm, Fuzzy Job-shop Scheduling, Multi-objective Function

目   錄

摘   要 I
ABSTRACT II
目   錄 IV
1 緒論 1
1.1課題研究背景及意義 1
1.1.1課題研究背景 1
1.1.2課題研究意義 2
1.2國內(nèi)外研究概況 3
1.2.1車間作業(yè)調(diào)度的研究概況 3
1.2.2遺傳算法在車間作業(yè)調(diào)度中的研究 4
1.2.3車間作業(yè)調(diào)度發(fā)展趨勢 5
1.3論文主要內(nèi)容 5
2 車間作業(yè)調(diào)度問題的研究 7
2.1車間作業(yè)調(diào)度問題 7
2.1.1車間作業(yè)調(diào)度問題描述 7
2.1.2模糊車間作業(yè)調(diào)度問題 8
2.2車間作業(yè)調(diào)度模型描述 10
2.3車間作業(yè)調(diào)度優(yōu)化算法分析 13
2.3.1數(shù)學(xué)規(guī)劃法 13
2.3.2近似算法 14
2.3.3智能搜索算法 15
2.4車間作業(yè)調(diào)度問題的求解方法—鄰域搜索算法 18
2.5本章小結(jié) 22
3 遺傳算法和模糊理論 23
3.1遺傳算法的產(chǎn)生與發(fā)展 23
3.2遺傳算法的基本思想及特點(diǎn). 23
3.2.1遺傳算法基本思想 23
3.2.2遺傳算法的特點(diǎn) 24
3.3遺傳算法的操作流程. 24
3.4遺傳算法參數(shù)選擇與操作設(shè)計(jì) 26
3.4.1編碼 26
3.4.2適應(yīng)值函數(shù) 29
3.4.3算法參數(shù) 30
3.4.4 操作設(shè)計(jì) 31
3.4.5算法終止條件 34
3.5模糊集合的定義 35
3.6模糊數(shù) 35
3.7模糊數(shù)的運(yùn)算與評價 37
3.8本章小結(jié) 39
4 模糊車間作業(yè)調(diào)度問題的研究 40
4.1模糊車間作業(yè)調(diào)度問題目標(biāo)函數(shù)的設(shè)計(jì) 40
4.2基于顧客滿意度的模糊遺傳算法 42
4.2.1種群初始化 42
4.2.2種群結(jié)構(gòu) 43
4.2.3遺傳操作 43
4.3 本章小結(jié) 43
5 算法驗(yàn)證 44
6 結(jié)論與展望 46
6.1結(jié)論 46
6.2 展望 46
參考文獻(xiàn) 47
致謝 48