（系统工程专业论文）多重入制造系统的在线重调度方法研究.pdf

摘要 摘要 随着调度问题的深入研究，重调度问题越来越受到人们的关注。在复杂的多 重入制造系统中，多变的市场环境，生产线的随机扰动，生产工艺的变更等不 确定因素将导致原有的优化调度方案不再适用。何时采取重调度，如何进行重 调度，这是重调度问题研究的重点，本论文的工作也围绕这两部分展开。 针对已有重调度策略的不足以及多重入制造系统不确定性特点，设计了一种 基于模糊p e t r i 网推理的重调度判定方法，建立了模糊p e t r i 网形式化推理机， 然后以实际半导体生产线为背景举例说明了模糊p e t r i 网建模过程，并通过实 际的生产线模型仿真验证了方法的有效性。 针对现有的重调度方法的局限性，以充分利用设备空闲时间为思想设计了设 备故障扰动下单台设备匹配重调度方法( s i n g l em a c h i n em a t c h - u p r e s c h e d u l i n g ，s m u r ) 和设备组匹配重调度方法( m a c h i n eg r o u pm a t c h - u p r e s c h e d u li n g ，g m u r ) ，然后以m i n i f a b 为生产模型，建立了输入层、决策层、 重调度层和评价层四层架构的重调度模块，仿真比较了s m u r 、g m u r 、全局生成 式重调度方法( f u l lg e n e r a t i o nr e s c h e d u l i n g ，f g r ) 和右移重调度方法( r i g h t s h i f tr e s c h e d u l i n g ，r s r ) 四种重调度方法，证明了s m u r 和g m u r 在稳定性和 有效性方面的优越性。 最后，针对某实际的半导体生产线设计并开发了基于e m p l a n t 仿真平台的在 线重调度系统。设计了一种考虑多扰动因素的重调度策略，采用全局修正式重 调度方法进行重调度。该系统己用于实际生产，实践表明系统对扰动有快速响 应的能力。 关键词：多重入，半导体制造，重调度，模糊p e t r i 网，匹配重调度 a b s t r a c t a b s t r a c t t h er e s e a r c ho nr e s c h e d u l i n gb e c o m e sm o r ei m p o r t a n tw i t ht h ed e v e l o p m e n to f t h es c h e d u l i n gt h e o r y i nar e a lr e - e n t r a n tm a n u f a c t u r i n gs y s t e m , t h e r ea r em a n y u n c e r t a i n t i e s ，s u c ha st h ef l u c t u a t i n gm a r k e te n v i r o n m e n t ，t h ed i s t u r b a n c e so ft h e p r o d u c t i o nl i n ea n dt h ep r o c e s su p d a t eo ft h ep r o d u c t s ，w h i c hm a k et h ee x i s t i n g o p t i m i z e ds c h e d u l i n gp l a ni n f e a s i b l e w h e na n dh o wan e ws c h e d u l es h o u l db eb u i l t a r et h ek e y p o i n t so f t h er e s c h e d u l i n g , w h i c ha r ea l s ot h em a i nc o n t e n t so ft h i sp a p e r f i r s t l y , w ep r o p o s e dan e wr e s c h e d u l i n gp o l i c yb a s e do n af u z z yp e t r in e t ( f p n ) r e a s o n i n gm a c h i n e ，a c c o r d i n g t ot h em a i nc h a r a c t e r i s t i c so far e e n t r a n t m a n u f a c t u r i n gs y s t e m w ed e s c r i b e dt h em o d e l i n gp r o c e s so ft h ep r o p o s e dm e t h o d w i t has e m i c o n d u c t o rp r o d u c t i o n1 i n em o d e l t h e nw ed e m o n s t r a t e dt h ev a l i d i t yo f t h ep r o p o s e dm e t h o dw i t har e a ls e m i c o n d u c t o r p r o d u c t i o nl i n em o d e lb ys i m u l a t i o n s e c o n d l y , w ep r e s e n t e dt w om a t c h u pr e s c h e d u l i n gm e t h o d sw i t hc o n s i d e r a t i o n o nt h em a c h i n e s u n f o r e s e e nb r o k e - - d o w n o n ei sf o ro n em a c h i n e ，c a l l e da ss i n g l e m a c h i n em a t c h 。u pr e s c h e d u l i n g ( s m u r ) t h eo t h e ri sf i tt ot h em a c h i n eg r o u p ， c a l l e da l sm a c h i n eg r o u pm a t c h - u pr e s c h e d u l i n g ( g m u r ) am i n i f a bm o d e lw a su s e d t ov a l i d a t et h ep r o p o s e dm e t h o d sb ys i m u l a t i o n t h es i m u l a t i o nr e s u l t ss h o w e dt h a t t h es t a b i l i t ya n du t i l i t yp e r f o r m a n c e sw e r ei m p r o v e d f i n a l l y , w ed e s i g n e da n dd e v e l o p e da no n l i n ef u l lr e s c h e d u l i n gs y s t e mb yu s i n ga s i m u l a t i o nt o o lc a l l e da se m p l a n t i th a sb e e na p p l i e dt oar e a ls e m i c o n d u c t o rf a c t o r y t oa s s i s td a i l y j o bd i s p a t c h i n g k e yw o r d s ：r e e n t r a n t ，s e m i c o n d u c t o rm a n u f a c t u r i n g ，r e s c h e d u l i n g ，f u z z yp e t r in e t r e a s o n i n g , m a t c h u pr e s c h e d u l i n g 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 岳斌 川年弓其 7 日 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 武加 菇钥 一力专年 第1 章绪论 第1 章绪论 制造业是国民经济的支柱产业，其发达程度体现了一个国家的科学技术和 生产力发展水平。作为人类经济生活的重要单元，自1 4 世纪以来，制造业一直 处于变迁过程中。1 8 世纪末至1 9 世纪4 0 年代，出现了以设备大工业为基础的 制造行业；1 9 世纪末2 0 世纪初，形成了以流水线作业为典型特质的制造业；2 0 世纪7 0 年代，出现了具有很大竞争力的日本“丰田生产方式 ( 精益生产) ；2 0 世纪的最后十年，基于日本“丰田生产方式”，结合信息技术的先进成果，逐步 形成了“大规模定制”的新型生产组织方式。 多重入制造系统的研究始于8 0 年代术，是随着半导体生产系统的发展而兴 起的。与其他类型的制造系统不同，它具有很强的重入性。所谓多重入是指工 件在不同的加工阶段经常重复访问某些机器。正是由于这类制造系统的多重入 性使其调度问题更为复杂。本文将以多重入生产线的典型代表半导体生产 线作为研究对象，对其重调度问题展开研究。 1 1 半导体生产线简介 1 1 1 半导体制造的工艺流程 首先让我们了解下半导体制造工艺。半导体制造是一个极其复杂的制造过 程1 ，2 ，3 1 ，这个过程中用于生产半导体的硅材料从高光亮洁薄片的形式最终转变为 半导体芯片。半导体的制造过程可以分为四个部分：晶圆片加工、中试、封装 及终测，如图1 1 所示。 第1 章绪论 晶嘲片 ， 、 f1 | f i ? ， 、 晶圆片加工 中试封装终试 图1 1 半导体制造过程的基本步骤 在半导体制造整个过程中，以晶圆片加工过程最为复杂、资金最为密集， 通常称为半导体生产线( s e m i c o n d u c t o rp r o d u c t i o nl i n e ) 。对于复杂的半导体器 件( 如微处理器) ，其工序多达数百步。为了防止尘埃污染晶片，许多工序都必 须在洁净的环境下进行；晶圆片以卡( l o t ) 为单位，一卡晶圆片一般作为一个 整体进行加工，加工完毕后再流向下一工序。晶圆片加工需要使用各种复杂昂 贵的加工设备，通过各种物理、化学加工工序在晶圆表面形成所需的电路层， 这些加工工序主要包括：氧化( o x i d a t i o n ) 、淀积( d e p o s i t i o n ) 、注入( i m p l a n t ) 、 溅射( s p u t t e r ) 、光刻( l i t h o g r a p h y ) 、刻蚀( e t c h i n g ) 、清洗( c l e a n ) 等。晶圆 片加工的具体过程如图1 2 所示。 2 第1 章绪论 图1 2 品圆片加f t 的基本工艺流程 1 1 2 半导体生产线的主要特征 与传统的制造系统相比，半导体生产线具有以下几个鲜明的特征： ( 1 ) 工艺流程复杂 典型的半导体产品的j n t 流程往往包括2 5 0 - - - - 6 0 0 步，使用的设备种类达 6 0 - 8 0 种，设备台数多达上百台。工件在加工过程中由于质量问题可能会返回 到前面若干工序重新加工，这种现象称为返工。返工现象的出现使得原本直线 型的工艺流程出现了一些环路，这大大增加了工件调度的难度。 ( 2 ) 多重入性 在半导体制造过程中，重入现象非常的普遍。工件在加工过程的不同阶段 会多次访问同一台设备，这主要是由两个原因造成的：一是半导体元件是层次 化的结构，每一层都是以相同的方式生产，只是加入的材料不同或精度有所变 化，因此可以使用同种类型的设备进行加工；二是由于半导体加工设备很贵， 为了最大化设备的利用率，某些设备被用于加工多种不同的工序。 第1 章绪论 图1 3 典型的可重入生产系统 如图1 3 是一个可重入系统的简化模型，在这个模型中共有两台加工设备 ( m 1 ，m 2 ) ，四个缓冲区( b 1l ，b 1 2 ，b 2 1 ，b 2 2 ) ，图中的箭头指示了一个工件 加工经过的路径，由图可见这个工件加工的不同阶段先后两次经过了m 1 和m 2 ， 正是由于这种可重入性，使得设备等待队列的长度很难预测，生产线往往出现 多个瞬时瓶颈。 ( 3 ) 混合加工方式 由于半导体生产线不同工艺使用的设备类型各异，其加工方式也呈现多样 化。例如氧化扩散设备是一种批加工设备，可以将多卡相同工序的工件组批加 工，其加工时间与只加工一卡的时间相同；光刻设备需要针对不同的产品更换 相应的掩膜板，其加工方式是按片加工，即将每一卡中的晶圆片一片一片的进 行曝光处理；还有像离子注入设备，它允许同时加工多片晶圆片。混合n - r 方 式的存在给半导体生产线调度带来了进一步的复杂性。目前大量的研究都将上 述多种加工方式简化为单卡加工和批加工两种方式。 1 1 3 半导体生产线不确定因素 半导体生产线具有很强的不确定性，具体表现为以下几点： ( 1 ) 设备情况变化 设备情况的变化包括旧设备淘汰、新设备投入、设备维护及不可预见性的 设备故障等。这些情况是影响半导体生产调度的重要因素，其中最为常见的是 设备预防维护和设备突发性故障。 4 第1 章绪论 ( 2 ) 客户需求变化 客户需求的变化主要包括订货量的变化、交货期的变化和产品品种更换及 特殊工艺的要求等。 ( 3 ) 加工瓶颈变化 一般的，半导体生产线在设计初期会考虑生产线设备的产能均衡问题，尽 量避免物理瓶颈的存在。但是由于某些关键设备( 如光刻机) 价格相当昂贵， 企业从赢利的角度出发会尽量少的购入此类设备，因此，生产线可能会存在物 理瓶颈。另外，在制品种类繁多，生产工艺复杂，设备可能产生突发性故障， 这些因素往往会造成生产线瞬时瓶颈的出现。 ( 4 ) 新产品试制 半导体生产线上除了客户定制的产品外，可能会有一定比例的处于研发阶 段的工件，这些非正式的产品一般数量少，工艺特殊，优先级高，它们也会影 响正常的生产线调度。 ( 5 ) 返工 返工是晶圆片加工过程中常见的现象。晶圆片在加工过程中会经过多次检 测，在某些阶段若检测结果不符合标准，需要返回到前面若干个工序重新加工。 由于半导体生产线上述特征及高度的不确定性使得半导体生产线调度不同 于以往的制造系统，半导体生产线调度问题已成为当今学者研究的热点。 1 2 半导体生产线调度问题研究现状 1 2 1 生产调度的分类 生产调度( p r o d u c t i o ns c h e d u l i n g ) 是生产管理的核心内容和关键问题，其 任务是在企业车间有限的资源约束下确定工件在相关设备上的加工顺序和加工 时间，以保证所选定的生产目标最优。 生产调度按照类型可以分为静态调度( 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 ) 。 静态调度又称排序( s e q u e n c i n g ) ，是在生产作业计划的基础上，假定调度 环境和任务确定不变，对加工任务按各自的工艺流程进行生产安排。它是在以 下假设条件下进行的：被调度的工件集合是确定的；工件的加工时间是确定的， 第1 章绪论 并且在安排计划时全部工件都已到达；加工工件的机器是连续可用的。静态调 度中所有待安排的工件均处于待加工状态，进行一次调度后，各工件加工顺序 即被确定，在以后的加工过程中将不再改变。 动态调度是依据动态变化的实时生产环境，逐步生成调度方案并指导实际 的生产过程，包括实时调度( r e a l t i m es c h e d u l i n g ) 和重调度( r e s e h e d u l i n g ) 两种实现方式。实时调度直接按照生产系统中的工件和设备的状况以及相关信 息，使用某种计算方法，实现工件的分派。重调度基于已有的静态调度方案， 根据生产系统的状态信息进行调度方案的调整或者重新生成。 1 2 2 半导体生产调度的研究现状 制造系统生产调度的目的是合理分配和利用生产线上有限的设备和资源， 在满足时间和工艺流程等约束条件的前提下完成对任务的加工，并从全局的角 度优化生产线的性能指标。 调度问题的研究始于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 问题的有效算法，代表着调度理论研究的开始。2 0 世纪 6 0 7 0 年代建立起了调度理论的主体，形成了经典调度理论。从此，人们围绕生 产调度展开了广泛研究，不断有最新的研究成果面世。到目前为止，对调度问 题的理论研究方法分为以下几类： ( 1 ) 基于数学规划的方法 从数学规划角度求解调度问题，一般有严格的数学推导过程，结果以精确 的解析解的形式给出，但计算量太大，甚至是n p 难的。在实际的求解过程中， 常常会遇到计算耗时过大，参数难以量化，对某些实时状况反映慢等问题。由 于半导体生产线自身的复杂性，更增加了计算的复杂度，基于数学规划的方法 一般难以解决大规模的半导体生产线调度问题。 ( 2 ) 基于离散事件仿真的方法 基于离散事件系统仿真技术的调度方法是仿真技术的最新应用。其基本原 理是：在调度规则的引导下，制造系统的仿真模型试探性的经历整个加工过程， 记录该过程中系统的状态变化及导致系统变化的事件，产生调度方案并统计性 能指标。仿真方法通过建立模拟真实生产环境的模型，可以有效避开调度问题 中理论分析的困难。 6 第1 章绪论 许多学者将离散事件仿真模型用于研究半导体生产线调度模型，使用预先 定义好的各种调度规则对任务集进行派工。如b i s p o 和t a 州4 】使用仿真与优化 相结合的方法研究可重入生产系统的能力分配、库存管理和生产控制等问题， r o s e 5 j 提出使用仿真模型来估计加工时间的分配。 ( 3 ) 基于启发式规则的方法 由于半导体生产线自身的复杂性，在研究的最初使用最多的是简单启发式 规则。k u m a r t 6 小1 等人做了许多开创性工作，在w e i n 1 4 。1 7 1 的工作中，首先对各种 调度策略进行了全面系统的比较。k i m 1 8 】等将不同的订单按照交货期的不同进行 划分，提出了一系列基于交货期的多产品调度方法。使用启发式规则可以较快 的得到较优的调度方案，目前许多实时调度系统都采用一些改进的启发式调度 规则。 ( 4 ) 基于计算智能的方法 计算智能方法在作业车间与流水车间的动态调度中得到了广泛的应用。遗 传算法，模糊集理论，模拟退火、神经网络和蚁群算法等，这些智能方法在调 度问题寻优过程中具有快速收敛的特性。如n o s e 坶】等人使用遗传算法求解可重 入车间调度问题，金辉宇【2 0 】尝试使用神经元动态规则解决可重入生产系统中的 调度问题。但是，与启发式规则相比，计算智能的搜索时间较长，主要适用于 解决小规模的问题，通常不能满足半导体生产线这类大规模多约束多目标的调 度需要。 1 2 3 重调度问题研究现状 对于复杂多变的多重入制造系统，许多生产线的扰动因素具有不可预测性， 而这些扰动因素往往会使得原本优化的调度方案不再优化，甚至失去了可行性， 这时需要对生产线进行重新调度，这也就引出了多重入制造系统的重调度问题。 所谓重调度，是指当既定生产调度方案在其执行过程中被干扰时，在既定 调度方案的基础上生成新的调度方案，以适应当前状态的过程。 目前，国内外的重调度研究主要集中于单台机器系统、并行机器系统、流 水车间和作业车间、柔性制造单元与系统。研究内容主要包括以下三个方面： 重调度策略、重调度方法和重调度评价。 7 第1 章绪论 1 2 3 1 重调度策略 重调度策略是根据各种重调度因素，决定何时产生重调度，采用何种重调 度方法。常见的有三种重调度策略：周期性重调度策略，事件驱动重调度策略 和混合重调度策略。 周期性重调度策略【2 l 】以恒定的时间间隔有规律的对设备进行重调度，不考 虑事件触发。周期性重调度是最普遍的重调度策略，通常是基于管理区间( 如， 一周或一天或一个班次) 进行的。c h u r c h 和u z s o y l 2 2 】给出了这种重调度策略详 细的解释。k e m p f t 2 4 】提出了一种基于人工智能的预先调度方法，该方法每个班次 执行一次，给出优化的调度方案。s a b u n c u o g l u 和k a r a b u k 2 5 】在柔性制造系统中 考虑重调度频率对系统效能的影响。不同的重调度周期对生产线的影响很大， 如何决定最佳重调度周期是一项困难而重要的工作。 事件驱动重调度策略【2 2 】由扰动事件触发重调度，能够即时响应动态制造系 统中的扰动事件，修改原调度方案或生成新的调度方案。v i e i r a 2 i 】等描述了在动 态系统中利用分析模型比较基于队列长度的事件驱动重调度策略的性能。 b i e r w i r t h 和m a t t f e l d t 2 6 j 研究的重调度策略，当每个新工件到来时创建一个新的调 度。然而，完全的事件响应可能会导致过度的计算开销，难以满足实时性的要 求。 混合重调度策略【2 1 2 2 1 将上述两种重调度策略相结合，在周期性触发重调度的 基础上，根据扰动事件对原调度方案的影响有选择的触发重调度。c h a c o n 27 】描 述了在s o n y 半导体中使用的系统，采用周期性重调度策略，并且当非预期事件 发生时手工进行重调度。s u w a 2 8 】采用固定周期重调度策略，同时计算累积任务 延迟，当累计任务延迟达到预先设定的临界值时开始重调度。混合型重调度既 可以避免周期性重调度对非预期事件不敏感的确定，又可以避免事件驱动型重 调度易造成过度频繁的重调度导致计算量过大的缺点。 1 2 3 2 重调度方法 重调度方法用于产生具有优化性能指标的重调度方案，主要有两种方式： 生成式重调度和修正式重调度。 生成式重调度根据是否考虑生产线不确定因素可以分为：常规性调度和鲁 棒性调度。常规性调度通常忽略随机扰动因素，旨在给出优化的静态调度方案， 但是对随机扰动处理能力不够。常规性调度可以借鉴已有的调度方法，如离散 第l 章绪论 时间系统仿真，运筹学，计算智能等。鲁棒性调度在常规性调度的基础上研究 生产线的各种随机因素，在调度的时候已经考虑各种干扰的影响，所以给出的 调度方案更适用于实际的生产。不少学者对不确性模型的鲁棒性调度展开了研 究，m e t h a 和u z s o y 提出的预期调度方案通过插入一些空闲的时间片来减少随机 扰动的影响【2 9 1 。d a n i e l s 和k o u v e l i s 等人【3 0 】考虑生产线处于最坏情况下给出优化 调度方案，这样可以更有效的减少随机事件的干扰，但是在扰动较少的情况下 可能会降低生产率。 当原有的调度方案由于各种随机因素不适用的时候，需要进行修正，即进 行修正式重调度。修正式重调度主要分为两类：局部修正式重调度、全局修正 式重调度。局部修正式重调度仅仅修正那些受扰动直接影响和间接影响的派工 方案。m i y a s h i n t 和s y c a r a 3 1 j 在基于约束的基础上根据不同的情况选择局部修正 的方法，具体包括调整开始加工时间、交换操作和切换到其他可选资源。全局 修正式重调度由重调度点开始更新整个调度方案。b i e r w i r t h 和m a t t f e l d t 2 6 】在原 调度方案的基础上使用遗传算法生成新调度，该方法可以有效的减少重新生成 调度方案的计算开销。j a m e s 等人提出了种基于原调度方案的匹配调度方法， 考虑了多种资源约束、工件的投料和生产线扰动1 4 3 。 1 2 3 3 重调度评价指标 重调度有许多不同的评价指标，这些评价指标大致可以分成三类：有效性 评价指标、稳定性评价指标和成本评价指标。 有效性评价指标通常使用一些基于时间的指标，比如加工周期1 2 引，平均延 趔3 2 。3 4 】，平均资源利用率【3 3 矧，最大延迟【2 2 】等。稳定性评价是重调度十分重要 的评价指标。w u 和s t o r d 3 5 】等人认为稳定性主要表现在新旧调度方案开始时间 的偏差和新旧调度方案各个操作顺序的差异。基于时问的指标不能明显的反映 经济效益，一些研究人员提出调度决策需要考虑一些经济性指标，如s h a f a e i 和 b r u n n t 3 6 3 7 】提到总成本、w i p 数、延迟交货代价和不同任务的收益等评价指标。 1 3 课题背景和意义 重调度问题是优化调度问题的延伸，也是优化调度理论研究的新阶段3 1 。在 半导体制造系统中，由于其本身的复杂性，重调度问题的研究还处于理论阶段， 9 第1 章绪论 对于重调度策略和重调度方法的研究还没有形成成熟的适用于大规模制造系统 的方法。 本课题以半导体生产线为对象，对多重入制造系统中在线重调度的策略和 方法展开研究，通过优化重调度策略和重调度方法来提高系统对不确定事件的 反映能力，使新调度方案不仅继承了原调度的优化性同时尽可能保持调度方案 的稳定性。 通过本课题的研究将形成一套适用于半导体生产线的重调度策略和重调度 方法。本课题的选取以国家自然科学基金重点项目“组件化可重构多重入制造 系统生产计划与调度体系结构及其关键技术研究( n o 7 0 5 3 1 0 2 0 ) ”、国家9 7 3 项 目“复杂生产制造过程实时智能控制与优化理论和方法研究”中的子任务“基 于群体智能模型的复杂生产制造过程智能调度理论及方法研究 ( n o 2 0 0 2 c b 3 1 2 2 0 2 ) 为背景，以半导体生产线为对象，对多重入制造系统在线重调 度问题进行深入研究，力争提出适用于多重入制造系统的重调度策略与重调度 方法。 1 4 各章节安排 本文各章节安排如下： 第一章：绪论。本章综述了多重入生产线的典型代表半导体生产线的特点， 总结了半导体生产线调度问题和重调度问题的研究现状，阐述了重调度问题的 研究意义。 第二章：基于模糊p e t r i 网推理的重调度策略研究。本章提出了基于模糊 p e t r i 网推理的重调度判定方法，详细介绍了模糊p e t r i 网推理机的实现原理，针 对实际的半导体生产线建立了模糊p e t r i 网模型，最后对提出的基于模糊p e t r i 网推理的重调度策略进行了仿真验证。 第三章：基于m a t c h u p 的重调度方法研究。本章针对静态方法的不足和现 有重调度方法的局限性，提出了以充分利用任务间空闲时间的单台设备匹配重 调度方法( s i n g l em a c h i n em a t c h - u pr e s c h e d u l i n g ，s m u r ) ，为了进一步利用设 备组中的空闲时间提出了设备组匹配重调度方法( m a c h i n eg r o u pm a t c h u p r e s c h e d u l i n g ，g m u r ) ，最后采用m i n i f a b 生产线模型验证了所提出方法的稳定 性和有效性。 1 0 第1 章绪论 第四章：半导体生产线全局重调度系统设计与实现。本章针对实际的半导 体生产线，采用用户层、模型层和数据层分离的三层架构，设计并实现了全局 重调度系统，其中考虑了多种扰动因素，设计了一种混合的重调度策略，并采 用全局重调度方法进行重调度。该系统已用于某实际的半导体生产车间，实践 证明该系统可以快速响应扰动，及时更新调度方案。 第五章：结论与展望。总结全文的研究工作及成果，并提出了需要进一步 研究的问题和未来的发展方向。 第2 章基于模糊p e t r i 网推理的重调度策略研究 制造系统中大量的不确定性因素往往使得原来较优的生产计划变得不再适 用，生产管理人员需要在适当的时候进行重调度。如何确定重调度的时机一直 是困扰管理人员的一个问题。 常用的重调度策略有周期性重调度策略、事件驱动重调度策略和混合重调 度策略。单一的使用周期性重调度策略容易造成对扰动事件反应不及时；采用 基于事件驱动的重调度策略，在扰动频繁的情况下，又会造成重调度次数过于 频繁，浪费大量的计算机资源和调度时间。将周期性重调度策略和事件驱动重 调度策略有机结合，可以有效避免重调度过于频繁，同时对扰动事件有较快的 响应速度。 本章将利用模糊p e t r i 网对不确定性问题的知识表示和p e t r i 网j 下向推理能力 构造一种混合重调度策略。生产线首先按照周期性生成的调度方案进行生产， 当扰动发生的时候，采用模糊p e t r i 网推理( f u z z yp e t r in e tr e a s o n i n g ，f p n r ) 的重调度策略进行重调度判定。 2 1p e t r i 网简介 p e t r i 网是对离散并行系统的数学表示。p e t r i 网是1 9 6 0 年由c a 佩特里发明 的，适用于描述异步的、并行的计算机网络模型。p e t r i 网既有严格的数学表达 方式，也有直观的图形表达方式，同时也是丰富的系统描述手段和系统行为分 析技术。 2 1 1 经典p e t r i 网 经典p e t r i 网是简单的过程模型，由库所、变迁、有向弧和托肯等元素组成， 如图2 1 。 第2 章基丁模糊p e t r i 网推理的重调度策略研究 乞 图2 1 经典p e t r i 网示例 p e t r i 网的形式化定义 一个经典的p e t r i 网( p e t r in e t ，p n ) 由五元组刚( p ，t ，i ，0 ，品) 组成，其中： 库所尸= p l ，p 2 ，以) 为有限库所集，用圆圈表示，l 为库所个数； 变j ：f g t = t l , t 2 ，t m ) 为有限变迁集，用短线或矩形表示，m 为变迁个数； 输入函数i ：p x t - - n 为输入函数，定义了从p 到丁的有向弧的集合； 输出函数0 ：t x p - - ) n 为输出函数，定义了从t n p 的有向弧的集合； 初始标识瓯为州的初始标识，表示初始状态时托肯( t o k e n ) 在各库所中 的分布情况。 由于基本的p e t r i 网存在着模拟能力和可解性等方面的局限，随着p e t r i 网理 论的发展和应用的推广，不断有新的p e t r i 网扩充形式产生。 2 1 2 模糊p e t r i 网的知识表示 在人工智能和专家系统中，存在着大量的基于规则的推理方法，可简单的 表示为 矿ua n d a n d a n d 虬t h e nq ，d 2 ，见 其中：u ，饥为条件；q ，砬，或为结论。这条规则的含义为，如果 以，虬为真，则可以推出结论d l ，d 2 ，见为真。 1 3 第2 章基丁模糊p e t r i 网推理的重凋度策略研究 在实际问题中，我们往往还要考虑以下几个问题： ( 1 ) 前提条件中，各条件的权重因素，它表示了对结论的贡献程度； ( 2 ) 规则实现的阈值，这是推理得以进行的最低可信度； ( 3 ) 结论的可信度，它代表了条件满足时结论的可信程度。 所以，更一般的规则推理可以表示为： 圹u ( ) a n d ( a 2 ) a n d a n du ( ) oq ( 局) ，d 2 ( 压) ，见( 成) 采用模糊逻辑表达式可表示为： ( ux 瞒) ( 呸) a a ( 巩吒) _ d i ( 届) ，皿( 履) ，域( 尾) 转化为模糊p e t r i 网模型，可表示为图2 2 的形式。 图2 2 一般性推理规则的模糊p e t r i 网模型 q 下面给出模糊p e t r i 网( f u z z yp e t r in e t ， f p n ) 的一般形式： f p n = p ，t ，0 ，_ f ，厂，s o ) 为模糊p e t r i 网，其中： p = 兄u 昂= 她，仍。岛) 是模糊库所节点的有限集合，表示模糊命题，由一 组模糊推理条件集p i j 和模糊推理结论集p d 的并集构成。 t = 辑，乞，f m ) 是模糊变迁节点的有限集合，表示规则的实现； ，是定义在p x t 上的一个带标识的模糊输入关系，表示库所节点到变迁节 点的连接情况和每一个连接的权系数，满足0 ，( 只，0 ) 1 ； 1 4 第2 章基丁模糊p e t r i 网推理的叵调度策略研究 d 是定义在t x p 上的一个带标识的模糊输出关系，表示变迁节点到库所结 点的连接情况和每一个连接的权系数，满足0 o ( 5 ，所) l ； f ：t 专【o ，1 是定义在集合r 上的一个映射函数，表示变迁节点的引发阈值。 ，：p 专 o ，1 】是定义在集合p 上的一个映射函数，表示库所节点的触发阈值。 s o ：p 一 o ，1 是定义在集合p 上的一个映射函数，表示库所节点在推理开始 时的初始标记状态，即已知命题的可信度，未知命题的可信度定义为0 。 魏热 乃= 0 2 y 2 = 0 2 k 乞2 0 4 图2 3 简单模糊p e t r i 网示例 图2 3 给出了一个模糊p e t r i 网推理的不例模型。 m ：v s 。( a ) = o 9 乃= o 2 ； h s 。( 见) = o 3 ) 托= o 2 ； 且 s 。( a ) 厶1 + 又( 仍) 厶。= o 7 8 ) q = o 5 ) ； 因此t l 可以引发，产生s ( p 3 ) = o 7 8 xq 3 = 0 7 8 x0 9 = 0 7 。然而，由于 s 。( p 2 ) x i 挖= o 3 ) 吃= o 4 ) ，所以乞不能引发，故s ( 段) 仍为0 。 2 2 模糊p e t r i 网形式化推理机 模糊p e t r i 网的运行过程就是一个问题求解的过程。推理机在这一过程中将 第2 章基丁模糊p e t r i 网推理的重调度策略研究 根据事实库，规则库中的已有知识不断以迭代的方式( 把推导出的结论作为新 的事实) 对新的事实的确信度进行计算，最后得出问题答案的可信度。常用的 推理过程有数据驱动( 也称正向推理) 和目标驱动( 也称反向推理) 两种方式， 由于p e t r i 网的运行机制采用的是变迁事件的驱动方式，在数据信息的流向上与 正向推理过程一致，因此采用正向推理模式进行形式化推理。 2 2 1 模糊p e t r i 网形式化推理机原理 首先，定义几种常用的运算操作，设么，b ，c ，d ，e 均为n xm 维矩阵 定义加法算子o ：c = 彳。占，其中勺= m a x ( a 口，) 定义比较算子。：。= 彳。b ，其中嘞= 三z 三乏 定义直乘算子圆：e = a o b ，其中e u = a u 上述算子中，i = 1 ，2 ，n ，j = 1 ，2 ，m 。 假设在一个具有n 个库所和m 个变迁的模糊p e t r i 网模型中，输入矩阵为 l 。，输出矩阵为q 。，变迁阈值向量为f ，状态向量为s 。推理过程可以分解 为以下六个步骤进行 3 8 , 3 9 。 ( 1 ) 计算等效模糊输入可信度 e = i r s o ( 2 1 ) 其中，e = q ，e 2 ，】7 。这一步是将同一变迁中多个模糊输入按照它们的 可信度和权系数等效为一个权系数为1 的模糊输入。 ( 2 ) 等效模糊输入可信度与变迁阈值的比较 g = e o f( 2 2 ) 其中，g 为朋维列向量，当等效模糊输入的可信度大于等于变迁的阈值时， g l = 1 ；否则g ，= 0 ，j f = l ，2 ，m 。 ( 3 ) 剔除等效模糊输入中可信度小于变迁阈值的输入项 h = e og( 2 3 ) 第2 章基丁模糊p e t r i 网推理的重凋度策略研究 其中，h 是与e ，g 同维的列向量，经过这一步计算后，h 中只包含可使 变迁触发的等效模糊输入的可信度。 ( 4 ) 计算模糊输出库所的可信度 s 1 = o o h( 2 4 ) 其中，s 1 为m 维列向量，表示经过第一轮推理后，可以直接得到的结论命 题的可信度。在s 1 中，不能直接推理得到不是结论命题的库所，可信度为零。 ( 5 ) 计算当前可得到的所有命题的可信度 s = s o o s l ( 2 5 ) ( 6 ) 用式2 5 中的墨代替式2 1 中的s o ，反复用式2 1 2 5 进行迭代。设文 为第k 步推理得到的结论，则在第k 步推理进行后，所有命题的可信度为 & = 瓯一lo s ( 2 6 ) 当推理计算不再使任何命题的可信度发生变化时，即瓯= 足一。时，推理结束。 2 2 2 模糊p e t r i 网形式化推理机实现 根据以上推理过程，我们采用e m p l a n t 仿真建模软件建立了如图2 4 的模糊 p e t r i 网形式化推理机。 1 7 第2 章基r 模糊p 0 1r 埘 | 【= 理的电调艘策略研究 地倒删删劂倒盥| h r 口o m 晰 咖”_ r ，m r i x t r 刚 rx e w d m m d n m 女“& m m 口r m i ) * # * m # 姒w * 囵_ 圜倒 圄 女 2 ) * # m 黼 日* # 女目自# 倒倒 w e 3j 酶# 目# # 十目口口十f 女d 目m # 日 旦| 删 圄倒 e5 * # m 日# 椭黜日日自 旦| 刿 凹2 4 栏鞲0p e 一阿形式化推理机 盟 该推理机的输入输出变量由图25 中的多张二维表给出，其中尸表示库所向 量、r 表示变迁向量、，表示输入矩阵、0 表示输出矩阵、只表示初始标识、r 表示变迁闰值和s k 表示最终标口 。 p a r m t 日 幽2 5 推理机输 输出变量 圄 剜。 剜。 面|面i园 囵 第2 章基丁模制p e t r i 咧干f | _ 珲的重调度策略研究 2 2 3 模糊p e t r i 网图形化表示与形式化表示转换 p e t r i 网可以使h j 图形化工具建模，j 郇时可以方便的转化为形式化矩阵表示。 在论文方法验证过程中，由于需要频繁改变g - ：p 输入量，一种有效的可以进行 模糊p c t r i 网图形化建模并且支持自动的形式化转换的工具将是事半功倍的。为 了与生产线模型无缝链接，本文又开发了模糊p e t r i 自动化建模与转化的_ 具， 下面介绍该丁具的实现过程。 删捌 p r e t r c e p t h t a s h o l d 幽2 6 模糊p e t r i 列建模与形式化转换 如图2 6 所示，给出了使j l j 浚工具建立的简单p e t r i 网模型，其中包含了3 种图形化建模对象： ( 1 ) 库所p ，使用圆圈表示，双击库所对缘可咀设置库所闽值和库所初始 标识，如图27 所示； ( 2 ) 变迁t ，使用加粗的蠖线表不，双击变迁对象可以设置变迁阚值，如 图28 所示： ( 3 ) 输入输出弧，使用带方向的线条袁示，取击输入输出弧可以设置输入 和输出的权重，如图2 9 所示。 圄一 倒w 剜一 崮 帖 一剜 第2 章壁丁模糊阢l n 同推理鹄重碣度策略研究 斟27j 年所蒯值殴鼍窗口 幽2 8 变迁创值设置窗口 第2 章基丁模糊p e t r lm 推理的重凋膛策略研究 幽2 9 输入输出权重设置窗口 在图2 6 中，p r e s o u r c e 、t r e s o u r c e 、p t h r e s h o l d 、t t h r e s h o l d 、i n p u t 和0 u t p u t 都是二维的数组结构。其中，p r e s o u r c c 和t r e s o u r c e 分别记录p e t r i 网席所对象 和变迁对象；p t h r e s h o l d 和t t h r e s h o l d 记录p e t n 网中库所闺值和，叟迁闽值；i n p u t 和o u t p u t 记录p e t r i 网中输入权蘑矩阵和输出权重矩阵。将p e t 6 网看做一个联 通图，通过对图的深度优先遍历，将库所阈值、变迁闽值、输入输 ：权重分别 保存到上述对应的二维数组巾。 通过以上工具我们町以方便的建立模糊p e t r i 网模型和进行形式化矩阵转 换，得到的矩阵也可以方便的作为形式化推理机的参数。 2 3f p n r 建模与仿真分析 利用上一节f p n r 形式化推理机，本节将