（机械制造及其自动化专业论文）面向mes的半导体封装调度系统体系建模研究.pdfVIP

接要 面向m e s 的半导体封装调度系统体系建模研究 研究生：营杰 攮嚣老攥：黪秉耩教授 史金飞教授 学校：东南大学 摘要 本文针对半导体封装生产系统产品种类多、加工数量大，加工设备多、设备类囊多耨生产信怠 变化快的特点，掇出了面向m e s 的半导体封装调度系统架构，研究了面向m e s 的半静体封装调度 系统的建模方法，掇出了面向m e s 的半搏体封装的调度算法。并结合国家自然科学撼众项目“动态 质量信息的x m l 体系建模研究”( 7 0 2 7 2 0 4 6 ) ，对面向s 的半导体封装调度系统中信息的集成方 法进行了研究。 论文熬主要王终耱舞究成累如下： 1 ) 分祈了半警体封装生产系统豹特赢，指出半导体封装瓣生产调度其有产品释炎多、生产数 量、生产流程固滋、加工设备多、设备种类多、生产目标多样化与生产信息动态性的特点。结合半 导体封装企业信息系统的现状，提出了耐向m e s 的调度系统的安现方案。分析了半导体封装调度系 统的实现难点，指出系统的实现需要依靠装统建模、调度算法姆信息表达三个方面研究的突破。 2 ) 研究了蕊离m e s 的半导体封装调发系统的建模方法，擞如了基于着色p e t r i 剐孵建模方法。 分羲了半导嚣封装调魔系统建摸戆难点，淤分瑟着磊p e t r i 嬲隽蒸端，提出了静对复杂系绕筑建搂方 法。研究了蓉琶p e l f i 褥与s m l 静络含技术，善次提出7 菪琶羚饿两运算单元概念，解决了使用着 色p e t r i 实现逻辑遐算的难题。并以此为熬础。建立了生产线模型与调度算法合二为的半导体封装 调度系统模型。 3 ) 研究了蕊向i v i e s 的半导体封装调度系统的调度算法。指出半导体封装生产属于混合f l o w s h o p ( i - i f s ) 。在研究现有h f s 启发式算法盼基础上，提出了基于辑步法的n e h 改进算法( t n e h ) ， 势对t n e h 算法筑戆能递霞了验涯。分辑了半导蒋封装戆生产秘壤，鬏撂热王爱蚕掬玻笺杂静特点 提出了m o s tm a t c hm a c h i n e 设备势琵觏剿侵麾羞色p e 畦弼建藏了半导体封装调度傍囊测试系统， 研究了各种启发式算法在半导体封装调度中的性能，并分析了缓冲区排序规b 对调度的影响。研究 结果表明，t n e h 十u 吓可以获得最好的调度效果。 4 ) 分析了丽向i v i e s 的半导体封装调度信息的特点，提出了调度信息的x m l 表达模式 s i - x m l ，并对该横式中涉及的主要子模式进行了详细设计。为了赛现基于x m l 的数搬蓐优化设计， 提出了x m l 与美繁数撰痒褪弦会麓垅他方寰耪基于x m l - e r 懿数据转换方法，势遁避实捌涯锈7 基于x m l 瓣数据 掌耱技术鲍可行性。 5 )介绍了燕珑褥向m e s 的半导体封装调度系统的关键技术，包括n e t r e m o t i n g 技术、n e t 的x m l 访问技术鞠x m l 与数据库的转按技术。结合江苏长电科技股份有限公司生产调度系统开发 项目，详细介绍了调度系统的实现方法。 关键词：调度，硼隅、半导体封装、饕惫p e t r i 瓣、禹发式算法，x h 纯 l a b s t r a c t s t u d yo nam e s - o r i e n t e dm o d e l o fs c h e d u l i n gs y s t e mf o rs e m i c o n d u c t o r p a c k a g i n gm a n u f a c t u r i n g b y c a oj i e s u p e r v i s e db yp r o f z i - i o n gb i n g l i na n dp r o f s h ij i n f e i s o u t h e a s tu n i v e r s i t y a b s t r a c t t h es c h e d u l i n gp r o b l e mf o rs e m i c o n d u c t o rp a c k a g i n gm a n u f a c t u r i n gi sq u i t ec o m p l e x 。b e c a u s eo ft h e g r e a tp r o d u c tr a n g ea n dt h el a r g en u m b e ro fp r o c e s s i n ge q u i p m e n t s am e so r i e n t e dm o d e lo fs c h e d u l i n g s y s t e mi sp r e s e n t e d 弧er e s e a r c h o ft h em o d e li sc o m p o s e do ft h r e ep a r t s ，m o d e lf r a m e w o r k ，m o d e l l i n g m e t h o d sa n di n f o r m a t i o ne x p r e s s i o np a t t e r n s o t i tr e s e a r c hi sf u n d e db yt h en a t i o n a ln a m r a ls e i e n c c f o u n d a t i o np r o j e c t “s t u d yo n ) 舭s y s t e mm o d e l i n go fd y n a m i cq u a l i t yi n f o r m a t i o n 1 1 忙m a j o rp a r to f r e s e a r c hw o r kc a l lb ei n c l u d e di nf o l l o w i n gs e c t i o n s t h ef e a t u r e so ft h es e m i c o n d u c t o rp a c k a g i n gm a n u f a c t u r i n ga r ea n a l y z e d i ti sh a r dt os c h e d u l et h e p r o d u c t i o no fs e m i c o n d u c t o rp a c k a g i n g ，b e c a u s eo ft h ep r o d u c tr a n g ei sg r e a t , a n dt h en u m b e ro ft h e e q u i p m e n t s i sl a r g e am e so r i e n t e dm o d e lo fs c h e d u l i n gs y s t e mf o rs e m i c o n d u c t o rp a c k a g i n g m a n u f a c t u r i n gi ss e tu o 皿em o d e lf r a m e w o r ki sc o m p o s e do f f u n c t i o nf r a m e w o r k , t e c h n i cf r a m e w o r ka n d h a r d w a r ef r a m e w o r k t h ek e yt e c h n o l o g yo f t h em o d e l i sa n a l y z e d m o d e l l i n gm e t h o df o rs e m i c o n d u c t o rp a c k a g i n gm a n u f a c t u r i n gi sp r e s e n t e d i ti sb a s e do nc o l o u r o d p e 翻n e lt om o d e l l i n gac o m p l e xm a n u f a c t u r i n gs y s t e m , am e t h o db a s e do nh i e r a r c h i c a lp e t r in e ti s a d d r e s s e d b yu s i n gt h ec o l o u r c lp e t r in e ta n ds t a n d a r dm l an e wc o n c e p t c p nc a l c u l a t i n gu n i ti s i n t r o d u c e d s o m es c h e d u l i n ga l g o r i t h m sc a nb em o d e l e db yc o l o u r e dp e t r in e tw i t ht h e s ec p nc a l c u l a t i n g u n i t s t h ew h o l ep r o c e s so fb u i l d i n gt h em o d e lo fs c h e d u l i n gs y s t e mf o rs e m i c o n d u c t o rp a c k a g i n g m a n u f a c t u r i n gi si n t r o d u c e d t h es e m i c o n d u c t o rp a c k a g i n gm a n u f a c t u r i n gs y s t e mi sb e l o n gt oh y b r i dh o ws h o p ( h f s ) o nt h e b a s i so ft h ec m u e n th f ss c h e d u l i n ga l g o r i t h m s a l li m p r o v e dn e ha l g o r i t h mi sp r e s e n t e d t h i sn e w s c h e d u l i n ga l g o r i t h mi sp r o v e dt ob em o r ee f f e c t i v e l y b ys t u d y i n gt h ee n t i r o n m e n to fs e m i c o n d u c t o r p a c k a g i n gm a n u f a c t u r i n g ，an e wr u l e - m o s tm a t c hm a c h i n e ，i si n t r o d u c e dt oa l l o c a t ep a r a l l e lm a c h i n e s a t e s tm o d e lo fs c h e d u l i n gs y s t e mb a s e do nc o l o u t e dp e t r in e ti se s t a b l i s ht of i n do u tw h i c hs c h e d u l i n g a l g o r i t h m si sa d a p tt os e m i c o n d u c t o rp a c k a g i n gm a n u f a c t u r i n g t h er e s u l ts h o w st h a tt h ei m p r o v e dn e h a l g o r i t h mw i t h 岍r u l ei sb e s tc h o i c e t h r o u g ht h ea n a l y s i so fs e m i c o n d u c t o rp a c k a g i n gm a n u f a c t u r i n gi n f o r m a t i o n ，a ne x p r e s s i o np a t t e m b a s e do nx l v i li se s t a b l i s h e d t h es u b m o d e l so ft h ef r a m e w o r ka r ed i s c r i b di nd e t a i l t oo p t i m i z et h e d e s i g n o f d a t a b a s e i n x m l m o d e a m e t h o d o f d a t a t r a n s l a t i o n t e c h n o l o g y b a s e do n f i n t i t y - r e l a t i o n m o d e l a ne x a m p l o di sg i v e nt os h o wt h ec a p a b i l i t yo ft h i sm e t h o d t h ek e yr e a l i z a t i o nt e c h n o l o g yo fs c h e d u l i n gs y s t e mf o rs e m i c o n d u c t o rp a c k a g i n gm a n u f a c t u r i n gi s i n t r o d u c e d 。s u c ha s n e tr e m o t i n g ，x m l a c c e s s i n gt e c h n o l o g yi n n e ra n dt r a n s l a t i o nt e c h n o l o g yb e t w e e n x v l la n dd a t a b a s e t h e 煅o r i e n t e dm o d e lo fs c h e d u l i n gs y r s t e mf o rs e m i c o n d u c t o rp a c k a g i n g p a n u f a c t u r i n g h a sb e e nu s e di nap r o j e c tf o rj i a n g s uc h a n g j i a n ge l e c t r o n i c st e c h n o l o g yc o t h e r e a l i z a t i o no f t h es y s t e mi sd e s c r i b e di nd e t a i l k e yw o r d s ：s c h e d u l i n g 。m e s ，s e m i c o n d u c t o rp a c k a g i n gm a n u f a c t u r i n g ，c o l o u r e dp c 仃in e t , h e u r i s t i c s a l g o r i t h m , x m l n 缩略语对照表 缩略语对照表 首次出现 英文缩写英文全称中文全称 页码 b g ab a l lg r i da r r a y 球栅阵列封装 9 c d s c a m p b e l l ，d u d e k ，s m i t h c d s 启发式算法 4 c p nc o l o r e dp e t r in e t 着色p e t r i 网 7 d i pd u a li n l i n ep a c k a g e 单列直插式封装 9 d t d d o c u m e n t t y p e d e f i n i t i o n 文档类型定义 8 e - r e n t i t y r e l a t i o n s h i p实体一联系 7 2 e r p e n t e r p r i s er e s o u r c ep l a n n i n g 企业资源计划 1 f a mf i r s ta v a il a b l em a c h i n e最先可用设备分配规则 4 2 f i f of i s ti nf i r s to u t 先入先出 2 h f s h y b r i df l o ws h o p 混合流水线 4 l p t l o n g e s tp r o c e s s i n gt i m e 最大作业规划 4 m e s m a n u f a c t u r i n ge x e c u t i o ns y s t e m制造执行系统 1 m i s m a n a g e m e n ti n f o r m a ti o ns y s t e m 管理信息系统 2 m lm e t al a n g u a g e兀语言 2 8 m 删m o s tm a t c hm a c h i n e 最优匹配设备分配规则 8 m r p m a t e r i a lr e q u i r ep l a n n i n g物料需求计划 2 m r p i i m a n u f a c t u r i n gr e s o u r c ep l a n n i n g制造资源计划 2 多项式复杂程度的非确 n pn o n d e t e r m i n i s t i cp o l y n o m i a ll 定性问题 p c sp r o c e s sc o n t r o ls y s t e m 过程控制系统 6 p g ap i n g r i da r r a y引脚矩阵封装 9 q f pq u a df l a tp a c k a g e小型方块平面封装 9 r l p tr e m a i nl o n g e s tp r o c e s s i n gt i m e剩余最大作业规划 4 1 s a x s i m p l ea p i sf o rx m l ) ( m l 简单应用程序接口 8 0 s t a n d a r dg e n e r i cm a r k u p s g m l标准通用标记语言 6 3 l a n g u a g e s i - x m l s c h e d u l i n gi n f o r m a t i o nx m l 调度信息x m l 模式 8 s y n c h r o n i z e dm u i t i m e d i a s m i l 同步多媒体综合语言 8 i n t e g r a t i o nl a n g u a g e s m ls t a n d a r dm e t al a n g u a g e 标准元语言 7 s o ps m a l lo u t l i n ep a c k a g e 小外形封装 9 s p t s h o r t e s tp r o c e s s i n gt i m e最小作业规划 4 1 w 3 cw o r l dw i d ew e bc o n s o r t i u m 万维网联盟 3 x m le x t e n s i b l em a r k u pl a n g u a g e 可扩展标识语言 3 x p a t hx m lp a t hl a n g u a g e x m l 路径语言 8 1 x s d lx m ls c h e m ad e f i n i t i o nl a n g u a g ex m l 模式定义语言 6 4 v 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名： 盟 日期： 口6 。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：盟 导师签名：曼虹日期：皿 粤卅 第一章绪论 第一章绪论 1 1 课题的意义及目的 半导体产业是现代信息产业和信息社会的基础。半导体产业可细分为设计，晶圆制造、封装、 测试和服务等几个领域。我国的半导体产业经过2 0 多年的发展，已经具备了相当的规模，而半导体 封装产业是我国半导体产业的主要支撑点。据统计，2 0 0 4 年我国半导体产业的销售收入5 4 0 亿元， 集成电路产量2 2 0 亿块，其中封装业销售收入为2 9 0 亿元，占总产值的5 3 * 0 。到目前为止，国内共 有封装企事业单位1 8 0 余家，其生产主要面向代工。在生产规模确定的情况下，生产调度对于产品 的生产周期起决定性作用。通过生产调度缩短产品的生产时间，可有效地降低生产成本。因此解决 好生产调度问题对于国内的半导体封装企业来说是至关重要的。 半导体的封装是一个复杂的生产过程，封装生产具有很多的特殊性。归纳起来有以下几点：1 ) 面向订单。国内的半导体封装生产多为代客加工型。为了树立企业的信誉，赢取更多的客户，企业 的生产不仅要保证产品的质量，还要确保按时交付2 ) 产品型号多。半导体芯片的封装已经历了许 多代的变迁。半导体封装的类型和规格非常之多。企业为了扩大客户来源，必须能够加工尽可能多 的产品类型。3 ) 加工批次多，生产数量大。基于以数量取胜的经营理念，国内封装企业一方面积极 开拓客户，争取更多的订单，另一方面努力扩大生产规模，提高生产能力。国内有很多大型封装厂 的日加工批次和产量相当大。例如，江苏长电科技股份有限公司的分立器件生产线，日加工批次平 均在二十批左右，日产量超过1 0 0 0 万枚。4 ) 加工设各种类多，数量多。半导体封装生产从晶圆蘑 划片到测试包装入库有十一道主要工序，每一道工序需要不同的加工设备。不同封装类型的产品t 需要不同型号的加工设备。在半导体封装的生产工序上，通常用多机并行加工的方式满足产能的需 要。在某些瓶颈工序，如测试工序，加工设备的总量会超过一百台。 依靠计算机辅助生产调度，是生产管理发展的一个趋势。在很多行业中，如机械制造，钢铁冶 炼、石油化工等等，都已经开发出或提出了相应的生产调度系统。在半导体封装的前道晶圆制 造业中，业已有许多生产调度方面的研究成果”j 1 4 胪j 。然而在半导体封装业，由于存在以下问题未能 解决，生产调度方面的研究几乎为空白。 第一，调度系统与信息管理系统的整合。由于封装生产的加工批次多、生产数量大，半导体封 装调度系统需要处理的信息量大，难以通过人工录入的方式及时的获取数据。封装企业为了提高运 作效率，已普遍实施了m r p 、e r p 或是m e s 等信息管理系统。生产中的订单、物料和设备等信息 都被纳入了信息系统的管理之中，企业的生产管理模式也与信息管理系统相对应。所以，调度系统 只有与已有的信息管理系统结合起来，通过信息管理系统获得必要的数据，再将调度结果返回给信 息管理系统，才能确保调度的有效执行。但是，由于技术发展的多样化，现有的信息管理系统种类 繁多，各系统的运行平台及数据库平台存在着相当大的差异。调度系统与信息管理系统的整合，需 要解决操作系统、数据库、网络连接、数据接口等诸多技术问题。并且为了确保调度系统能与不同 的信息管理良好的衔接，调度系统在设计时应考虑架框的柔性和开放性。 第二，调度算法的突破。半导体封装生产具有多工序、多机并行加工的形式按生产调度中系 统复杂程度的分类，属于混合f l o w s h o p 生产( 混合流水线车间，以下简称h f s ) 。h f s 的调度问题 相当复杂。即使在仅有两个工序且其中只有一个工序具有并行机，调度的目标函数是最小化最大完 工时间这样最简单的情况下，h f s 的调度仍是n p h a r d 问题i o j 。而如半导体封装这样具有复杂生产 流程的h f s 调度问题则是强n p - h a r d 问题。针对h f s 问题，国内外的一些学者提出了分支定界法、 启发式算法、人工智能法等理论f _ ”。现有的理论在某些设定的场合下可以得到较好的解。但是对于 半导体封装系统，由于存在着生产工艺复杂，生产设备多样、调度多目标等问题，目前还没有算法 被公认为可以较好的解决半导体封装的调度问题。 第三，调度模型的实现。传统建模的方法是使用编程语言。由于半导体封装生产的复杂性，用 东南大学博士学位论文 编程实现调度系统模型既不直观，工作量也很大。更为重要的是，半导体封装生产具有动态性。生 产的流程、加工设备会随加工批次的不同，或随时间的推移发生一定的变化。用编程方式实现的调 度模型很难跟上生产系统发生的变化，调度系统维护的代价非常大。因此，不论是研究调度理论， 还是建立实际的半导体封装调度系统，都需要一种快速、直观的建模方法，以较短的时间，较小的 代价组建出调度系统模型。并能在生产系统发生变化时，允许使用者方便快速地调整模型。 第四，调度信息的表达与交换。调度信息包含大量数据，例如生产流程、加工批次、生产设备、 在制品数量和原材料库存等。表达存储大量调度信息的传统方法是将定量数据存储于数据库的数据 表中。这种方法不利于信息的集成、共享和分析，可扩展性差。很难应用于存在大量变数的调度系 统。因此，必须为调度信息提供一种良好的表达方法，具有高度的结构化、良好的扩展性、支持异 构系统，便于网络传输等特点。良好的调度信息表达模型将有助于调度系统的柔性和开放性。 本文的研究目标是提出符合实现生产需要的半导体封装调度系统的实现方案。研究工作将从以 下几个方面展开： ( 1 ) 研究面向半导体封装企业信息系统的调度系统架构 企业信息管理系统经历了从m i s 、m r p 、m r p i i 到e r p 、m e s 的发展过程”l 。目前e r p 和m e s 己成为封装企业的主流信息管理平台。e r p 主要面向供应链的管理。而i v i e s 着重于车 间层的管理，实现在统一的平台上对质屋控制、文档管理、生产调度等进行集成。许多封装企 业的m e s 系统中集成了基本的调度功能，可以实现单工序的调度优化。然而局部的调度优化无 法解决整体调度的最优问题。m e s 系统由于缺少调度理论的支持，无法对整个生产流程进行调 度优化。由于半导体封装调度问题属于h f s 调度，使用简单的调度规则很难得到最优解。所以， 调度系统必须建立在h f s 调度理论的基础之上。而半导体封装调度系统又必须与现有的m e s 系统相合起来，才能较好地解决实际的调度问题。因此作者认为，与m e s 系统相结合是半导体 封装调度系统的基本要求。调度系统的架构设计必须面向m e s ，调度系统的架构必须有一定的 柔性和开放性，能够适应与多种i v i e s 的兼容。本文将研究面向m e s 的调度系统的架构及其实 现的关键技术。 ( 2 ) 研究半导体封装调度系统的建模方法 目前调度系统的建模方法主要有排队网模型( q u e u i n gn e t w o r k s ) 、b r o w n i a n 模型、连续流 模型( f l u i dn e t w o r k s ) 和p e t r i 刚模型”j 。p e 仃i 网模型具有图形化的表现形式和严格的数学定义， 可以很好的描述加工过程中的并发、同步、共享、冲突等问题，因此被广泛应用于生产调度问 题的研究之中。由于p e t r i 网本身的语义过于简单，建立复杂的系统的模型比较困难”“。人们在 建立实际的调度系统时，常常使用高级p e 硒网着色p e t r i 网。着色p e t r i 网对p e t r i 网的语言 进行了扩展，加入了颜色、层次和时间等概念，在很大程度上增强了p e 砸网的建模能力。利用 着色p e t r i 网软件，用户可以很快地建立起一个简单系统的模型并进行仿真运行。然而面对复杂 系统，由于缺乏方法论的指导，使用着色p e t r i 网进行建模会变得十分困难。作者在早期的研究 中对着色p e m 网的建模能力做了一些探索【l “。本文将深入研究着色p e t r i 网建模的方法，提出 针对复杂系统的完整建模方法。并揭示使用着色p e t r i 网实现逻辑算法建模的方法。 ( 3 ) 研究适用于半导体封装调度系统的算法 1 9 7 3 年，s a l v a d o r 基于石油工业的背景，首次提出了h f s 环境的生产调度问题”“。以接下 来的3 0 年里，国内外的学者提出了整数规划法，启发式算法、人工智能法等理论解决h f s 问 题。研究证明，整数规划法对求解中、小规模的h f s 问题的最优解和近优解比较有效；启发式 算法虽然不能求出问题的最优解，但能在较短的时间内对规模较大的问题求出近优解，因此对 解决生产实际问题具有很高的应用价值“”。然而由于半导体封装生产流程复杂，生产过程存在 着相当多的变数。不论是整数规划法还是启发式算法都存在着目标单一性、缺乏交互性及对生 产环境进行了简化等问题。现有算法还无法较好地解决封装调度问题。另外，在以往的调度研 究中，通常使用f i f o 规则作为缓冲区分配规则。但是由于i - i f s 的特殊性，每道工序有多个并 行设各。在后面的各工序，如果还按前面的优先级排序，会出现设备空闲而工件排队等待的情 2 第一章绪论 况。这在实际生产中是不允许的。本文将以现有的i - i f s 启发式算法为基础，研究适合于半导体 封装调度的启发式算法，并探寻启发式算法与缓冲区分配规则的最佳组合。 ( 4 ) 研究封装调度系统的信息表达模式与交换技术 传统的信息管理方法是将定量数据存储于数据库的数据表中。这种方法不利于信息的集成、 共享与分析，可扩展性差，很难应用于信息变化量大的调度系统。x m l ( e x t e n s i b l em a r k u p l a n g u a g e ，可扩展标记语言) 是w 3 c ( w o r l dw i d e w e bc o n s o r t i u m ，互联网联合组织) 创建的 一组规范，其目的不仅在于满足不断增长的网络应用需求，同时还希望确保通过网络进行的交 互合作具有良好的可靠性与互操作性。它为基于网络的数据表示和数据交换提供了有效途径。 如果充分应用x m l 的基于网络的数据表示和数据交换功能，则有望较好地解决调度信息的表 达与共享问题。其基本思路为：首先应用x m l 基于网络的数据表示和数据交换功能将调度信 息转化并表达成规范化、结构化的数据存储格式，以实现调度信息网络共享的需要。 综上所述，本文将主要研究面向i v i e s 的调度系统架构、基于着色p e m 网的建模方法、封装调 度的启发式算法及调度信息的x m l 表达模式。并利用以上研究内容，建立适用于半导体封装生产 的调度系统。 1 2 相关领域及研究现状 1 2 1 生产调度 1 )生产调度的基本概念 生产调度是针对一项可分解的生产任务，探讨在尽可能满足约束条件( 如交货期、工艺路线和 资源情况等) 的前提下，通过下达生产指令，安排其组成部分( 操作) 使用哪些资源、其加工时间 及加工顺序，获得生产任务执行时间或成本的最优化“q 。 生产调度按加工系统的复杂度可分为单机、f l o ws h o p 、j o bs h o p 和多台并行机“。单机调度 问题是所有的操作任务都在单台机器上完成，为此存在任务的优化排队问题。f l o ws h o p 型问题假设 所有产品都在同样的设备上加工，并有一致的加工操作和加工顺序。j o bs h o p 是最一般的调度类型、 并不限制产品操作的加工设备，并允许一个产品加工具有不同的加工路径。多台并行机的调度问题 最为复杂，因而优化问题史加突出。 生产调度的准则分为调度费用和调度性能两类。调度费用包括与生产相关的固定费用、延迟代 价、库存代价等。调度性能包括许多不同的量度，如生产资源设备的利用率、任务的平均或最大延 迟或提前等。生产调度的目标一般分为两类：一类基于经济指标，另一类基于性能指标。在多层调 度结构中，高层的生产计划完成原料的分配，常用基于经济的目标函数；低层的调度完成任务的排 序与调度，常用基于性能的调度目标。基于经济的调度目标主要有：总体生产费用最小；由一种产 品到另一种产品的切换引起的切换与准备费用最小；生产利润最大等。基于性能的调度目标主要有： 全部产品生产所需要的总时间或生产周期( m a k e s p a n ) ；平均的产品流经时间( m e a nf l o wt i m e ) ；最 大的产品流经时间( f l o wt i m e ) ；平均的进度延迟时间；进度延迟时间( t a r d i n e s s ) ；最大进度延迟 时间；一种产品生产转为另一种产品生产所需要的转换或者准备费用( c h a n g - o v e r o rs e t u p c o s t ) ；产 品成本等。 生产调度的经典算法 1 9 5 4 年，j o h n s o n 对两台机床的f l o w s h o p 型调度问题进行研究后，生产调度问题逐渐引起了人 们的重视。早期的调度问题研究局限于整数规划法、仿真法和简单的规则。随着对调度问题计算复 杂性的研究，调度问题中的大部分被归结为n p - c o m p l e t e 问题。当调度问题规模扩大，特别是涉及 动态性和实时性时，这些方法不是调度结果不理想就是难以解决复杂的问题。近年来，随着各种新 的相关学科与优化技术的建立与各种交叉学科的发展，研究者从不同的角度提出了许多新的生产调 3 东南大学博士学位论文 度理论与方法。主要有启发式搜索法、模拟退火法、禁忌搜索法、遗传算法和蚁群算法等。例如， s t a r k w e a t h e r 应用遗传算法解决了多目标j o bs h o p 调度问题“。刘民用遗传算法解决并行多机调度问 题“。张纪会用遗传算法进行生产动态调度的知识获取“。a m a n c i o 用遗传算法解决流程工业中能 量和生产的调度优化问题“w 。王凌提出求解同顺序加工的改进遗传算法。s f i d h a r 使用模拟退火方 法进行单元制造系统的调度”“。张雪江提出了一种基于模拟退火法的知识获取方法j 。r a a y m a k e r s 使用模拟退火法来解决无等待约束的多目标流程企业的调度问题田j 。庞哈利提出求解最小化平均流 程时间的两阶段启发式算法”。熊红云使用面积补偿法构造解模糊f i o ws h o p 问题的有效遗传算法 ”1 。韦有双提出了改进的n e h 算法求解f l o w s h o p 问题”j 。姜桦将蚁群算法应用于生产调度中”。 3 )混合f l o ws h o p ( h f s ) 调度问题 1 9 7 3 年s a l v a d o r 基于石油工业的背景，首次对i - i f s 的生产调度问题进行研究“。h f s 的定义 为：工件在相同的加工阶段上加工，加工阶段的次序是相同的。加工阶段中至少有一个阶段有并行 机。每个工件在每个阶段中只能在其中一台设备上加工，每台设备同时最多只能加工一个工件。h f s 调度问题是一般意义上的j o bs h o p 带并行机( j s m p ) 调度问题加上工件工艺路线约束后形成的，实 际上是f l o ws h o p 问题和并行机问题的组合，这也是将它定义为混合流水车间的原因。 h f s 的调度问题相当复杂。即使在仅有两个工序且其中只有一个工序具有并行机，调度的目标 函数是最小化最大完工时间这样最简单的情况下，h f s 的调度即是n p h a r d 问题 6 1 。而如半导体封 装这样具有复杂生产流程的h f s 调度问题则是强n p h a r d 问题。目前针对 玎隧调度问题的求解方法 有分支定界法、启发式算法与人工智能法。 分支定界法包括下界的计算，分支和节点消除。分支定界算法可以精确求解。因此被广泛用于 获取h f s 的最优解。例如，s a l v a d o r 、b r a h l 2 9 1 提出了目标为最小最大完工时间的h f s 问题的分支 定界法。b r a h 在文献 3 0 冲给出了基于工件确定下界的方法，并指出当h f s 问题中的工件数和阶段 数较大时，基于工件界比基于机器界更有效。然而，分支定界理论很少应用于实际的调度问题。原 因是现有的分支定界算法是基于简化的设备环境而提出的，不能用于复杂的生产现场。当设备环境 较为复杂时，对于中等规模的调度问题，使用分支定界法将非常耗时。 由于h f s 调度问题是强n p - h a r d 问题，所有精确算法的执行时间随着问题规模的增加呈指数增 加。因此，研究者寄希望于使用启发式算法获得合理的调度。例如，v i g n i e r 提出基于最早交货期法 ( e d d ) 的启发式算法解决两级的h f s 问题”。g u p t a 提出基于最大作业规划( l p t ) 的启发式算 法”“。李霄峰提出基于改进的r a 斜度指标的启发式算法1 3 ，j 。文献 3 3 q a 提出用f l o ws h o p 的启发式 算法求解h i s 的调度问题，研究了设备选择规则与c d s 、n e h 、t o w 等启发式算法在对h f s 问题 的求解，并得出n e h 算法最佳的结论。 求解h i s 调度问题的另一类方法是使用人工智能算法，如遗传算法、禁忌搜索和模拟退火等。 然而由于人工智能算法的编码和搜索复杂，该方面的研究成果相对较少。王莉使用遗传算法对h f s 进行编码。p o r t m a n n r 提出用遗传算法改进分支定界法中的上界值 3 7 1 。吴云高利用遗传算法求解 h f s 调度问题”。 综上所述，虽然近年来有许多研究者对h i s 的调度提出了很多理论，但是能应用于工业现场的 还比较少。h f s 在理论研究方面作了相当的简化，因而问题显得有些抽象，忽略了许多实际中必须 考虑的约束。对于半导体封装这样复杂的h f s 系统，其生产流程、设备环境等都存在着很多的特殊 性。现有的分支定界法或启发式算法都不能较好地解决封装调度问题。本文将研究适用于半导体封 装实际生产环境的调度算法。 1 2 2 信息管理系统 第一代企业信息管理系统m i s ( m a n a g e m e n ti n f o r m a t i o ns y s t e m ) 出现于2 0 世纪7 0 年代末。 d i s 主要完成大量原始数据的记录、查询和汇总等功能。在接下来的2 0 多年中，分别出现了 m r p ( m a t e r i a l r e q u i r e p l a n n i n g ) 和m r p i i j 。m r p 对产品构成进行管理，借助计算机的运算能力及 4 第一章绪论 系统对客户订单、在库物料和产品构成的管理能力，将客户订单按照产品结构清单展开并计算物料 需求计划，实现减少并优化库存的目标。m r p i i 在m r p 管理系统的基础上，增加了对企业生产中 心、加工工时和生产能力等方面的管理，以实现计算机进行生产排程的功能，同时也将财务的功能 囊括进来，在企业中形成以计算机为核心的闭环管理系统。 2 0 世纪8 0 年代，美国计算机技术咨询和评估集团g a r t e r g r o u p i n c 提出了e r p 系统( e n t e r p r i s e r e s o u r c ep l a n n i n g ) 1 4 0 l 。e r e 系统以“供应链管理”为核心、强调供应链的管理、以“客户关系管 理”为前台重要支撑、突出以人为本的竞争机制、帮助企业实现制度刨新、追求企业团队协作、实 现电子商务，全面整合企业内外资源h “。由传统m r p i i 系统的制造、财务和销售等功能扩展到了人 力资源管理，分销管理、运输管理、仓库管理、质量管理、设备管理和决策支持等功能。 当e r p 进入中国后，国内的半导体封装企业纷纷建立起了e r p 系统。以江苏长江电子科技股份 有限公司( 以下简称长电科技) 为例，该企业于2 0 0 3 年完成了c d e r p ( 长电e r p ) 系统的实施。 c d e r p 分为三个层次，如图1 - 1 所示。底层是作用管理层，c d e r p 系统的所有数据将从该层采集： 第二层是业务管理层，根据其职能划分为采购管理、物料管理、生产管理、成品管理和销售管理， 这些业务管理层的模块采集底层数据，进行处理和平衡后产生资金计划、采购计划、物料需求计划、 主生产计划、生产能力和销售计划；系统的最顶层是企业决策层，它负责对整个企业的物流、资金 流进行宏观调控，也就是根据各业务部门汇总统计的数据信息进行企业内部所有资源的计划控制。 圈， 圈一 ( d- 亘多t 采购一* 物漉 教据 二j 至多，物譬科 勘( 墅至) ，生产企划部，i c 生警辩豫生管科蕃片供应科 重盛( 9 戚鲋 重量盘 ( 竺兰兰兰) 戚警科 肼。 对t p e t r i 网c p n 的两个标识肘和肼，若存在激发序列b 使得m m ，则称肘为从肼可达的。 记m 的可达标识集为刖 f ) 。 3 1 2 着色p e t r i 网动态特性 与着色p c 啪网初始标识有关的性质称为p e t r i 网的动态特性。着色p e t r i 网主要具有以下动态特 性： 1 ) 可达性 在着色p e t r i