《2022年遗传算法作业调度优化研究报告.docx》由会员分享，可在线阅读，更多相关《2022年遗传算法作业调度优化研究报告.docx（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用摘 要 在现今的经济全球化制造时代,客户化的产品需求要求更短的产品生命周期；现 代制造业与服务业出现融合的状态；车间作业调度技术是生产治理技术的核心技术,直接关系到企业产品以及服务的质量；有效的车间作业调度技术,可以增强车间资源 优、化配置才能、提高企业的生产效率、削减生产损耗,使企业在经济全球化的竞争 中处于领先位置；现代制造业的生产特点是品种多、批量小 甚至是单件生产 ,而车间资源的有限性制约着能否有效利用车间现有资源完成任务,以最快的速度响应市场需求；调度的 任务是依据生产目标和约束,为每个加工对象确定具体的加工
2、路线、时间、机器和操 作等；优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用；作业车间调度问题是一个典型的NPhard 问题,是最困难的组合优化问题之一；本文主要争论了制造车间作业调度问题；本文系统地介绍了车间作业调度理论及 其进展状况、用于作业车间调度理论的优化算法及其特点；针对生产过程的作业调 度,描述了调度的分类以及常规调度方法；建立了制造车间调度模型；利用染色体编码方法和遗传算子,用遗传算法解决该调度问题；此外,用Matlab 强大的数值运算能力和众多库函数来编写算法,通过仿真实例对算法的求解成效进行了测试；实例证 明,该程序算法结果较好,能充分利用设备资源组织生产
3、,对于车间的实际生产具有 较强的指导意义；关键词：作业调度,遗传算法,MATLAB名师归纳总结 - - - - - - -第 1 页,共 39 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 Job Scheduling OptimizationBased on Genetic AlgorithmABSTRACT In the manufacturing era of economic globalization, demand for our products of customer requires shorter product life cycle. M
4、odern manufacturing and service rendered to the state of integration. The job-shop scheduling technology is the core technology of the production and management technology, is directly related to the quality of enterprise products and services. Effective job shop scheduling techniques can enhance th
5、e workshop resources, optimal allocation of capacity, improve production efficiency, reduce production losses, so that enterprises can locate in the central positionin the competition of economic globalization.The feature ofmodern manufacturing sector is variety, small batch or even a single piece p
6、roduction. The limited resources of the workshop restricting the effective use of existing workshop resources to complete the task to meet market demand in the fastest pace. The scheduling task is to determine the specific processing route, time, machinery and operation according to production goals
7、 and constraints for each processing object. Good scheduling strategy has a great role for the optimal production system, improve economic efficiency. The job shop scheduling problem is a typical NP-hard problem,and is the most difficult combinatorial optimization problems.In this paper, we study ma
8、nufacturing job shop scheduling problem. The paper systematically introduces the job shop scheduling theory and its development, optimization algorithm for job shop scheduling theory and its characteristics； contrary to j ob scheduling of the production process, we describes the classification of sc
9、heduling and conventional scheduling methods； we have established a manufacturing shop scheduling model； we use chromosome coding, genetic operators and genetic algorithm to solve the scheduling problem. In addition, using the Matlab numerical computing power and number of library functions to write
10、 the algorithm to test the effects of algorithm by simulation examples. Examples show that The program algorithm is better, equipment of organizing production resource utilization, The algorithm has a strong guiding significance for the actual production of the workshop.名师归纳总结 - - - - - - -第 2 页,共 3
11、9 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用名师归纳总结 Keywords: Job Scheduling, Genetic Algorithm, MATLAB第 3 页,共 39 页- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 目录1 绪论 1 1.1 课题争论背景及意义 1 1.1.1 问题的提出 1 1.1.2 课题的现实与理论意义 1 1.2 国内外争论现状综述 3 1.3 本文的争论内容 4 2 车间作业调度算法 5 2.1 调度问题特点与分类 5 2.2 车间作业调度问题描述 5 2.3
12、 调度问题优化算法 6 3 求解调度问题的遗传算法 103.1 遗传算法求解调度问题的优越性 10 3.2 遗传算法简介 11 3.2.1 遗传算法概述 11 3.2.2 遗传算法基本过程 12 3.2.3 遗传算法执行策略 15 4 车间作业调度的建模 17 4.1 车间作业调度问题描述 17 4.2 遗传算法设计思想 18 4.2.1 编码 18 4.2.2 生成初始种群 194.2.3 适应度函数 19 4.2.4 挑选算子 19 4.2.5 交叉算子 19 4.2.6 变异算子 19 4.3 遗传算法流程 19名师归纳总结 5 用 Matlab 实现模拟作业调度22第 4 页,共 39
13、 页5.1 程序设计思想及伪代码22- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用 5.2 分析结果的可行性、运行时间以及目标函数值 26 5.2.1 仿真输出结果 26 5.2.2 分析结果 27 6 结论与展望 30 参考文献 32 致谢 34名师归纳总结 - - - - - - -第 5 页,共 39 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用1 绪论1.1 课题争论背景及意义1.1.1 问题的提出随着科学技术、经济全球化和信息技术的迅猛进展,生产企业面临着多变的商业 环境1；现代科学技术的快速进
14、展和客户对产品的个性化需求越来越高,这给传统制 造加工业带来了庞大的挑战和机遇；原先简洁的、局部的、常规的方案和仅凭体会的 治理已经不能满意现代化的要求；当前的机械制造企业采纳多元化、多品种、小批 量、高柔性生产方式来适应猛烈的市场竞争；制造业的经营重心已从企业规模和产品 成本转移到用户需求和上市时间、产品质量、制造成本和售后服务；制造过程中的生 产治理与调度是保证生产质量和生产效率的关键,先进的生产治理与调度技术能够快 速响应顾客需求变化的多样性；为了保证生产的高效稳固运行,以获得最大的经济效 益,企业治理者必需能依据市场上原料供应和产品需求的变化进行经营决策和组织生 产,能利用现有的资源做
15、出最有效的调度方案,使企业生产获得最大的综合经济效 益；21世纪企业的先进制造模式是完全面对顾客,灵敏制造是综合了 JIT的求解目标是寻求某种最 优策略,找到的调度方案能将加工作业支配到车间制造机器上,并且使加工作业能够名师归纳总结 - - - - - - -第 6 页,共 39 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用最高效的完成；每个作业都由一些工序组成,而每个工序就必需由指定的机器加工处 理；一个调度方案就是依据作业内在规律的先后次序条件将全部工序支配到机器上的 一种方案；以前大部分企业主要依靠体会丰富的工人手工支配调度方案,在调度问题比较简 单的情
16、形下仍是可行的；然而,当前的产品的加工工艺复杂度相当高,在调度任务规 模较大且动态多变的环境中,手工调度表现的特别低效甚至无法实现调度；1973年harrington博士提出运算机制造集成制造CIM 的概念, CIM 是一种组织、治理与运行企业生产的新哲理,它借助运算机软件、硬件,综合运用现代治理技术、制造技术、信 息技术、自动化技术、系统工程技术,将企业生产过程中有关人、技术、经营治理三要素及其信息流与物质流有机地集成并优化运行34 ；运算机集成制造系统 CIMS 能给企业带来庞大的综合经济效益,因此国内、外各大中型企业都争论与实施运算机集 成制造系统；作为实施 CIMS工程中的一个重要组成
17、部分,生产方案与调度系统是运算 机集成制造系统功能结构模型中不行缺少的一个层次；当前在自动化程度较高的生产 系统中,使生产过程合理、高效运行的调度问题变得特别复杂,需要建立有效的运算 机调度掌握策略、因此调度问题的争论具有重要的现实意义；由于大量的调度问题是 NP完全问题 13,近几年各种智能运算方法逐步被引入到调度问题中,如遗传算法、模 拟退火算法等,但是目前尚无有效的求解策略,因此调度问题的争论也具有重要的理 论意义 5；车间作业调度是一个交叉的争论领域,以数学为基础,涉及运筹学、运算机、控 制工程和工业设计等多门学科；具体就是针对一项可分析的工作 如产品制造）,探讨 尽可能满意约束条件
18、如交货期、工艺路线、资源情形）的前提下,通过下达生产指 令,支配其组成部分 操作哪些资源）、其加工时间及加工的先后次序,以达到合理利用产品制造资源,获得产品制造时间和成本的最优化14,提高企业经济效益的目的；制造系统生产治理的核心就是车间生产调度,生产治理任务顺当实施与完成,最终要 靠合理的生产调度来保证；它争论的是如何合理地配置加工过程的各种资源,削减零 件在加工过程中的各种铺张,从而提高设备利用率和生产率,降低生产成本；因此,合理的生产调度是生产系统的高效运行的前提,生产调度可以保证 :生产方案的有效实 施；高效低耗地使用生产资源；均衡生产,削减在制品的资金占用；缩短产品生产周 期、确保产
19、品交货期、降低生产成本,以适应多变的市场需求；生产调度对企业来说名师归纳总结 - - - - - - -第 7 页,共 39 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用是至关重要的,在品种多、中小批量生产环境下的主生产调度问题更加复杂和重要12；1.2 国内外争论现状综述车间作业调度问题是一个经典而又传统的问题,对于它的争论始于 20世纪50年代；1954年, Johnson对两台机床 Flow-Shop型调度问题进行了争论后,提出明白决车间调度部分特殊问题的优化算法,代表理论争论的开头；60-70岁月都是利用混合或纯整数规划、动态规划和分枝定界法解决一些有
20、代表性的问题,并开头重视调度复杂性的 争论；由于车间调度问题的复杂性,各种不同的具体问题往往有不同的解决方法；大量 的争论促使车间调度领域取得了丰硕的成果,产生了很多重要的调度方法；随着 70年 代后期调度理论争论的深化及各种交叉学科的进展,又涌现出了很多新的车间调度理 6、基于掌握的方法、基于 DEDS离散大事动 论与方法,如：基于运筹学 的概念, Koza成功地将他提出的遗传编程方法应用到了 人工智能、机器学习、符号处理等方面,进一步证明白遗传算法在解决 NP问题方面的 有效性 11；国内对于车间调度问题的争论起步比较晚,基本上是靠调度人员的体会进行车间 作业安排和调度；随着遗传算法在作业
21、调度方面的应用,国内也掀起了一股应用遗传算法争论车间作业调度问题的热潮；目前,争论工作主要集中在清华高校等CIMSComputer Integrated Manufacturing System国家重点试验室,这些试验室的系统名师归纳总结 - - - - - - -第 8 页,共 39 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用开发基本上仍处于试用阶段,距离开发出成熟的软件系统仍有很长一段距离,因此仍 需要投入大量的人力物力进行该方面的争论；1.3 本文的争论内容本文针对先进制造环境下车间治理与调度的特点,分析了车间作业调度的特点,给出了遗传算法求解车间作业
22、调度的过程；通过争论与分析车间作业调度系统,给出了调度的数学模型,运用Matlab 遗传算法工具箱进行了仿真调度,并分析了结果；本文主要分五章,具体支配如下：第一章说明白课题的提出背景和争论意义,争论了车间调度的国内外争论现状,最终给出了本文的争论内容和文章的结构支配；其次章具体阐述了车间作业调度问题,分析了调度模型及模型描述,总结了车间 调度的求解方法；第三章简要说明白遗传算法的产生、进展、特点及操作流程；重点争论了遗传算 法在车间作业调度优化中的操作过程,包括了编码方式、种群大小、交叉方式与概 率、变异方法与概率等参数的挑选；第四章将实际的车间作业问题抽象成数学模型,并且设计遗传算法的基本
23、算子以 及操作；第五章运用 Matlab遗传算法工具箱,通过编码实现模拟作业调度；并且分析结果 的可行性,运行时间以及目标值；名师归纳总结 - - - - - - -第 9 页,共 39 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用2 车间作业调度算法2.1 调度问题特点与分类调度问题的主要特点有 : 1建模、运算复杂性；车间中工件、机器、操作人员和搬运系统之间相互影 响、相互制约；每个工件又要考虑它的加工时间、安装时间和操作次序等因素,因而 相当复杂,调度问题往往是通过等式或不等式等约束条件来运算的,属于典型的 NP-hard问题；随着问题规模的加大,运算量
24、也急剧加工,所以调度问题往往没有精确的 解,通常是在解答过程中寻求其最优解；在现有运算条件下,一般优化方法对于车间 调度问题是低效甚至是无能为力的；2动态随机性调度中存在很多随机性和不确定性；如机器故障、作业交货期的 变更,如工件到达时间的不确定性,实际工件的加工时间也有肯定的随机性；如机器 故障、紧急任务插入、作业交货期的变更等一些突发大事也增加了调度的难度和随机 性；3多约束性调度中受到很多约束条件的限制；车间的生产才能不仅会受到机床 的制约,仍会受到工人和帮助工具的制约,各道工序的先后关系不能颠倒,如缓存容 量、资源数量、工件到期时间与操作次序等也是制约因素；此外,仍有人为的附加因 素,
25、如机器负荷平稳等等约束条件；4多目标性调度的目标很多,目标之间往往又相互冲突；如基于作业交货期的 目标、基于作业完成时间的目标、基于生产成本的目标等；依据不同的分类标准,可分为6 种类型 :l 开环车间和闭环车间；2单台处理机、多台并行机、 Jobshop 和 Flowshop；3基于调度费用和调度性能的指标；4确定性调度、随机性调度；5静态调度、动态事实调度；6 有序加工,无序加工；现代车间调度类型往往是2.2 车间作业调度问题描述Job-shop、Flow-shop 型；一般车间调度问题可以描述为:n 个工件在 m 台机器上加工,每个工件分为k 道工序,每道工序可在不同的机器上加工；每一台
26、机器在每个时间只能加工某个工件的名师归纳总结 - - - - - - -第 10 页,共 39 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用某道工序,只能在上道工序加工完成才能开头下一道工序的加工,前者称为占用约束,后者称为次序约束；调度的结果就是确定决策方案,决策内容包括安排决策 工件的加工次序 和时间决策 工件各工序的加工时间 备的安排 ；以及路径决策 工件工序的加工设生产车间显现调度问题主要缘由是生产资源受到了制约；车间调度的问题是多个 工件在有限的机器上加工,每台机器在切换不同的工件加工时又需要肯定的生产加工 预备时间；切换加工的次数越多越有利于削减工
27、件的库存,但导致生产率的下降；如 果车间有足够多的机床设备和其它生产资源安排给每个工件或每条工艺加工路线,那 么一切都会井然有序,也就不存在调度问题；但是,对于企业主来说,这样必定会造 成资源铺张和制造成本的增加,于是显现了工件和相应的工序数量多于生产资源的情 况,也就显现了车间调度问题；因此,需要在库存成本与切换加工次数频率之间寻求 一个动态的平稳；生产的柔性表达在设备的使用和设备的支配两个方面,设备使用的 柔性是指设备可用于多个零件的多道工序加工,设备支配的柔性是指工件的设备加工 路径,而不是固定或预先确定的；具有可选的路径,可以通过将如干设备组作为一条 或者多条生产线加工一种工件,使得该
28、工件的生产率最大；典型的车间调度问题包括一个要完成的作业集工件集 ,每个作业由一个操作集工序集 组成,各操作的加工需要生产资源机器、人员、刀具和帮助资源,并且必须按一些可行的工艺次序进行加工；车间调度就是对一个可用的加工机床集在时间和 空间上进行加工任务集安排,以达到生产性能指标最优化；每台机床可加工工件的如 干操作,并且在不同的机床上能加工的操作集可以不同；调度的目标是将作业合理地 支配到各机床以及合理地使用其它生产资源,并合理支配作业的加工次序和加工时 间,使约束条件被满意,同时优化其中的一些生产性能指标；2.3 调度问题优化算法目前的车间调度问题的算法争论有很多,归纳起来主要有 : 1）
29、确定性最优化方法 该方法主要通过对车间调度问题建立一个数学模型,采纳基于枚举思想的分枝定 界或动态规划法进行求解,分枝定界法有很多,其主要不同点在于分枝规章、定界机 制和上界的产生等三个方面的差异；这类方法从理论上来说是能求得最优解,但通常名师归纳总结 - - - - - - -第 11 页,共 39 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用由于运算复杂性缘由,不能获得真正的有用；采纳数学规划的方法,表达清楚,易于在运算机上求解,但生产环境具有很多不 确定的因素,存在建模不确定性和求解空间太大,造成运算困难,特殊是不能反映特 定调度领域的自然结构,所以很难
30、应用体会学问去处理调度问题；采纳数学规划的方 法大致可以分为三类：简洁规章、复合规章、启示式规章；,其本质是给每一个生产任务和操作,并赐予优先级,优先级高的生产任务和操作优先考虑；这类方 法因调度规章易于实现,运算复杂度低,能够用于动态实时调度系统中,很多年来一 直受到广泛关注和争论,并不断涌现很多新的调度规章；如作业的平均等待时间、机 床的平均利用率、作业总加工时间等；,依据系统当时所处的属性转台,打算实行何种规章 策略 ,确定或挑选活动发生的次序和时间,即所谓的状态指导的智能调度方法；缺乏理论意义； b应用仿真进行生产调度的费用很高；判定和技巧的限制；仿真的精确性很大程度受编程人员的现实中
31、的制造系统往往是离散大事系统,因此可以用争论离散大事系统解读模型名师归纳总结 和方法探讨车间调度问题,诸如排队论、极大微小代数模型、Petri 网等,；比如,第 12 页,共 39 页- - - - - - -精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用Petri 网作为一种图形建模工具可以形象地表示和分析FMS节点语义的单义性,使得所携带的系统信息量不够丰富； 2重用性差； Petri 网是基于 FMS 中作业的加工流程建模,当作业需求或工艺略微变动,必需改模型结构；很难对高级的调度规章建模；在人工智能中启示式图搜寻法是图搜寻的重要策略之一,在启示式图搜寻法中
32、最引人注目的 A* 算法,在图搜寻过程中A* 算法能够通过挑选合适的评判函数查找达到目标结点的正确路径；在调度问题的离散图模型基础上,启示式图搜寻法在调度领域 得到应用；对于表述为整数规划的调度问题,最初采纳分枝界定法,而后其他的启示 式图搜寻法也被应用于解决调度问题；该方法主要需要解决搜寻效率和降低内存使用 问题,对大规模的问题需进一步探讨；7）模拟退火 模拟退火法 最优解；模拟退火法的改进算法有加温退火法、记忆退火法；模拟退火法可以用于具有最小MakesPan 指标的 FlowShop 排序问题；由于模拟退火法能以肯定的概率接受差的能量值,因而有可能跳出局部微小,但它的收敛速 度较慢,很难
33、用于实时动态调度环境；8）禁忌搜寻法 对于复杂的组合优化问题,禁忌搜寻也是一种通过领域搜寻以猎取最优解的方法,Gfover 首次表达了它的基本原理；该方法已经用于解决 是一种模拟人脑神经系统的结构和功能,运用大量的处理部件,经广泛互连而组成的网络系统；搜寻网络Hopfield）模型可以求解各种有约束的优化问题,随机 Hopfield 也可以用于解决 job-shop的调度问题；放松算法LR 算法由于其在可行的时间里能对复杂的规划问题供应较好的次优解,并能对解的次优性进行定量评估,近年来已成为解决复杂生产调度问题的一种重要方法；但名师归纳总结 - - - - - - -第 13 页,共 39 页
34、精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用同时 LR 算法的对偶问题存在搜寻效率低,可行调度的构造有待于进一步争论等问 题；由于调度问题的复杂性,其争论策略主要形成了以下几种：分解与成组策略：利用分解生产方案或 GT 的调度策略可以大大降低问题的运算复杂性和规模,求得调 度问题的较优解,同时优化系统的一些性能指标；实时或动态重调度策略：车间制 造过程的随机性、不确定性需要不断地进行重调度,以处理突发的大事；基于目前的争论,对于动态调度的具体策略有:周期调度,连续调度,大事驱动调度,周期与事件驱动混合调度,周期与连续调度混合的策略等；生产方案与调度集成策略：生产
35、 方案、调度的集成争论具有全局优化的特点,也符合先进制造模式的思想；多目标 权衡调度策略：实际调度问题往往是多目标的,而这些目标往往相互冲突；对此类多 目标优化问题,常用数学规划中的约束法、评判函数法、分层序列法、功效函数法 等；随着各种特殊调度问题的攻克和新方法、新设备的显现,作业车间调度争论正在 向 动 态 、 敏 捷 、 多 重 入 、 多 资 源 、 智 能 化 的 方 向 发 展 ；名师归纳总结 - - - - - - -第 14 页,共 39 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用3 求解调度问题的遗传算法3.1 遗传算法求解调度问题的优越性
36、遗传算法 搜寻过程不直接作用在变量上,而是在参数集进行了编码的个体；2搜寻过程是从一组解迭代到另一组解,采纳同时处理群体中多个个体的方 法,降低了陷入局部最优解的可能性,并易于并行化；这使的遗传算法能以较少的计名师归纳总结 - - - - - - -第 15 页,共 39 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用算获得较大的收益；3遗传算法属于一种自适应概率搜寻技术,其挑选、交叉、变异等运算都是以 一种概率的方式来进行的,从而增加了其搜寻过程的敏捷性；采纳概率的变迁规章来 指导搜寻方向,而不采纳确定性搜寻规章；4对搜寻空间没有任何特殊要求如连通性、凸性等,
37、只利用适应性信息,不需要导数等其他帮助信息,适应范畴更广；遗传算法的自组织、自适应和自学习性 智能性 打算遗传算法可求解复杂问题；5黑箱式结构；应用遗传算法时,依据具体问题的特性,进行编码与适应度设 计之后,其余操作按常规算子自动运行即可,只等最终输出最优解个体,而不必关怀 求解的实际过程,所以遗传算法特别便于处理那些输入输出之间因果关系复杂的问 题；基于遗传算法以上的特点,本文选用遗传算法作为求解优化问题的有效方法；3.2 遗传算法简介3.2.1 遗传算法概述遗传算法是基于自然挑选,在运算机上模拟生物进化机制的寻优搜寻算法；由于 遗传算法是自然遗传学与运算机科学相互结合渗透的产物,因此在遗传算法中借用了 很多自然进化的概念；这些概念如下所示：1. 串String）：串是个体 Individual ）的形式,在算法中为字符串,并且对应于 遗传学中的染色体 Chromosome）；2. 群体Population）：肯定数量的个体组成了群体,或叫种群；串是群体中的元 素；3. 群体规模 Population Size）：群体中个体的数目成为群体个数,也称为群体规 模或群体大小；4. 基因 Gene）：基因是串中的元素,基因用于表示个体的特点；例如,有一个串 S = 1001,就其中的元素 Alleles）；1,0, 0, 1 分别称为基因；它们的