（控制理论与控制工程专业论文）生产调度设备流程工艺图配置优化及其自动生成.pdf

山东大学硕士学位论文 摘要 在生产调度领域中关于建模方法、算法求解等问题的研究 比较多，而对调度结果显示的研究还比较少。调度结果通常存 储在数据库表格中，设备间连接和物流走向通常以表格形式给 出，结果并不形象直观。调度人员通常依靠经验来对上次调度 结果进行分析，并做出下一次的调度决策。如果能够把数据库 中的数据提取出来，以设备流程工艺图的形式表达出来，则能 够大大减轻调度人员的工作量，因此本文将研究内容放在了基 于调度结果的生产调度设备流程工艺图配置优化及其自动生 成方面。 本文研究的生产调度设备流程工艺图配置优化及其自动生 成系统是国家8 6 3 项目“流程工业实时优化调度软件 f2 0 0 1 a a 4 13 4 2 0 ) ”的子系统。该系统通过对炼油厂生产设备单 元连接关系的研究，通过自动布局与自动布线，生成具有美观 规范的生产调度设备流程工艺图。本课题重点研究了设备流程 工艺图自动生成系统中布局和布线等问题。 本文在布局过程中分为列定位和行定位两个步骤进行。在 列定位过程中，根据实际生产过程中经常出现的设备间物料循 环走向形成反馈的情况，以反馈环作为流程图设备布局列定位 的基本框架，对设备列的位置进行定位，从而避免了迂回走线 的情况，更好地保持中间产品流向的连续性。在行定位过程中， 考虑到避免连线的交叉，减少长距离走线，借鉴重心法思想， 将输入输出相同的设备集中放置。在调整过程中，改变了原来 算法受初始点影响较大的缺点，动态的改变设备行的相对位 置。 本文在布线研究中采用基于知识的方法，根据实际绘图的 经验建立布线规则库，通过模式识别的方法对数据库表格中的 山东大学硕士学位论文 连线特征进行识别，从而在规则库中选择相应的布线规则，产 生美观规范的设备流程图。 在上述研究工作基础上，构造了一个较完善的设备流程工 艺图自动生成子系统，经过测试表明本系统工作正确，性能稳 定，能够有效解决设备流程工艺图的成图问题，为整个系统实 用化做出了贡献。 关键词：生产调度：设备流程工艺图：自动布局：自动布 线；布线规则库；可移动线性输入集合 i i 山东大学硕士学位论文 a b s t r a c t i nt h ef i e l do f p r o d u c t i o ns c h e d u l i n g ，t h e r e s e a r c ha b o u t m o d e l i n g a n d a l g o r i t h m i s m u c h ，b u t t h e s c h e d u l i n g r e s u l t v i e w i n gr es e a r c hi s al i t t l e t h es c h e d u l i n gr e s u l ti so f t e ns t o r e d i nd a t a b a s ea n dt h e l i n k i n g r e l a t i o nb e t w e e nt h ef a c i l i t i esi s u s u a l l yv i e w e db yt a b l e ，s ot h er e s u l ti s n o tv i v i de n o u g h t h e s c h e d u l i n gw o r k e ru s u a l l ym a k e s t h en e x ts c h e d u l i n gd e c i s i o nb y a n a l y z i n gt h es c h e d u l i n g r e s u l to nh i s e x p e r i e n c e i ft h e d a t a c o u l db ed i s t i l l e df r o mt h ed a t a b a s ea n dt h er es u l ti sv i e w e di n t h ef o r mo fs y s t e ms t r u c t u r es c h e m a t i cd i a g r a m s ，t h ew o r k l o a do f t h es c h e d u l i n gw o r k e rw o u l db el i g h t e n e dl a r g e l y o nt h eb a s eo f a n a l y z i n ga b o v e ，t h i s a r t i c l e m a i n l y d i s c u s s e dt h e p r o d u c t i o n s c h e d u l i n gf a c i l i t y s c h e m a t i c d i a g r a m s s t r u c t u r e o p t i m i z a t i o n a n dt h ea u t o m a t i cg e n e r a t i o no nb a s eo ft h es c h e d u l i n gr e s u l t t h e p r o d u c t i o ns c h e d u l i n gf a c i l i t y s c h e m a t i c d i a g r a m s s t r u c t u r e o p t i m i z a t i o n a n dt h ea u t o m a t i o n g e n e r a t i o ns y s t e m d i s c u ss e di nt h i sd i s s e r t a t i o ni sas u b s ys t e mo f “f l o wi n d u s t r y r e a lt i m eo p t i m i z a t i o ns c h e d u l i n gs o f t w a r e ”b y s t u d y i n gt h e r e l a t i o n s h i p b e t w e e nt h e p r o d u c t i o nf a c i l i t y u n i ti nt h e o i l r e f i n e d f a c t o r y ，p l a c i n gl o g i c u n i t s a u t o m a t i c a l l y a n d r o u t i n g l i n e s ，t h e s u b s y s t e m c a n a u t o m a t i c a l l yg e n e r a t e g o o d l o o k i n gp r o d u c t i o ns c h e d u l i n gf a c i l i t ys c h e m a t i cd i a g r a m s t h ek e y s t o n eo fo u rr e s e a r c hi st os o l v et h et e c h n i c a lp r o b l e m s p r o d u c e dd u r i n g t h e p r a c t i c a l i t y o fa u t o m a t i cs c h e m a t i c s g e n e r a t i n gs y s t e m i i i 山东大学硕士学位论文 i i 曼曼曼曼曼芭鼍寡曼曼曼曼曼! 皇曼置曼皇量曼墨矗曼量量皇曼曼皇曼曼曼! 曼詈曼皇曼曼皇鼍曼曼皇曼曼黑 t h e r ea r et w os t e p si nt h ep r o c e s so fl a y o u t ：c o l u m nl o c a t i o n a n dr o wl o c a t i o n i nt h ep r o c e s so fc o l u m nl o c a t i o n ，b a s e do n t h er e s e a r c ho nt h e c o m p l e xr e l a t i o n s h i pa m o n gt h e f e e d b a c k l o o p s ，w eu s et h ef e e d b a c kl o o p sa st h eb a s i cf r a m ea n dp l a c et h e c o l u m nl o c a t i o no ft h eu n i t s t h i sm e t h o dc o u l da v o i dt h eb y p a ss l i n k i n ga n dm a i n t a i nt h ec o n t i n u i t yo fm e d i c a lp r o d u c t i o n sf l o w b e t t e r + i nt h ep r o c e s so fr o w l o c a t i o n ，t a k et h ea v o i d i n gt h el i n e c r os sa n dr e d u c i n gt h el o n gl i n k i n g ，w eus et h em e t h o do fc e n t e r o fg r a v i t yf o rr e f e r e n c ea n dp u tt h eu n i t sw i t ht h es a m ei na n d o u t t o g e t h e r i nt h e p r o c e s so fa d j u s t i n g ，t h e f a u l t y o fb e i n g i n f l u e n c e db yi n i t i a lu n i ti no l da l g o r i t h mh a sb e e ni m p r o v e da n d t h e c o m p a r a t i v e r o wl o c a t i o n0 fu n i tw o u l db ea l t e r e d d y n a m i c a l l y i nt h er e s e a r c h0 fr o u t i n gl i n e s ，w eu s et h em e t h o db as e do n k n o w l e d g e a n db u i i tt h e r o u t i n g 1 i n esr u l eb a s eb a s e do nt h e e x p e r i e n c eo fp r a c t i c a ld r a w i n g w eu s et h e m e t h o do fp a t t e r n r e c o g n i t i o nt or e c o g n i z et h el i n e sa m o n g t h et a b l ei nt h ed a t a b a s e a n ds e l e c tt h er e l e v a n t r o u t i n g l i n e sr u l et o g e n e r a t e g o o d l o o k i n gp r o d u c t i o nf a c i l i t ys c h e m a t i cd i a g r a m s b a s e do nt h ea b o v er e s e a r c h w o r k s ，ap e r f e c ta u t o m a t i c p r o d u c t i o nf a c i l i t y s c h e m a t i c d i a g r a m sg e n e r a t o r h a sb e e n c o n s t r u c t e d t h et o o li s p r o v e nt o b ec o r r e c ta n ds t a b l e h a v i n g u n d e r g o n et e n s o ft e s t e x a m p l e s i tc a ns o l v et h e g e n e r a t i o n p r o b l e m o f p r o d u c t i o nf a c i l i t y s c h e m a t i c d i a g r a m s a n d c o n t r i b u t e sg r e a t l yt ot h ep r a c t i c a b i l “yo ft h ew h o l es y s t e m k e y w o r d s ：p r o d u c t i o ns c h e d u l i n g ；p r o d u c t i o nf a c i l i t ys c h e m a t i c d i a g r a m s ；a u t o m a t i cp l a c e m e n t ；a u t o m a t i cr o u t i n g ； r o u t i n gl i n e sr u l eb a s e ；m o v e a b l el i n e a r i t yi n s e t i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：玛先潮日期湖峰。一k 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅：本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：绉盟导师签名：拯日期： 2 o o # - 当一2 0 山东大学硕士学位论文 i i 第一章绪论 1 1 课题研究背景及选题的意义 随着过程工业生产规模的大型化、激烈的市场竞争和市场需 求的多样化，现代企业不但对过程控制的要求越来越高，而且对 优质、高效的生产管理的要求也越来越强烈。自动化孤岛模式己 不再适应现代工业企业的生产要求，国内外企业界已把注意力转 移到节能降耗、少投入多产出的高效生产模式上，即集直接数字 控制、监控优化、生产调度、经营决策等功能于一体的综合自动 化模式( c i p s ) 【“。 生产管理与调度是综合自动化系统的核心 2 - 3 】，直接关系到企 业的经济效益和社会效益。随着综合自动化的实施，人们已认识 到，单纯提高个别生产装置的控制水平，寻求局部最优的投入产 出比远远低于提高整体调度水平的投入产出比【4 】。因此国外许多 著名的公司在看到这一趋势后，纷纷推出自己的生产管理软件产 品，如i b m 、d e c 、l i n d e 、s e t p o i n t 和a b b 等公司推出了 r t p m s 、l i n k w o r k s 、o p t i s m 、p r o s k e d 和s i m c o n 等商 品化管理调度平台或软件，并推广应用到数百家工厂，取得十分 显著的经济效益。我国也已把优化调度列入国家计委“九五”攻 关任务，可以预料，这将进一步推动我国企业生产的发展，给国 民经济建设带来巨大的经济效益和社会效益。 调度问题就是在满足一定的约束的前提下，寻求某一调度目 标最优的过程，也就是在资源基础上确定最优的行为序列。调度 的复杂性、调度领域知识的多样性和生产环境的动态性决定了调 度问题的解决单纯依靠人或计算机是难以完成的，必须把人、人 工智能、数学规划和计算机有机结合起来去研究调度问题【“。 山东大学硕士学位论文 在生产调度领域中关于建模方法、算法求解等问题的研究比 较多，而对调度结果显示的研究还比较少。以流程工艺图的形式 将调度的结果形象直观的表达出来，对于调度人员的工作效率的 提高会产生很积极的影响。 设备流程工艺图问题的产生与p c b 问题有相似之处。超大规 模集成电路( v l s i ) 的飞速发展使信息产业成为2 0 世纪以来发展 最为迅速的产业，超大规模集成电路性能价格比的提高对信息产 业的发展举足轻重。集成电路技术正迅速向着更高集成度、超小 型化、高性能、高可靠性的方向发展，除了努力提高超大规模集 成电路的工艺，电路设计方式的变革也非常关键。专用集成电路 ( a s i c ) 技术直接面向客户需求，根据电路系统行为和功能要求， 自顶向下逐层完成相应产品的设计描述、综合与优化、模拟与验 证，最终生成满足用户设计需求的器件1 6 1 。传统的逻辑级设计方 法不但设计起来相当复杂，而且需要处理的数据量非常大，处理 时很难避免错误的出现，尤其是当出现错误时几乎无法对错误进 行定位和改正，难以适应市场对于产品在设计周期、效率方面的 要求，产生了严重的设计瓶颈。作为解决矛盾的一种有效途径， 高层次设计( h l d ，h i g hl e v e ld e s i g n ) 方法和工具正日益为设 计工程师所采用并逐步成为主流设计手段，高级综合就是其中突 出的代表。高级综合系统可以实现从算法行为级到逻辑级的设计 自动化，设计者可以集中精力于系统的行为功能设计，而不必限 于繁琐的逻辑设计当中，从丽可以极大的缩短设计周期，满足当 前专用集成电路设计的需要。经过二十余年的深入研究，目前已 经形成了比较成熟的高级综合理论和方法，提出了以图论、微码 压缩、整数线性规划等为基础的综合算法。进入八十年代以后， 以高级综合系统为核心的高层次设计自动化工具逐渐商品化。 c a d e n c e 、s y n o p s y s 和m e n t o r 等e d a 厂商纷纷推出新一代的e d a 工具。但由于高级综合是一个极其复杂的过程，而且伴随高级综 合深入实际设计，其应用和研究领域也极大地扩展，而以高级综 合为核心的新一代e d a 工具，由于其发展时间较短，无论其设 山东大学硕士学位论文 i i , 曼曼量曼鼍目目量曼曼皇曼 计自动化的水平，还是设计效果都难以满足设计人员的需要，尚 需进一步的研究与开发。 逻辑图作为人类表达电路设计思想的一种有力工具长期以来 己经为众多的设计人员广泛使用。在电路的设计过程中，设计人 员通过信号线将标准的图形符号连接形成逻辑原理图，借以直观 表达电路的功能信息。而在生产调度领域中设备流程工艺图则是 对系统流程结构一种有效的描述手段，为了增强调度结果的可观 性，有必要将设计的结果以流程工艺图的形式显示输出。这样一 方面可以帮助调度人员更好的理解调度结果，检查调度结果的正 确性，同时也有助于调度结果的备份和存档。随着现代化大规模 生产的高速发展，工厂设备越来越多，设备间的逻辑连接关系日 益复杂，要求调度人员根据调度结果和设备逻辑连接关系手工绘 制设备的流程工艺图是不现实的。工业自动化的发展使得设备流 程工艺图作为输出媒介或者显示媒介的使用已经逐步的进入议 程。 设备流程工艺图自动生成对于设备布局的设计和调度结果的 验证具有十分重要的意义，它为设计者提供必要和直观的反馈信 息。具体而言，流程图自动生成的作用主要体现在以下几个方面： 1 为高级综合及工艺映射提供形象的输出表示。 2 对生产调度结果的直观验证。设计人员可以通过自动生成 的设备流程工艺图对调度结果进行分析、修正。 3 设计存档。设备流程工艺图自动生成系统可将直观的调度 结果( 逻辑图) 作为文档予以保存，为今后进行调度结果的 查询验证提供依据。 4 自动化过程不仅能够提高绘图的效率，还可减少人工绘图 无法避免的错误，从而在一定程度上缩短生产调度周期。 基于上述背景，在国家8 6 3 项目“流程工业实时优化调度软 件”支持下，本文设计开发了生产调度设备流程工艺图配置优化 及其自动生成系统，该系统通过对炼油厂生产设备单元连接关系 的研究，通过自动布局与自动布线生成具有美观规范的基于调度 山东大学硕士学位论文 结果的生产调度设备流程工艺图。 1 2 设备流程工艺图自动生成系统概况 1 2 1 设备流程图自动生成系统发展和现状 早在7 0 年代初流程图自动生成问题就己经被提出17 8 1 ，但由 于受计算机技术及集成电路发展水平的制约，直至8 0 年中期， 才引起人们广泛的兴趣与深入的研究 9 - 14 ，到9 0 年代初期就已 经出现了大量介绍原理图自动生成系统和方法的文献【l5 。们。总 体而言，经过近二十年的发展，有关流程图自动生成问题的研究 形成了两种基本模式，一种是基于形式化算法的传统模式，另一 种是基于知识的途径，是人工智能的又一应用领域。 基于形式化算法的流程图自动生成 在早期的研究中，凡乎所有的流程图自动生成系统都将问题 集中在布局和布线两个方面进行研究，从而形成了一种基本的处 理模式。8 0 年代中后期至9 0 年代初期，人们将流程图自动生成 的算法应用到各自的系统实现中，相继出现了一些实用系统。这 一时期代表性的主要包括下述系统。 1 a s c g e n 系统【2 1 】 a s c g e n 系统出现于1 9 8 2 年，该系统最初的设计目标是为 印刷电路板( p c b ) 绘制原理图。a s c g e n 系统的主要贡献在于它 能够生成包含门级符号和芯片符号的图形，这种图形可以在很大 程度上帮助p c b 电路设计人员。但p c b 原理图中的电路设备通 常为规则的结构，而一般的逻辑原理图通常具有更多的设备数或 者是更不规则图形。a s c g e n 系统没有论及处理反馈的方法， 也没有提到任何完成复杂电路布局任务的方法 2 1 i t d 系统 i i t dc a d 系统是1 9 8 5 年由印度理工大学研制开发的一套计 算机辅助集成电路设计系统。其流程图自动生成系统指定结构式 4 山东大学硕士学位论文 的设计作为输入，该系统突出的特点在于它提出了两段式的处理 方法：逻辑阶段和物理阶段。提出两段式的布图方法主要目的是 简化流程图的生成过程。在逻辑阶段，构造统一的网格系统，忽 略各设备符号实际的几何形状，生成粗略草图。第二个阶段，即 物理阶段，进一步细化逻辑阶段的布图结果，最终生成完整的图 形。与传统的布局方法类似，该系统无论是在逻辑阶段还是在物 理阶段，都是由布局和布线两个步骤完成。在逻辑布局完成之后 确定信号流的方向，在布线完成之后确定各设备具体的物理位 置。在逻辑布局开始之前，首先要对连线进行分析，识别哪些连 线是总线，哪些连线是由左至右的普通信号线。最后对整个图面 进行压缩以保持图面的紧凑。该系统试图将人类绘图的经验转化 为定量目标，但由于这些目标之间错综复杂的关系，因而整个过 程由一系列冗长的步骤组成。系统试图为每个步骤定义一个精确 的公式及有效的解，必要时做合理的近似，但如何将人类绘图的 经验转化为具体的算法实现没有提出有效的方法，同时缺少形式 化的算法描述。此外，尽管该系统注意到拆环的重要性，但未提 出解决拆环问题的有效方法。 3 g e m s 系统 2 2 1 g e m s 系统出现于1 9 8 6 年，它是寄存器传输级综合工具m s s 的图形编辑子系统，该系统最具特色之处在于它所采用的布线算 法。在完成设备之间的互连过程中，g e m s 采用三种不同的布线 器，分别为：s n a k e 布线器、o u t s i d e 布线器及b u b b l e 布 线器。在将线网的源与目标相联接的过程中，分别按照指定的顺 序选择使用上述三种布线器中的一种或多种，直至搜索到通路为 止。“s n a k e ”布线器是在布线过程中首先使用的布线器，其设 计思想来源i c 布线中的线探索方法。对于每个连接，s n a k e 布 线器总是尽量寻找两个端口之间最直接的直角线路，从而避免不 必要的拐角。当s n a k e 布线器不能完成布线任务时，就交给 o u t s i d e 布线器进行处理。o u t s i d e 布线器选择距离源点和目 标点最近的边，并在布线过程中使用该边。g e m s 使用的第三个 山东大学硕士学位论文 布线器是b u b b l e 布线器，该布线器只是简单地对源点和目标 点采用唯一的标识符进行标记，即使在复杂而且曲折的线路中， 采用这种布线方法亦不会受到干扰。尽管g e m s 系统在布线方 面上作了比较深入的研究，但通过分析不难发现其布线算法主要 还是沿用经典的i c 布线算法，并不符合逻辑图布线的特点。此 外，其布局方法也有缺陷，布局过程只是简单的按照设备之间的 输入输出关系进行定位，缺少对反馈环路的识别和处理，因而对 于具有环路的设计电路无法进行有效的处理。 4 v i s i o n 系统 通过上述对原理图自动生成中基本问题的研究，自动生成的 图形质量较从前有很大改善。研究的重点也逐步从对布局、布线 规则的探讨转向环路的拆环及功能的划分等全局问题的思考， 1 9 8 7 年推出的v i s i o n 系统是代表性的系统之一。该系统主要 用于从门级数字逻辑电路的网表描述生成原理图。c h u n 等人认 为系统最终的目标是生成一个具有功能可读性的原理图。在实践 中，他们发现在门级电路中出现的反馈绝大多数可归于触发器和 环行振荡器两种类型。因此通过对触发器结构和环行振荡器( r i n g o s c i l l a t o r ) 结构的识别，系统能够处理电路中的反馈结构。尽管 c h u n 等人的工作仅能识别最基本的r s 触发器，但他们已经 注意到了实际电路中存在反馈结构的现象，并提出了初步的解决 方案。因而它对于逻辑原理图自动生成的研究起到了一定的推动 作用。 5 h e r e s y 系统l “ h e r e s y 系统由美国加州大学伯克利分校于1 9 9 1 年推出，与 其它逻辑图自动生成系统不同。该系统并不特别强调连线交叉及 拐角数的最小化而是精心选择了一组图形生成的评估标准，通过 在实现过程中强化这些优化目标( 评估标准) ，在很大程度上降低 连线交叉和拐角对图形可读性的影响。h e r e s y 系统将整个处理 过程分为：电路设备的模式识别、分层、第一层的布局与布线、 中间各层的布局与布线及最后一层的布局与布线。由此可以看出 6 山东大学硕士学位论文 h e r e s y 系统并不是将布局和布线过程完全区分开考虑，而是按 照层次的顺序将两者结合在一起考虑。但h e r e s y 系统并未给 出识别和处理反锁环路的具体算法，文中的实验示例是仅包含六 个模块的简单电路，不足以说明系统的实用性。 6 s p a r 系统 1 9 9 3 年推出的s p a r 系统又将用算法解决逻辑图自动生成的 研究工作推向一个更高的阶段。该系统将影响图形可读性的两个 原则：1 ) 电路逻辑功能的可辨认性( f u n c t i o n a li d e n t i f i c a t i o n ) 2 ) 连 线的可跟踪性( t r a c e a b i l i t y ) 作为系统实现的主要依据，并将这两 个原则贯穿于整个系统的实现过程中。s p a r 系统的自动生成过 程分为五个相对独立的阶段：网表的划分、页内设备的布局、总 体布线、局部布线及输入输出模块的添加。在实现过程中，系 统采用一种名为角钩链( c o r n e r s t i t c h i n g ) 的二维空间管理技术， 为设备的布局提供便利。在总体布线阶段，对拥挤程度和布线长 度的估计组成造价函数，并通过该造价函数指导布线。由于s p a r 系统具有以上特点，它所产生的逻辑图可读性相对较高。但同样 它也存在很大的局限性：对于规模较大的设计电路，系统布局、 布线耗费的时间量显著提高，而且生成图形的质量降低，因此不 能够适应当前大规模集成电路设计的需要。 基于知识的流程图一自动生成系统 流程图自动生成问题不同于以往的p c b 或i c 布图问题。对 于后者，整个问题的目标是尽量使互连线的长度最短、所占的芯 片面积最小同时满足一定的约束条件( 如时间延迟等) 。而且在同 一层绝对不允许存在连线的交叉。流程图自动生成结果的评价是 以清晰易读为标准的，即应当能够反映出流程图的结构与功能， 布局和布线则希望能符合某种习惯的表达规则，从而使阅图者能 尽快的把握其逻辑含义。因此，流程图自动生成的设计目标非常 主观而且不易确定，对于这类问题，部分学者认为更适于采用基 于知识方法。 1 9 8 5 年h o n e y w e l l 计算机科学中心的m l a h l s t r o n 等人开发 7 山东大学硕士学位论文 的h a l 系统就是个基于规则的专家系统。该系统适用于由 m i m o l a 硬件描述语言生成的流程图，为此选择了两位硬件设 计方面的专家，根据他们提供的启发知识建立强化的知识库。 h a l 实验系统中调用了大量的l i s p 程序，在流程图生成的初始 阶段，用o p s 5 规则调用l i s p 例程，开始对m i m o l a 硬件描述 文件的扫描和分析。然后o p s 5 规则调用l i s p 函数，将所需信 息从数据结构转移至o p s 5 环境中。o p s 5 规则主要分为两类： 布局规则和布线规则。其中布局规则包括控制、策略与设计操作。 控制操作决定系统的不同策略途径，策略操作规定将执行何种设 计操作，设计操作最终执行流程图中的模块布局。布线规则是在 模块定位的同时进行考虑的。h a l 系统的布线规则分为三种： 一段、三段和五段布线。当输出端口直接位于对应输入端口的上 方时，采用一段布线；当连线的输入端口在输出端口之下的左边 或右边时，采用三段布线。当待连接的输出模块位于输入模块的 下方时使用五段布线。基于知识的流程图自动生成的研究，主要 集中在对流程图局部结构进行优化的考虑，在某些单元的定位和 局部走线的安排上显得合理，但由于研究很少从问题的整体目标 上进行，在流程图的整体布图上略显不足，特别是对于具有反馈 结构电路的处理不能令人满意更重要的是此类系统的时间耗费 非常大，以o e m s 系统为例，其执行的时间比h a l 快8 10 倍。 由此可见纯粹采用基于知识的方法同样难于满足系统实用化的 要求。 1 2 2 设备流程图自动生成设计原则 所谓设备流程工艺图自动生成，实际上就是接受某种特定的 设备逻辑连接的描述，将工厂中的所有设备及其连接关系在同一 平面正确地表示。对于本系统其输入是生产调度结果所要求的设 备逻辑连接关系，系统通过对数据库中设备逻辑连接关系进行分 山东大学硕士学位论文 析，对设备进行自动布局，对设备问的连线自动布线，将调度结 果所要求的设备连接通过设备流程工艺图的形式输出。简言之设 备流程工艺图自动生成实际上就是设备逻辑符号及其互连线在 二维平面上的合理排列，同时标注文本注解以提高其可读性。 k u m a r 等人对设备流程工艺图自动生成问题简单定义如下： 假设给定： 1 ) 设备集合m 2 ) 线网集合n 3 ) 引脚集合t 4 ) t t ，引脚t 位于设备边沿且具有一定的方向性，即对应 于i n 、o u t 两种端口模式中的任意种 5 ) m m ，m 上的引脚集合m ( t ) c t ；若系统输入和输出分别 为s 平口t ，贝0 有s m ，t m 6 ) n n ，n 上的引脚集合n ( t ) c t 求解： 1 ) 各个设备的位置 2 ) 线网通路 同时满足： 1 ) 任何一个设备不与其它设备重叠 2 ) 任何一条线网通路不与其它线网通路重叠 3 ) 信号线的总体流向自左至右 4 ) 尽可能减少通路长度，连线拐角及交叉 实际上，由于设备流程工艺图表达的是设计人员的主观设计 思想，尽管有约定的表达方式，但依然具有不同设计者的主观特 征，因此很难给出精确的定义和描述。以上只是对设备流程工艺 图自动生成问题的一个简单描述，同时也是系统应当达到的最基 本的要求。究竟什么样的设备流程工艺图能够既准确地表达设计 思想，同时又符合设计者的习惯，这一直都是设备流程工艺图自 动生成研究领域探索的焦点，有关学者对此作了大量研究，并提 出具有各自特点的设计规则，概括而言自动生成的流程图应具备 山东大学硕士学位论文 如下特点： 首先对于设备布局应当满足： _ 设备的布局应当均匀、对称、设备需按行或按列有规则地分 布 一设备的定位应当保证多数信号流向一致，通常为从左至右 _ 强连接的设备应当彼此相邻放置，这是由于在连接关系密切 的设备之间通常存在着某种工艺流程上的依赖关系【2 4 】 在布线方面满足： 连线之间允许存在交叉，但需要尽量避免不必要的交叉 一直线最能清晰表达设备之间的连接关系，因而应尽量减少连 线拐角 一虽然线网通路长度最小化并非主要的约束特征，但要避免迂 回走线 总之，设备流程工艺图自动生成系统必须以其输出结果是否 易为设计人员所理解来评判其优劣。换言之，它必须能够迅速而 且准确表达设备之间的连接关系。由于上述规则难以转换为定量 的表述，而且对于一个给定的设备连接，同时满足上述所有约束 也是不现实的，理论证明这是一个n p 完全问题 25 】，因此在设计 实现设备流程工艺图自动生成系统时，我们必须找出最能反映原 理图本质的因素，尽量将各种设计规则之间的冲突减少到最小， 在合理的时问内使生成的设备流程工艺图尽可能美观、易读。同 时可以看出，正是由于该问题的主观性和复杂性，设备流程工：艺 图自动生成问题只能通过启发式或者局部优化的方法来解决。 从上面的论述中可以看出，流程图自动生成技术发展至今相 对比较成熟，流程图所能提供给设计人员的简洁、直观的电路功 能和结构图，是其它任何形式的描述方式无法比拟的。纵观前人 的研究工作，本文认为还存在以下问题有待于进一步研究解决： 1 ) 从实际工作中可以看出，由于研究流程图自动生成的困难在 于它的最优标准是主观的、未明确定义的，因而先前的工作 主要集中在设计规则的探寻及围绕这些规则所进行的布局、 山东大学硕士学位论文 布线算法的研究。人们最关心的是布图的质量。在一个交互 式设计系统中，“快速响应”对于用户来讲是至关重要的，因 而，规模与速度问题是该领域中亟待解决的问题。 2 ) 在实际的设备连接中，通常难免会存在反馈，这在流程图中 表现为一环路结构，此时涉及到对环路的处理问题。由于恢 问题不仅要处理反馈环路内部的产品物料流向，而且还涉及 反馈环路与其它单元的相对关系，因此一直都是流程图自动 生成领域中的一个难题。尽管部分学者涉及这方砸的瑚f 究工 作，但至今尚未提出理想的解决方案，因而对于反馈环路的 处理问题还有待于进行更深入的研究。 3 ) 流程图的布线问题是n p 完全问题，鉴于i c 布线算法的成熟 性，多数流程图自动生成系统仍沿用i c 布线中的经典算法如 李氏迷路法、线探索法等完成流程图的布线。然雨流程图布 线与i c 布线的优化目标具有很大差异，它允许连线之削存在 交叉，也不要求连线长度最短。其追求的最终目标是线网布 线在整体上的简洁性和易读性，机械套用i c 布线算法不仅增 加系统在运算时间方面的开销，而且布线结果也不能恰当反 映流程图的特征。因此需要结合流程图自身的特点并针对其 特定的优化目标设计相应的布线算法。 本文将针对上述问题，展开流程图自动生成系统实用化的研 究研究的重点是通过建立合理的布图模型、采用优化的布图算 法，在前人研究的基础上将流程图自动生成问题引入生产调度领 域中，形成生产调度设备流程工艺图。 1 3 本文研究的主要内容 本文研究的重点是通过建立合理的布图模型、采用优化布图 算法，解决生产调度设备流程工艺图自动生成问题，使其成为实 用化的工具。本系统中设备流程工艺图自动生成主要由两个相对 独立的过程完成，它们分别是自动布局过程和自动布线过程。 山东大学硕士学位论文 1 3 1 设备流程工艺图的自动布局 自动布局是设备流程工艺图自动生成系统的第一个步骤。也是 非常重要的一个环节，其结果的优劣将直接影响整个图形的质 量。布局阶段的任务是将设备放置在适当的位置，使其满足一定 的目标要求。通常我们把图面的紧凑、图形的均匀对称等目标作 为自动布局过程的主要评价指标，同时布局的结果应当能够为布 线提供便利并且保持产品物料得的流向一致性。本文通过研究设 备连接形成反馈环的复杂关系，以避免迂回走线为目标，采用基 于反馈环的行定位算法，对设备的横向坐标进行初步定位，可以 更好地反映或保持物料流向的连续性。算法考虑系统中设备与外 部输入( 出) 的连接关系，以此作为系统初始定位的依据，一定程 度上避免输入与输出连线的交错，使布局结果更好体现出系统中 各个设备的连接关系。在列定位过程中，通过手工绘图，发现一 种可移动线性输入集合，可将其尽可能放置在相邻位置，减少长 距离走线，从而在一定程度上减少连线交叉。与传统的动态规划、 模拟退火等布局优化算法相比，该算法具有较强的实用性，更适 于解决大规模逻辑图的布局问题。 1 3 2 设备流程工艺图的自动布线 自动布线用于完成设备之间的连接，即确定逻辑图中的每条 连线的具体位置。这主要包括确定连线的走向及其在图形中占据 的具体位置。布线阶段的首要目标是确保连接关系正确，在此基 础上对布线的结果进行优化。在布线过程中，要尽量避免连线重 叠及连线交叉。在保证连线走线清晰、分布均匀的基础上尽可能 减小连线的长度和拐角数量。根据系统设计的需要，采用了符合 流程图特点的基于知识的布线策略。借鉴i c 布线中分级布线的 思想，将布线问题划分为整体布线和区域布线，通过分阶段优化 的策略来解决流程图布线阶段优化目标多的特点。 山东大学硕士学位论文 1 4 本章小结 本章阐明了论文课题的研究背景和意义，介绍了流程图自动 生成系统的发展概况及其重要性，并概要介绍流程图自动生成系 统的基本结构，确定了本文的主要研究工作。 山东大学硕士学位论文 第二章设备流程工艺图的自动布局 2 1 自动布局特点及目标要求 我们在以前的工作中主要进行的是在p c b 问题中自动布局技 术的研究。在p c b 关于自动布局问题的研究中，主要是考虑工 艺和电学上的约束条件，例如某些模块必须邻接安置、某些模块 必须布在芯片周围、模块之间不可重叠、信号线不能相交、电源 线的散热要求等等，布局的目标包括芯片面积最小、布通效率最 高、电性能最优等。但是，流程工艺图自动生成领域中的布局问 题与p c b 中的自动布局问题有着很大的差别，目标要求截然不 同。 在流程工艺图自动生成领域中，我们的目标要求是美观大方， 工艺图线路清晰，便于工作人员的读图。显而易见，流程工艺图 自动生成的目标主观性很强，没有明确定义，我们很难用数学定 义来对这个目标进行描述，只能根据作图过程中的经验和人们通 常的判断标准来对此类问题进行表达。人们通常认为美观的图形 其构成元素要均匀、对称，具有整体性，物流方向整体基本致， 输入设备通常放置在图形左端，输出设备放置在右端，以保证图 形的对称性。总而言之，流程工艺图自动生成系统必须能够迅速 而且准确的传达各个设备之间的连接关系，并且以其输出结果是 否容易为工作人员所理解来评判其优劣。 本章重点讨论流程工艺图的布局问题。所谓流程工艺图的布 局，就是将设备在同一平面上合理排放，为后期的布线工作做好 准备，使得做出的图形美观大方，满足目标要求。流程图布局的 好坏将影响其布线过程，并将直接影响到最终生成的流程图的质 量，因而自动布局是流程工艺图自动生成的关键。本文将按照人 山东大学硕士学位论文 们的阅图习惯，并且将自动布线的影响考虑进来，从实际出发综 合衡量各项评价指标，总结出符合实际的一些优化目标，对设备 进行布局定位。 1 ) 正确性 布局结果能够正确反映数据库中所描述的设备间的连接关 系。 2 1 整体性 布局结果保证图形均匀，对称，如果设备过多集中在局部， 很难产生美感。 3 ) 流向性 布局结果保证流程图中设备物流方向基本一致，尽量减少不 必要的反馈线。 4 ) 便利性 稚局结果能够为流程工艺图的布线工作做好准备，为布线提 供便利，减少连线的反馈和交叉。 流程工艺图的布局过程就是为各个设备进行定位的过程，这 是一个在二维平面内的定位，因此就涉及到每个设备的二维坐 标。本章首先通过对数据库的深度优先搜索，找到流程图中存在 的反馈环，以反馈环为基础对每个设备进行了列的初步定位，然 后通过行定位算法对设备的行坐标进行定位，最后基于重心法思 想完成设备的实际布局，从而完成整个流程图的布局过程。在流 程工艺图自动布局的整个过程中，上文提出的目标始终贯穿于本 文提出的启发式算法中。 2 2 流程图自动布局列定位算法 2 2 1 列定位过程中存在的问题 设备流程工艺图类似于图论中的有向图的概念。在流程图中， 每个设备对应于有向图的结点，设备之间的连线对应于有向图中 山东大学硕士学位论文 的边，物流的方向确定有向边的始结点和终结点。我们布局的结 果应该为后面的布线工作做好准备，使得布线的结果能够保证设 备间物流走向的整体一致性，而各个设备的相对位置对应着设备 间的物流走向，因此在布局阶段我们首先要确定各设备的相对位 置关系。如果流程图中不存在反馈环，即其对应的有向图为无环 图时，我们可以采用常见的广度优先搜索算法 2 6 - 2 8 】确定设备的 先后顺序，流程图中左端为系统输入，右端为系统输出。但是在 工业生产过程中，最常见的是一些设备的加工副产品需要返回到 其前驱设备中进行二次加工处理，还有一些设备的产品就是其前 驱设备的进料，这样就恰好形成一个局部的循环。由此可见，在 流程图中反馈环的存在不可避免，如果我们仅仅进行简单的搜 索，那么在很大程度上就会受到初始条件的影响。初始点的不同 就会产生不同的搜索顺序，那么同一个反馈回路对观察