（系统工程专业论文）基于蚁群算法的半导体生产线一体化调度方法.pdf

摘要 摘要 半导体生产线的控制与调度问题一直是学术界及工程界研究的热点，研究 半导体生产线的一体化调度具有重要的经济和学术价值。蚁群优化算法是模拟 蚁群觅食行为衍生而来的种并行搜索算法，已在多种组合优化问题中得以成 功运用。近年来，该算法在j o b s h o p 与f l o w - s h o p 调度中有所应用，但由于半 导体制造生产线调度的特殊复杂性，还未能成功运用于该问题求解。本文主要 探索在半导体生产制造复杂环境下该理论的应用。 首先，介绍了半导体生产线，指出半导体制造生产线调度具有大规模，非 零初始调度状态，设备负载不均衡，混合加工方式等特点，造成其调度问题具 有特殊复杂性。其次，介绍了蚁群优化算法基本原理及其应用。 再次，在分析了半导体生产线特点以及蚁群优化算法原理和应用的基础上， 分层次由浅入深展开研究。先针对半导体生产线中存在的批加工设备调度展开 研究，提出考虑未来到达工件的单台批加工设备蚁群优化调度方法与并行批加 工设备蚁群优化调度方法；然后以半导体生产线调度为对象，提出以瓶颈加工 中心为核心的，基于蚁群优化算法的半导体生产线排程方法。该方法首先获得 瓶颈加工中心排程方案，然后以其为约束，获得并行批加工设备排程方案，最 后以前面的排程方案为约束，递推其他设备的排程方案，最终形成一体化调度 方案。 最后，实现了基于蚁群优化算法的半导体生产调度仿真软件，整体功能是 在n e t 平台上实现的。利用该软件对基于蚁群优化算法的调度方案进行了验证， 并与e m - p l a n t7 0 上根据生产线建立的简单模型仿真进行对比，得到了满意的 结果。 关键词：半导体制造，蚁群优化算法理论，瓶颈调度，批加工设备调度 a b s t r a c t a b s t r a c t t h ec o n t r o l l i n ga n ds c h e d u l i n gp r o b l e mo fs e m i c o n d u c t o rf a b r i c a t i o nl i n eh a s a l w a y s b e e nt h eh o t s p o tf o rr e s e a r c h ；t h e r ea r ei m p o r t a n te c o n o m i ca n ds c i e n c e v a l u e si ni ta n tc o l o n yo p t i m i z a t i o na l g o r i t h mi sak i n do fp a r a l l e ls e a r c h i n g a l g o r i t h mw h i c hc o m e sf r o ms i m u l a t i n gt h ew a y a n t sl o o k i n gf o rf o o d , i th a sb e e n w e l lu s e di nl o t so fc o m b i n a t i o na n dc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m i nr e c e n t y e a r s ，t h i sa l g o r i t h mh a sb e e nu s e di nj o b - s h o pa n df l o w - s h o ps c h e d u l i n g ，b u ti th a s n o tb e e nu s e di nt h es e m i c o n d u c t o rf a b r i c a t i o nl i n ep r o b l e mf o rt h ec o m p l e x i t yo f t h e l i n e t b i sp a p e ri sm a i n l yt os e a r c hf o rt h ew a yt h a tt h et h e o r yu s e di nt h e c o m p l i c a t e ds e m i c o n d u c t o rf a b r i c a t i o ns i t u a t i o n f i r s to fa l l ，s e m i c o n d u c t o rf a b r i c a t i o nl i n ew a si n t r o d u c e d t h ec h a r a c t e r i s t i c s l i k el a r g e s c a l e ，n o n - z e r os t a t e ，u n b a l a n c e dl o a d ，m i x e dp r o c e s s i n ga n de t c ，m a k et h e s c h e d u l i n ge s p e c i a l l yc o m p l e x s e c o n d ，b a s i ct h e o r ya n da p p l i c a t i o no fa n tc o l o n y o p t i m i z a t i o na l g o r i t h mw a si n t r o d u c e d t h i r d ，b a s e do nt h ea n a l y s i so f t h et h e o r ya b o v e ，d e p l o y i n gt h er e s e a r c hf r o mt h e e a s yt ot h ed i f f i c u l ta n dc o m p l i c a t e d f i r s t l yr e s e a r c ht h es c h e d u l i n go fb a t c hm a c h i n e f r o mf a b r i c a t i o nl i n e ，t og e tt h ea c o s c h e d u l i n gm e t h o df o rb o t l ls i n g l em a c h i n ea n d m u l t i p l em a c h i n et h i n k i n ga b o u tt h ef u t u r ea r r i v a lt i m e t h e ng e tt h es c h e d u l i n g m e t h o db a s e do na c o a l g o r i t h mw h i c hc e n t e r i n go nb o t t l e n e c km a c h i n e b yt h i s m e t h o ds c h e d u l i n gp r o j e c to fb o t t l e n e c km a c h i n e sw a sg o t t e nf i r s t l y ，t h e nb a t c h m a c h i n e s ，i nt h ee n dt a k et h es c h e d u l i n gp r o j e c tg o t t e nb e f o r ea sr e s t r i c t i o n ，t og e t s c h e d u l i n gp r o j e c to f o t h e rm a c h i n e st of o r mt h ei n t e g r a t i v es c h e d u l i n gp r o j e c t i nt h ee n d ，t h ee m l u a t o rs o f t w a r ef o rt h es e m i c o n d u c t o rf a b r i c a t i o nl i n e s c h e d u l i n gw a sb u i l tb a s e do na c oa l g o r i t h m ，a n dt h ei n t e g r a t i v ef u n c t i o nw a s i m p l e m e n t e db a s e do n n e tp l a t f o r m b e t t e rr e s u l tw a sg o t t e na r e rc o m p a r i n gt h e s c h e d u l i n gp r o j e c tf r o mt h es y s t e m 晰t l lt h ep r o j e c tf r o me m - p l a n t7 0m o d e l k e yw o r d s ：s e m i c o n d u c t o rf a b r i c a t i o n , a n tc o l o n yo p t i m i z a t i o nt h e o r y ， b o t t l e n e c km a c h i n es c h e d u l i n g ，b a t c hm a c h i n es c h e d u l i n g i l 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版：在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第l 章绪论 第1 章绪论 1 1 研究工作的背景和意义 半导体生产线的控制与调度问题一直是学术界及工程界研究的热点。研究 半导体生产线的一体化调度具有重要的经济和学术价值。首先，良好的调度帮 助企业迅速响应市场的需求，提高产品满足客户的能力；缓解资本积累和缓冲 存储空间，减少芯片暴露于空气中的时间：也有利于协调工序之间的配合。其 次，半导体生产线是可重入生产线的典型代表，研究半导体生产线的控制与调 度问题，将极大地促进可重入生产系统调度研究的发展，而且对胶片、通讯等 可重入生产系统也有极大的参考价值。第三，半导体生产线具有设备多、产品 种类多、可重入、半成品报废与重加工、机器失效等特点，因而给生产线的调 度与控制带来了极大的复杂性。因此，设计出一类能真正解决现场实际问题的 用于调度、控制与性能分析的工具，改变目前人工调度与控制的不准确现状， 实现计算机控制生产过程具有重要意义。 本课题以半导体制造生产线调度为研究对象，以蚁群优化算法为主要工具， 充分考虑半导体生产线非零初始调度状态、混合加工方式、高度不确定性等特 点，提出生产排程与在线调度相结合的半导体生产线一体化调度新方法。该方 法能够根据生产线实际状态，获得可操作的全局优化的调度决策方案，指导生 产的实际运行。 蚁群优化算法是模拟蚁群觅食行为衍生而来的一种并行搜索算法，已在多 种组合优化问题中得以成功运用。近年来，该算法在j o b - s h o p 与f l o w - s h o p 调度 中有所应用，但由于半导体制造生产线调度的特殊复杂性，还未能成功运用于 该问题求解。本研究在充分考虑半导体制造生产线调度特点的基础上，使用蚁 群优化算法及其中的信息素间接交互机制获得具有解决实际生产调度问题的解 决方案，丰富了蚁群优化算法的应用研究领域：同时为半导体生产线调度问题求 解提供了新的思路与方法。 本课题的研究希望提出基于蚁群优化算法的适用于实际半导体生产线一体 化调度的求解方案，指导生产的实际运行，摆脱半导体生产线调度当前以启发 式规则及离散事件仿真技术为主的局面。 第l 章绪论 1 2 调度 1 2 1 制造系统中的计划、调度与控制 生产管理自动化系统的最优运行效果应该体现在：通过它的管理，能够将 输入的原材料等通过最经济、有效的生产活动，加工、装配成产品以供应市场。 制造过程中的物料流受控于一系列生产控制指令，这些指令的产生又是一系列 决策活动的结果，制定决策的基础和依据则是制造过程中的信息流。生产管理 自动化系统的计划、调度与控制就是借助制造过程中的信息流，制定出最优决 策方案并控制物料流，使制造过程以尽可能优化的方式运行。生产管理自动化 系统的计划、调度与控制的目标是通过对制造系统中各种资源的合理计划、调 度与控制，缩短产品的制造周期，减少在制品，降低库存，提高生产资源的利 用率f 1 】o 生产计划：生产计划( p r o d u c t i o np l a n n i n g ) 是企业为一段时间内的生产活 动制订的目标，一般是从总体上讲的，有效期比较长，且往往不涉及具体的设 备及加工工序。按涉及的时间长度不同，可分为年度计划、季度计划、月计划、 周计划、日计划等。随着时间粒度的细化，加工的产品会被明确在某个具体的 时间段内完成，但不指定某个具体的加工工序何时在哪台设备上完成。 生产作业计划( p r o d u c t i o no p e r a t i o n a lp l a n n i n g ) 则是在下达的月、旬或周 生产计划的基础上，根据制造系统中各种资源的实时状态数据，制定制造系统 具体的工序级生产作业计划。生产作业计划将确定计划期间内各种制造设备的 具体使用，每日班内加工的工件种类及数量等。该功能一般在车间级完成。 生产调度：生产调度( p r o d u c t i o ns c h e d u l i n g ) 是在满足工件加工流程和其 他约束条件的基础上，合理分配和利用生产线上有限的设备和资源，完成生产 活动并尽可能优化系统的性能指标。生产调度的结果是形成调度方案 ( s c h e d u l e ) ，即为加工任务的所有工序指定由某台设备在某个确定的时间段内 完成，通常可以表示为甘特图或进度表等形式。调度方法有静态调度与动态调 度之分。 静态调度( 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 ) 是依据动态变化的实时生产环境，逐步生 2 第1 章绪论 成调度方案并指导实际的生产过程。动态调度包括两个子问题，一是工件向设 备缓冲区的分派：二是缓冲区中的工件向设备上的分派。 工件向设备缓冲区的分派需以满足加工任务的工艺流程约束为条件，考虑 设备的实际工作状态，将工件分派到合适设备的缓冲区中，同时考虑生产作业 计划的要求，以及系统性能指标的优化。 缓冲区中的工件向设备的分派是为等待加工的工件排序，确定其加工优先 级，以满足生产作业计划的要求，并尽可能优化系统性能指标。 动态调度的实现方式有两种：一种是不使用静态调度方案，直接按照生产 系统中的工件和设备的状况以及相关信息，使用某种计算方法，实现工件向设 备缓冲区的分派或缓冲区中的工件向设备的分派，即所谓的实时调度( r e a l t i m e s c h e d u l i n g ) ；二是在已有静态调度方案的基础上，根据生产系统的现场状态， 及时进行静态调度方案的调整，此种方式也被称作“重调度”( r e s c h e d u l i n g ) 。 生产控制：上述生产管理自动化系统的生产计划与调度主要在制造系统的 中上层进行，其结果需要在实际运行中付诸实施，也就是通过设备级的控制来 具体完成由调度形成的生产任务。另外，制造系统在实际运行中往往会出现各 种随机的扰动，从而使系统的实际状态与期望状态之间产生偏差。此时，也需 要在制造系统的下层进行即时“生产控制”( p r o d u c t i o nc o n t r 0 1 ) ，在执行计划与 调度方案的同时，对可能出现的系统状态偏差进行校正或反馈。 由以上分析可知，计划是从上层对制造系统进行管理，以较粗的时间粒度 安排企业生产，其结果的表现形式是该时间段内生产的产品数量和或进度；生 产运作计划介于传统的计划与调度之间，确定计划期间内各种制造设施的具体 使用，每日班内加工的工件种类及数量等。调度的含义比较丰富，或是为调度 时段内的加工任务( 即工序) 指派时间和设备，生成诸如工序的加工时间表或 设备甘特图形式的调度方案，以保证生产活动按调度方案执行，进而获得较好 的系统性能指标；或是实时决策工件加工使用的设备或工件在设备上加工的优 先级。无论哪种调度，都应以生产计划为依据，以优化系统性能为目标。控制 则是对制造系统底层设备级的调控，使计划与调度方案得以具体实施，并对可 能出现的偏差及时加以有效处理。 文中介绍的基于蚁群算法的半导体生产线一体化调度方法就属于生产调度 中的静态调度，处于中间层。再进一步研究中如果能加入动态调度，将静态调 度与动态调度相结合，既能对生产线进行优化排程，又能对生产线上的突发事 3 第1 章绪论 件进行及时反应，这将增强了一体化调度方法的实用性。 1 2 2 调度问题概述 调度( s c h e d u l i n g ) 问题，也称排时或排序问题。典型的车间调度包括一个 要加工的工件集，每个工件的加工由一个工序集组成，各工序的执行需要占用 设备或其它资源，并且必须按各自的工艺流程进行加工；每台设备可加工工件 的若干工序，并且在不同的设备上能加工的工序集可以不同。调度的目标是将 工序合理地安排给各设备，并合理安排工序的加工顺序和开始加工的时间，使 约束条件被满足，同时优化一些特定的性能指标。 调度问题的研究工作是在制造业背景下发展起来的。一般认为，j o h n s o n 于 1 9 5 4 年发表的对两台机床的f l o w - s h o p 型调度问题的论文【i 】是最早的研究调度 问题的文献。此后，调度问题的研究因其应用范围的不断扩大而渐受关注，现 已发展成为- - f - j 集运筹学、系统科学、控制科学、管理科学与计算机科学等多 个学科领域于一体的交叉学科，广泛应用于工程技术和管理工程的各个领域， 但制造业的一些术语仍然用在调度问题的描述中【2 】1 3 j ： 工件( j o b ) ：指待完成的任务或作业，可以是待加工的零件、待执行的程 序，也可以是课程、节目等； 设备( m a c h i n e ) ：指完成工件加工所必须的主要的处理机，如机床、c p u 、 教室等，在本书的后续内容中，设备、机器、机床作为通用概念可以互换； 资源( r e s o u r c e ) ：指完成工件加工可能需要的辅助性的手段，如工具、材 料、人员等； 工序( o p e r a t i o n ) ：指工件加工所包含的最小任务单元，如零件的加工工序、 计算机程序的线程、课程中的一个课时等。一般地，一个工序的完成需花费一 定的加工时间t 。如果用向量t = ( f l ，t 2 ，t 。) t 表示一个工件各工序的加工时间， p 为该工件工艺流程中的工序总数，则完成一个工件加工需要的总加工时间t p 是其所有工序加工时间的代数和： 乃：兰 j 越 经典调度问题的描述如下： 定义：给定工件集- ，= - ，j 2 一，以 ( n 为工件总数) ，设备集 m - - m ，m 2 一，帆 ( m 为设备总数) ，资源集r = 僻，玛，r ) ( s 为资源总数) ， 4 第1 章绪论 每个工件的加工流程由工序集 ： ，n ，j n ，- ，帆 确定( p i 为工件i 的工序 总数) 。调度问题指的是在满足对工件、设备及资源的约束条件下，把设备m 和资源r 按时间分配到工件的各个加工工序j “，以使目标函数达到最优。 从以上对调度问题的定义可以看出，调度要解决的就是如何将有限的设备 和资源在不同的时间段内分配给不同的工序。从工序( 或任务) 的角度看，调 度结果就是个工序( 或任务) 在一个( 些) 时间段内占用设备和或资源；从设 备或资源的角度看，调度结果就是设备或资源在一系列的时间段内处理或加工 不同的工序( 或任务) 。 调度问题基本上由设备情况、工件性质和目标函数所决定，相应地，国际 上通常采用三邻域法( aibh ) 表示调度问题，其中： a 域描述设备情况，口= 口：，其中a l 用来描述设备类型，毗描述设备数量。 根据设备情况可将调度问题进行如图1 1 所示的分类。 设同型号机：加工速度相同 囊微调乓霈豺篡黧黧 蘑_ f l o w - s h o p 裟篙淼艺流 茬 。o p e n - s h o p ：工件的工艺流程是任意的 图1 1按机器类型对应的调度问题划分 p 域描述工件性质，萨p l p 2 p 3 f 1 4 p 5 p 6 ，其中p l 用来描述加工是否允许中断，艮 用来描述工件对设备以外其它资源的要求，f 1 3 用来描述工件之间的先后约束关 系，f 1 4 用来描述设备的整定时间( s e t - u p t i m e ) ，p 5 用来描述j o b s h o p 工件工序 的数目，b 6 用来描述工件工序的加工时间。 t 域描述要优化的目标函数，主要包括： 最大完工时间c 麟( m a x i m u mc o m p l e t i o nt i m e ) ，一般使g 嗽最小： m i n k 完工时间( c o m p l e t i o n t i m e ) 和 c j ，一般使完工时间和最小：坳2 q ； 第l 覃绪论 加权完工时间( w e i g h t e dc o m p l e t i o nt i m e ) 和篷嵋c i ，一般使加权完工时 间和最小：m i n f w j c i ； 最大误工时间l m a x ( m a x i m u ml a t e n e s st i m e ) ，一般使最大误工时间l m a x 最小：m i n k ) ； 误工工件数u ( n u m b e ro f l a t e j o b ) ，一般使误工工件数u 最少：m i u 。 三邻域法在调度问题研究中已被普遍采用，本文第四章建立的基于蚁群优 化算法的一体化调度的数学模型就是采用三邻域法建立的。将半导体生产线上 的设备m ，工件l 和表示排程的优化目标函数的g 与三邻域法中的alpl 丫一 一对应了起来。 1 2 3 调度问题的研究现状 前己述及，对调度问题的研究是在制造业背景下发展起来的，目前其研究 对象虽然涉及工程技术和经济管理的各个领域，但制造系统的调度问题仍然是 人们的主要研究热点。现对经典调度问题的研究现状进行简要综述。 经典调度问题的研究多针对j o b - s h o p 和f l o w - s h o p 两类系统，且一般是对静 态和确定性调度问题进行研究，研究方法也多是采用基于运筹学的方法，如排 队论【4 】、整数规划【5 1 、分支定界法【6 】等。 调度问题的一个重要特点是只要将模型条件稍加改变，适用于该模型的算 法及不适用。s m j o l l n s o n 【1 l 于1 9 5 4 年解决了两台机器同顺序的调度问题后， 人们试图将其推广到三台及以上的机器上去，但直到1 9 7 7 年，才有人证明三台 机器同顺序排序问题是一个n p 完备问题【2 】。 近几十年来，针对各类单机调度问题的研究工作取得了大量的研究成果。 b r o w n 等人【刀研究了基本加工时间为随机变量的一类非线性加工时间的单机调 度问题，得出加工时间在各种增函数情况下获得最优调度方案的排序算法，其 结论可推广到加工时间为确定值的情况。g u p t a 等人【8 】对加工时间为多项式函数 的非线性加工时间单机调度问题也进行了研究，并给出了极小化最大完工时间 的启发式算法。k u b i a k , c h e n g 与b a c h m a n 等人【9 】【1 0 1 【1 1 1 证明了单机调度问题中， 当加工时间为增函数时，极小化最大延误问题是强n p 难的。 由于调度问题一般具有较大的规模，实际生产系统的调度问题更是如此， 其求解是n p 难的，采用基于运筹学的方法受到了限制。而启发式调度规则具有 实现简单，计算量小，对静态及动态调度问题都适用的特点，因而获得了大量 的研究和应用。b l a c k s o n e ，p a n w a l k a r 等人【1 2 1 f 1 3 1 对启发式规则进行了综合分析。 6 第l 章绪论 但启发式规则实际上是一种分派( d i s p a t c h i n g ) 规则，可动态地根据当前状态确 定下一个要加工的工件，因而不能直接得到经( 全局) 优化的调度方案。随着 计算机运行速度的飞速提高，人们希望寻找新的近似调度方法，用合理的计算 时间代价，取得比基于启发式规则更好的调度方案。如a d a m s 等人 1 4 1 提出了移 动瓶颈算法，可解决j o b - s h o p 调度问题，并能获得较好的调度方案。 近年来，计算智能技术得到了迅速发展，其在制造系统调度问题的求解也 得到了越来越广泛的研究和应用1 1 5 1 。d a v i s 、刘民、g u o 、j o h n 等人【1 6 】f l r l 1 8 】【1 9 】 利用研究了遗传算法在j o b s h o p 调度问题中的应用；n o w i c h i 等人 2 0 1 提出了一种 解决f l o w s h o p 调度问题的快速禁忌搜索算法，孙元凯【2 l j 提出了基于禁忌搜索算 法的i o b - s h o p 调度算法；张长水等人 2 2 1 研究了应用人工神经网络技术来解决 j o b - s h o p 调度问题；d r o n d o r f 等人1 2 3 】研究了用进化算法解决j o b _ s h o p 调度问题时， 如何结合知识学习来改进个体性能的问题；m a t s u o 、l a a r h o v e n 等人阱】【2 5 1 研究了 模拟退火算法在解决j o b - s h o p 调度问题中的应用等。但这类基于智能算法的调 度问题解决方法存在一个缺点，即不能用来解决大规模的调度问题，一旦调度 问题的规模变大，就会因计算量骤增而致算法失效。 目前，对群体智能的研究尚处于初级阶段，但是由于其所具有的分布式、 自组织性、协作性、鲁棒性等特点，使之在没有全局信息的情况下，为寻找复 杂问题的解决方案提供了快速可靠的基础。目前，群体智能解决调度问题的应 用还相对较少，但也有一些研究成果。例如汪镭等【2 6 j 将粒子群算法用于半导体 制造后段工艺封装的调度中，李莉，乔非【2 7 】等模拟蚁群生态系统，提出了半导 体生产线群体智能调度模型。 基于启发式规则的调度方法所进行的优化一般只考虑了局部因素，且不能 直接产生调度方案，因此引入仿真作为评价启发式规则有效性的工具。也有学 者研究仿真技术在解决制造系统调度问题中的应用，如c h o n g 等人团】研究了离 散时间仿真技术在解决动态离散制造系统调度问题中的应用。 从本质上讲，基于运筹学的研究方法是从所有可能出现的组合中选取最优 的调度方案，所以需对可行的调度方案进行全部或部分枚举；而基于智能计算 的研究方法只是巧妙的避开了某些显然不是最优的调度方案，其解决问题的方 法并没有本质上的改变。因此，这两种方法虽然是从全局的角度寻求最优调度 方案，但不能有效地解决大规模的调度问题。基于启发式规则的方法简单易行， 能够适用于大规模的调度问题，但其解决问题的角度是局部的，即不能寻求全 7 第1 章绪论 局最优调度方案。随着计算机技术的迅速发展，商用c p u 的运算速度已大大提 高，使得对大规模离散制造系统的生产过程进行仿真运行所花的时间代价大大 降低。因此，对含有大量不确定性因素的离散事件动态系统的动态调度问题来 讲，基于分派规则和仿真技术相结合的调度方法研究变得可行，且有希望成为 新的研究热点。 1 3 论文的内容安排 1 3 1 课题来源 本课题来自国家自然科学基金重点项目“组件化可重构多重入复杂制造系统 生产计划与调度体系结构及其关键技术研究( 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 3 2 论文结构 本文主要在蚁群优化算法的思想上，提出了基于蚁群优化算法的半导体生 产线调度算法，能够有效地改进半导体生产线调度现状，为半导体制造厂提供 一种提高生产效率、创造更高收益的解决方案。 依据上述思想，本文个章节的具体安排如下： 第二章主要介绍了半导体产业的战略意义和半导体制造系统的高度复杂 性，从而引出了半导体研究半导体生产线问题的重要性和复杂性。通过对半导 体生产线调度问题、特点和研究现状的分析，指出了半导体研究的发展方向。 第三章主要介绍了蚁群优化算法的基本原理，并给出了蚁群优化算法的算 法模型和算法结构，分析了蚁群优化算法的适用范围以及解决问题的方法。其 中还包含对蚁群优化算法研究进展和应用领域的介绍，能更进一步明晰其发展 方向和发展中的问题。 第四章主要介绍了一体化调度方案，给出了一体化调度方案的模型，以及 详细的一体化调度方法，其中详细描述了如何利用蚁群优化算法来实现半导体 生产线上调度优化问题，并给出了算法的详细流程和说明及算法的优化方法 第五章主要介绍了基于蚁群优化算法的半导体调度系统的设计，对于这样 一个系统应采用软件工程的思想来对其进行分析和设计，其中包括需求分析、 8 第1 章绪论 数据库设计、系统框架设计以及系统实现等。通过对系统的分析与设计，使得 系统的进一步实现更加容易。并通过仿真得出该方法与e m p l a n t7 0 平台仿真 结果的性能比较，另外还给出了该系统中蚁群优化算法的参数设置和性能分析。 第六章总结了论文的工作和研究成果，并提出了以后尚需进一步研究的问 题。 9 第2 章半导体生产线调度问题 第2 章半导体生产线调度问题 2 1 半导体生产概述 2 1 1 半导体制造产业战略意义 半导体产业主要由四个部分组成：半导体设计业、半导体制造业、半导体 封装业与半导体测试业嗍。作为国民经济重要支柱的一部分，半导体产业的发 展对各相关产业和人们的生活、工作产生着举足轻重的影响。目前，半导体产 业已成为当代高新技术产业群的核心和维护国家主权、保障国家安全的战略性 产业。 半导体制造是整个半导体产业的基础。半导体制造业分为两大阵营，即集 成器件制造( i n t e g r a t ed e v i c em a n u f a c t u r i n g ，i d m ) 与代工( f o u n d r y ) 。全球 范围内，主要m m 厂商包括英特尔、意法、1 r i 、美光、英飞凌，三星等；主要 代工厂商包括台积电、台联电、特许、中芯国际等。据电子资讯时报2 0 0 4 年报道，目前，全球正在运营的1 2 英寸、8 英寸和6 英寸的集成电路生产线数 量如表2 1 所示。 表2 1 全球半导体生产线分布情况 从2 0 0 1 年开始，全球半导体业的平均资本支出每年萎缩了3 0 ，而我国半 导体业的资本支出年增长率却高达5 0 。2 0 0 4 年中国有中芯国际、上海先进、 华虹n e c 、和舰和宏力五个主要硅片代工厂，仅8 英寸硅片厂就达8 个，总月产 能达到1 5 5 万片，较2 0 0 3 年单月的8 4 万片大幅增长8 3 。 目前，我国半导体产业主要分布在长江三角洲、京津环渤海湾和珠江三角 洲地区，三个地区的产值占全国半导体行业产值的9 5 以上。 表2 2 国内半导体产业分布情况 地区当前状况 长三角地区长三角地区近几年的高速发展，成为最主要的开发和生产 l o 第2 章半导体生产线调度问题 基地，在我国半导体产业中占有重要地位。在半导体设计 方面，长三角地区的半导体设计业销售额占全国的4 5 左 右；硅片制造约占全国的7 0 左右；2 0 0 3 年近8 0 的封装 测试企业和近6 5 的封装测试量都集中在长三角地区。目 前，长三角地区已形成半导体设计、制造、封装、测试及 设备、材料等配套齐全、较为完整的半导体产业链。 包括北京、天津、山东、河北、辽宁行政区域，其中北京、 天津的信息产业在我国占有重要地位。中国第一座1 2 英寸 京津环渤海湾地硅片厂，中芯国际四厂正是设在北京经济技术开发区：现 区被中芯国际收购的原摩托罗拉8 英寸硅片厂位于天津。 2 0 0 7 年i n t e l 投资2 5 亿美元开始在辽宁大连建设1 2 英寸晶 圆加工厂。 是中国大陆地区电子产品的重要制造地，集中了大量的下 珠三角地区游整机制造商，对进口半导体产品的依赖程度极高，消费 量占我国大陆进口总量的8 0 以上。 在未来几年，受到经济高速增长的拉动、政策的扶持、2 0 0 8 北京奥运会以 及2 0 1 0 上海世博会等众多因素的影响，我国半导体需求将持续高速增长，预计 到2 0 0 8 年市场规模将达到人民币6 0 0 0 亿元以上。 在未来1 0 一1 5 年内，世界半导体产业的分布格局将会发生一些微妙的变化， 亚太地区将成为全球半导体制造业的中心，中国将迅速崛起，有望成为全球半 导体制造业重镇。在这样的背景下，机遇与挑战并存，研究如何把握住中国半 导体产业高速发展的脉搏，如何促进半导体制造厂加工能力和加工水平的提升 将具有重要的经济和学术价值。 2 1 2 半导体集成电路制造工艺简介 我们通常所说的芯片叫做集成电路，集成电路的制造过程非常复杂。从硅 片制造开始，经过一系列的机械、化学及物理工序的处理后，在半导体硅片上 形成了多个能完成一定电路性能的半导体电路层，即通常所说的芯片；接着将 芯片分割，按一定的封装模型封装；封装好的集成电路须经老化试验，监测合 格后方可成为商品流入市场。此过程分为五个阶段例，如图2 1 所示： 第2 章半导体生产线调度问题 夏i n c u s 一1 麓黜恶“- i 嚣箍。j 黑黑m m _ 薹。戮盏f _ 郦1 | i _ m勰勰v 雩黟 蠹篡：彩笋管椰 图21 半导体集成电路产品的制造过程 硅片在加工过程中，需要经过各种物理、化学工序在硅片上形成所需的电 路层，这些加工工序主要包括：氧化、沉积( c v d 及p v d ) 、离子注入，溅射、光 刻、刻蚀、清洗等。氧化工序的目的一般是在硅片表面形成具有绝缘或隔离作 用的s l 幔层：沉淀和离子注入的目的主要是在硅片中形成不同导电形式的p 型 或n 型s ：溅射工艺的目的是形成连接各元件或电路层之间的连线；光刻工序 的目的是让需刻蚀的区域暴露出来；刻蚀工序的目的是将光刻工艺暴露出的s i o ： 层腐蚀掉；而清洗的目的是为了使经前一道工序加工后的硅片上没有杂质。 根据所形成电路层的不同，加工完成一层电路需采用的工序也有不同。以 在硅衬底上的指定区域内形成p 型s i 为例，其过程如图22 所示：首先将硅片 清洗干挣( 图22 a ) ，在硅村底上采用氧化工艺形成一层s i 0 2 薄膜( 图2 2 h ) ， 然后采用光刻工艺将需形成p 型硅的区域( s i 0 2 薄膜) 曝露出来( 图22 c ) ： 利用刻蚀工艺将曝露的s i 0 2 薄膜腐蚀掉，露出硅衬底，并将硅片清洗，去除硅 片表面的杂质( 图22 d ) ：接着采用注入工艺将三价元素硼( b ) 注入到曝露出 的硅衬底中( 图22 e ) ；最后采用扩散工艺使注入的b 元素分布均匀形成所 需的p 型硅区域( 图22 f ) 2 9 1 。 第2 章半导体生产线调度问题 翻e 衬意一氧化j厶删一 捆蚀je i i ：入一j 门& 一 图2 2 形成p 型硅区的工艺流程 $ i 0 ，薄膜 p 区一 通过改变半导体的导电性质，即可制造出相应的半导体元件。集成电路的 制造过程与上述形成p 型硅的加工过程类似，只是要复杂得多，平均要经过 4 0 0 6 0 0 个加工工序，使用上百台设备才能完成。而且，随着集成电路性能的复 杂化及元件尺寸的小型化，硅片加工工艺变得更加复杂和精细，生产线的重入 性也更严重了。从上面的工艺介绍中，我们可以看到半导体集成电路的制造工 序是如此繁琐，那接下来介绍的，由此而产生的半导体制造系统的高度复杂性 应该也不难理解。 2 1 3 半导体制造系统的高度复杂性 半导体制造业是信息时代的基础产业，主要产品为集成电路。他的一般制 造流程为：硅圆片设备圆片制造中测组装及封装成品测试， 其中每一步都是一个非常复杂的处理过程，它具有不同于传统制造业的特点， 是属于继作业车间和流水车间之后发展起来的第三类生产系统可重入生产 系统【3 0 】。实际的半导体制造系统中，通常将硅片的组装、封装与测试称为后端 工艺，而将硅片的加工过程称为前端工艺。与后端工艺相比，前端工艺使用的 设备价格昂贵，加工工艺流程复杂，因此对前端工艺系统的研究也比较多。本 文中对半导体生产线的研究主要集中在前端工艺上。与一般的制造系统相比， 半导体生产线具有以下明显特征： 1 、重入 一般的制造系统中，可能存在工件重新访问前道工序已经访问过的同一台 1 3 第2 章半导体生产线调度问题 设备的情况，但这种“重入现象并不严重。在半导体制造系统中，由于工件 ( 硅片) 的加工工艺流程中存在很多相同的加工工序，且产品的工艺流程长度 不同，而所使用的设备一般非常昂贵，所以并不是让一台设备固定加工某一道 工序，而是让工件的多道相同的加工工序重复访问同一台设备。由于“重入” 现象的存在，使得每台设备需加工的工件数大大增加，再加上生产线上产品种 类、数量及其组合的不同，以及各产品工艺流程的复杂程度不同，因此，使得 半导体生产线的调度与控制问题比一般制造系统变得更加复杂，研究半导体生 产线就不得不考虑重入问题。半导体硅片加工工艺流程示意图如图2 3 所示例， 图中所使用设备及其功能如表2 3 所示。 1 4 第2 章半导体生产线调度问题 开始 图2 。3 半导体硅片加工工艺流程示意图 表2 3 设备功能明细 设备编 号 功能( 即完成的加工工序) 1 沉积( d e p o s m o n ) 2 沉积 3 沉积 4 沉积 5曝光( l l t h o g r a p h y ) 6曝光 1 5 第2 章半导体生产线调度问题 7曝光 8刻蚀( e 1 h i n g ) 9去胶( r e s i s ts t r i p ) 1 0离子注入( 1 0 ni 好l a n t ) 在该模型中，除设备4 外，所有设备都被处在加工流程中不同阶段的工件 多次访问，如完成沉积工艺的设备l ，重入次数多达1 0 次。在实际的半导体生 产线上，因所加工硅片的工艺流程更复杂，设备被重入的次数更多。总之，重 入是半导体生产线有别于j o b - s h o p 与f l o w s h o p 系统的重要特点。在第四章提出 的排程算法中，充分考虑了瓶颈设备重入次数最多的特性，提出了以瓶颈设备 排程方案为中心的一体化调度，充分体现了半导体生产线上重入这一特性的重 要性。 2 、工艺流程复杂、平均加工周期较长 硅片在生产线上的平均加工周期二般较长，多为一个月左右。但硅片的工 艺流程因产品不同而不同，短的工艺流程可能包含几十步工序，长的工艺流程 则可能有多达几百步工序，所以硅片在生产线上的平均加工周期有较大的分散 性，从十几天到几十天不等。一般情况下，生产线上流动的具有不同工艺流程 的产品多达几十种，再加上工艺流程中存在的重入现象，使得生产线上的在制 品对机器使用权的竞争非常激烈。在本文第四章的生产线模型中，工件的工艺 步数都在一百五十步以上，加工周期从十天到二十五天不等，足见其生产线上 工艺流程之复杂，平均加工周期之长，半导体生产线调度的复杂性由此可见一 斑。 3 、混合加工模式 在实际的半导体硅片加工生产线上，流动的硅片装在一个特制的盒子里， 成为一卡( 1 0 t ，一般装有2 4 或5 0 片) 。 一般地，将具有相同或类似功能的设备安放在一起，称为设备群。设备群 内的设备具有特定的互换性。不同设备群内的设备，可能具有不同的加工方式。 设备的加工方式主要有三种，即串行批量加工、单卡并行批量加工、多卡并行 批量加工。串行批量加工的设备是按片加工的，但一次可装入多片硅片，如光 刻机、离子注入机；单卡并行批量加工的设备每次加工一卡硅片，如刻蚀机； 而多卡并行批量加工的设备则可一次加工多卡硅片，如氧化炉等。多卡并行批 量加工设备使半导体生产线改变了经典调度问题中一台设备一次只能加工一个 1 6 第2 章半导体生产线调度问题 工件的约定，这也是半导体生产线调度问题区别于经典调度问题的重要原因之 一。本文所建的模型当中，串行批量加工、单卡并行批量加工模式对应的设备 为瓶颈设备和单片卡设备，共有6 9 台；与多卡并行批量加工模式相对应的设 备为批加工设备，共有7 2 台。其中有些设备是完全可互换的，而有些设备则只 对某些特定的工序具有互换性。机器的特定互换性及多种加工方式并存使得半 导体硅片加工生产线的调度问题变得更加复杂。 4 、不确定性 半导体生产线是典型的离散事件动态系统，存在各种各样的不确定性( 不 可预见性) 事件。这些不确定性事件主要由设备情况变化、客户需求变化、