（机械制造及其自动化专业论文）基于混合遗传算法的制造系统job+shop调度问题的研究.pdf

辽宁工程技术大学硕士学位论文 摘要 作业车问调度问题是制造系统实际生产中的重要问题，也 是理论研究的难点之一。本文针对作业车间调度现存的几个问 题，以混合遗传算法为核心算法，以基础数据库为根据，用c + + b u i l d e r6 0 开发了可视化动态车间调度系统。该系统可以实现 对车间零件的初始调度。考虑到车间调度问题的复杂性以及人 机交互的必要性，系统可以实现对调度结果进行部分修改。针 对在加工过程中出现的意外情况，系统还设计了重调度部分， 当达到重调度要求的时候对系统实施重调度，实现了动态调度 的目的。论文通过实例验证，证明了该调度系统解决作业车间 调度问题的有效性。 关键词：制造系统，作业车间调度，遗传算法，模拟退火算法， 动态调度 辽宁工程技术大学硕士学位论文 a b s t r a c t j o bs h o ps c h e d u l i n gp r o b l e mi sa ni m p o r t a n tp r o b l e mi na c t u a l p r o d u c t i o no fm a n u f a c t u r i n gs y s t e m ，i ti sa l s oo n eo f t h ed i f f i c u l tp r o b l e m s o f t h e o r y r e s e a r c h i no r d e rt os o l v eaf e wp r o b e m so f j o bs h o ps c h e d u l i n g e x i s t e dt o d a y , av i s u a ld y n a m i cj o bs h o ps c h e d u l i n gs y s t e mi sd e v e l o p e d u s i n gc + + b u i l d e r6 0 ，a n di tt a k e sh y b r i dg e n e t i ca l g o r i t h ma st h ec e n t u f l a l g o r i t h m ，t a k e sb a s i cd a t a b a s ea st h eb a s i si nt h i sa r t i c l e t h es y s t e mc a r l r e a l i z et h ei n i t i a ls c h e d u l i n go fp a r t si ns h o p c o n s i d e r i n gt h ec o m p l e x i t y o ft h ej o bs h o ps c h e d u l i n gp r o b l e ma n dt h en e c e s s i t yo ft h ei n t e r a c t i o n b e t w e e nm a na n dm a c h i n e s ，t h es y s t e mc a i lm o d i f yp a r to ft h es c h e d u l i n g r e s u l t s a i m e dt ot h ea c c i d e n t so c c u i t e dd u r i n gt h ec o u r s eo fp r o c e s s i n g , t h es y s t e ma l s oc o n t a i n st h er u n i o no fr e s c h e d u l i n g ，w h i c hc a nr e a l i z et h e p u r p o s eo fd y n a m i cs c h e d u l i n g v a l i d a t e db yas a m p l e ，i ti sp r o v e d t h a tt h e s c h e d u l i n gs y s t e mi se f f e c t i v ei nr e s o l v i n gj o bs h o ps c h e d u l i n gp r o b l e m k e yw o r d s ：m a n u f a c t u r i n gs y s t e m ，j o bs h o ps c h e d u l i n g ，g e n e t i c a l g o r i t h m ，s i m u l a t e da n n e l i n ga l g o r i t h m ，d y n a m i cs c h e d u l i n g 辽宁工程技术大学硕士学位论文 创新点声明 本人声明所呈交的学位论文是我个人在导师指导下进行 的研究工作及取得的研究成果：以混合遗传算法为核心算法， 用c + + b u i l d e r6 0 开发了动态车间调度系统，该系统不仅可以 对车间零件进行初始调度，还可以根据加工过程中所发生的意 外情况，实现重调度。 。 作者：妊鹞鑫。 日期：竺! ! ： 辽宁工程技术大学硕士学位论文 1绪论 1 1车间调度在企业生产中的重要性 科学技术的发展为制造业的技术进步创造了条件，同时也使制造企 业面临越来越激烈的竞争。企业必须在竞争中求生存，在竞争中求发展。 传统制造业面临着新的机遇和挑战，为了能在市场竞争中立于不败之 地，如何缩短产品上市时间，提高质量，降低成本是企业永无止境的追 求，要做到这些，不仅需要生产过程的自动化，而且要求与生产过程相 关的调度、计划、决策等也实现自动化。 1 1 1车间调度问题的定义 车间调度就是对一个可用的加工机床集在时间上进行任务集分配， 以满足一个性能指标集。典型的车间调度问题包括一个要完成的作业 集，每个作业由一个操作集组成；各操作的完成需要占用机床或其他资 源，并且必须按一些可行的工艺次序进行加工；每台机床可进行零件的 若干操作。在约束条件下，调度的目标是将作业合理地安排到各机床， 并合理安排作业的加工次序和加工开始时间，同时优化一些性能指标 9 1 o 在实际车间调度中，一般需要考虑两个方面的问题，一是生产作业 的调度，二是生产资源的分配。本文考虑生产作业的调度，把资源问题 当成约束来考虑。 1 1 2 车间调度的重要性 车间调度是制造系统生产管理的核心，生产管理任务顺利实施与完 成，最终要靠合理的车间调度来保证。它研究的是如何合理配置加工过 程的各种资源，减少零件的加工准备、等待与传送时间，从而提高设备 利用率与生产效率，降低生产成本。车间调度对任务的交货时间、各项 生产任务的生产周期、设备利用率和在制品占用量都有影响。因此，及 辽宁工程技术大学硕士学位论文 时准确的车间调度对生产系统的高效运行有着重要的影响，主要表现在 车问调度可以保证：生产计划的有效实施：高效低耗地使用生产资源； 均衡生产，减少在制品的资金占用。所以，车间调度是制造业生产中最 活跃和生产系统研究的前沿问题之一。 1 2车间调度问题概述 1 2 1车间调度问题的分类与特点 车间调度问题的分类，根据研究的侧重点不同有不同的分类方法。 ( 1 ) 按照资源约束种类和数量，可分为： 单资源车间调度( s i n g l er e s o u r c ec o n s t r a i n e d ) ：只有一种资源制约 着车间的生产能力。在绝大多数的相关科技文献中，单资源一般指车间 生产环境中，只有机床设备的数量不能同时满足所有可能可加工工序立 即被加工的要求。 双资源车间调度( d u a lr e s o u r c e c o n s t r a i n e d ) ：同时有两种资源制约 着车间的生产能力。机床设备往往是制约资源之一，车间有时会缺乏有 经验或一技之长的工人，也可能某种类型的刀具数量有限，因此这两种 资源可以是机床设备和工人或刀具。车间中也常常会发生一些辅助资源 有限的情况，如一个车间只有一辆或两辆自动物料运送车，然而需要同 时传送的零件数量可能较多，在这种情况下，自动物料运送车也会成为 制约车间提高生产能力的一个重要因素。同理，奇缺的刀具、夹具以及 运送零件的叉车、吊车和货盘等都可能成为第二种制约资源。 多资源车间调度( m u l t i p l er e s o u r c ec o n s t r a i n e d ) ：同时有两种以上 的生产所需资源制约着车间的生产能力。这些资源包括员工、机床设备、 机器人、物料运送系统和辅助资源，如货盘、夹具和刀具等。 ( 2 ) 按照零件和车间构成，可分为： 作业车间调度( j o bs h o p ) ：在这种车间中，机床设备的布局可以是 任意的，因此零件的加工路径也是任意的，并且各零件的工序内容和数 量也是任意的。这是一种最典型的车间调度形式。 流水车间调度( f l o ws h o p ) ：在这种车间中，每个零件都有相同的 辽宁工程技术大学硕士学位论文 加工路径。这样，机床设备的布局如同流水线一样，零件依次从流水线 的一端进入，最后从另一端流出“。 开放车间调度( o p e ns h o p l ：每个零件的工序之间的加工顺序是任 意的。零件的加工可以从任何一道工序开始，在任何一道工序结束。 单车间调度( s i n g l es h o p ) ；在这种车间调度中，每个零件只能有一 道工序。 ( 3 ) 按照加工特点，可分为： 。 静态车间调度( s t a t i cs c h e d u l i n g ) ：所有的零件在开始调度时刻已经 准备就绪。车间的调度不考虑零件在加工过程中出现的意外情况，如机 床突然损坏、零件的交货期提前、有更紧迫的零件要求被加工等等。 动态车间调度( d y n a m i cs c h e d u l i n g ) ：车间的调度要求考虑零件在 加工过程中出现的各种意外情况。这种调度方法要求调度能随时响应车 间加工能力的变化，在有突发事件出现后，能立即根据当时的车间加工 能力，对待加工零件重新展开调度，以确保在任何时候，都能保持车间 的加工性能指标处于最优或次优状态。 车间调度问题有以下特点： ( 1 ) 复杂性。一是生产因素的多样与复杂，二是车间调度问题是在 等式或不等式约束下优化某些性能指标，在计算量上往往是n p 完全问 题，因此，在求解车间调度问题上，一些常规的优化方法无能为力。 ( 2 ) 动态随机性。生产中会出现设备故障、急件插入、人员误操作 等不可预见因素，生产调度需要根据生产情况做出动态调整。 ( 3 ) 多目标性。车间调度往往是多目标的，可分为基于作业交货期 的目标、基于作业完成时间的目标、基于生产成本的目标等1 。 1 2 2车间调度问题的研究现状和研究方法 调度l 、口j 题的研究始于2 0 世纪5 0 年代，j o h n s o n 提出了解决 n 2 f c m a x 和部分特殊的n 3 f c m a x 问题的优化算法，代表调度理论 研究的开始；6 0 到7 0 年代建立了调度理论的主体并重视调度复杂性的 研究。随着7 0 年代后期调度理论研究的深入及各种交叉学科的发展， 又涌现了许多新的车间调度理论和方法。我国“八五”期间也有一些高 辽宁工程技术大学硕士学位论文 4 校和研究机构如清华大学、上海交通大学、西安交通大学、北京机械工 业自动化研究所等进行此类问题的研究，并已开发出相应的计算机辅助 生产调度与管理系统，逐步从理论研究阶段走向应用阶段。 虽然对车间调度领域的研究已有几十年的历史，但至今仍是一个研 究的热点和难点，存在的问题还很多。 ( 1 ) 车间调度很难形成一套系统的方法与理论，因为大多研究对 约束问题考虑不是很周全，建模时对真实环境也进行了大量的简化，还 不能很好地应用到实际生产中。 ( 2 ) 实际的生产系统是一个动态生产环境，即实际生产系统中存 在着很多不确定性的变化，如加工设备的故障与维修造成的加工环境的 变化，经常变化的市场需求所带来的任务变化，以及生产任务的变化导 致所追求的生产目标的变化等。所以，实际的调度应该是动态调度，只 用静态调度的理论解决问题不会达到最好的效果。 ( 3 ) 虽然针对车间调度问题开发了不少软件，但调度系统应用到 生产实际中，和实际结合一定会有不如意的地方，所以调度系统再发达， 也不可能完全忽略调度专家的作用。 ( 4 ) 多种调度方法结合的问题。在过去几十年中，人们将许多算 法应用于调度领域，但是人们使用各种调度算法需要特定的应用环境， 判断何种算法适合何种环境是一个很有现实意义的问题。 当然其他问题还很多，本文准备从以上后三个问题入手，进行车间 调度问题的研究。 经过5 0 多年的发展，车间调度问题的研究方法经历了从简单到复 杂、从单一到多元的过程。但由于车间调度的复杂性，至今尚未形成一 套系统的理论与方法。总结来说，现有的解决方法大体上可以分为以下 几种类型： ( 1 ) 启发式规则 1 9 5 4 年，j o h n s o n 提出了两台机床上f l o ws h o p 排序问题的最优算 法，从此人们开始对排序理论的研究。s t e v e n sa n dg e m m i l l ( 1 9 9 7 ) 用启 发式方法解决了两机器f l o ws h o p 的排序问题。这些启发式规则简单易 行，但难以得到全局优化结果，且对问题的性质与应用场合的依赖性较 辽宁工程技术大学硕士学位论文 强。 ( 2 )仿真方法 建立在排队论、p e t r i 网、极大代数等方法的基础之上，通过仿真分 析在不同情况下系统的性能来进行计划和调度，其效果依赖于仿真模型 的优劣( 蔡自兴，1 9 9 0 ) 。另外，对j o bs h o p 问题有较好性能的方法并 不能保证对f m s 调度问题同样有较好的结果( r a h i m i f a r da n d n e w m a n ，1 9 9 7 ) ； 。 ( 3 ) 经典运筹学中的分枝定界法、割平面法等被用来解决表达为 整数规则的调度问题( b e r r a d ae t a l ，1 9 8 6 ) 。这些解析方法可以解决规模 较小的一些问题，但是在解决多重复杂条件约束和含有不确定因素的调 度优化问题时结果不理想( a a n e ne t a l ，1 9 9 3 ) 。 ( 4 ) 模拟退火方法( s i m u l a t e da n n e a l i n g ，s a ) 。 模拟退火方法s a 模仿晶体的冷却过程，它渐近收敛于全局最优解， 但收敛速度较慢。m i t t e n t h a l 用s a 实现了单台机器n 工件的调度问题， s a 还被用于f l o ws h o p 排序、机器分组和有资源约束的调度问题 ( r a b e l oe t a 1 1 9 9 3 ) 。 ( 5 ) 神经网络方法( n e u r a ln e t w o r k s ，n n ) n n 已被成功地应用于解决组合优化问题，但在大规模、复杂调度 系统中，存在计算速度慢与结构参数难以确定的缺点。f o o 等( 1 9 9 8 ) 应用随机h o p f i e l d 网络来解决调度问题，构造网络能量函数一l y a p n o v 函数进行优化，当网络迭代收敛时，能量函数达到最小。 ( 6 ) 基于知识的方法 基于知识的调度方法用专家系统自动产生调度来辅助人去调度 ( f a r h o o d if a 1 9 9 0 ，d o - 1 a b l e g e r iz ，1 9 9 3 ，b e n a r i e h ，1 9 8 6 ) 。它将传统的调 度方法与基于知识的调度评价相结合，对设计用于生产实际的高效益、 高柔性的c i m s 具有启发意义。 ( 7 )遗传算法 遗传算法是一种兼顾优化效果和计算效率的方法，适合于在复杂而 庞大的搜索空间中寻找优化解，在搜索过程中自动获取和积累有关搜索 空间的知识，并自适应地控制搜索过程。算法简单、鲁棒性强，易于并 辽宁工程技术大学硕士学位论文 6 行分布处理，非常适合于解决调度问题( o r v o s h d a v i d1 9 9 4 ，c h i ua n df u 1 9 9 7 f i e u r va n dg o u r g a n d19 9 8 ) 。1 9 8 5 年d a v i s 首次将遗传算法用于解 决调度问题，d a g l i 提出了排序中局部交换、环状交换及序基变异操作 等 15 l 。 ( 8 ) 各种算法的混合算法。由于各种调度算法都不同程度地存在 着这样或那样的优缺点，所以，近来人们开始把各种近似算法的组合应 用研究作为热点，以弥补各自的缺点，发挥各自的优势，+ 达到次优的目 的。 1 2 3 车间调度问题的研究策略 由于调度问题的复杂性，其研究策略主要形成了以下几种： 分解与成组策略利用分解生产计划或成组技术的调度策略可以 大大降低问题的计算复杂性和规模，求得调度问题的较优解，同时优化 系统的一些性能指标。 实时或动态重调度策略车间制造过程的随机性、不确定性需要 不断进行重调度，以处理突发的事件。基于目前的研究，对于动态调度 的具体策略有：周期调度，事件驱动调度，周期与事件驱动的混合调度 等。 多耳标权衡调度策略实际调度问题往往是多目标的，而这些目 标往往相互冲突。对此类多目标优化问题，常用数学规划中的约束法、 评价函数法、分层序列法等。 1 3本论文要进行研究的内容 1 3 1研究的内容 随着市场经济的发展，需求多样化更加明显，所以生产的批量越来 越小，又由于作业车间调度问题的典型性，本文将研究作业车间调度问 题且把批量设定为1 。本论文将根据车间调度存在的问题完成以下工作： ( 1 ) 对调度问题进行科学描述，并分析制造系统的车间状况。 ( 2 ) 介绍遗传算法的发展过程、原理、数学基础以及遗传操作。 辽宁工程技术大学硕士学位论文 ( 3 ) 针对j o bs h o p 车间调度的具体情况， 算法运算，给出该问题的数学模型。 ( 4 ) 建立加工基础数据库，包括设备库、 是车间调度决策的基础数据。 应用混合遗传算法进行 零件库、工艺库，它们 ( 5 ) 根据c + + b u i l d e r 的可视化特性，编制车间调度的可视化软 件。该系统以混合遗传算法为核心算法，以基础数据库为基础，可以对 j o bs h o p 问题实现初始调度。根据车间实际情况，可对调度结果进行部 分修改，实现人机结合。若实际生产中出现意外情况，可根据需要进行 重调度。 1 3 2 研究的意义 通过本文的研究，将可以看出：混合遗传算法是解决车间调度问题 的有效方法，用该方法解决车间调度问题，可以更快更准确地找到近似 最优解。 用调度软件运行的结梁，由于是在许多假设情况下得出的，并不一 定十分完善，可能需要作部分修改。本文所做出的动态车间调度系统可 以允许对调度结果进行局部变动，这样更好地发挥了专业调度员的作 用。通过该文的完成，还可以分析加工过程中出现的意外情况，对车间 实行重调度。 辽宁工程技术大学硕士学位论文 8 2制造系统车间调度情况分析 2 1调度问题及其描述 2 1 1调度问题 调度问题通常指对生产过程的作业计划，譬如工件在机器上的加工 顺序、生产批量的划分等。就生产方式而言，调度问题可分为开环车间 ( o p e ns h o p ) 型和闭环车间( c l o s e ds h o p ) 型。开环调度问题，也称加工排 序问题，它本质上只研究工件的加工顺序，即定单所要求的产品在所有 机器上的加工排序，其中定单均来源于顾客，不考虑库存的设立。闭环 调度问题除研究工件的加工顺序外，还涉及各产品批量大小的设置，即 在满足生产工艺约束条件下寻找一个调度策略，使得所确定的生产批量 和相应的加工顺序下的生产性能指标最优，其中顾客需求的产品均由库 存提供，生产任务一般只由产品存储策略来决定。 对于m 台机器 m ，m 。 对 个工件的加工过程，所谓调度就是分配 各工件在各机器上的加工时间。调度问题通常用甘特图( g a n t tc h a r t ) 表 示，图2 1 为4 个工件、3 台机器的面向机器的甘特图，而图2 2 则是 相应的面向工件的甘特图。 图2 - 14 个工件、3 台机器的面向机器的甘特图 辽宁工程技术大学硕士学位论文 十 五工工强 也e 田 图2 24 个工件、3 台机器的面向工件的甘特图 2 1 2机器加工数据和特性的描述 调度问题中，通常一个工件以包含_ 个操作( o p e r a t i o n ) q l ， ，d f 。 ， 每个操作d ，的加工时间或需求为岛。若蜂= 1 ，则工件以仅包含一个操作 p ，简记其加工时间为f 。称工件以的第1 个操作可执行的时刻为释放 时间( r e l e a s ed a t e ) ，记为i 。记加工操作q 的机器集为心 m i ，坂 ，q 可以在“，中任何一台机器上加工。许多实际生产系统中，各机器可装备 相同或不同的工具，操作可以在任何一台装备合适工具的机器上加工， 这就是生产系统所谓的柔性，该调度通常称为多目的机器( m u l t i p u r p o s e m a c h i n e s ) 调度。若q ，的加工过程同时占有h ，中所有机器，则该调度问 题称为多处理机任务调度( m u l t i p r o c e s s o rt a s ks c h e d u l i n g ) 。对于每一个 工件以，记r 时刻完成以的加工费用函数为z ( t ) ，记计划完成时间或交 货期为z ，与之相关的权重或优先权( w e i g h t ) 为q 。 若同一机器上既没有任意两个时间区间重叠，也没有分配给同一个 工件的任意两个时间区问重叠，并且满足调度问题的一些特殊工岂约 束，则称一个调度为可行( f e a s i b l e ) 调度。进而，称使得调度准则或指标 最优的可行调度为最优调度( o p t i m a l ) 。 通常，工件的加工特性可用六元组尸= 届，岛，届，反，屈，尾1 来表示， 其中： 辽宁工程技术大学硕士学位论文 届用来表示加工方式，包括抢占式( p r e e m p t i o n ) 和非抢占式 ( n o n p r e e m p t i o n ) 。其中，抢占式加工中操作在加工过程中可以被打断， 再在原机器或别的机器上重新开始；非抢占式加工则一旦操作开始，直 到加工完毕，不能被其他加工打断。通常，记抢占式加工为届= p m t n ， 而非抢占式加工则不在中出现届。 届用来表示工件间的加工优先关系( p r e c e d e n c er e l a t i o n ) 。该优先 关系可以用非循环有向图g = ( 矿，4 ) 来表示，+ 其中v = 1 ，聍 表示工件， ( f ，k ) a ，当且仅当以必须在以开始加工之前完成。若g 为任意非循环有 向图，则记孱= p r e c 。若g 对应树( t r e e ) ，则记履= t r e e 。若g 对应链( c h a i n ) ， 则记房= c h a i n 。若g 对应的图具有系列一并行( s e r i e s p a r a l l e l ) 特性，则记 乜= 印一g r a p h 。若调度问题不考虑工件加工的优先权，则卢中不出现压。 屈用来表示工件的准备加工时间。若0 ，则记尼= ；若所有 = 0 ，则卢中不出现屈。 屈表示加工时间或操作数量的限制。若屈记作只= 1 ( 或岛= 1 ) ， 则每个工件( 或操作) 有一次操作需求( 或加工时间为1 ) 。有时，屈也 可为一些具有明显意义的别的值，如n l ，2 ，碡= d 。 屈用来表示交货期信息。屈= 吐表示有交货期要求，否则中不 出现屈。 孱用来表示批量信息，即工件是否成批联合进行加工。批量调 度中，同批的各工件的完成时间等于该批量的完成时间，假定各批量的 加工设置时间相同且与加工顺序无关。屈= p b a t c h 或成= s b a t c h 分另 表示批量长度等于该批量中所有工件的加工时间的最大值或加工时间 之和。若不考虑批量调度，则中不出现展。 2 1 3机器加工环境和加工性能指标的描述 机器加工环境通常可用一个参数串d = q 口：来表示，其中 口。e 0 , p ，a ，r ，p 删，q m p m ，g ，z ，o ，j ，f ，符号0 表示空。若t 2 i = o ，则 口= 吃。若a 。 o ，p ，o ，r ，p m p m ，q m p m ，则每个工件仅包含一个操作。 若q = o 则每个工件必须在一个规定机器上加工。 若呸 尸，o ，r ，则表示并行机加工环境，每个工件可以在 m i ，m m 辽宁工程技术大学硕士学位论文 中任一台机器上加工。其中，= p 表示相同并行机( i d e n t i c a lp a r a l l e l m a c h i n e s ) ；q = q 表示均匀并行机( u n i f o r mp a r a l l e lm a c h i n e s ) ；= r 表 示不相干的并行机( u n r e l a t e dp a r a l l e lm a c h i n e s ) 。 若= p m p m 或剑删订，则表示加工环境对应具有相同或均匀速度 的多目的机器。 若= f g ，x ，0 ，j ，f ，则表示多操作模型，即每个工件包含多个操作。 同时，所有机器是专用性的，即。，只有。二个元素，且各操作间存在优先 顺序。该调度称为一般车间( g e n e r a ls h o p ) 调度，记= g 。 对于j o bs h o p 调度问题，记瞄= j ，假定各操作的优先顺序为 q l 斗q 2 寸哼，i = 1 ，以，且一般假定, u u u i , j + i ，j = 1 ，q 一1 。若允许 如一j + l 不成立，则称之为可重机器j o bs h o p ( j o bs h o p w i t hm a c h i n e r e p e t i t i o n ) 。对于j o bs h o p 问题，结合考虑工件特性，若设置屈为吩兰2 ， 则所有工件最多包含2 个操作。 对于f l o ws h o p 调度问题，记= f ，它是j o bs h o p 的一个特例，即对 f _ 1 ，竹和_ ，= l ，m 有= m ，心= m ， 。若f l o ws h o p 中各机器上工件的加 工顺序相同，则称为置换f l o ws h o p 。若f l o ws h o p 不考虑操作的优先 顺序，则称之为o p e ns h o p 。记口= o 若问题为f l o ws h o p 和j o bs h o p 的 混合问题，则称之为m i x e ds h o p ，记a l = x 。 口，表示机器数。若机器数给定且已知，则记以为相应的数值；若机 器数给定但任意，则记= k ；若机器数任意，则记= 0 。 鉴于j o bs h o p 的代表性，现以n 个工件、m 台机器的j o bs h o p 为例 ( 约定调度问题为非抢占式，每个工件或操作不能在同一机器上多次加 工，不考虑工件加工优先权和批量) 来讨论调度性能指标。为了使表达 清晰，有必要先介绍一些相关变量和符号。 ( 1 ) ，：工件z 进行第_ ，道操作的等待时间。 ( 2 ) ：工件以的总加工等待时间，即w f = 。 ( 3 ) e ：工件一的加工完毕时间，则e = i + ( + 所) 。 j = l ( 4 ) e ：工件t 的流经时间( f l o w t i m e ) ，即鼻= c f 一。 辽宁工程技术大学硕士学位论文 1 2 ( 5 ) 厶：工件以的推迟完成时间( 1 a t e n e s s ) ，即= g - d i 。 ( 6 ) z ：工件以完成的拖后时间( t a r d i n e s s ) ，即l = m a ) ( 厶，0 ) 。 ( 7 ) 巨：工件正完成的提前时间( e a r l i n e s s ) ，即e = m a ) 【 一厶，0 ) 。 ( 8 )：机器m 的空闲时间，即= c 咄一巧， 其中 j = 1 c 聃= m a x fc l ，g ，为机器m 上加工的工件总数。 ( 9 ) 虬( t ) ：f 时刻处于等待状态的待加工工件数。 0 0 ) ，( f ) ：t 时刻正在加工的工件数。 ( 1 1 ) m ( t ) ：f 时刻已加工完毕的工件数。 ( 1 2 ) 帆( f ) ：t 时刻未加工完毕的工件数。 我们现在给出调度问题的一些典型性能指标。 ( 1 )基于加工完成时间的性能指标：最大流经时问，眦，总流经时 间f ，加权流经时间只，平均流经时间f ；最大完成时间c m 。 r = l i = 1 ( m a k e s p a n ) ，平均完成时间e 。 ( 2 )基于交货期的性能指标：平均推迟完成时间三，最大推迟完成 n 时间三m 。；平均拖后时间于，最大拖后时间k ，总拖后时间z r , f = l 拖后工件个数1 6 ( 完成时间大于交货期的工件个数) 或拖后工件比 例叼。 ( 3 )基于库存的性能指标：平均待加工工件数瓦；平均未完成工 件数鼠；平均已完成工件数；平均正在加工工件数死；平均机器 空闲时间t ；最大机器空闲时间。 ( 4 )多目标综合性能指标：流经时间和总拖后时间的综合，如 户+ 且z ，其中五为权重；m a k e s p a n 与总拖后时间的综合，即 辽宁工程技术大学硕士学位论文 月 + a 王：e t 指标，即心巨+ 属巧) ，其中q 和尼为权重。 f l 2 1 4性能指标的正规性、等价性和活动调度 定义2 1 1对于一个调度问题，称性能指标函数r 是正规的，若 对于满足不等式关系c l c l ，c o5 c o 的任意两组加工完成时间 g 和 e ， ，对r 必满足r ( c l ，e ) r c 1 ，g 7 ) 。 定义2 1 2对于j o bs h o p 调度问题，称两个性能指标4 和口是等 价的，若性能指标a 下的最优调度也对应性能指标曰下的最优调度( 称彳 的最优性蕴涵了b 的最优性) 。 定义2 1 3称一个调度为活动调度，如果在不推迟其他操作或破 坏优先顺序的条件下，其中没有一个调度可以提前加工。 定义2 1 4称一个调度为半活动调度，如果在不改变机器上加工顺 序的条件下，其中没有操作可以提前。 定义2 1 5称一个调度为非延迟调度，如果至少存在一个工件等待 加工时，对应地不存在相应的空闲机器。 以上定义表明，若j o bs h o p 处于非活动调度下，则一定可以找到某 些操作，使其可以更早加工。譬如当一个操作在前道工序完成后，可将 其插入到同机器中操作时间比它长而出现时刻比它早的另一个操作 之前，也即在那个操作还未开始加工前插入到机器的空闲时间内。显然， 通过将非活动调度转化为活动调度，正规性能指标必然有所改善。 对于正规调度指标，如最大完成时间，业已证明最优调度必为活动 调度。因此，在设计优化算法时，如果将搜索空问限于活动调度集，不 仅能保证最优调度的存在，而且能够提高优化效率【7 i 。 三者的包含关系如图2 - 3 所示。 辽宁工程技术大学硕士学位论文 1 4 图2 - 3 三种类型调度的关系 n d 表示非延迟调度集；a c 表示活动调度集；s a c 表示半活 动调度集 2 2制造系统车间情况分析 随着经济发展的不断全球化，企业之间的竞争日益加剧，单件小批 生产方式已成为当今制造业的主流。特别是信息化程度较低的重型机械 制造企业，它们所加工的产品种类繁多，调度工作尤其复杂，要想在竞 争中立于不败之地，有效地利用现代化科技手段，协调、调度好企业生 产过程中出现的各种问题是一项具有现实意义的工作 4 1 j 。 车间作为独立又相对完整的制造单元，是制造企业物流与信息流的 交汇点，企业的制造信息最终将在这里被物化出来。制造业的发展在近 一、二十年间从生产主导快速地演变成市场主导、竞争主导，因而也使 得生产现场的状况起了很大的变化，传统现场管理方式已无法适应这一 新的局面，主要变化表现在以下方面： ( 1 ) 产品生命周期缩短。产品汰旧换新加速迫使产品设计、工程及 生产部门之问的关系越来越紧密。生产单位不断面临新的零组件、新的 设备、新的工艺及经常性的工程变更，生产现场需要一套实时生产指挥 系统，有效地指引生产人员规范作业，同时能正确迅速地将生产状况反 映给设计制造管理部门，及时找出新产品生产问题。 ( 2 ) 多品种小批量的生产形态。由于少量多样的生产形态，现场随 辽宁工程技术大学硕士学位论文 时充斥着众多不同的制造指令、不同的在制品和零组件，生产单位必须 具备混线生产能力，弹性而有效地在一天当中应对不同产品的生产所 需。 ( 3 ) 市场变化迅速难以预测。随着经济的发展，人们的需求也在不 断变化，市场当然要适合人们的需要而迅速变化。制造企业要能应对变 化的市场需求，生产现场也要能机动地应对变化快速且难以预测的定单 式生产形态。 ( 4 ) 国际竞争日益激烈。经济的发展日渐国际化，所面临的不仅是 国内竞争，还要面对全球各地一流产品的竞争压力。就生产而言，所面 临的是要不断提升产品品质及降低生产成本。过去在计划经济下，只把 生产现场当作是一个黑箱作业，如今在市场经济的竞争压力下必须将黑 箱作业透明化，找出任何影响品质及成本的问题，并寻求具体的对策。 2 3 阜新矿务局机电总厂车间调度情况分析 阜新矿务局机电总厂是中国煤炭系统集检修与制造为一体的综合 型机械加工企业。机电总厂主要承担部属系统、本局和地方的矿山机电 设备制造和大修任务。厂内的产品检测、试验设备齐全，是中国煤炭系 统挖掘维修中心及齿轮加工中心。其中齿轮加工车间是该厂的一个重要 车间，齿轮类型多，工艺复杂。 由于资金、生产状况的制约，齿轮加工车间的设备大多比较陈旧， 加工精度与自动化程度都无法同数控机床与加工中心相比，加工精度往 往依靠生产人员的经验来保证，而且沿用原有的生产管理模式，在这种 情况下，良好的生产调度对于提高生产效率的作用更为显著。因此建立 一个实用的生产调度系统，除了具备先进的生产调度算法外，还需密切 结合企业的生产特点。 机电总厂现有的生产调度模式如图2 - 4 所示。可以看出，该，的车 间调度并不是很系统、规范，只是依照经验来制定调度计划。本文将以 齿轮车间的部分工件的调度为例，说明在这样的制造车间中应用动态车 间调度系统进行调度，可以收到良好的效果。 齿轮车间部分工件的工时定额表见表2 - 1 ，其中工时以小时为单位。 辽宁工程技术大学硕士学位论文 1 6 具体的调度操作将在系统实例应用中说明。 图2 4 生产调度步骤 表2 - 1 齿轮车间工时定额表 g 1 印8 g 1 6 0 8f 8 0 l 1 1f 8 0 1 1 1f 1 5 0 1 0 1 0 1f 1 5 0 1 0 1 0 2 图号 0 5 1 80 5 3 90 1 0 10 2 0 3- 4 主动从动轴圆弧圆弧轴圆弧圆弧 名称 伞齿轮伞齿轮 伞齿轮伞齿轮伞齿轮伞齿轮 编号 23456 工序 工时工序工时工序工时工序工时工序工时工序工时 工 1 生 8 车 8 生 0 5 主 3 盘 6 至 7 件 2 铣齿 9铣齿 8 仿型 1平磨1 5 外磨 2 铣齿 6 工 时 3 钳 2钳3 5钳o 3 铣齿 2 5 铣齿 6钳 1 2 定 4 外磨 1对滚l 外磨 o 6钳0 8锚0 5外磨 1 2 额 表 5对滚o 6铣齿1 5对滚0 1 对滚 0 1对滚 0 - 3 6对滚o 1 辽宁工程技术大学硕士学位论文 该车间的设备状况如下：有车床两台，用于进行车削加工；插齿机 一台，用来进行齿轮加工；平台用于进行钳工操作；磨床一台用来进行 磨削操作；对滚机一台来进行对滚操作；仿形机一台用来进行仿形操作。 2 4本章小结 本章介绍了调度问题的一些科学描述方法及其常用符号所表示 的意义。对制造系统车间情况进行了分析，同时根据实际应用的需要， 介绍了阜新矿务局机电总厂齿轮加工车间的几个主要零件的加工工序 情况及设备信息。 辽宁工程技术大学硕士学位论文 3遗传算法的理论基础 3 1 遗传算法概述 3 1 1遗传算法的形成和发展 遗传算法( g e n e t i ca i g o r i t h m s ，简称g a ) 是一种借鉴生物界自然选 择和自然遗传机制的高度并行、随机、自适应搜索算法。它是模拟自然 界生物进化过程中“物竞天择，适者生存”的原理而进行的一种多参数、 多群体同时优化方法。遗传算法是j h o l l a n d 于1 9 7 5 年受生物进化论的 启发而提出的。遗传算法适用于最优化问题，要归功于h o l l a n d 的学生 d ej o n g ，而g r e f e n s t e t t e 则开发了第一个遗传算法软件，称为g e n e s i s ， 对遗传算法的推广普及起了重要作用。1 9 8 9 年美国伊利诺大学的 g o l d b e r g 所著的“g e n e t i ca l g o r i t h m si nr e a r e h ，o p t i m i z a t i o n ，a n dm a c h i n e l e a r n i n g ”，成为对遗传算法研究影响力最大的专著。2 0 世纪8 0 年代中 襄以来是遗传算法的蓬勃发展期，以遗传算法为主题的多个国际会议在 世界各地定期召开，如1 9 8 5 年在美国卡耐基梅隆大学召开的第一届 国际遗传算法会议i c g a 8 5 ，以后该会议每隔一年举行一次。 我国有关遗传算法的研究，从2 0 世纪9 0 年代以来一直处于不断上 升的时期，特别是近年来，遗传算法的应用在许多领域取得了令人瞩目 的成果p 】。 3 1 2 遗传算法的基本思想和特点 遗传算法是从代表问题可能潜在解集的一个种群( p o p u l a t i o n ) 开始 的，而一个种群则由经过基因( g e n e ) 编码( c o d i n g ) 的一定数目的个体 ( i n d i v i d u a l ) 组成。每个个体实际上是染色体( c h r o m o s o m e ) 带有特征的实 体。染色体作为遗传物质的主要载体，其内部表现是某种基因组合，它 决定了个体的性状的外部表现。因此，在一开始需要实现从表现型到基 因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰 的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中 个体的适应度( f i t n e s s ) 大小挑选个体，并借助于自然遗传学的遗传算 辽宁工程技术大学硕士学位论文 1 9 子( g e n e t i co p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) ，产生出 代表新的解集的种群。这个过程将导致种群像自然进化一样，后生代种 群比前生代更加适应于环境，末代种群中的最优个体经过解码 ( d e c o d i n g ) ，可以作为问题近似最优解。 遗传算法与传统优化算法相比，有如下特点： ( 1 )自组织、自适应和自学习性( 智能性) 。应用遗传算法求解 问题时，在编码方案、适应度函数及遗传算子确定后，算法将利用进化 过程中获得的信息自行组织搜索。自然选择消除了算法设计过程中的一 个最大障碍，即需要事先描述问题的全部特点，并要说明针对问题的不 同特点算法应采取的措施。因此，利用遗传算法的方法，我们可以解决 那些复杂的非结构化问题。 ( 2 ) 遗传算法的本质并行性。主要表现在两个方面，一是遗传算 法是内在并行的，即遗传算法本身非常适合大规模并行。可以说，适合 在目前所有的并行机或分布式系统上进行并行处理，而且对并行效率没 有太大影响。二是遗传算法的内含并行性。由于遗传算法采用种群的方 式组织搜索，因而可同时搜索解空间内的多个区域，并相互交流信息。 ( 3 )遗传算法对问题的参数编码成“染色体”后进行进化操作， 而不是针对参数本身，这使得它不受函数约束条件的限制。 ( 4 ) 遗传算法使用的遗传操作均是随机操作，同时根据个体的适 应度信息进行搜索，而无需其他信息。 ( 5 ) 遗传算法具有全局搜索能力，最善于搜索复杂问题和非线性 问题。 3 1 3遗传算法的应用情况 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖 于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很 多学科。主要有： ( 1 )函数优化。函数优化是遗传算法的经典应用领域，也是对其 进行性能评价的常用算例。 ( 2 ) 组合优化。随着问题规模的扩大，组合优化问题的搜索空问 辽宁工程技术大学硕士学位论文 急剧扩大，有时在目前的计算机上用枚举法很难或者甚至不可能达到其 精确最优解。对于这类复杂问题，人们已意识到应把精力放在寻求满意 解上，而遗传算法则是寻求这种满意解的最佳工具之一。 ( 3 )生产调度问题。生产调度问题在许多情况下所建立起来的数 学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简 化太多而使得求解结果与实际相差甚远。遗传算法已成为解决复杂调度 问题的有效工具，在作业车间调度、流水线车问调度、生产规划、任务 分配等方面遗传算法都得到了有效的应用。 ( 4 )自动控制。在自动控制领域中许多与优化相关的问题需要求 解，遗传算法的应用日益增加，并显示了良好的效果。例如用遗传算法 进行航空控制系统的优化、基于遗传算法的模糊控制器优化设计、基于 遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计 和权值学习，都显示出了遗传算法在这些领域中应用的可能性。 ( 5 ) 机器人智能控制。机器人是一类复杂的难以精确建模