遗传算法的车间调度问题的研究
摘要：在当今激烈的竞争环境下，计算机集成制造系统(ClMS)在制造业的广泛实施给各大中型企业带来了巨大的经济效益，正逐渐成为国内外企业研究和实施的热点。生产管理与控制系统是CIMS中的不可缺少部分，而车间调度问题(JSP)是企业的生产管理与控制系统的核心问题之一。对车间作业调度问题的研究因此成为热门课题，具有重要的意义。这一问题具有计算复杂性、建模复杂性、多目标性、动态多约束等特点，属于组合优化问题范畴，已被证明是典型NP-hard问题。近几年各种智能算法正被逐渐引入到求解作业调度问题中，如禁忌搜索算法、遗传算法、模拟退火算法等。遗传算法(Geneti Algorithm，GA)是模拟生物进化论的自然选择与遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，是应用最广泛的演化计算方法之一[1]。本文第一章通过论述车间调度问题的基本内容以及意义展示研究生产调度问题的必要性；第二章首先描述了车间调度问题，然后建立了车间调度问题的数学模型；第三章研究了车间调度系统中关于遗传算法的基本理论，包括其基本概念、基本思想与特点；第四章详细研究了如何应用遗传算法求解车间调度问题，包括遗传算法的基本处理流程、基本步骤、交叉变异算子以及参数选择等，利用自适应的交叉变异概率加快了收敛速度，详细讲述了LOX、POX两种交叉方法，同时本文构造了针对基于工序编码的变异方法；第五章在遗传算法中引入模拟退火算法，模拟退火中采取定步长的抽样策略，并详细讨论了混合策略；第六章列举了具体运行结果，并对运行结果进行了分析与评估；最后，第七章总结全文并对车间调度研究的发展趋势进行展望。
目录
摘要： I
Abstract： II
第一章 绪论 1
1.1 课题的提出 1
1.2课题的意义 1
1.3车间调度问题的研究现状 1
第二章 车间调度问题 3
2.1车间调度问题的描述 3
2.2 车间调度问题的数学模型 3
第三章 遗传算法简介 5
3.1遗传算法的基本思想 5
3.2遗传算法的特点 5
第四章 求解车间调度问题的基本遗传算法 7
4.1 编码设计 8
4
*好棒文|www.hbsrm.com +Q: ￥351916072￥
.1.1基于工序的编码 9
4.1.2基于工件的编码 10
4.1.3基于先后表的编码 10
4.2 基于工序编码的解码设计 10
4.3 适应度定义及其尺度变换 11
4.3.1常见的适应度 11
4.3.2适应度函数的作用： 12
4.3.3适应度函数的尺度变换 13
4.4 交叉算子 13
4.4.1 LOX 13
4.4.2 POX 14
4.5 变异 15
4.6 选择 15
4.7自适应交叉、变异概率 16
第五章 混合遗传算法 18
5.1 模拟退火算法 18
5.2 混合遗传算法 19
5.3混合遗传算法的优点 19
第六章 运行结果及分析 21
6.1 基本遗传算法求解 21
6.1.1 POX与LOX比较 21
6.1.2两种变异操作的比较 24
6.2模拟退火算法求解 25
6.3 混合遗传算法(GASA)求解 26
第七章 总结与展望 30
致谢 32
参考文献 33
附录 36
Abstract：
In todays fierce competition environment, computer integrated manufacturing system (ClMS) widely implemented in manufacturing industry of the large and mediumsized enterprises has brought huge economic benefits and is gradually become a hot research point both at domestic and abroad enterprises.
Production management and control system is an indispensable part of CIMS, while Job Shop Problem (JSP) is one of the important influence factors for an enterprises production management and control system. Therefore, the study of Job Shop Problem has become many scholars’ research topic, with the vital significance.This problem has the computational complexity, the complexity of modeling, the characteristics of multiobjective and dynamic constraint and so on. Belong to the category of combinatorial optimization problem, the problem has been proved to be a typical NP hard problem. In recent years,all kinds of intelligent algorithm is being gradually introduced into the job scheduling problems, such as Tabu Search algorithm, Genetic Algorithm, simulated annealing algorithm, etc.
Genetic Algorithm (Geneti Algorithm, GA) is calculation model by simulating the evolution of natural selection and genetic mechanism of biological evolution process and is a kind of method searching optimal solution by simulating the natural evolution process, and is also one of the most widely used evolutionary computation method[1].The first chapter of the paper show the necessity of the research production scheduling problem by discuss the basic content of job shop scheduling problem and its sense.The second and third chapter first describes the job shop scheduling problem, and then established its mathematical model.The fourth chapter studies the basic theory of the shop scheduling system on genetic algorithm, including its basic concepts, basic thoughts and characteristics.The fifth chapter studied how to apply genetic algorithm to solve the shop scheduling problem in detail , including the basic process, the basic steps of genetic algorithm, crossover and mutation operator and parameter selection, etc, using adaptive crossover mutation probability to speed up the convergence speed, and detailed tells the cross methods of LOX, POX.In the same time,this paper is to construct the mutation method based on the operationbased coding method.In Chapter 6,the simulated annealing algorithm is introduced into the genetic algorithm, simulated annealing algorithm using step sampling strategy, and discusses the mixed strategies in detail.Chapter 7 lists the specific operation results, and the operation result was analyzed and evaluation.Finally, the eighth chapter summarizes the full paper and discuss the development trend of the research of job shop scheduling.
目录
摘要： I
Abstract： II
第一章 绪论 1
1.1 课题的提出 1
1.2课题的意义 1
1.3车间调度问题的研究现状 1
第二章 车间调度问题 3
2.1车间调度问题的描述 3
2.2 车间调度问题的数学模型 3
第三章 遗传算法简介 5
3.1遗传算法的基本思想 5
3.2遗传算法的特点 5
第四章 求解车间调度问题的基本遗传算法 7
4.1 编码设计 8
4
*好棒文|www.hbsrm.com +Q: ￥351916072￥
.1.1基于工序的编码 9
4.1.2基于工件的编码 10
4.1.3基于先后表的编码 10
4.2 基于工序编码的解码设计 10
4.3 适应度定义及其尺度变换 11
4.3.1常见的适应度 11
4.3.2适应度函数的作用： 12
4.3.3适应度函数的尺度变换 13
4.4 交叉算子 13
4.4.1 LOX 13
4.4.2 POX 14
4.5 变异 15
4.6 选择 15
4.7自适应交叉、变异概率 16
第五章 混合遗传算法 18
5.1 模拟退火算法 18
5.2 混合遗传算法 19
5.3混合遗传算法的优点 19
第六章 运行结果及分析 21
6.1 基本遗传算法求解 21
6.1.1 POX与LOX比较 21
6.1.2两种变异操作的比较 24
6.2模拟退火算法求解 25
6.3 混合遗传算法(GASA)求解 26
第七章 总结与展望 30
致谢 32
参考文献 33
附录 36
Abstract：
In todays fierce competition environment, computer integrated manufacturing system (ClMS) widely implemented in manufacturing industry of the large and mediumsized enterprises has brought huge economic benefits and is gradually become a hot research point both at domestic and abroad enterprises.
Production management and control system is an indispensable part of CIMS, while Job Shop Problem (JSP) is one of the important influence factors for an enterprises production management and control system. Therefore, the study of Job Shop Problem has become many scholars’ research topic, with the vital significance.This problem has the computational complexity, the complexity of modeling, the characteristics of multiobjective and dynamic constraint and so on. Belong to the category of combinatorial optimization problem, the problem has been proved to be a typical NP hard problem. In recent years,all kinds of intelligent algorithm is being gradually introduced into the job scheduling problems, such as Tabu Search algorithm, Genetic Algorithm, simulated annealing algorithm, etc.
Genetic Algorithm (Geneti Algorithm, GA) is calculation model by simulating the evolution of natural selection and genetic mechanism of biological evolution process and is a kind of method searching optimal solution by simulating the natural evolution process, and is also one of the most widely used evolutionary computation method[1].The first chapter of the paper show the necessity of the research production scheduling problem by discuss the basic content of job shop scheduling problem and its sense.The second and third chapter first describes the job shop scheduling problem, and then established its mathematical model.The fourth chapter studies the basic theory of the shop scheduling system on genetic algorithm, including its basic concepts, basic thoughts and characteristics.The fifth chapter studied how to apply genetic algorithm to solve the shop scheduling problem in detail , including the basic process, the basic steps of genetic algorithm, crossover and mutation operator and parameter selection, etc, using adaptive crossover mutation probability to speed up the convergence speed, and detailed tells the cross methods of LOX, POX.In the same time,this paper is to construct the mutation method based on the operationbased coding method.In Chapter 6,the simulated annealing algorithm is introduced into the genetic algorithm, simulated annealing algorithm using step sampling strategy, and discusses the mixed strategies in detail.Chapter 7 lists the specific operation results, and the operation result was analyzed and evaluation.Finally, the eighth chapter summarizes the full paper and discuss the development trend of the research of job shop scheduling.
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jxgc/zdh/2980.html
