基于遗传算法的模糊车间作业调度问题的研究.doc

基于遗传算法的模糊车间作业调度问题的研究

摘   要

在现今全球化制造时代，更加客户化的产品需求和更短的产品生命周期要求更加先进生产管理技术，车间作业调度技术是生产管理技术的核心技术。有效的车间作业调度技术，可以增强车间资源优化配置能力，提高企业的生产效率，减少生产损耗，使企业在经济全球化的竞争中处于领先地位。然而以往人们多将目光投在确定性车间作业调度问题上，但现实生产中，受多种随机因素的影响，加工时间和交货期往往都是模糊的，所以，本文在现有理论的基础上，研究了模糊车间作业调度问题。
本文首先在综合国内外关于车间作业调度问题研究状况的基础上，考虑目前车间作业运作的实际情况，对车间作业调度理论问题进行了深入系统的研究。其次考虑了车间作业调度问题复杂性与离散机械加工的特点，本文提出用遗传算法来优化车间调度问题。分析了遗传算法的基本理论，包括遗传算法的概念、操作流程、操作算子等，在此基础上重点探讨了几种目前看来最有效的邻域搜索算法。然后，比较分析了多种编码方式、遗传操作的优劣，设计了一种适用于车间作业调度问题的动态自适应遗传算法。此算法融入了保优策略和反复交叉变异策略，并且可以自适应调整交叉概率和变异概率。进而，又采用模糊数来表示工序加工时间和交货期，定义了客户满意度来表示产品完成时间令客户满意的程度，利用模糊数的运算、评价准则和所设计的遗传算法，定义并研究了多目标模糊车间作业调度问题。
通过遗传算法在车间作业调度中的研究，在实际的车间生产中运用遗传算法进行作业优化，可以更大地提高车间的加工管理水平，使企业获得更大的生产效益。

关键字:车间调度，遗传算法，模糊车间作业调度，多目标函数

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国内外研究概况 3
1.2.1车间作业调度的研究概况 3
1.2.2遗传算法在车间作业调度中的研究 4
1.2.3车间作业调度发展趋势 5
1.3论文主要内容 5
2 车间作业调度问题的研究 7
2.1车间作业调度问题 7
2.1.1车间作业调度问题描述 7
2.1.2模糊车间作业调度问题 8
2.2车间作业调度模型描述 10
2.3车间作业调度优化算法分析 13
2.3.1数学规划法 13
2.3.2近似算法 14
2.3.3智能搜索算法 15
2.4车间作业调度问题的求解方法—邻域搜索算法 18
2.5本章小结 22
3 遗传算法和模糊理论 23
3.1遗传算法的产生与发展 23
3.2遗传算法的基本思想及特点. 23
3.2.1遗传算法基本思想 23
3.2.2遗传算法的特点 24
3.3遗传算法的操作流程. 24
3.4遗传算法参数选择与操作设计 26
3.4.1编码 26
3.4.2适应值函数 29
3.4.3算法参数 30
3.4.4 操作设计 31
3.4.5算法终止条件 34
3.5模糊集合的定义 35
3.6模糊数 35
3.7模糊数的运算与评价 37
3.8本章小结 39
4 模糊车间作业调度问题的研究 40
4.1模糊车间作业调度问题目标函数的设计 40
4.2基于顾客满意度的模糊遗传算法 42
4.2.1种群初始化 42
4.2.2种群结构 43
4.2.3遗传操作 43
4.3 本章小结 43
5 算法验证 44
6 结论与展望 46
6.1结论 46
6.2 展望 46
参考文献 47
致谢 48