（机械制造及其自动化专业论文）不确定环境下车间调度算法研究.pdf

武汉科技大学硕士学位论文 第1 页 摘要 随着工业技术的进步和全球化市场经济的发展，对制造企业的生产管理提出了更高的 要求，尤其是生产管理中的核心技术车间调度。然而以往对车间调度问题的研究多是 集中在确定性车间调度问题上，难以准确描述实际生产中出现的各类随机因素。针对生产 中往往存在着的各种不确定性因素，对求解不确定环境下车间调度问题的算法进行分析和 设计。 对车间调度问题进行数学建模分析，分析模型的建模方法、输入与输出数据、模型优 化目标，并对常用的智能求解方法进行分析和比较。 研究了基本遗传算法，在考虑到遗传算法的优缺点的条件下，设计出了一种能较快收 敛并能收敛于全局最优解的改进的遗传算法：采取精英个体保留和交叉，按群体适应度值 的分布调整交叉和变异概率，加快算法的收敛速度，同时避免陷入局部最优解。 针对不确定环境下车间调度问题，建立了基于模糊数学规划理论的不确定作业车间调 度模型，不确定加工时间用三角模糊数来表示，不确定交货期用梯形模糊数来表示，以最 大化产品平均客户满意度为优化目标，运用基于模糊数学的改进的遗传算法来求解这类问 题，并通过m a t l a b 进行仿真实验，达到求解不确定环境下车间调度问题的目的。 关键词：车间调度；模糊加工时间；模糊交货期；遗传算法 第1 i 页 武汉科技大学硕士学位论文 a b s t r a c t w i t l l 也ed e v e l o p m e n to fi i l d u s t r i a lt e c l l l l o l o g ya 1 1 d 酉o b a l i z e dm a r k e te c o n o m y ；t 1 1 ed e m a n d s f o rp r o d u c t i o ni i m a g e m e n to fm 锄脚k 舰血ge n t e 印r i s e sb e c o m e1 1 i 曲e r ，e s p e c i a l l ym ec o r e t e c h n o l o g ) ri i lp r o d u c t i o n 眦l a g e m e 时- j o bs h o ps c h e d u l i i l g p r e v i o u s 咖d i e so nj o bs h 叩 s c h e 眦崦p r o b l e ma r em 0 s u yc o n c e n 仃a t c d i 1 1 也cd e t e m i i l i s t i cj o bs h 叩s c h e d u l i n g p r o b l e m ，w m c hc a n n o ta c c u r a t e l yd e s c r i b et 1 1 er a n d o m f a c t o r si i lm ea c t u a lp r o d u c t i o n a c c o r d i n g t 0m eu n c e 吨l i l lf - a c t o r si i lp r o d u c t i o n ，m ep 印e r 嘶l d i e st l l ea l g o r i t l l mt os o l v et l l ej o b s h o p s c h e d u l i i l gp r o b l e m su n d e ru n c e r t 血e n v i r o m n e n t t 1 1 i sp a p e rs 叫i e sm a m e m a t i c a lm o d e l i l l go f 也ej o bs h o ps c h e d u l i n gp r o b l e m ，a 1 1 a l y s e st h e m o d e l i r 培m e m o do fm ep r o b l e m ，t l ：l em p u t 锄do u 勺? u td a t a ，n l e0 p t i l i l i z a t i o no 场e c t i v ea 1 1 d t l l e c o n m o i l l yu s e do p 缸z a ：t i o na l g o r i t h sm e t h o do f 吐l em o ( 1 e l t 1 1 i sa n i c l ea l s os t u d j e st 1 1 eb a s i cg e n e t i c 舢g o r i 也m ，a n dd e s i 印s ai r n p r 0 v e dg e n e t i c a k o 甜吼w h i c hc a i lc o n v e r g et o 位g l o b a lo p t i l a ls o o nq u i c y ，讹1 ec o n s i d e 血gm e a d v 锄t a g e sa n dd i s a d v a n t a g e so ft h eb a s i c ( 论n e t i c 灿g o m m ei i n p r o v e da l g o r i 岫，t a l 【et l l e e l i t e 砌i v i d u a j st or e t a l i i la n dc r o s s g r o u p6 恤e s sv a l u ed i s t r i b u t i o na d j u s 缸n e n to fc r o s s o v e ra i l d m l l t a t i o np r o b a b i l i 吼 aj o bs h o ps c h e d l l l ep r o b i e mm o d e lb 舞e do nm z z ym a m e m a t i c sm e o r yi sp r e s e n t e di n o r d e rt 0d e a l 诵也n l ei o b s h o ps c h e d u l i n gu 1 1 d e r u 1 1 c e r t a i ne n v i r o n m e n t t h eu 1 1 c e r t a i n p r o c e s s i n g 缸l ei sr e p r e s e n t e db yt r i a n g l e 舵z yn u m e r a l s t h eu 1 1 c e n a i nd u ed a t ei sr e p r e s e n t e d b yt r a p e z o i d a lf u z z ym m l e r a l s t h eo p t i m i z a t i o nt a 唱e ti s t om a x i i i m mt l l ea v e r a g ec u s t o m e r s a t i s 觚i o no f 也ep r o d u c t s ah r l p r o v e dg e 球嫩ca l g o r i t h i i l b a s e do n 如z z ym a t l l e m a t i c si s p r o p o s e dt os o l v em e 吼c e r t a i nj o b s h o ps c h e d l l l i n gp r o b l e m s s h r m l a t i o ne x p e r i m e n t sw h j c h u s e m a t l a ba r ec a r r i e do nt op r o v e 廿1 ee 虢c t i v e n e s sa | l ds t a l ) i l 埘o fm ea l g o r i t h ma n d a c l l i e v et l l e p u 坤o s eo fs o l v i i l gm ej o b s h o ps c h e d u l i n gp r o b l e m u n d e ru i l c e n a i ne n v i r o r 吼e n t k e yw o r d s ：j o b s h o ps c h e 眦i i l g ；舵z ) rp r o c e s s 啦缸e ；如z z ) r d u cd a t e ；g e n e t i c 触g o r i l i i l 武汉科技大学硕士学位论文 第1 页 1 1 选题背景及意义 第一章绪论 随着当前科技进步和经济建设的飞速发展，市场竞争全球化的趋势日益明显，企业间 的国际化竞争更加激烈。人们对商品的需求更加多样化，从而导致企业产品更新速度更快， 生产系统越来越复杂化，大规模化。对企业的生产过程的管理与监控也提出了更高的要求， 传统的凭经验决定的简单的、局部的的生产管理方法已经无法满足现代企业复杂生产的要 求。在满足企业设备要求和产品工艺过程的前提下，合理地根据市场要求以及企业资源现 状安排生产过程的生产调度成为了时下研究的热点。 生产调度，即是对企业生产制造活动的一个预先安排和计划，是整个生产制造体系的 一个重要组成部分，也是先进生产制造系统实现自动化生产的核心。有效地改善企业的生 产调度水平，能确保企业生产制造活动的高效稳定地运行，并提高实际的生产效率和对生 产资源充分利用，以获得最大的经济效益，进而能增强生产企业在整个市场经济中的竞争 能力n 1 。 传统的生产调度系统大都是针对生产调度数据均为确定的精确数据的理想情况实施 的，仅仅把作为一个数学问题来看待。众所周知，生产系统是一个包含了各类生产要素的 综合大系统晗1 ，系统中有着各类的不确定性因素，如果不考虑这些生产中的不确定性因素， 在对生产制造系统进行确定性建模时就需要进行大量的假定操作，可想而知在运用大量不 准确的确定性生产数据上运用优化算法取得的优化结果( 即最优调度策略) ，在作用于实 际车间生产中时和实际情况常会有偏差，在偏差太大时则会导致调度策略的无法运行而失 败。为使生产调度系统得出的调度方案能更加接近生产的实际情况，在制定生产计划和调 度算法时就必须要结合实际生产情况，尤其是要充分考虑那些实际生产过程中有可能的那 些不确定性因素。只有这样，才能使生产调度系统在实际生产中发挥有效的作用，从而使 企业能够完成预定的生产任务，提高生产效率，在激烈的市场竞争中求得生存和发展。因 此，在企业调度过程中充分考虑车间生产中的各类不确定性因素，研究在不确定环境下的 作业车间调度问题具有很大的理论意义和实际应用价值。随着模糊数学和运筹学以及控制 理论的快速发展和应用，将在不确定条件下的车间调度中各种不确定性因素用模糊数学的 方法来进行处理，把不确定条件下的作业车间调度问题转化为模糊调度问题能更加贴近于 生产的实际情况。 作为一种当前在各个领域应用非常广泛的智能优化算法，遗传算法( g e n e t i c 硝g o r i t i l r n ， g a ) 以其优良的计算性能和对具体问题的普遍适应性以及显著的应用效果等特点受到了学 者们的高度关注3 。为更好对不确定环境下的车间调度问题进行建模与优化，本课题主要 研究将遗传算及其改进的算法法应用于车间调度问题中进行求解。 第2 页武汉科技大学硕士学位论文 1 2 车间调度问题的研究概况 车间调度是根据时间来安排当前可用资源以完成制定的加工任务。目前，车间调度是 在企业先进制造系统研究中的一个关键部分，是企业合理地安排生产任务以达到生产目标 的前提条件，也是在理论研究中典型的最困难的问题之一，又大多数的调度问题都有相当 高的计算复杂性，属于n p 难题。目前，关于求解车间调度问题的优化算法的研究已经受 到了学术界极大的重视，经过学者们近些年的不断的实际研究，对特定的典型调度问题已 取得了相当大的进步，但还不是非常成熟。 对于调度问题的研究最早开始于上世纪5 0 年代，s m j o l l l l s o n 【4 】在1 9 5 4 年提出了能够 求解i 以f c m 毅和部分n 3 f c m 舣问题的优化算法，这也代表着经典调度理论的产生。直到 5 0 年代末期，调度理论研究提出了针对某些规模较小的单机和简单的流水线生产车间的调 度问题的调度算法，其研究的范围较窄，却逐渐成为了经典调度理论的基础。在6 0 年代， 关于调度的理论研究多集中于纯整数或混合整数规划、动态规划以及分枝定界法等运筹学 的方法来解决一些有代表性的问题，同时也有些人开始用启发式算法来尝试解决一些调度 问题，如g a v e t t 瞄1 ，这也标志了经典调度理论体系的初步形成。在7 0 年代，在经典调度体 系形成后，人们开始关注对调度算法复杂性的分析与研究，期间多数的调度问题被证明是 n p 难问题或是n p 完全问题，因此难以用经典的运筹学的方法来解决。对于调度问题的研 究开始倾向于启发式算法，如p a n 、a 】k a r 嘲总结归纳了1 1 3 条调度规则，并对其进行了分类。 在八十年代以及以后的几十年里，随着计算机科学、生物科学、机械科学、管理科学的飞 速发展，以及它们之间的学科的交叉和渗透，众多夸学科的新方法被应用到调度领域中来。 出现了很多新的人工智能算法，如神经网络算法、模拟退火算法、遗传算法、禁忌搜索算 法等。 目前，从国内外的关于在调度领域中取得的研究成果来看，最早的经典调度理论仍然 是当前在调度领域中使用的智能调度优化算法理论的基础。各类智能算法被尝试用来解决 调度问题，智能调度已成为当前研究的主流，在某些具体的调度问题中，基于人工智能调 度算法取得了非常好的效果。但有些调度算法只是局限于求解一类经典的调度难题，必须 要能够作用于实际生产中才能证明算法的科学性和有效性。针对具体的大规模的复杂的生 产制造系统，主要是将某类或某几类智能优化算法加以改进或结合，充分与生产实际相结 合。以使其有用于实际生产过程中。因此，将调度理论应用在实际调度问题中，优化企业 的生产制造过程，并发挥良好的作用成为了当前研究人员研究的重点和方向。 1 3 不确定环境下车间调度问题研究概况 遗传算法是一种模拟自然界生物进化的高度随机、并行的搜索算法，非常适用于求解 一些传统优化算法难以求解的优化问题，近年来被广泛应用于车间调度领域中，在求解某 些较为简单的调度问题时取得了良好的效果。在将其应用不确定环境下的车间调度问题中 时，由于遗传算法自身的全局搜索能力较差，搜索精度不够高，易陷入局部极小解、对参 武汉科技大学硕士学位论文第3 页 数有一定依赖性等缺陷，所求解的结果难以让人接受。 针对较为复杂不确定环境下的车间车间调度问题，简单遗传算法往往难以取得较好的 效果，国内外众多学者提出了许多对遗传算法进行改进的算法以解决不确定性车间调度问 题，主要集中在对算法的不确定性因素的数学表示，遗传算法的种群大小或数量、编码方 式、交叉和变异算子、种群个体选择方法等领域进行优化口。1 引，在遗传算法中引进粒子群 算法、神经网络、模拟退火算法等其他智能算法来进行改进以解决不同的实际问题，也取 得了一定的效果。 o m a r 采用三角模糊数表示不确定环境下的车间调度问题中的多目标优化问题【7 】；m * 吨研究了不同模糊交货期下的多目标作业车间调度问题 8 】：m a s a t o s l l i 和r y o 提出了一种用 三角模糊数描述完工时间，梯形模糊数描述交货期的多目标作业车间调度问题，考虑三个 优化目标的算法，并对三角模糊数、梯形模糊数的取和取大和比较提出了一种准则；k a c e m 和s l 硫等作业车间调度问题，其模糊逻辑主要运用在对多个目标的优化判断和选择上【9 】； d o b r i l a 和m e j a n d r a 等采用决策支持的方法研究了具有模糊时间的多目标作业车间调度问 题【l o j ：l i 和z h u 等考虑了具有模糊加工时间，模糊交货期，可选机器的作业车间调度问题 并对多个优化目标进行了讨论，提出了一种可行的算法并用一个简单的实例进行了验证。 l e i 用三角模糊数描述完工时间，梯形模糊数描述交货期的多目标作业车间调度问题采用粒 子群优化算法进行了研究，提出了一种新的优化算法，并对其可行性进行了验证【1 1 】。 国内方面，王书锋，梁燕等对在车间调度中的不确定因素，采用模糊遗传算法进行求 解，并设计了新的算法的交叉方法 1 射；王成尧，高麟等对车间调度中的不确定加工时间， 分析了模糊加工时间的录属度函数，研究了加工时间不确定条件下的单机调度模型n 引；顾 幸生对车间调度中的不确定性因素进行了分类和数学描述，也提出了求解不确定环境下的 车间调度问题的调度方法n 制；耿兆强，邹益仁对于不确定环境下的车间调度问题，创建了 两种调度模型，并应用遗传算法来进行求解n 引；徐震浩，顾幸生针对不确定环境下的流水 车间调度问题，运用模糊规划理论，创建了调度模型，设计了解决调度模型的免疫算法来 进行求解n 剐；张国军，李婵娟对车间调度中的不确定性因素，运用随机变量来表示，建立 了不确定性调度模型，分析了求解算法n7 | ；吴会江研究了一种具有模糊交货期的最小化全 部满意度的单机调度问题，并利用动态规划状态空间松弛来求解n 引；卢冰原，陈华平等针 对不确定环境下的车间调度问题，将模糊数学的思想运用其中，并设计了一种新的交叉操 作，运用遗传算法来进行求解n 9 1 。 可以看到，正是由于遗传算法具有搜索精度不够高、易陷入过早收敛、对算法的控制 参数有一定的依赖性等缺陷，难以将其直接应用于生产实践中。因而将基本遗传算法进行 算法改进以解决车间调度问题中成为时下研究的热点，其主要集中在对适应度函数、遗传 算子、染色体的编码与解码，种群的的数量和初始化以及种群更新迭代算法中对遗传算法 进行改进。 第4 页武汉科技大学硕士学位论文 1 4 调度问题的研究方法 自从调度问题被提出以来，通过近几十年对于解决生产调度问题的各类调度算法的研 究，国内外学者提出了许多调度方法，总体而论，可将目前所使用的调度方法归纳为优化 方法和启发式方法两大类。 优化方法指运用运筹学的理论来进行数学建模，然后通过对模型进行精确求解，获得 最优解，是从全局的角度出发，在实际生产中的所有的生产机器、生产任务、生产时间之 内进行全局搜索来获得最优的调度结果，该调度方法是以传统的数学规划的方法为基础。 虽然目前对数学规划方法的理论和实际研究较别的调度算法更为成熟，但是只是对规模较 小的调度优化问题能取得较满意的结果，而难以对于较大规模的组织复杂的生产调度问题 进行求解，当加工设备，生产任务以及生产时间的增大时，优化方法的数学解析模型的规 模会急剧增大，从而导致求最优解成为了全m 难题，对调度模型的求解主要运用如下以下 两种方法： ( 1 ) 分支定界法 分支定界法动态地构造出一棵树，此树即是代表着待求解的调度问题的所有的可行 解，在算法的运行中采用广度优先或最小耗费优先的方法对解的空间树进行搜索，直到找 到调度问题的最优解，即最优的调度策略，分支定界法在应用中对上下界的确定非常敏感， 且只适合于求解规模较小的的调度优化问题，这种方法虽然在理论上能保证算法能求得问 题的最优解，但由于具体调度问题的计算的复杂性，难以应用于实际生产中。 ( 2 ) 动态规划算法 动态规划算法主要思想是瞳0 1 ：首先将问题进行分解，划分为一定数量的子问题；对划 分出的子问题进行求解操作，最后在划分出的一定数量的子问题的解上推理出主要问题的 最优解。在应用于车间调度的问题中时，与分支定界法一样，也会在问题的解空间的剧烈 膨胀时无法找到问题的解。 启发式调度方法；该方法以启发推理为基础，根据决策点时刻的设备，任务的所处于 的实际状况来进行调度，从而保证了取得的解是调度问题局部最优解，但却难以保证能取 得全局最优解。该方法主要包括： ( 1 ) 基于规则调度方法 基于规则调度方法是由事先确定的一定的规则确定下一步骤的优化方法，它有简单实 用、直观等优点，且在应用中所需的求解时间较短，也教容易实现，是一类动态调度的典 型代表，在实际的生产过程中被广泛地应用。产生式规则是由在企业生产中的经验丰富的 技术人员和管理人员经过生产的积累总结出来的行之有效的调度法则，其中包含了技术人 员和管理人员的各类技术和管理方面的专业知识，反映了生产过程以往的经验，因而，能 够较好地解决某一些规模较大的较复杂的调度问题。从本质上说，规则调度方法是一种局 部的优化方法，很难能保证能得到全局的优化结果。且当生产系统规模扩大到一定程度时， 较多的规则会造成规则匹配速度的变慢，规则自适应能力较差，难以应用在动态的系统中。 又调度方案产生于规则，规则在不同地方或不同的规则能产生不同的调度，故在解决实际 武汉科技大学硕士学位论文第5 页 调度问题中对于规则的选择成为了基于规则的调度方法的一个瓶颈部分。 ( 2 ) 基于人工智能的方法 近年来，随着人工智能技术被引进到调度领域，有效地解决了某些调度问题，成为了 调度算法中了一个热门课题，其主要有下面一些常用的方法： 专家系统方法首先集合在生产系统中生产人员的各类经验来组成算法的数据空间，然 后在调度算法中直接在数据空间中搜寻，直到找到问题的最优解，这种方法使用简单、方 便、灵活，但在实际操作中对于经验的收集是一个瓶颈，难以全面包含生产系统中的的方 方面面，且难以准确化。以神经网络、微粒群算法、蚁群算法、遗传算法等为代表的群体 进化算法，都是仿效了自然界中生物群体的信息处理模式来获得智能系统信息功能的理 论，因其对具体问题有简单和普遍的适用性等特点，成为了解决较大规模调度问题有效途 径。 神经网络方法的思想主要是基于人脑的网络组成结构，由众多的互相连接而成的各类 神经元以网状的形式组成瞳，通过由底到顶的自学习和自组织的并行分布式方式来表示信 息，主要利用训练过程中对网络中的输入数据和输出数据来取得各神经元相互间的连接权 值，这种方法并不需要精确地知道调度模型中的内容，便能确保所创建的神经网络能够准 确地代表实际问题的全部特性。 遗传算法模拟自然界的生物的进化过程，先对具体问题进行参数化编码，产生出初始 的种群，然后计算群体中每个个体的适应度值，如果不满足算法结束条件，则进行进化操 作，依次循环，最后取得系统的全局最优解。 进化算法作为一类优化算法自诞生来在许多研究领域都有较快发展乜2 | 。同别的优化算 法相比有其突出的特点，首先，进化算法从本质上说是一种并行的算法，搜索效率较高； 其次，在解空间中采用随机的搜索方式，较容易摆脱局部的最优解，达到全局最优；最后， 不需要了解问题领域的具体的专业知识，使用范围广，对具体问题适应性度强，鲁棒性较 好。由此可以预言进化算法在复杂的工业生产过程中有广阔的应用前景，值得进一步去研 究与探索。 ( 3 ) 基于仿真的方法 基于仿真的优化方法是建立在p e t r i 网，排队论等数学优化方法的基础之上的，通过利 用对离散事件仿真模型来模拟实际制造系统中的生产过程。p e t r i 网作为一种数学工具，为 对特定的离散系统的建模、性能分析与设计提供了一个相对统一的环境。利用p e t r i 网建模 虽然比较直观，却难以用数学的方法来模拟分析它状态的演变过程，且当调度系统规模越 大时，p e t r i 网的规模也越大，失去了其原有的客观性。因而改进型的p “网受到了人们 的重视，随着当前面向对象技术的迅速发展，将这两种数学方法相互结合起来，以增强p e t r i 网的功能，并降低对特定模型的依赖和难度成为了当前理论研究的热点。 ( 4 ) 基于控制理论方法 基于控制理论方法是将控制理论应用于生产调度领域的方法。生产调度模型的建立是 为了尽可能地减少机器的故障、原材料的短缺、产品需求变化以及其他各类不确定性因素 第6 页武汉科技大学硕士学位论文 对实际调度过程的影响。它的缺点是：调度模型对实际生产情况的描述能力非常有限，在 建模过程中必须要对实际的调度环境中各种不确定性的因素进行大量简化处理，因为算法 在求解过程中的时间消耗将会随着生产调度问题规模的增大而呈现指数性增长，所以这种 方法也只适合于对规模较小的调度问题进行求解瞳驯。 ( 4 ) 基于模糊数学理论的方法 基于模糊数学理论的方法目前是一种比较新的优化方法，该方法以模糊数学理论为基 础，以模糊概念来处理一些实际中的模拟信息。在应用到调度领域中时，当在处理一些生 复杂生产系统中的不确定的信息时，往往能取得比较好的效果，但是这种优化方法在实际 运用需要比较长的周期来收集所需要的各类信息，需要非常丰富的生产调度经验以及相关 的工程技术知识。 针对启发式调度方法和优化调度方法各自都存在的优缺点，可设计一种结合这两种方 法的混合优化算法，互相克服自身缺陷，以使算法更有利于解决生产调度问题。 1 5 车间调度问题的分类 对于车间调度问题的分类可有多种不同的分类方法，由g r a v e s 等人的研究，可将车间 调度问题划分为如下几种类型晗副： ( 1 ) 根据生产制造系统的组成的规模的复杂程度，可将车间调度分为如下的四种调 度类型：单机调度、多台并行机调度、流水车间调度、作业车间调度。 单机调度是指所有待加工工件都是在一台机器上加工，是在全部生产环境中最为简单 的类型，也是对其他生产环境的一个特例，在单机调度中主要的任务就对工件的排队优化 问题；多台并行机调度指并行的多台机器，加工任务可在所有机器中每一条机器上进行加 工，这种调度类型比单机调度问题更为复杂；流水车间调度是指生产环境中有串行的多台 设备，每个工件都必须要在所有设备上进行加工，且全部工件的加工工艺顺序相同，即所 有工件在第一台设备上加工完后直接到到第二台设备的加工任务，以此类推，主要优化的 是队列问题；作业车间调度指有多台设备，所有待加工工件的工艺顺序不一样，每个工件 在每台设备上的加工次数不限，对于作业车间调度问题，由于其本身的复杂的特性，计算 复杂度相对较高，是数学上最困难的组合优化问题之一，计算规模较大，是典型的难 题。 ( 2 ) 根据车间调度所在的实际生产环境特点，可将车间调度分为确定型车间调度和 不确定型车间调度，确定型车间调度指生产过程的各项数据全部为确定的精确数据；不确 定型车间调度指调度数据为不确定的有一定规律的模糊数据。 ( 3 ) 根据实际的加工生产环境中各类生产特性，可将车间调度分为静态车间调度和 动态车间调度两类，静态车间调度指车间生产过程中各项参数是明确不变的；动态车间调 度则是各加工工件不问断地进行生产制造系统中进行加工，并且在完成加工任务后的的加 工工件又会不断地离开，在调度过程中要考虑生产系统中各种扰动因素，如人员、设备、 工件的所处状态等，因此需要不断地由算法产生的调度方案进行调整与修改。 武汉科技大学硕士学位论文第7 页 ( 4 ) 根据实际生产中的加工性能指标，可将车间调度分为基于调度费用车间调度与 基于调度性能车间调度。基于调度费用车间调度指为了实现在调度方案的生产中所消耗的 人工费用、设备磨损、存储费用、运输费用以及交货提前或拖后损失费用等达到最小；基 于调度性能车间调度指为了实现调度方案生产中某一个或某几个性能指标最小，这些性能 指标主要指：加工最大的完成时间、客户对工件的交货期的满意度、生产设备的磨损量或 利用率、整体的工件运输费用等，在实际的生产调度过程中，这两种调度方案往往需要结 合来考虑，从而使得企业的整体加工成本最少和生产效益最大。 1 6 车间调度问题的特点 车 间 调 度 系统复杂程度 不确定型车间调度 加工特点h 静态车间调度 动态随机调度 调度费用车间调度 调度性能车间调度 图1 1 车间调度问题的分类 在实际的调度问题中主要有以下共有的特点： ( 1 ) 复杂性。车间调度中从原材料到产品的过程，工件加工和设备、仓库、搬运系 统等之间都是相互影响、相互作用的。又由于产品加工工艺的多样性，以及内外部环境的 不确定性，当调度的规模扩大到一定程度时，相应调度模型的解空间以及计算该模型的计 算量也会呈指数性增长，导致调度问题成为n p 完全问题，难以求解，常规的优化方法难 以计算，即使在当前流行的基于人工智能的调度算法中，对于解的优劣性也难以判断。 ( 2 ) 不确定性。生产制造系统是一个有人员、物料、设备、信息等组成的一个大系 统，其中各种随机因素，如人员的状态、设备的故障、物料的运输、市场的需求等会造成 产品实际到达时间、加工时间，材料运输时间，订单的更改、设备的状态等数据的不确定 性，都是在生产之前的车间调度中无法预测的，从而使得调度问题成为了一个随机的不确 定性问题。 ( 3 ) 多约束性。在调度过程中，实际生产资源包括生产原料、生产设备、生产人员， 产品交货期，产品固有的工艺要求等等都是在车间调度中必须要遵守的约束条件，只有在 遵守生产车间的这些约束的前提下制定的生产调度方案才有可能会有用于实际生产中，否 一一一一一一一一一 第8 页武汉科技大学硕士学位论文 则产生的调度方案是无效的。 ( 4 ) 多目标性。调度的目标有很多，常见如最小化最大完工时间、最小化生产周期、 最大化利润、最大化产品完工时间相对交货期的客户满意度等等。在这些目标中，某些目 标往往是相互抵触的，这就需要综合考虑各种目标，包括成本，资源利用效率、利润等， 在相应的调度算法中需要结合各类优化目标，创建一个由多个目标的加权值来作为算法的 优化目标函数。 1 7 本课题研究的主要内容 本论文以不确定环境下的车间调度为主要研究对象，采用基于运筹学的数学规划方法 对问题进行数学建模，并讨论求解模型的方法。在基本遗传算法的理论基础上设计出新的 改进型的遗传算法，将模糊数学的思想应用到算法中，并通过m a t l a b 对设计的算法进 行编码以及实例仿真。本文的主要研究内容如下： ( 1 ) 阐述了对车间调度问题的研究现状，对了车间调度进行分类，归纳了在车间调 度中常用的优化方法，从而引出了对不确定环境下车间调度问题进行研究的必要性和重要 性。 ( 2 ) 对车间调度问题的特点和建模方法进行详细分析，在对问题进行数学建模的基 础上，分析模型的输入与输出数据、建模方法、模型优化目标，并对常用的智能求解方法 进行介绍与分析。 ( 3 ) 对遗传算法的起源、发展、应用等基础理论进行深入分析，并在基本遗传算法 的基础上进行改进，在基本遗传算法的编码、遗传算子( 选择、交叉、变异) 、适应度函 数等方面进行分析并进行相应的设计使改进的遗传算法能够适用于求解在不确定环境下 的车间调度问题。 ( 4 ) 对模糊数学的基本理论进行深入分析，将模糊集合和模糊数的理论应用于不确 定环境下车间调度问题中，将车间调度中的不确定加工时间以及不确定交货期都用模糊数 学的方法来表示，并应用于设计的遗传算法中进行运算，来对不确定性车间调度问题进行 求解。 ( 5 ) 用m a t l a b 软件对设计的改进的模糊遗传算法进行编码，并通过不确定性调度 实例来对算法进行验证工作，证明算法的正确性和有效性。 ( 6 ) 对全文所做的工作进行总结，并对不确定环境下车间调度算法的更深入的研究 做出展望。 武汉科技大学硕士学位论文第9 页 第二章车间调度问题研究 车间调度问题是将生产系统中有限的资源分配给在一定时间段内进行的生产任务，从 而实现某些既定的生产目标。其中系统中的资源和任务可呈现为多种形式：车间中的加工 人员、加工设备、运输设备、原材料、仓库等都可以看做是资源；任务则是在生产过程中 的工件工艺所需的加工任务、生产过程的运输过程，储存等，每个任务对于进行调度的决 策者而言可能有不同的优先级，所有调度目标也会有不同的形式，有些甚至是相互抵触的， 在达到这一目标时也许会难以达到另一个目标。 2 1 车间调度问题概述 生产企业中，提交的加工订单都需要划分为带有工期的加工任务，这些任务大多需要 在一个以上的设备上以特定的加工次序进行生产加工，如果某些设备正繁忙，则任务就会 延迟，若优先级更高的任务到达设备，那么设备就需要中断。如果生产中加工设备故障或 实际生产时间过长，也将可能对调度产生重大影响，因此，对生产任务做一个详细的车间 调度对于维持生产的效率是非常有帮助的。 车间也不是生产系统里唯一能影响调度过程的部分。它也受到企业在一段时间的整个 中长期计划的生产计划过程的影响。而整个过程是在基于企业库存水平、需求预测以及资 源的需求上基础上，优化公司所有产品组合和长期的资源分配。车间调度的制定必须要受 到这个更高层次的计划的影响，图2 1 是生产制造系统的信息流图盥刳。 能力状况 调度约束 ：调度性能 车间状态 订单，需 求计划 物料需求 日期 详细 调度 图2 1 生产制造系统的信息流图 在制造企业中，车间调度过程也必须要和企业中其他的决策活动进行交互，一个实用 的，使用广泛的是物料需求计划系统( m a t e r i a li 沁q u i r e m e n t sp l a n r 血g ，m r p ) 。m r p 系统非常 细致，每项工作都需要有一个物料清单( b i l lo f m a t e r e a l s ，b o m ) ，这个清单详细列举了生产 第1 0 页 武汉科技大学硕士学位论文 中需要的各种零部件。且m i 冲系统会持续跟踪各类原材料的库存，以及采购它的时间点。 一个车间调度产生后，必须使生产中的各类资源以及原材料在特定的一段时间内可用，其 生产时间也需要和m r p 联合确定。 2 1 1 车间调度问题描述 一般情况下，车间调度问题可以表述为：在满足一定加工要求的条件下，将一定数量 的加工任务分配在一定数量的加工设备上，每个任务的一道工序都需要在一台相应的设备 上进行无间断地加工，以满足既定的性能指标。简而言之，车间调度就是把加工任务的加 工工序分配在加工设备上，确定加工的开始于结束时间，已达到优化目标。在实际的车间 调度中需要考虑的调度约束主要有：工件的加工工艺、加工人员的数量、加工设备的实际 生产能力、原材料的多少，可用性、企业实际的成本、产品交货期。 车间调度问题也可称为对车间作业任务的的排序的问题，主要可分为f l o w - s h o p ( 流 水作业) 与j o b s h o p ( 作业车间) ，这两类问题是目前在调度领域的文献中讨论得最多的， 也是具有特殊工件特性以及生产加工环境的最典型与最重要的两种调度问题。车间调度主 要研究n 个工件( j l ，j 2 ，j n ) 在m 台机器( m l ，m 2 ，m n ) 上的加工过程，0 “表示第i 个工 件在第j 台机器上的加工操作。每个待加工工件的加工工艺约束不同，即各工件在各个加 工机器上的加工次序不一样，且各工序的加工时间是确定的。要求在满足各工件的加工工 艺的条件下，确定工件各工序在机器上的加工顺序，使最小化最大完成时间，最大化机器 利用率、客户满意度等优化目标达到最优。当所用的待加工工件的加工工艺约束都相同时， 即所有工件在各机器上的加工次序一样，则一个j o b s h o p 调度问题就转化为了一个 f l o w - s h o p 调度问题，对于典型的j o b s h o p 调度问题，通常还有如下假设： ( 1 ) 所有待加工工件在各个机器上的加工次序是确定不变的，工件都需要按照其既 定的加工顺序在各个机器上按规定的次序进行加工操作； ( 2 ) 在每一时刻，每台机器上同时只能有一个工件在加工，对于同一个工件，在任 意时刻也只能在一台机器上加工； ( 3 ) 所用工序一开始就不能中断，且机器也一直可用； ( 4 ) 所有工件都具有相同的优先级，不存在某个工件优先加工； ( 5 ) 所有工件的某一道工序必须在该工件的前一道工序完成之后才能开始，即操作 允许等待； ( 6 ) 若无特殊说明，所有机器的缓存区容量不限。 由于j o b s h o p 调度和f l o w - s h o p 调度的特殊性，典型性和重要性，一般可称为基本车 间调度问题。又因为市场的激烈竞争和多变性、产品的多样化、客户的需求变化性等，对 于一般的生产制造企业而言，生产大多是多品种小批量生产，即实际调度问题为j o b s h o p 调度问题，且由于j o b s h o p 调度的多变性、多约束性以及不确定性，j o b s h o p 调度问题相 对于f 1 0 w _ s h o p 调度问题调度解的编码更加复杂、解空间巨大、多工艺约束，调度目标函 数的计算更麻烦，造成j o b s h o p 调度问题多为n p 难题，难以用常规优化算法进行求解。 武汉科技大学硕士学位论文 第1 1 页 所以在本文中，主要以j o b s h o p 调度问题作为研究对象，运用智能优化算法进行求解，从 而使既定的调度目标达到最优，最终求得最优调度策略。 2 2 车间调度问题数学建模 车间调度主要是对生产作业进行排序，使某个目标达到最优。 2 2 1 车间调度表示符号 在对车间调度问题建模前可先约定车间调度中的表示符号： ( 1 ) 工件集合j _ ( j 1 ，j 2 ，j n ) ，其中n 表示工件的总数量； ( 2 ) 机器集合m = ( m l ，m 2 ，m m ) ，其中m 表示机器的总数量： ( 3 ) 任务集合o i k ，表示工件i 的第k 道工序； ( 4 ) 触表示工件i 的第k 道工序o 设的实际加工时间。 2 2 2 车间调度模型的输入与输出 在对车间调度问题进行建模过程中，需要先确定调度模型的输入与输出数据。如图2 2 所示： m 2 m 3 图2 2 车间调度模型的输入与输出 生产任务为企业在面向市场需求时确定的产品生产数量、投产时间、完工时间、提前 或拖后处理；产品工艺路线为企业所生产的特定产品根据产品设计所确定的工艺路线，即 加工的依次工序。生产资源为加工前生产系统中应具有的加工人员、机器、原材料、仓库 等资源的清单；其中对模型进行求解的优化算法主要是当前应用较广泛的智能优化算法如 遗传算法、粒子群算法、模拟退火算法等；甘特图( g a 斌c h a n ) 是描述车间调度方案的良好 第1 2 页武汉科技大学硕士学位论文 工具，能清楚地显示工件各工序在各机器上的加工开始时间以及结束时间。 2 2 3 车间调度问题的建模方法 在实际的自然科学和工程技术的科学研究中，模型已经成为了对问题进行定性和定量 分析的有效工具，系统建模成为了了研究分析的主要对象，当应用在车间调度中，主要可 分为如下两大类： ( 1 ) 基于运筹学的方法 基于运筹学的数学模型一般是通过数学等式或不等式来表示所研究系统中的变量及 变量之间的相互关系。大部分是描述性的，即在一定的变量组合条件下某一优化目标的数 值，并通过特定的方法分辨结果的优劣。在应用在车间调度中，就是在满足一些列约定的 约束条件在，在所有解的空间中搜寻满意答案，即最佳调度方案这个寻找的过程称为优化 过程。假定在一个生产制造系统中有n 个工件，m 台机器，每个工件由其工艺规划要经过 多个工序，o 。代表工件j 。的第k 个工序在机器m q 上加工，其开始时间以及加工时间为s 岫 和t 曲；工件j 。的最后一道工序的开始加工时间以及完工时间为s ；。和t 。；工件j ：的开始 加工时间以及交货期为r 。和d ，p 。为有序工序对 0 ；k p ，o ，。 集合，代表0 i k p 优先于o 。加工； r 。代表在机器m 。加工的所有工序的集合。优化目标为最小化最大完成时间或最小化加工 周期，即安排n 个工件在m 台机器上加工使所有工件在机器上的总的完工时间达到最短， 该j o b s h o p 用数学规划方法建模的模型描述为： 施彬= 胍f ，+ 夕 f 公式( 2 1 ) 盯 一、 ，d 衄，d 沏， 公式( 2 2 ) 后，z j ，2 ，聊f f 一 或 一 ，d 衄，j 7 r e 公式( 2 3 ) i j nq m s 脚d f i g f g ， 0 ，2 ，行f 公式( 2 4 ) 上式中，公式2 2 为工件的工艺工序约束，且不同工序不能同时加工；公式2 3 为设 备约束，且一台机器不能同时加工两工件；公式2 4 为工件开始加工以及交货期约束；公 式2 1 为模型优化目标，应在满足公式2 2 至公式2 4 的条件下达到公式2 1 的优化目标。 可以看出基于运筹学的数学规划模型逻辑性强，清晰地表达了模型中的的各种输入和 输出以及约束情况，是在实际车间调度中应用非常广泛的一种方法。 ( 2 ) 基于网络和图的方法乜7 1 应用于车间调度中的基于网络与图的常用的建模方法主要有p e t r i 网、析取图、关键 路径法等。 基本的p 耐网简单，容易使用，但在应用在规模较大的优化系统中时会造成节点数过 多的缺陷，故只用于对规模较小的系统建模中，实际中多为扩展的p 耐网，主要有e p - n 模型、c p - n 模型、t p - n 模型、p 厂r p - n 模型等，扩展p e t r i 网节点较少，比较适用于车间 调度模型。 武汉科技大学硕士学位论文第1 3 页 析取图模型为有向图模型：g = f ，y ，c u d ) ，v 为所有节点的集合，包含所有工件的全 部工序的节点以及两个虚节点，其中两个虚节点为开始节点和结束节点，加工时间都为0 ； 在应用到车间调度问题中就是确定析取图上的全部吸取边，即确定所有加工任务在机器上 的加工次序，得到一个有向图，从而使某个目标达到最优。当以最小化最大加工完成时间 为目标时，对于作业车间调度问题的求解就可转变为寻找在各弧上所有操作的一个序列， 当在同一机器上出现多任务的冲突时，用上述序列来对多任务进行排序，由此得到一个满 足所有约束要求的调度方案，即形成一个有向的非循环图，在此图中的关键路径的长度就 为调度的优化对象，即最大完成时间。 123 789 图2 33 3 作业车间调度问题析取图 基于对上述建模方法的分析与介绍，在结合车间调度问题的复杂性，在本文中将采用 基于运筹学的数学分析的方法来对车间调度问题进行建模。 2 2 4 车间调度优化目标 在实际的车间调度中，在不同的生产制造系统中有各自不同的车间调度目标，可以是 库存费用最少、加工周期最短、机器的实际利用率最高、运行成本最小、生产能力最大等。 总体而言，主要有以下几种：基于生产的完成时间，有最小化最大加工完成时间和最小化 平均完成时间或生产周期；基于生产的