（机械电子工程专业论文）基于petri网和遗传算法的车间作业调度问题研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着企业信息化步伐不断加快，先进的制造技术逐步被企业所采用，更加 客户化的产品需求和更短的产品生命周期要求下，有效的调度方法和优化技术 的研究与应用已成为先进制造技术实践的基础。车间作业调度技术是企业实现 生产高效率、高柔性、和高可靠性的关键技术，可以增强车间现有资源优化配 置能力，提高企业的生产效率，缩短客户等待时间，使企业在经济全球化的竞 争中处于领先地位。 本文首先在国内外关于车间作业调度问题研究的基础上，考虑到车间作业 调度的复杂性，对车间作业调度理论进行了系统的研究和p e t r i 网基础理论知识 的介绍，提出了用p e t r i 网基本模型来建立单件车间作业调度模型，用遗传算法 来优化车间作业调度问题。分析了遗传算法的基本理论，包括遗传算法的概念、 操作流程、操作算子等，在此基础上重点研究了遗传算法在车间作业调度中的 应用，为了克服遗传算法容易早收敛的缺点，在基本遗传算法基础上改进了遗 传操作算子( 选择、交叉、变异算子) 来优化车间作业调度问题，得到了该问 题的最优解或次优解。 最后本文采用m a t l a b 和遗传工具箱编写算法程序并通过实例来验证算法的 有效性和程序的正确性。证明了基于遗传算法求解车间作业调度方法的有效性， 这对实际的车间作业调度问题具有理论指导和现实意义。 关键词：车间作业调度，遗传算法，赋时库所p e t r i 网，建模与优化 西南交通大学硕士研究生学位论文第l i 页 a b s tr a c t a st h es t e po fe n t e r p r i s ei n f o r m a t i o n i z a t i o nq u i c k e n i n g ，a d v a n c e dm a n u f a c t u r e t e c h n o l o g ya d o p t e ds t e pb ys t e p ，t h e t r e n d so fi n c r e a s e dd e m a n d sf o rm o r e c u s t o m i z e dp r o d u c t sa n dd e c r e a s i n gp r o d u c t sl i f ec y c l e s ，r e s e a r c h i n go ne f f e c t i v e j o b - s h o ps c h e d u l i n g ( j s p ) m e t h o d sa n dt h ea p p l i c a t i o no fo p t i m i z a t i o nt e c h n o l o g y h a v eb e e nt h ef 0 u n d a t i o no fa d v a n c e dm a n u f a c t u r et e c h n o l o g y j o b s h o ps c h e d u l i n g t e c h n o l o g ya r et h ek e yt e c h n o l o g yw h i c he n t e r p r i s ef u l f i l l st a s kt h eh i g he f f i c i e n c y 、 l l i 曲f l e x i b l i t y 、h i g hr e l i a b i l i t y e f f e c t i v ej o b s h o ps c h e d u l i n gt e c h n o l o g yc a nb o o s t t h ea s s i g n a b i l i t yo fc o r p o r a t i o nr e s o u r c e s i ta l s oc a ni m p r o v ep r o d u c t i v i t ya n dr e d u c e c o s t t h i sw i l le n h a n c et h ec a p a c i t yo ft h ec o r p o r a t i o na n dm a k et h ec o r p o r a t i o nt h e l e a d e ri nt h ec o m p e t i t i o n d u et ot h e c o m p l i c a t i o no fj o b - s h o ps c h e d u l i n gp r o b l e m ，o nt h e b a s i so f d o m e s t i ca n df o r e i g nr e s e a r c ho nj o b - s h o ps c h e d u l i n gp r o b l e m ，t h i st h e s i s f i r s t l y i l l u s t r a t et h ef o u n d a m e n t a lk n o w l e d g eo fj o b s h o ps c h e d u l i n gp r o b l e ma n dp e t r i n e t ；u s et h eb a s i cm o d e lo fp e t r in e tt om a k et h em o d e lo fj o b - s h o ps c h e d u l i n ga n d d e v e l o pg e n e t i ca l g o r i t h mt oo p t i m i z ej o b s h o ps c h e d u l i n g a n dt h e ng e tt h eo p t i m a l a n s w e ro rt h eb e t t e ra n s w e r a tt h es a m et i m e ，t h i st h e s i sa n a l y z et h ef o u n d a m e n t a l c o n c e p t i o n ，p r i n c i p l ea n do p e r a t o r so fg e n e t i ca l g o r i t h m f u r t h e r t or e s e a r c ho ng e n e t i c a l g o r i t h mt oa p p l yi tt oj o b - s h o ps c h e d u l i n gp r o b l e mi no r d e rt oo v e r c o m et h e w e a k n e s so fp r e m a t u r ec o n v e r g e n c ea p p e a r i n gi n g e n e t i ca l g o r i t h m ，觚i m p r o v e d g e n e t i ca l g o r i t h mi sp r o p o s e da n da p p l i e di nt h ej o b - s h o ps c h e d u l i n gp r o b l e m a tl a s t ，t h et h e s i su s e ss o f t w a r em a t l a bp o w e r f u lc a l c u l a t i n ga b i l i t ya n dm a n y f u n c t i o n st oc o m p i l ea l g o r i t h mc o d e s ，g i v et h ee x a m p l eo f j o b - s h o p ，a n ds h o wt h e i r s c h e d u l i n gg a n t tp i c t u r e s ，t ot e s tt h ea l g o r i t h mc o d e se f f i c i e n c ya n dt h ep r o g r a mi s r i g h t t h i sp r o v e st h ea l g o r i t h ma p p l i e dt oj o bs h o ps c h e d u l i n gi se f f i c t i v e a c c o r d i n g t ot h er e s e a r c ho fg e n e t i ca l g o r i t h mo nj o bs h o ps c h e d u l i n gp r o b l e m ，t h eu s eo f g e n e t i ca l g o r i t h mt o a c t u a lj o b s h o pc a l l h i g l l l yi m p r o v et h e l e v e lo fs h o p m a n a g e m e n ta n dg u i d et h et h e r i o a la n dr e a l i z e dm e a n s k e y w o r d s ：j o b s h o ps c h e d u l i n g ；g e n e t i ca l g o r i t h m ；t i m e dp l a c ep e t r in e t ；m o d e l a n do p t i m i z a t i o n 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书： 2 不保密使用本授权书。 ( 请在以上方框内打“ ) 指导老师签名： 上， 弓替 吼a 。p 眵 冯 夕哆 二： 名 k 獬 者翱， 作 砌 一叩 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所 得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 1 。利用p e t r i 网基本模型建立赋时库所车间作业调度模型。 2 分析了遗传算法的基本理论，提出改进的遗传操作算子，基于工序编码的 部分调度保留和顺序交叉的混合算子，局部区域循环变异算子。 3 采用m a t l a b 和遗传工具箱编写算法程序并通过实例来验证算法的有效性 和程序的正确性。 学位敝赭躲歹够 日期哆涉乡 西南交通大学硕士研究生学位论文 第1 页 1 1 引言 第一章绪论 现代企业的多元化、多品种、小批量、柔性大的生产模式，使企业生产变 得更加复杂，对企业的生产和管理提出了更高的要求。为了保证生产的高效稳 定运行，以获得最大的经济效益，原来简单的、局部的、常规的计划和仅凭经 验的管理己经不能满足现代企业生产要求。企业管理者和车间调度人员面临的 新问题是：如何根据市场上原材料供应和产品需求的变化及时进行经营决策和 组织生产：如何在生产计划改变的情况下对生产过程进行控制，以便最大限度地 发挥生产的柔性；如何在生产工艺不作大的改变的前提下进行管理、决策，使企 业产生最大的综合经济效益。如今，并行工程、精益生产、敏捷制造等等生产 模式，其目的就是降低成本，增加效益，满足顾客多样化的需要。我们也知道 在这些模式下，如何安排生产计划，如何进行车间调度，如何进行车间生产单 元的重构等都是我们面临的主要问题。其中车间调度与控制技术是实现生产高 效率、高柔性和高可靠性的关键。有关资料表明，制造过程中9 5 的时间消耗 在非切削过程中【l j 。 制造业是国民经济的基础，是国家经济实力的重要体现。制造业技术先进 与否，既是国家科技实力的体现，又是促进科技技术发展的强大动力。而科技 的进步既为制造业的发展到来了机遇，也加剧了制造业的竞争，企业在竞争中 求生存、在竞争中求发展。企业要在现实的环境中立于不败之地，缩短产品上 市的时间、提高产品质量以及降低产品的成本无疑是企业的必有之路，要实现 这些目的，不仅要采用先进的生产设备和工艺技术提高设备的自动化程度，同 时也要提高生产过程中计划、调度以及决策的水平。 生产调度是制造系统生产管理的核心，生产任务顺利实施与完成，最终要 靠合理的车间调度来保证，生产调度研究的是合理配置加工资源，减少零件的 准备时间、等待时间与传送时间，从而提高设备利用率与生产效率，降低生产 成本。车间调度对产品的交货时间、产品的生产周期、设备利用率和在制品占 有率都有影响。因此，及时准确的车间调度对生产系统高效运行有着重要的影 西南交通大学硕士研究生学位论文 第2 页 响，主要表现在：生产计划的有效实施；高效低耗的使用生产资料；均衡生产 及准时生产，减少在制品的资金占用。所以，有效的车间调度方法与优化技术 研究和应用是缩短产品上市时间、及时满足客户需求，从而使企业赢得市场的 有力武器。因此，本文以机械零部件加工行业为研究背景，对其展开车间作业 调度方法和技术的研究有及其重要的理论意义和现实意义。 1 2 选题背景及意义 随着市场竞争加剧，制造业的经营环境也发生了变化，其主要表现在经营 理念由过去的以产品为中心转变为以顾客为中心；生产组织方式由过去的大批 量生产转化为大批量定制生产或单件小批生产：企业由过去庞大而全的模式转 化为合理社会分工企业集团模式或动态联盟模式。制造业正从传统的以机械为 特征的传统技术时代朝着以信息为特征的系统技术迈进，将信息技术应用于制 造领域并对之进行改造，是现代制造业发展的必由之路【2 l 。美国曾于上世纪8 0 年代提出了先进制造技术( a d v a n c e m a n u f a c t u r i n g t e c h n o l o g y ，a m t ) 的概念。先 进制造技术定义为：它不断吸收机械、电子、信息、材料、能源和现代管理等技 术成果：将其综合应用到制造全过程，实现优质、高效、低耗、清洁、灵活生 产，取得理想经济效益的制造技术的总称【3 】。1 9 7 3 年h a r r i n g t o n 博士提出了计 算机集成制造c i m 的概念，c i m 是一种组织、管理与运行企业生产的新哲理， 它借助计算机软件、硬件，综合运用现代管理技术、制造技术、信息技术、自 动化技术、系统工程技术，将企业生产过程中有关人、技术、经营管理三要素 及其信息流与物质流有机地集成并优化运行，以实现产品的高质、低耗，从而 使企业赢得市场竞争【4 1 。c i m s 通过信息技术提高系统的自动化水平，并通过系 统集成提高系统的运行效率和降低运行成本【5 】，注重对系统功能构成和静态控 制结构的研究，适于某种可预测、相对稳定的经营环境。随着制造环境的动态 多变和不可预测，客户对产品的个性化要求越来越高，同时制造系统内部也存 在故障和物料短缺等很多随机模糊等因素。上世纪9 0 年代，美国政府提出敏捷 制造【们，强调技术、组织和人三者间的有机集成，它是一种可重用、可重构、 可伸缩的制造系统。 在上述诸多先进制造模式中，都是以生产调度为基础【_ 7 1 ，车间管理及其作 业调度是制造系统的核心和重要组成部分，车间调度的优化是先进制造技术和 西南交通大学硕士研究生学位论文 第3 页 现代管理技术的核心技术。对调度方法与优化技术的研究，已成为先进制造技 术实践的基础和关键。在这些自动化程度较高的生产管理系统中，使生产过程 合理、高效运行的调度问题己变得非常复杂，需要建立有效的计算机调度控制 策略，因此车间作业调度问题的研究具有重要的现实意义，而大量的车间作业 调度问题是属于n p h a r d 问题，目前尚无有效的求解策略，因此车间作业调度 问题的研究也具有重要的理论意义。研究生产调度对于提高我国制造业执行系 统的科技水平，促进我国制造执行系统的发展和应用，有着重要的理论和现实 意义。 制造过程组织和执行是围绕产品的生产而展开的，实际的生产调度就是从 时间和空间上对生产过程中的各方面( 产品、设备、人员等) 进行有效的、及 时的控制，使得生产能够有序、高效的进行。而制造系统的所有模块几乎都与 产品的生产调度不可分割。制造执行系统的生产排程就是调度技术的体现，生 产排程的合理性、科学性、高效性，会极大的影响车间的生产效率和资源利用 率；数据采集功能对生产过程的物料、人员以及设备等数据进行采集，但这些 数据是车间按生产调度的结果进行生产而产生的，数据采集的目的之一就是为 了以数据为指导，促进车间进行更为合理、高效的生产。在制品的管理对于离 散制造行业的物料控制极为重要，但在制品的管理好坏一方面取决于系统本身 的数据搜集与反馈，更主要的是对生产调度的水平，底水平的、不合理的生产 调度往往导致较高的在制品库存，降低生产效率、增加成本开支，但需要解决 这些问题，关键在于提高生产调度的水平；过程控制主要对生产过程中的各种 突发事件，比如，设备故障、物料延期、人员不足等等，如果没有良好的、高 效动态调度方法作为支撑，过程管理的管理水平就会大大的下降。 生产调度是制造执行系统( m e s ) 的核心，对整个生产制造过程有着重要的指 导和控制作用。由于我国对m e s 的研究起步较晚，现阶段还主要停留在对m e s 内涵等研究上，对m e s 关键技术和理论的研究还缺乏，从机械制造行业的特点 来看，企业的准时制生产需求企业在合适的时间点生产出合适的产品，因此如 何做好静态的计划编制和动态的实时调度才能生产出满足客户需要的产品，是 企业的难题。从接受的任务来看，机械零部件的加工多品种、小批量，大部分 是按定单组织生产。 车间作业调度( j o b s h o ps c h e d u l i n gp r o b l e m ，j s p ) 的求解目标就是要找到 一个将加工作业安排到车间制造机器上，按照某种最优化策略，使加工作业能 西南交通大学硕士研究生学位论文第4 页 够最优完成的方案。每个作业都由一些工序组成，而每个工序则必须由指定的 机器加工处理。一个调度就是按照作业内在逻辑的先后顺序条件将所有工序安 排在机器上的一种方案。 车间生产过程的作业调度问题是制造系统中运筹技术、管理技术与优化技 术发展的核心。作为制造系统生产管理核心内容是车间作业调度系统，是实现 生产计划和生产作业计划，并使企业生产效率最大化的重要手段。有关资料表 明，机械制造过程中9 5 的时间消耗在非切削过程中【l 】，及时准确的调度可以提 高资源的利用率，均衡生产，减少在制品的资金占用。 我国制造业与工业发达国家的差距主要是在制造装备落后和生产组织管理 技术落后，如我国大多数企业仍以普通机床为主，生产管理和调度仍以手工和 经验为主。在这种现状下通过大量的投资更新工艺设备、提高制造工艺水平和 自动化程度是不太现实的。完善和清晰的调度管理体系、有效的调度方法和优 化技术应用，协调、调度好企业生产过程中出现的各种问题，对提高我国企业 的市场响应能力具有十分重要的现实意义，使我国企业在全球经济一体化竞争 中处于领先地位。 1 3 国内外研究现状 在静态调度和动态调度方面，国内外学者都做了相应的研究，下面从这两 个方面分析。 1 3 1 静态调度研究现状 研究生产调度问题始于2 0 世纪5 0 年代，j o h n s o n 提出了解决车间调度部分 特殊问题的优化算法，代表调度理论研究的开始。6 0 , - 7 0 年代建立了调度理论 的主体经典调度理论并重视调度理论复杂性的研究。大量的研究促使车间调度 领域取得了丰硕的成果，产生了许多重要的调度方法。随着7 0 年代后期调度理 论研究的深入及各种交叉学科的发展，又涌现出了许多新的车间调度理论与方 法。d a v i s 是最早把g a ( g e n e t i c a l g o r i t h m ，遗传算法) 应用于车间调度问题的学者 之一，他在使用g a 求解车间调度的研究中取得了近似最优解。1 9 8 5 年，d a v i s 发表了关于把g a 成功应用于车间调度问题的论文，充分展示了g a 在解决车 西南交通大学硕士研究生学位论文 第5 页 间调度问题的前景。此后，很多学者就遗传算法在车间调度问题方面的应用作 了大量的研究，发表了大量卓有成效的论文，从而看到了解决车间调度这类 n p h a r d 问题曙光。以d a v i d e ，g o l d b e r g , y a m a d a ，n a k a n o ，w l l i u e y , f a n g ，k o b a y a s h i 等为代表的一些学者在他们的论文中提出了一些具有突出性的新思想，改进并 完善了传统g a 车间调度中的应用方法，同时在解决一些著名的标准检测问题 ( b e n c h m a r k ) 中取得了最优( 或接近最优) 解，进一步证明了遗传算法在解决 n p - h a r d 这类问题的有效性【l q 。 生产调度问题是对具体生产环境中复杂的、动态的、多目标的调度问题的 一种抽象和简化。传统的静态调度问题对生产的研究进行如下假设：1 ) 被调度 的工件集合是确定的；2 ) 工件的加工时间是确定的；3 ) 加工工件的机器是无 故障运行的。 现在主要的静态调度：单件车间作业调度问题( j o bs h o ps c h e d u l i n g p r o b l e m ) 、流水车间作业调度问题( f l o ws h o ps c h e d u l i n gp r o b l e m ) 、并行机调 度问题( p a r a l l e lm a c h i n e ss c h e d u l i n gp r o b l e m ) 、柔性作业车间调度( f l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m ) 、柔性流水车间作业调度问题( f l e x i b l ef l o ws h o p s c h e d u l i n gp r o b l e m ) 南京航空航天大学机电工程研究所的鞠全勇i s 】等在研究双资源、多工艺路 线作业车间调度的基础上，从实际作业车间出发，建立了模糊调度数学模型。 以最小完工时间和平均满意度最大为优化目标，应用改进的遗传算法，求解最 优调度工序。但并没有将此方法和实际动态调度过程相结合，进一步提出动态 调度算法；另外，该方法只对两个单独目标进行了优化，并没有实现多目标的 优化过程。 辽宁工程技术大学机械工程学院工业工程系的马光锋【9 】等人在分析了单件 生产调度问题的基础上，提出了求解j s s p 问题的混合遗传算法。该算法结合了 遗传算法并行搜索和模拟退火算法自适应变概率的变异操作特点，使得两种算 法的各自弱点得到补充，求得了较好的优化效果。 国内对车间调度研究较晚，由于技术上的制约，基本上靠调度人员的经验 进行车间作业分配和调度。随着遗传算法在作业调度方面的应用，国内也掀起 了应用遗传算法研究车间调度的热潮；研究工作主要集中在清华大学计算机集 成制造系统( c s ) 国家重点实验室，而且目前这些实验室的系统开发基本上 还处在刚投入运行阶段，离成熟的软件系统还有一段较长的时间，因此，各个 西南交通大学硕士研究生学位论文 第6 页 实验室还需要投入大量的人力和物力进行车间调度方面的研究，特别是在开展 对车间作业调度算法方面的研究，目前尚处在实验研究阶段。 1 3 2 动态调度研究现状 j a c k s o n 1 0 】于1 9 5 7 年就对静态调度和动态调度的概念作了区别。传统的静 态调度方法在动态调度领域应用的最多的是调度规则和仿真方法，具有计算量 小、效率高和实时性等优点，非常适合于动态调度，但通常需要和智能方法结 合应用。 武汉科技大学机械学院雄禾根【1 1 】等人提出在考虑工序相关性的、工件批量 到达的动态车间调度问题。在对工序相关性进行了定义和数学描述的基础上， 进一步建立了动态车间调度问题的优化模型，并设计了一种组合式的调度规则， 提出基于规则的启发式算法以及该类动态车间调度问题的算例生成方法。该文 中对于动态时间的定义只限于工件的批量到达，而没有涉及一些突发事件和故 障的出现等的处理。 北京航空航天大学机械工程及自动化学院的王健【1 2 1 等人研究了基于约束满 足的再调度过程和再调度策略，并使用i l o g 优化组件实现基于约束满足的车间 再调度原型系统，系统可以对常见的突发事件引起的原有调度方案的变动进行 处理。该系统主要的动态调度对象还是车间中的突发事件以及紧急事件，对一 般常规动态调度的事件没有进一步深入研究。 上海交通大学机械学院的华山【1 3 】等人在e t a i l a r d 的研究基础上，用蚂蚁算 法对车间调度问题进行了仿真优化，得到了较为理想的优化效果；该文中蚂蚁 算法只是最基本的思想，并没有就蚂蚁算法现有的一些缺点进行相应的改进从 而获得更加优化的结果。 1 3 3 研究现状分析 通过对国内外研究现状的分析，在车间调度领域，已经有大量的优化方法 得到了研究和应用。从理论上说，这方面的经典调度理论很成熟，但是在实际 的生产调度中的应用情况时不太理想的，主要有三个方面： ( 1 ) 调度模型的局限性 调度模型的局限性主要体现在两个方面：一是模型不具有通用性，现 西南交通大学硕士研究生学位论文 第7 页 在很多的建模和优化方法，只是针对某一个经典的算例，即缺乏通用的建模方 法和优化算法。二是模型对实际的生产约束考虑不够。经典的调度理论在数学 上很完全，但在研究问题时对于真实的环境进行了大量的简化，从而导致调度 模型脱离实际的生产环境。 ( 2 ) 优化目标单一 现在大多数调度都是针对单一的目标进行优化，对其他指标研究少，而在 实际的生产中，调度目标多，且它们之间的相互制约。这就导致企业不愿意用 单一目标来指导实际的生产计划。 ( 3 ) 动态性和实时性的处理不够 实际生产过程中存在很多紧急事件和突发事件，譬如生产设备故障、订单 交货期的变更、人员的矿工等，这些紧急事件和突发事件往往导致事先做好的 生产计划无法顺利进行，造成企业的损失。现在国内外对于车间的静态调度研 究多，对于如何应对实时生产状况的动态调度研究相对较少。特别是如何同时 应对紧急事件和突发事件的动态调度的研究更少。况且车间生产的负荷不可能 一成不变、均匀的、因此需要研究针对车间负荷变化情况下的动态调度的调度 方法，这也是需要进一步研究之处。 1 4 研究的主要内容及章节安排 1 4 1 论文的主要内容 本文针对制造企业的特点，分析了制造企业的车间作业调度( j o b s h o p ) 的 特点，给出了基于p e t r i 网和遗传算法求解车间作业调度的过程。主要内容如下： ( 1 ) 分析了生产调度在国内外研究的现状，提出了本文要解决的生产调度 问题，并论述了车间作业调度( j o bs h o ps c h e d u l i n g ) 问题的特点、分类以及优 化求解方法。例如：数学规划方法、启发式搜索方法、系统仿真方法、人工智 能方法和计算智能方法等。 ( 2 ) 阐述了p e t r i 网基础理论。p e t r i 网的定义，基本规则以及基本模型的 建立，例如，缓冲区模型、工件队列模型、并行和同步模型、竞争模型。并运 用基本模型建立车间作业调度的赋时库所p e t r i 网模型。 西南交通大学硕士研究生学位论文第8 页 ( 3 ) 研究和分析车间作业调度系统理论和p e t r i 网，建立了车间作业调度 的赋时库所p e t r i 网模型。针对离散的、大非线性、复杂的机械制造企业的车间 作业调度的特点，提出了用遗传算法求解j o b s h o p 车间作业调度。 ( 4 ) 通过研究遗传算法的基本理论，详细分析了遗传算法在求解车间作业 调度问题操作过程和算法的编码方式、选择、交叉、变异等参数的选择方法。 在基于操作的编码方式下，改进了交叉方法和变异方法，保证了交叉操作后代 的可行性和从父代继承优良的特征。 ( 5 ) 运用m a t l a b 软件和遗传工具箱编写程序，给出了仿真实例和仿真结 果，证明了遗传算法在求解车间作业调度问题的有效性。 1 4 2 论文的章节安排 本文主要分6 章，具体安排如下： 第一章说明了课题的提出背景和研究意义，讨论了车间调度的国内外研究 现状，最后给出了本文的研究内容和论文的章节安排。 第二章阐述了车间作业调度问题的特点、分类；调度模型的数学语言描述。 总结了车间作业调度的优化算法。 第三章阐述了p e t r i 网的定义，基本规则以及基本模型的建立，例如，缓冲 区模型、工件队列模型、并行和同步模型、竞争模型。并运用基本模型建立车 间作业调度的赋时库所p e t r i 网模型。 第四章介绍了遗传算法的产生、发展、基本思想和操作流程。重点研究了 遗传算法在车间作业调度优化中的操作过程，包括了编码方式、种群大小、交 叉方式与概率、变异方法与概率等参数的选择。 第五章针对车间作业调度的特点，详细分析了在遗传算法在求解车间作业 调度问题操作过程和算法的编码方式、选择、交叉、变异等参数的选择方法。 提出了在基于操作的编码方式下，选择新的交叉方法与变异方法，保证了交叉 操作后代的可行性和从父代遗传优良特征。运用m a t l a b 软件和遗传工具箱编写 程序，给出了仿真实例和仿真结果，证明了遗传算法在求解车间作业调度问题 的有效性。 第六章对全文进行了总结，并说明了基于遗传算法在调度中所存在的问 题，展望以后进一步研究方向。 西南交通大学硕士研究生学位论文 第9 页 第二章车间作业调度问题的描述 车间作业调度与控制是管理与生产自动化的核心技术，车间生产作业调度 是其中重要的一环，它在工厂经营管理、产品制造这两个层次都占有极其重要 的地位和作用，它主要解决工件在机器上的调度和资源分配问题。合理的车间 作业调度是实现车间作业调度自动化和集成化重要环节。 车间作业调度的研究主要分为建模和调度算法设计两个方面。它是一个交 叉的研究领域，涉及运筹学、数学、计算机工程、控制工程、工业设计等多个 学科。其中，建模主要研究调度模型、调度规划、目标函数等内容；算法主要 研究算法的设计、算法的复杂性、算法的收敛性和优化质量等内容。本章研究 车间作业调度的模型建立并分析求解车间作业调度的优化算法，提出采用遗传 算法来求解车间作业调度问题。 2 1 车间作业调度问题 2 1 1 车间作业调度问题描述 研究刀个工件在朋台机器上的加工过程，各个工件在各台机器上的加工时 间己知，事先给定每个工件在各个机器上的加工次序( 称为技术约束条件) ，每个 机器一次最多只能加工一道工序，调度就是把工序分配给机器上某个时间段， 确定与技术约束条件相容的各机器上所有工件的加工次序。问题的目标是找到 最小化最大完成时间的调度顺序。若各个工件的技术约束条件相同，则把这种 j o bs h o p 调度问题称为f l o ws h o p 调度问题( 流水车间调度) 。在过去的4 0 年里， 机器调度问题吸引了无数研究者的浓厚兴趣，大量的研究成果相继问世，文献【1 5 】 给出了相关文章列表。 车间作业调度问题是对生产计划过程的作业计划具体安排，一般可以描述 为：针对某项可以分解的工作，在一定的约束条件下，安排其组成部分( 操作) 所占用的资源、加工时间及先后顺序，实现产品制造时间或成本等最优，描述 如图2 1 所示。 西南交通大学硕士研究生学位论文 第10 页 图2 1 车间作业调度描述图 车间作业调度问题是安排工件加工任务到加工设备上，它是在工件加工工 艺等约束条件下，通过决策与优化，达到加工时间最短、成本最低等目标。影 响调度问题的因数很多，正常情况下有：产品的投产期、交货期( 完成期) 、生 产能力、加工顺序、加工设备占用和原料的可用性、批量大小、加工路径、成 本限制等，这些都是约束条件。有的约束条件是必须满足的，如交货期、生产 能力等，而有一些达到一定的满意度就可以了。如生产成本等，这些约束在进 行调度时可以作为确定性因数。而对于设备故障，原料供应变化、生产任务变 化等非正常情况，都是事先不能预见的，在进行调度时大都作为确定性因数考 虑。生产调度中涉及的工厂资源包括：原料、设备( 加工、存储、运输) 、人力、 资金、能源等。资源的详细分配受到产品的生产工艺限制。 车间作业调度问题的性能指标可以是成本最低、库存量最少、生产周期最 短、生产切换最少、设备利用率最高、三废最少等。 2 1 2 车间作业调度的特点及分类 车间作业调度将生产任务分解，将任务安排在加工设备上，实现最优化加 工过程，其主要特点有： ( 1 ) 建模与计算复杂性，车间中机器、工件、缓存搬运系统之间关系复杂， 它们之间又相互影响相互作用。每一个工件之间又要考虑它的加工时间、完成 时间以及安装时间和操作顺序等，因而车间作业调度问题显得相当复杂。调度 问题往往是通过等式或不等式约束条件来计算的，属于典型的n p h a r d 问题。 随着问题规模的加大，计算量急剧增加，所以调度问题往往没有精确的解，通 西南交通大学硕士研究生学位论文第11 页 常是在解答过程中寻求最优解或满意解。 ( 2 ) 动态随机性调度中存在很多随机性和不确定性，如工件的交货期变更， 工件的加工完成时间，工件的到达时间。另外一些突发事件也增加的调度难度 和随机性。如机器故障、作业交货期的变更等。 ( 3 ) 多约束性调度中受到很多约束条件的限制，如缓存容量、资源数量、 工件到期时间与操作顺序等。此外，还有人为的附加因数，如机器负荷平衡等 等约束条件。 ( 4 ) 多目标性调度的目标很多，目标之间往往有相互冲突。主要有基于作 业交货期的目标，基于作业完成时间的目标，基于生产成本的目标三类目标。 按照不同的分类标准，车间生产调度可分为6 类： ( 1 ) 开环车间和闭环车间型：在开环车间中，调度问题基于订单，而不考 虑库存，在闭环车间则要考虑库存，显然闭环调度问题避开环调度问题复杂； ( 2 ) 根据加工系统的复杂程度：单台处理机、多台处理机、j o b s h o p 和 f l o w s h o p ； ( 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 车间作业调度问题是企业生产活动中最一般最复杂的作业调度问题，是许多实 际生产调度问题的简化模型，也是最困难的组合优化问题之一【1 4 1 ，本文将分析 j o b s h o p 车间作业调度的描述及优化技术。 2 2 车间作业调度模型描述 车间作业调度( j o bs h o p ) 问题研究n 个工件在m 台机器上的加工过程， 已知各操作的加工时间和各工件在各机器上的加工次序约束( 称为技术约束 条件) ，要求确定与工艺约束条件相容的各机器上所有工件的加工次序，使 加工性能指标达到最优。已知： 西南交通大学硕士研究生学位论文 第12 页 ( 1 ) 工件集，_ 厂= l ，2 ，n ，即工件数为n 个。 ( 2 ) 机器集膨，m = l ，2 ，朋 ，即机器数为m 个。 ( 3 ) 工序序列集o p = o p l ，印2 ，o p 。 ，o p f = o p 订，d p ，2 ，o p 拥) 为工件 p ，的工序序列。 ( 4 ) 每个工件使用每台机器的时间矩阵t ，t 甜t 为第i 个工件使用第， 个机器的时间。当t 静为零时，表示工件p ，不使用机器_ ，。 在典型的j o bs h o p 调度问题中，除了技术约束外，通常假定以下条件： ( 1 ) 整个加工过程中，一个工件不能在同一台机器上加工多次； ( 2 ) 任何一个工件的前一道工序加工完成以后，方能进行后一道工序的加 工，在同一机器上一个加工任务完成之后，方能开始另一个加工任务； ( 3 ) 各工件必须按工艺路线以指定的次序在机器上加工； ( 4 ) 不考虑工件加工的优先权； ( 5 ) 每个工件的工序一旦进行就不能中断； ( 6 ) 一个工件同一时间只能在一台机器上加工，一台机器同一时间只能加 工一个工件，加工的开始时间为零； 确定调度结果，安排机器的加工工序，必须满足工件的工艺约束条件和 资源占用约束，其各类约束条件描述如下： ( 1 ) 顺序约束 令c 肚表示工件在机器后上的完工时间，t 批表示工件_ ，在机器尼上的加工时 间。对于工件，如果在机器h 上的加工先于机器k ，则有约束 c 肛一t 雄c 肚 ( 2 。1 ) ( 2 ) 技术约束 任何一个工件的前一道工序加工完成后才能进行后一道工序的加工，即 当工件i 先于工件，在机器k 上加工时有： c 肚一c 雎t 雄( f ，j = 1 , 2 ，n ；k = 1 , 2 ，掰) ( 2 2 ) 定义如下的指示函数： f l ，对于给定的工件f ，如果在机器 上先于在机器尼 一0 ，其它 f l , 对于给定的工件f 先于工件，= 芷机器疋匕加工 “毋一1o 其它 综上所述，以最大流程时间最小为目标j s p 调度问题可以用数学公 西南交通大学硕士研究生学位论文 第13 页 式描述为1 刀：m i n m a x tn 哆x o k 1 后历，l f 万 ( 2 3 ) 一 l l g 翔 j s 7 c 雎一f 雎+ m ( 1 一口激) c a ；i = l n ；k = l m ( 2 4 ) 一e l k + m o a # t ) ；f ，j = 1 n ；k - 1 m ( 2 5 ) 约束( 2 4 ) 保证每个工件的工序的加工顺序满足预先的要求，约束( 2 5 ) 保证 每台机器一次只能加工一个工件。 2 3 车间作业调度研究方法 车间作业调度问题是最困难的组合优化问题之一。业已证明：超过两台机器 和两个工件的一般调度问题是h p h a r d 难题。虽然对车间调度问题的研究已经 有几十年的历史，提出了一百多种调度方法，但至今尚未形成一套系统的调度 方法。最初是集中在数学规划、仿真和简单的规则上，这些方法不是调度结果 不理想，就是难以解决复杂的调度问题。随着各种新的相关学科与优化技术的 建立和发展，在调度领域出现了许多新的优化方法，比如人工智能、计算智能 和实时智能等调度方法，这些已经成为调度方法的主流。 求解调度的优化算法，可分为精确求解方法和近似求解方法。其中精确求 解方法包括解析方法、穷举方法、分支定界等，近似求解方法包括基于规则的 构造、智能搜索方法等1 1 7 】【1 8 】f 1 9 1 。 2 3 1 运筹学方法 数学规划方法是调度问题的精确算法，它主要是通过对车间调度建立一个 整数规划模型，采用枚举方法寻求调度问题的最优解。 在枚举方法中，主要的枚举策略是分支定界法，其基本思想是先求出对调 度整数规划模型所对应的线性规划问题的最优解，如果解不能满足调度问题的 整数条件，则对应的线性规划问题的最优解必是调度问题目标函数值的上界， 而调度问题的任意可行解的目标函数值则是其最优解的下界，然后将对应的线 性规划问题的可行域分成子域，通过不断减少上界和增大下界，最终寻求到最 优解。分支定界法的实现方法是动态构造一个表示调度问题所有可行解的树， 通过对树的搜索寻求调度问题的最优解。s a r i ns c 和p o r t sc n 等提出了改进的 西南交通大学硕士研究生学位论文第1 4 页 分支定界法，其不同点主要在于分析规则、定界机制和上界的产生三方面的差 异。分支定界法只适合小规模的调度问题，并且对实际问题比较敏感，因此限 制了它在调度问题上的应用。 数学规划方法的优点是任务分配和排序的全局性比较好，所有的选择同时 进行，因此可以保证求解问题的全局优化。但是数学规划方法是一种精确求解 方法，它需要对调度问题进行统一建模，任何参数的变化都会使得算法的重用 性很差，因此对于复杂多变的车间作业调度来说，单一的数学规划模型不能覆 盖所有的因数，存在求解空间大和计算困难等问题。 2 3 2 启发式算法 由于数学规划法的局限性，从2 0 世纪7 0 年代开始出现了启发式算法，这 些算法基本上是在一些信息和规则的启发下进行推理和计算，从而获得调度问 题的近似最优解。启发式搜索方法的优点是利用面向特定问题的知识和经验， 因而可以产生好的解决方案，求解时间也可以接受。启发式搜索方法的缺点是 用来评估解决方案的质量手段还较少，如何提高搜索效率以解决规模较大的问 题，还需要迸一步探索。启发式算法主要有： ( 1 ) 基于启发式规则的调度算法 最早的近似算法是基于启发式规则的调度算法，其本质是给每一个生产任 务和操作赋予优先级，优先级高的生产任务和操作优先考虑。由于其具有简单、 易于实现、计算复杂度低的特点。调度规则在调度问题上得到了广泛的应用， 同时不断有新的调度规则产生。p a n w a l k a r 和i s k a n d e r 总结了1 1 3 条规则【2 0 1 ，并 将它们分为三类：简单规则、复合规则、启发式规则，其中属于简单规则有3 0 多条，比如先进先出、最短加工时间、交付期最早等经常使用的规则，其它规 则基本上是简单规则的组合或加权组合；另外，调度规则经过适当的组合和变 形后，往往可以得到很好的调度效果。调度规则的缺点在于其精确度不够高， 尤其是在单纯使用简单规则的情况下。