应用遗传算法求解车间作业调度问题

1、应用遗传算法求解车间作业调度问题  目    录摘要.1前言.21遗传算法的简介.3 1.1遗传算法的原理.3 1.2遗传算法的设计.42 turbo c的特点及简介.5 2.1  c 语言的产生与发展.5 2.2  c 语言的特点.5 2.3  turbo c 概述.53 jssp问题的描述及简单分析.7 3.1  jssp的数学模型及其参变量. .74基于遗传算法的车间作业调度的实现技术.9 4.1  jssp的遗传算法应用及处理.

2、9 4.2  jssp的遗传算法的实现.115 适用于车间作业调度的遗传算法描述.16 5.1  总体算法的描述.16 5.2仿真实验及结果.16结论.19参考文献.20致谢词.21附录.22应用遗传算法解决车间作业调度问题摘要车间调度问题简单来说就是设备资源优化配置问题。近年来遗传算法得到了很大的发展，应用遗传算法来解决车间调度问题早有研究。本文在已有算法基础上详细讨论了染色体编码方法并对其进行了改进。最后根据改进的编码进行遗传算法的设计，本文提出了1种求解车间作业调度问题的改进的遗传算法，并给出仿真算例表明了该算法的有效性。关键词：车间作业

3、调度;遗传算法;改进遗传算法染色体编码genetic algorithms for job shop scheduling problemabstractsimply speaking, the job shop scheduling problem is the equipment resources optimization question. in recent years, the genetic algorithms obtained great development, it was used to solve the job shop scheduling problem ear

4、ly. this paper discusses the chromosome code method in detail based on the genetic algorithms and make the improvement on it. in the end, according to the code which improved carries on the genetic algorithms design, this paper offer one improved genetic algorithms about soloving to the job shop sch

5、eduling problem, and the simulated example has indicated that this algorithm is valid.key  words: job shop scheduling ;genetic algorithms ; improvement genetic algorithms chromosome  code前言随着社会不断向前发展，竞争的加剧，制造业中普遍面临的许多问题不断地突现出来。如何在有限的生产资料条件下，以最短的生产周期、最小的成本将产品制造出来以满足客户的需求是每1个制造商不断追求的目标。如何运用有

6、限的资源，降低产品的生产成本，缩短产品的制造周期，保证按时交货，提高企业信誉，赢得更多的客户，成为制造厂商在竞争中生存的1个重要的条件。有效的利用现有的资源，合理的制定企业和车间生产计划，是达到这个目标的关键。由于车间调度问题不仅是1个典型的np难题，也是至今为止所有组合优化问题中最难问题之1，所以得到了广泛的关注。早在20世纪50年代早期就有很多关于调度问题的研究文献。在计算机出现以前，作业车间调度问题(job shop scheduling  problem，简称为jssp或jss问题)是用手工计算完成的。但是由于问题本身复杂、计算量大，手工操作可靠性差、调度方案优化性能不好，跟

7、不上产品的多变性要求又容易受随机因素的干扰，使资源和生产能力得不到充分的发挥和利用，生产车间效率不高。即使随着计算机的出现和发展，调度问题也没有得到很好的解决，因为问题的规模和实时性要求也在不断提高。通常用于求解jssp的技术与方法主要分为两类，1类是近似求解方法，1类是最优化求解方法。用近似方法求解时，可以很快地得到问题的解，但它们不能保证所得到的解是最优的；用最优化方法求解这1问题时，它们可以得到全局最优解，但它们只能解决小规模的，而且速度很慢。鉴于jssp在实际应用中的重要地位，论文的具体安排如下:第1：本文将对车间作业调度问题的基本概念、数学模型、表示方法及其基本理论进行阐述。在深入对

8、问题进行剖析的基础上，借鉴自然进化思想机理，对jssp的求解问题进行探索性研究。旨在为求解jssp问题提供新的解决思路。而本文主要的研究重点放在基本遗传算法，求解jssp的研究上的编码问题。同时给出以最小化生产周期(minimum makespan)为目标函数的问题jssp模型，并还给出了关于问题的复杂性描述。 第2：对遗传算法在jssp应用中的编码问题、解码问题以及jssp的遗传算子设计进行了深入的分析，参照了西安电子科技大学姜迪刚，叶尚辉共同编写的论文基于遗传算法的车间调度作业，针对1个生产周期最小化的优化目标进行实现。 最后，对本文进行了总结并对以后的研究工作给出了1些建议和展望。1遗传

9、算法的简介1.1  遗传算法原理遗传算法(genetic algorithms) 是1种大致基于进化论优胜劣汰、适者生存的物种遗传思想的搜索算法。通过变异和重组当前1致的最好假设来生成后续的假设，每1步，更新被称为当前群体的1组假设，方法是通过使用目前适应度最高的假设的后代替代群体的某个部分。遗传算法的普及主要考虑以下因素:(1) 在生物系统中，进化被认为是1种成功的自适应方法，且具有更好的健壮性；(2) 遗传算法搜索的假设空间中，假设的各个部分相互作用，每1部分对总的假设适应度的影响难以建模； (3) 遗传算法易于并行化。遗传算法的不同实现在细节上有所不同，但他们都具有以下的共同结构:算法迭代更新1个假设池，这个假设池称为群体。在每1次迭代中