（管理科学与工程专业论文）fms生产调度建模、优化与仿真研究.pdf

摘要 摘要 柔性制造系统( f m s ) 是制造领域中的高新技术之一，是一种典型的离散事件 动态系统( d e d s ) 。生产调度是实现计算机集成制造系统的关键和瓶颈，一个合 理的调度方案能给企业带来很大的经济效益；在理论上调度是一个多目标、多约 束的优化问题。所以研究生产调度具有重要的理论意义和使用价值。 本文通过研究p e t r i 网在f m s 中的建模理论与方法，建立了一个f m s 生产调度的 非确定p e t r i 网模型。模型中通过调度知识库跟踪工件令牌信息的手段，更好的描述 了系统动态调度的思想。在启发式调度算法的思想上，提出分层调度的思想。在 算法的执行过程中综合考虑系统生产效率和系统制造成本，以实现优化系统生产 效率和系统制造成本的多目标调度；最后，将p e t r i 网模型转换成e m p l a n t 仿真模型， 运用e m p l a n t 仿真工具对一个柔性制造单元进行了仿真研究，对f m s 的生产调度进 行动态模拟，并监测系统运行情况，得出数据；通过对比分析两种调度策略的结 果数据，验证了提出的思想的价值。 关键词：柔性制造系统调度非确定p e t ri 网仿真 a b s t r a c t a b s t r a c t a so n eo ft h eh i g h - t c c h si nt h ef i e l do fm a n u f a c t u r i n g ，f m si sa l s oat y p i c a ld e d s p r o d u c t i o n s c h e d u l i n g i st h eb o t t l eo f i m p l e m e n t i n gc o m p u t e ri n t e g r a t e d m a n u f a c t u r i n gs y s t e m ( c i m s ) ，a n dar e a s o n a b l es c h e d u l i n g s o l u t i o nc a nc r e a t e a b u n d a n tp r o f i t s p r o d u c t i o ns c h e d u l i n gi sam u l t i - o b j e c t i v ea n dm u l t i - c o n s t r a i n ti s s u e i nt h e o r y , a n dt h es t u d yo fs c h e d u l i n gi so ft h e o r e t i c a ls i g n i f i c a n c ea n dp r a c t i c a lv a l u e i nt h i sp a p e r , b yd o i n gr e s e a r c ho nt h et h e o r ya n dm e t h o da b o u th o wt oa p p l yp e t r i n e tt ob u i l dm o d e li nf m s ，e s t a b l i s han o n - d e t e r m i n a t i o np e t r in e tm o d e lf o rf m s p r o d u c t i o ns c h e d u l i n g t h ed y n a m i cs c h e d u l i n gi d e ao ft h es y s t e mw i l lb eb e t t e r d e p i c t e db yt r a c k i n gt h ei n f o r m a t i o no ft h ew o r k p i e c et h r o u g ht h es c h e d u l i n gr e p o s i t o r y i nf i e l do fh e u r i s t i cs c h e d u l e ，t h i sp a p e rp u t sf o r w a r dt h ei d e ao fs c h e d u l i n gb y l a m i n a t i o n i nt h e p r o c e s so fi m p l e m e n t i n gs c h e d u l i n go p t i m i z a t i o n , p r o d u c t i o n e f f i c i e n c ya n dm a n u f a c t u r ec o s tm u s tb ec o n s i d e r e ds y n t h e t i c a l l y i no r d e rt oo b t a i nt h e s y s t e mo p e r a t i n gd a t a , w ec o n v e r t e dt h en o n d e t e r m i n e dp e t r in e tm o d e lo ff m s p r o d u c t i o ns c h e d u l i n gt oe m - p l a n ts i m u l a t e dm o d e lw h o s es i m u l a t e dt o o l si su s e dt o s t u d yo n eo ff m sc e l l ，a n dc a r r yo nd y n a m i cs i m u l a t i o nt ot h ep r o d u c t i o ns c h e d u l i n g s y s t e m , w h i l em o n i t o rt h ee x e c u t i n gs i t u a t i o n ；b yc o m p a r i n gt h ed a t ao b t a i n e df r o mt h e d i f f e r e n ts c h e d u l i n gm e t h o d s ，i m p r o v e dt h ei d e ai sv a l u a b l e k e y w o r d ：f m ss c h e d u l i n g n o n d e t e r m i n e dp e t r in e t s i m u l a t i o n 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：日期塑墨! ! ：! 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容i 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 第一章绪论 第一章绪论 1 1 研究背景 本世纪5 0 年代末、6 0 年代初，一些工业发达的国家和地区，在达到了高度工业 化的水平之后，就开始了从工业社会向信息社会转化的过程。形成了一个从工业 社会向信息社会过渡的时期【1 1 。这个时期人们意识到大批量生产只是机械制造业的 一小部分，而中、小批量生产占到了7 5 n 8 5 。在国民经济的生产部门中比重占 绝对优势的多品种中、小批量生产企业的劳动生产率极大地落后于大批量生产企 业。随着国际贸易和技术交流的发展，跨国产品和出口产品在生产中的比重大大 增加。这个时期的主要特征是电子计算机、遗传工程、光导纤维、激光、海洋开 发等新技术的日益广泛而深入的应用。 f m s 最初是由英国m o l i n s 公司雇员t h e ow i l l i a m s o n 于6 0 年代提出来的。1 9 6 5 年 m o l i n s 公司取得了该项发明的专利。当时，称此方案为“系统2 4 。同年，美国 k t s w a s e y 公司也建成了一条柔性制造系统，并取名为f l e x i b l em a n u f a c t u r i n g s y s t e m ，这是首次正式提出了柔性制造系统的名称。 自从1 9 6 8 年英国出现第一个柔性制造系统( f l e x i b l em a n u f a c t u r i n gs y s t e m ， f m s ) 和1 9 7 5 年日本研制出实用化的柔性制造系统后，机械工业开始了柔性自动 化时期。f m s 出现后，并未得到迅速的发展，直n 7 0 年代末，由于国际市场竞争 日趋激烈、生产周期缩短的追求、为了降低成本等几个方面的原因，才引起了比 较普遍的重视。 随着科学技术特别是计算机技术的发展，柔性制造系统的生产技术和生产管理 得到了飞速的发展。在制造系统向着多品种、中小批量自动化生产发展的今天， 传统的生产方式受到了挑战，柔性制造系统则越来越受到人们的重视。1 9 8 8 年， 国际上以柔性生产方式生产的产品产值已占制造业总产值的7 0 以上，其中美国占 7 7 ，日本占8 0 ，且有不断增长的趋势【2 1 。f m s 可以高效灵活地进行生产，提高 企业生产设备的利用率和生产效益。它还可以和c a d c a p p c a m 及生产管理经 营决策系统相结合，借助计算机和网络技术把管理信息和制造活动有机地联系起 来，向计算机集成制造系统( c i m s ) 【3 】方向发展，以实现整个企业生产管理的现 代化。 由于f m s 使用更为复杂的机床和信息处理技术，与单台机床相比，必然要花 费更多的精力进行规划管理工作。f m s 的成功运行相当大程度上取决于管理的质 2 f m s 生产调度建模、优化与仿真研究 量。f m s 控制管理的主要任务之一，是根据在f m s 中产品的交货期，对进入系统 的多种零件的生产计划进行制定，同时对零件的加工进行调度。在制定计划和进 行调度的同时，要考虑交货期、零件加工工艺、设备加工能力、设备利用率和系 统生产率等因素。一个好的f m s 生产计划和调度方案将提高生产系统的生产效率 和生产设备的利用率，充分利用系统的柔性，在同样的生产条件下，降低生产成 本、增加经济效益。 2 0 世纪9 0 年代f m s 从探索阶段走向了实用化和商品化的阶段，成为机械制造技 术进步的重要标志。1 9 9 4 年初，据统计世界各国已投入运行的f m s 约有3 0 0 0 多个， 其中日本拥有2 1 0 0 多个，占世界的首位。我国第一套f m s 于1 9 8 6 年1 0 月在北京机 床研究所投入运行，用于加工伺服电机的零件。 1 2 研究的目的和意义 近年来，国外一些工业技术比较发达的国家为了进一步提高劳动生产率，降低 生产成本，缩短产品的研制和生产周期以加强产品更新换代和产品市场竞争力， 正在机械制造领域里进行技术更新。这在我国的机械制造行业中已经引起很大的 重视，因此有必要对于f m s 进行一个比较全面的系统的研究。f m s 是一个高投资 的高技术项目，并已在工业生产部门得到较为广泛的应用，但由于多种复杂因素， 导致某些f m s 项目的应用效果不佳【4 1 。 作为一类先进的人造系统，f m s 具有复杂性、递阶结构、多约束、多资源相互 协调等特点，而生产调度作为其中的一个关键模块，是整个系统实现管理技术、 运筹技术、自动化与计算机技术发展的核心。车间生产调度通过对各项作业的排 序，确定各工作地上工件的最优加工顺序，以达到充分利用设备能力、减少工序 平均流程时间、降低工序在制品占用量的目的1 5 1 。有效的调度方法和优化技术的研 究与应用，是实现先进制造和提高生产效益的基础和关键，对于提高生产系统的 最优性、提高经济效益均有着极大的作用。 生产调度是实现计算机集成制造系统的关键和瓶颈，一个合理的调度方案能给 企业带来很大的经济效益；在理论上调度是一个多目标、多约束的优化问题，但 多数研究的问题忽略了很多实际因素，目标单一，所以研究生产调度具有重要的 理论意义和使用价值。 从f m s 的产生到目前在世界各国机械生产领域的广泛应用，虽然各套f m s 的规 模和作用有很多不同，但其工作原理大同小异，本文通过对f m s 的生产调度问题 的研究，以期达到如下目的： 1 ) 根据p e t r i 网理论提出了一个适合f m s 生产调度的p e 仃i 网模型，以期更好的 描述系统动态调度的思想； 第一章绪论 2 ) 研究f m s 调度的方法，优化f m s 生产效率以及f m s 制造成本； 3 ) 过仿真软件e m p l a n t ，对f m s 的动态生产调度模拟、监测系统运行情况， 得出数据；运用所得到的数据对系统进行分析，从而得到更有利于获得系统运行 最佳选择的方法。 1 3f m s 生产调度概述 1 3 1f m s 的组成及其生产调度问题 柔性制造系统( f m s ) 可概括为由下列三部分组成【6 】：数控加工系统，物流系 统和信息流系统，其构成如图1 1 所示。 图1 1f m s 的构成图 1 ) 数控加工系统 数控加工系统的功能是以任意顺序自动加工各种工件，并能自动地更换工件和 刀具。通常由若干台对工件进行加工的机床和所使用的刀具构成。 2 ) 物流系统 在f m s 中工件、工具流统称为物流系统，物流系统即物料贮运系统，是柔性 制造系统中的一个重要组成部分。一个工件从毛坯到成品的生产过程中，很大一 部分时间都消耗于物料贮运系统中，合理的选择f m s 的物料贮运系统，可以大大 提高整个制造系统的柔性和效率。 物料系统一般由三个部分组成： 输送系统：建立各加工设备之间的自动化联系； 贮存系统：具有自动化存取功能，可以调节加工节拍的差异； 操作系统：建立加工系统同物流系统和贮运系统之间的自动化联系。 f m s 中的物料输送系统与传统的自动化生产线或流水线不同，f m s 的工件输 送系统可以不按固定节拍运送工件，工件的传输也没有固定的顺序，甚至可以是 4 f m s 生产调度建模、优化与仿真研究 几种工件混杂在一起输送，而且工件输送系统都可以进行随机调度。 f m s 的物料贮运系统一般包含工件装卸站、托盘缓冲站、物料运送装置和自动 化仓库等几个组成部分，主要用来执行工件、刀具、托盘以及其他辅助设备与材 料装卸、运输和贮存工作。 3 ) 信息系统 信息系统包括过程控制及过程监视两个子系统。其功能分别为：过程控制系统 进行加工系统和物流贮运系统的自动控制；过程监视系统进行在线状态数据自动 采集和处理。信息系统的核心是一个分布式数据库管理系统和控制系统，整个系 统采用分级控制结构，即f m s 中的信息由多级计算机进行处理和控制，其主要任 务是：组织和指挥制造流程，并对制造流程进行控制和监视向f m s 的加工系 统、物流系统( 贮存系统、输送系统及操作系统) 提供全部控制信息；进行过程 监视，反馈各种在线检测数据，以便修正控制信息，保证安全运行。 生产系统的柔性是指其加工多种零部件、生产多样化产品的能力。这种能力既 取决于系统设计时所确定的设备与运输系统等硬件配置因素，同时也取决于生产 管理中各种计划决策，这些柔性可概括如下： 机器柔性机器能处理不同操作的能力，一般取决于机器所能执行的不同操 作的个数及在不同操作间进行切换所需要的时间，这一类柔性由机器本身的特性 决定，与计划决策问题无关。 产量柔性生产系统在已有的产品和零部件生产中生产不同产量而仍能获取 利润的能力。高的产量柔性意味着低的损益平衡点，这是柔性制造( 装配) 系统 效益的主要体现之一，也是柔性制造( 装配) 系统被应用的主要动力。 零部件的选路柔性给定工艺下，一个零部件按不同路径被有效j n - r 的路径个 数，降低机器的利用率可增加零部件的选路柔性。这方面研究目前是柔性制造( 装 配) 系统研究的重点。 过程柔性系统无须重新装设而能生产的零部件集合大小的测度，它取决于 机器柔性、物料运输方式的柔性和生产线中机器的连接与控制方式，是一种短期 柔性的测度。相关的决策问题为生产线上机器的组合问题：如何对机器进行分组， 以使机器组的利用率最高，零部件通过生产系统的时间最短且选路柔性最大等。 产品柔性系统只须很少的重新装设而能生产的零部件的集合大小的测度。 扩张柔性系统扩张的能力，即增加生产能力导致边际投资减少的幅度。目 前这方面的研究集中在“模”式( m o d u l a r ) 生产系统的研究方面。 程序柔性系统运行一段时间而无须外部干预的能力，它通常取决于高的选 路柔性和或过程柔性。这是柔性制造( 装配) 系统被应用的主要动力，也是系统 绩效评估的主要内容。 生产柔性系统无须大的设备投资而能生产的产品的集合大小的测度。 第一章绪论 市场柔性系统能有效适应市场条件变化的能力，分为短期市场柔性( 处理 消费者订单变化的能力) 和长期市场柔性( 应付消费者需求的变化、产品寿命周 期缩短和产品技术变化的能力) 。短期市场柔性的决策问题本质上是如何在作业计 划中直接体现市场需求的变动影响；长期市场柔性的相关的决策问题一般为在满 足市场需求的前提下如何使总成本最小或总收益最大或产出管理。 在不同的时间范围上，柔性的作用不同。在短的时间范围上，产品组合与加工 工艺不变，产品需求稳定，产品设计的变化很少。短期柔性的作用在于设备故障、 小的设计变动、原材料供应不确定和需求的变化性下，维持生产系统的正常生产。 在中期时间范围上，产品设计和产量变化了而制造系统的结构基本不变。中期柔 性的作用在于在新的产品和不同的需求结构下有效利用现有设备与能力进行生 产。在长期时间范围上，制造系统本身也变化了，长期柔性的作用在于改变生产 规模而无须对不断发展的操作做大的破坏，增加的投资极少。 f m s 车间生产调度问题可以描述为【7 】：n 个工件在m 台机器上加工，一个工件 需要经过k 道工序，每道工序可以在若干台机器上加工。每台机床可加工零件的若 干操作，并且在不同机床上能加工操作集可以不同。每一台机器在每个时刻只能 加工某个工件的某道工序，只能在上道工序加工完后才能开始下一道工序的加工。 在约束条件下，调度的目标是将作业合理地安排到各机床，并合理安排作业的加 工次序和加工开始时间，同时优化一些性能指标。 在动态变化的制造环境中，些不可预见的或随机的内外扰动事件( 如机床故 障、新订单进入等) 的发生往往使得原有的优化调度不再可行，因而有必要采用 动态调度方法，以快速响应环境变化，修复原定调度计划，使得f m s 持续优化地 运行【8 】，这就是f m s 的动态调度或重调度问题【9 】【1 0 】。 在实际车间生产调度中，一般需要考虑两个方面的问题，一是生产作业的下达 与调度，二是生产资源的分配。 车间生产的基本特点是能以中小批量、多种路径加工多种产品。要保证车间生 产的各种设备装置与物流能自动协调工作，并具有一定的柔性，能迅速响应系统 内外部的变化，及时调整系统的运行状态，关键就是要准确地获得各种物流信息、 设备状态，并在此基础上对信息进行规划，使各个子系统之间的信息有效、合理 地流动，从而使机加工车间的计划、管理、控制和监控功能有条不紊地运行。 1 3 2f m s 生产调度建模方法 f m s 是一类极其复杂的离散事件动态系统( d i s c r e t e e v e n td y n a m i cs y s t e m ，简 写为d e d s ) 。概括地说，d e d s 是指离散事件按照一定的运动规则相互作用导致 状态演化的一类动态系统。d e d s 研究中最基本的一个问题是系统的建模。因此， 6 f m s 生产调度建模、优化与仿真研究 要研究f m s 也必然要从建模方法开始。 围绕从不同视角和用不同数学工具来描述d e d s ，形成了研究d e d s 的多种方 法体系。第一种方法从逻辑模型的角度研究d e d s 中事件和状态的序列建模方法， 主要有形式语言有限自动机、时态逻辑、p e t r i 网等【1 1 1 。第二种方法从时间模型的 角度研究d e d s 运动轨道及其特性的建模方法。主要包括有限递归过程、极大极 小代数( 或更一般的双子代数) 、赋时p e t r i 网等。而排队网络、广义马尔可夫过程 等，则是第三种方法，它从统计性能模型的角度研究d e d s 过程性能的建模。 尽管这三种方法所研究的是同一过程，但它们不同的侧重点和不同的描述手段 使之组成了d e d s 的一个“模型体系”，以适应于不同的研究目标。目前，基于逻 辑层次模型、时间层次模型和统计性能层次模型的研究d e d s 的各种方法都已得 到了很大发展，并开始形成各具特色的理论框架。下面概要地介绍几种有代表性 的建模方法。 ( 1 ) 极大代数法 法国g c o h e n 等人在8 0 年代初将极大代数法成功地应用于d e d s 的建模和 分析。这种代数方法的基本思路是：利用双子( d i o i d ) 或极大代数中的特殊运算 规则，将逻辑非线性关系转化为线性关系，从而在d e d s 理论中建立起与线性系 统理论相类似的理论。 这种代数的“线性”系统模型及其相应理论的优点表现为其线性属性、严格的 理论体系以及易于处理时间因素。它以极大代数为工具，将f m s 视为确定性系统， 系统中各加工活动的开始时间被看作是离散事件系统的状态变量，工件和机床等 资源的投入时间被看作是输入变量，而资源从系统中释放即任务的完成时间被看 成是输出变量。这样，就得到了根据系统的运行关系建立起的一系列事件发生时 间的状态议程。在这种“线性 系统模型的框架下，对d e d s 的研究集中于诸如： 稳定性、周期性稳态、特征结构、能控能观性等系统行为的规律性分析。例如， 通过特征值分析可以得到系统的加工周期和各机床的利用率。 极大代数法的主要问题是所能处理的问题范围较窄，它比较适合处理无故障的 确定性系统。由于实际的f m s 系统具有随机性，且要求进行人工干预，因此必须 拓宽代数方法的适用范围。 ( 2 ) 排队网络模型 排队网络模型是较早用于d e d s 研究的。在排队网络模型中将服务的对象称为 顾客，而将提供服务的机构或人称为服务台或服务员。一般的排队系统都有三个 基本组成部分： 输入过程、排队规则、服务机构，其最重要的三个数量指标是队列长度、等待 时间和忙期。 排队网络模型的目的是研究服务台与顾客之间的效益问题，希望服务台效益 第一章绪论 高，而顾客的等待时间又不太长。其理论基础为排队论，又称为随机服务理论。 系统中的每个顾客都要经过到达、排队等待和服务过程。将此方法应用于f m s 时， 系统中的设备为服务台，流动的工件为顾客。在此模型的基础上，人们提出了多 种统计分析方法，如：随机分析法、运行分析法、平均值分析法、近似分析法、 扰动分析法和仿真法。 排队网络方法的好处是能考虑随机因素、阻塞状态，且能够很好地描述系统的 复杂关系。以排队网络模型为基础的分析方法往往是以一些诸如稳态、独立性等 假设为前提的，而这些条件在实际中不一定满足，因此不能保证结论的正确性。 而且，这些方法对系统的动态过程只做了统计运算，不能用于实际的动态调度和 控制研究，也导致了其应用上的局限性。 ( 3 ) 扰动分析法 扰动分析法是1 9 7 9 年由y c h o 等人提出并发展起来的。它兼容了仿真法 与理论分析法的长处，同时避免了单纯用仿真方法的大量计算和纯理论分析法研 究复杂系统所遇到的困难，是较实用的一种研究方法。扰动分析法主要用于研究 离散系统的性能指标( 如生产率) 对参数变化的敏感性，并且以此为基础对系统 的运行进行优化。但当扰动较大时，该方法近似程度差，而且应用该方法的两个 必要条件对大多数实际问题可能不成立。这个缺陷既影响了它在理论上的严格性 和普通性，也导致应用上的局限性。 ( 4 ) 活动循环图( a c d ) 法 活动循环图目前广泛地用于离散事件系统的建模仿真。这种方法以直观的方式 显示了系统的状态变化，便于理解和分析。a c d 中两类节点分别代表了系统中实 例的静态和动态，各个实体的动态、静态交替转换反映了系统的运行特征a c d 可 以根据问题的需要，对所分析的系统建立不同层次的模型，高层次的模型可进一 步解为低层次的模型。a c d 另外一个特点是通过a c d 描述的模型可以方便地转 换为e c s l 仿真语言的仿真程序。但系统过于庞大、复杂时，系统的a c d 图就会 变得十分复杂。 ( 5 ) p e t r i 网方法 由于p e t r i 网深刻、简洁地刻画了控制系统，尤其是那些含有并行操作成分的系 统的动态性质，因而其重要性越来越为人们所认识。 p e t r i 网是一种图形化的建模工具，它能精确地描述事件之间的顺序、并发、同 步和竞争的关系，并能对系统的动态性质进行分析，因而被广泛地用于像f m s 这 种复杂系统的设计、分析和仿真中，可以对作业进行分析、仿真并生成相应的控 制程序。p e t r i 在描述能力以及分析手段上具有良好的可扩充性，因而是f m s 的理 想的建模工具，但p e t r i 网除了具有上述显著优点之外，也存在着某些局限性，主 要表现在模拟能力和可解性两个方面。在模拟能力方面，p e t r i 网最突出的缺点是 8 f m s 生产调度建模、优化与仿真研究 网规模会随系统复杂性的增加而急剧扩大，当对象系统的复杂性过大时，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 网在离散事件建模系统中的广泛应用。也正是由于 经典p e t r i 网理论与离散事件系统实际应用之间存在着这样或那样的不和谐之处， 因此，人们在应用中不断根据实际的需要对p e t r i 网加以改进和扩展，如时间p e t r i 网、有色p e 仃i 网、随机p e t r i 网等。 1 3 3f m s 生产调度的研究现状 针对车间生产调度的问题，早在1 9 5 4 年，j o h n s o n 就对两台机床的调度问题进 行了研究，其后有人开始了对生产调度问题广泛研究。在研究方法上，最初是集 中在整数规划、多目标优化和简单的规则上，这些传统的调度方法在应用中存在 很大的局限性，如难以建立准确的约束条件下的数学模型，并且求最优解时间是 随问题规模呈指数倍增长的，因此只能对小规模的系统求解。近年来，随着各种 新的相关学科与优化技术的建立与发展，出现了许多新的优化方法，如神经网络、 遗传算法、基于知识的方法、基于离散事件系统( d e d s ) 的解析模型和方法等。 值得关注的是，人们将这些优化方法有机地结合起来，如遗传算法与调度规则、 仿真与基于知识的方法等相结合，产生了良好的应用前景。国际上等诸多学者对 车间生产调度做了大量的研究： j i a n g 掣1 2 j 研究了一类具有多个可选加工机器的f m s 调度问题，考虑了各工件 的加工操作工序确定但每一工序可在多台可选机器上完成的情况；l o g e n d r a n 等【1 3 】 进一步扩展了路径柔性的概念，认为加工工艺计划是关于工件所需加工操作及完 成这些操作所需机器的描述，即工件可有多种加工操作工序选择，而每一操作工 序又可从多台可选机器中选择一台完成。i s t u oh a t o n o 1 4 】以及t a k a m u r aa n d h a t o n o 1 5 】利用分层建模方法建立了f m s 的p n 模型。其中，加工过程用连续时间 随机p e t r i 网，物料搬运系统采用离散时间随机p e t r i 网。构建了在线调度规则 库，当冲突产生时，通过选择合适的优先策略来选择变迁的实施。最后通过对所 建立的f m s 模型进行仿真，对选择合适的优先策略的性能作了评价。 m a r c u sd a h m s 1 6 】将调度规则进行分类，建立系统彩色p e t r i 网模型后仿真不同调 度规则。 h u a n ga n dc h a n g 1 7 1 利用p e t r i 网构建出设备群组的仿真器，其中嵌入调度规则 选择引擎，同时，一个统计制程控制模块和一个设备维护模块与仿真器连接实现 更好的监控。 第一章绪论 9 h u i r a nl i u 1 8 】通过一种新的分层彩色时序p e t r i 网建立半导体制造系统的模型， 然后通过仿真调度规则探索实时调度的实现。 近年来，我国的学者也对车间生产调度作了大量的研究： 张国庆等人【1 9 】针对用数学方法解决计划编制问题所存在的适用范围的灵活性 等方面的不足，提出了生产计划编制的智能支持思想，他们通过对计划编制任务 分析和分解，用多库协调技术将决策者、计划模型、计划编制人员、经验和知识 有机地结合起来。 徐昌茂和李方军【2 0 】将决策支持系统引入到生产计划的编制中，他们提出了生产 决策支持系统的设计方法，并作了有意义的尝试。龙连文和王月霞1 2 l 】提出了一种 基于知识推理的专家系统模型，以实现作业排序问题的求解，并给出了采用三种 不同表示方式和分解推理的排序知识处理方法。仲伟俊、赫琪等人【2 2 】针对我国 c i m s 技术的应用，提出了建立有能力约束的提前拖期罚款下的准时生产作业计 划模型，利用拉格朗日松弛法和启发式方法，有效求解了大规模优化问题，获得 最优准时生产计划。汤和与袁俊良【2 3 】根据排序理论建立平行顺序移动方式下排序 问题的数学模型，提出了有效的启发式算法，初步实现计算机辅助编制作业计划。 胡立德等人【2 4 】详细研究了f m s 制造单元生产计划调度系统的功能需求，提出了由 单元生产作业计划、静态作业调度和实时动态作业调度三个调度层次组成的递阶 单元控制器生产计划调度系统。杨丹等人【2 5 】提出了按三维体系结构描述f m s 生产 调度问题的概念，建立了f m s 生产调度问题的四层结构模型。曹桂琴等【2 6 j 开发了 一个生产调度系统，建立以有向图表示的因果推理模型，生产计划的制定采用基 于面向对象环境的因果推理方法。王胤等【2 7 】开发了一种f m s 的可视化、分布式仿 真平台并成功的在该平台上实现了一种基于遗传算法的f m s 动态调度算法。饶运 清等【冽开发了一个集f m s 规划设计、计划调度、控制及仿真为一体的集成设计系 统。 由些可见，我国目前有关生产调度问题理论的研究及应用不仅仅局限在数学领 域，而且己开始涉及到仿真技术、人工智能、计算机科学等新技术领域，并开发 出相应的计算机辅助生产调度与管理系统，已逐步从理论研究阶段走向实用阶段。 1 4 本文的主要工作和章节安排 本文介绍了f m s 的建模和f m s 动态生产调度过程的仿真，工作侧重于f m s 动态生产调度过程中基于不同目标下的调度决策。通过生产线仿真来验证生产线 调度方案的操作性。 1 ) 研究典型柔性制造系统的模型设计和动态调度问题，建立一个更好的描述 了系统动态调度的思想的p e t r i 网模型； l o f m s 生产调度建模、优化与仿真研究 2 ) 基于f m s 生产调度过程中生产效率最高目标，建立生产效率优化模型； 3 ) 基于f m s 生产调度过程中生产成本最小目标，建立制造成本优化模型； 4 ) 通过仿真软件e m p l a n t 对系统进行仿真建模，运行系统得出数据，对数据 进行分析，并提出自己的看法。 本文章节的具体安排如下： 第一章为绪论部分，首先介绍论文的研究背景和选题的目的和意义，接着介绍 f m s 生产调度的建模方法和国内外生产调度的研究现状； 第二章重点研究了p e t r i 网在f m s 中的建模理论与方法，根据某产品的工艺信 息，建立了一个f m s 生产调度的非确定p e t r i 网模型； 第三章的重点主要放在调度算法的研究之上，提出了基于生产效率的启发式调 度优化算法和基于制造成本的启发式调度优化算法； 第四章利用e m p l a n t 仿真工具对一个制造单元进行仿真分析； 最后一章总结描述论文的创新、不足以及有待研究的方向。 第二章f m s 的生产调度p e l r i 网模型构建 1 l 第二章f m s 的生产调度p e t r i 网模型构建 2 1 1f m s 的布局组成及作用 2 1f m s 的物理模型 柔性制造系统的布局关系到f m s 整体性能，对f m s 的设计、制造、运行、维 护全过程的工作都有直接影响。f m s 布局合理还能降低f m s 的开发费用，缩短开 发周期。针对f m s 的特点，得出一种布局方法，如图2 1 所示。在这个布局图中， 包括机器人和小车两种物料运输系统。其中，机器人专门负责运送刀具，小车专 门负责运送工件。机床分布于系统的中央，夹在小车和机器人的轨道之间。上方 的刀具进出站的重用是机器人加工工件取出刀具和加工结束后送回刀具的周转 站。刀具进出和中央刀库相连，由刀具预调系统统一控制。控制室主要控制其它 设备。工件进入系统时首先进入装卸站，再由小车把毛坯运送到机床。当工件加 工完毕后由小车送出系统。 1r h1 1 席 阿丽司 l 调 i 1 - j 圜圈圆圈圜 厂 l 装卸站i 口 圆回 托盘缓冲站 _ llll 图2 1f m s 物理模型 f m s 生产调度建模、优化与仿真研究 2 1 2f m s 的运行策略 f m s 的单个工件的运行状况如图2 2 所示【2 9 1 ，毛坯被小车运入系统，同时机器 人接到命令，去刀具出入站领取刀具，当刀具和毛坯全部安装完毕时，系统开始 加工，加工完毕后，机器人送回刀具，工件由小车送出系统。 图2 2 工件调度模型 2 2f m s 的生产调度非确定p e t f i 网模型 制造系统是由一系列活动组成的，而活动又与资源联系在一起。制造中的活动 主要包括物流活动与信息流活动。物流活动的例子，如物料输送、零件加工、零 件装配等。信息流活动的例子，如数控程序传送、质量信息采集、质量信息统计 等。与活动联系在一起的资源包括原材料、机器、人员等，资源是活动的主体或 第二章f m s 的生产调度p e t r i 网模型构建 1 3 受体。在所有的建模方法中，p e t r i 网比较适合描述f m s 的离散事件动态系统【3 0 1 。 p e t r i 网是由c a p e t r i 博士于1 9 6 2 年创立的一种对分布、并发等系统进行描述 的工具。p e t r i 网不仅能描述系统的静态结构，也能描述系统的动态行为；它既有 有严格的数学基础，也有易理解的可视化表达，是一个理想的系统级描述工具。 正是由于p e t r i 网有强有力的表达能力、良好的数学基础和便于工程化等特点，p e t r i 网的应用范围也在日益扩大。如通信网络系统、计算机系统、机械制造系统等进 行建模和分析。8 0 年代以来，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 网、开放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 网均无法描述 这种特征。所以便有人提出了一种令牌驱动式计算模型，引入了后继支持系统的 概念，较好的解决了这个问题。经研究发现，令牌驱动式模型的控制结构的抽象 模型是一种称为非确定的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 网为确定的p e t r i 网。 2 2 1p e t r i 网的概念 为了后面描述的方便，先介绍几个p e t r i 网基本术语： 1 ) 资源：在系统中发生的变换所涉及的与系统状态有关的因素，称为资源。 2 ) 库所( 或称为位) ：资源按其在系统中的作用的分类，每一类存放在一处， 则该处抽象为一个相应的库所。库所不仅表示一个场所而且表示在该场所存放了 一定的资源。 3 ) 变迁：资源的消耗、使用及产生对应与库所的变化，p e t d 网理论中将此变 化称为变迁，又称t 元素。 4 ) 条件：如果一个库所只有两种状态，有令牌和无令牌，则该库所称为条件。 5 ) 事件：涉及条件的变迁称为事件。 6 ) 容量：库所对贮存资源的数量限制称为库所的容量。 p e t r i 网是一种可以用图形表示的组合模型，它由库所，变迁和有向弧组成，如 图2 3 。 1 4 f m s 生产调度建模、优化与仿真研究 图2 3 基本p e t r i 网 图中，圆圈表示库所，小矩形( 或短线) 表示变迁，带箭头的线条表示有向弧。 除了上述三种元素外，还可以在库所中加入可以沿着有向弧流动的托肯用来表示 系统的动态特性，托肯一般用实心黑点来表示，标记于圆圈( 库所) 之内。 定义1 ( 确定p e t r i 网) 三元组p n = ( s ，t ；f ) 称为确定p e t r i 网： 1 ) snt = 囝 2 ) sut g 3 ) f s tu 丁s 4 ) d o m ( f ) 1 jc o d ( f ) = su 丁其中，d o m ( f ) = xi 砂：( x ，y ) f ) ， c o a ( f ) = yl3 x ：( x ，y ) f ) 在实际系统中，s 和t 被分别称为位子集和变迁集，它们都是有限集。所以， 以下的讨论均在有限网的基础上进行。记为n 0 = 0 ，1 ，2 ，) ，n = 1 ，2 ，3 。 定义2 ( 确定p e t r i 网系统) 五元组= ( p ，t ；f ，w ，) 称为确定p e t r i 网系 统： 1 ) p n = ( p ，t ；f ) 为确定p e t r i 网，称为的基网； 2 ) m ：son o 称为p n 的标识； 3 ) 标识m o 称为系统得初始标识； 4 ) w ：f - - 4n 称为p n 的权函数。 定义3 ( 前位子集和后位子集) 设= ( s ，t ，f ，形，) 为确定p e t r i 网系统， t t ，则前位子集t 和后位子集t + 分别定义为： f = 川( s , t ) f ) ，t + = pi ( s ，t ) f ) 定义4 ( 确定p e t r i 网的发生权) 设= ( s r ，t ，f ，w ，m o ) ，m 是的基网 p n = ( s ，t ，f ) 上的一个标识，f t ，则t 在m 有发生权的条件是： v s t ，m ( s ) w ( s ，t ) ，记作m 【t 。 第二章f m s 的生产调度p e t r i 网模型构建 1 5 定义5 ( 确定p e t r i 网的发生结果) 设= ( s ，t ，f ，w ，i o ) ，m 是的基 网p n = ( s ，t ，f ) 上的一个标识，t t 。若m 畛，则t 在m 下发生的结果为m 的后继标识m ，m 的定义为：v s s ： i m ( s ) 一w ( s ，t ) 若s t - t 宰 m b ) = m o ) + 形。芦)若s r 一? ( 规则1 )、7 lm ( s ) 一w ( s ，f ) + w ( t ，s ) 若s t 奉n t im ( s )若s 萑t 幸u 。t 记作m t m ，显然m 是一个标识。 以上是确定p e t r i 网、网系统以及其上的变迁规则。在确定p e t r i 网系统中，如 果一个变迁有发生权，那么它发生的结果是所有后位子将按定义5 同时得到一个 数目的托肯。但在实际系统中还存在另外一种情况，即当某个变迁发生时，需要 在它后位子集中动态的选择至少几个( 最少一个) 位子按定义5 放置托肯。我们 将这种变迁称为非确定变迁，非确定变迁集记为t n 。， “： 定义6 ( 非确定变迁的发生结果) ：设= ( 尸，t ；f ，w ，m o ) ，m 是的基 网p n = ( p ，t ；f ) 上的一个标识，m t ，f 瓦则发生的结果为后继标记m m 定义为：v s s ： m ( s ) = m ( s ) 一w ( s ，f ) m ( s ) + w ( t ，s ) 若s t t 奉 m ( s )若s t 宰一t ( 规则2 ) m ( s ) 一m ( s ，t ) + w ( t ，s )若s tn t 木 或m ( s )若sg tu t 宰 m ( j ) 且最少有一个s t ，使m 0 ) = m 0 ) + w ( t ，s ) 或 m ( s ) = m ( s ) 一w ( s ，矿) + w ( t ，s ) 。记