（系统工程专业论文）混合智能算法在半导体生产线生产计划中的应用研究.pdf

摘要 摘要 生产线生产计划是半导体企业生产管理的核心问题之一，生产计划的合理 与否直接关系到企业生产目标的实现。随着市场竞争的同趋激烈，半导体企业 迫切需要切实可行的生产计划来有效地利用企业里的各种生产资源，缩短产品 的平均加工周期，提高准时交货率。 半导体制造过程具有规模大、产品种类多、流程复杂、加工周期长等特点， 通常需用到几百台设备，上十道甚至百余道加工工序，这些特点都给其生产计 划的制定带来了很大的困难。另一方面，随着市场需求的多样化和个性化，半 导体制造企业普遍转向多品种小批量的生产方式。然而，这种生产方式在适应 市场需求的同时，也给企业的生产管理带来了诸多困难，如产品品种多，工艺 流程各不相同，而产量也不同，这些也增加了生产计划制定的难度。过去，半 导体企业在制定生产线生产计划时大都借助一些启发式规则或经验规则，但随 着企业生产规模的扩大、市场竞争的激烈，这些方法已越来越不能满足半导体 企业管理者的需求。 本文针对半导体企业的生产线特点及生产方式，提出了一种全新的半导体 生产线生产计划优化模型的构建方法，及用于该优化模型求解的混合智能优化 算法。具体地，本文提出的智能优化方法首先以不突破产能资源限制为约束条 件，以保持在制品数稳定和减小订单拖期率为目标，构建完全不同于传统确定 性优化模型的模糊生产计划模型。随后，采用一种结合了模糊模拟、神经网络、 人工免疫的混合智能算法来求解计划模型，得到一个可行的、优化的生产线月 投料计划，再通过构造启发式规则将月投料计划进一步细化为日投料计划。最 后，本文以实际的半导体生产线为对象，构建了基于智能优化方法的半导体生 产计划系统。并通过模型仿真，验证了本方法的可行性、有效性。 关键词：半导体制造；生产计划；模糊机会约束规划；混合智能算法 a b s t r a c t a b s t r a c t m a k i n gp r o d u c t i o np l a no fp r o c e s sl i n e si so n e o ft h em o s ti m p o r t a n tt a s k so f p r o d u c t i o nm a n a g e m e n ti nas e m i c o n d u c t o re n t e r p r i s e w h e t h e rt h ep r o d u c t i o ng o a l c a nb ea c h i e v e do rn o ti sd i r e c t l yr e l a t e dt ot h ep r o d u c t i o np l a n w i t ht h ee x p a n s i o n o fm a r k e tc o m p e t i t i o n ，s e m i c o n d u c t o re n t e r p r i s e sn e e dap r a c t i c a lp r o d u c t i o np l a nt o u t i l i z ep r o d u c t i o nr e s o u r c e se f f e c t i v e l y , r e d u c et h ea v e r a g ec y c l et i m ea n d r a i s et h eo n t i m ed e l i v e r yr a t e s e m i c o n d u c t o rm a n u f a c t u r i n gh a st h ec h a r a c t e r i s t i c so fl a r g es c a l e ，m u l t i p l e p r o d u c tt y p e s ，c o m p l e xp r o c e d u r e ，l o n gc y c l et i m ea n ds oo n u s u a l l y , t h e r ea r e s e v e r a lh u n d r e do fe q u i p m e n t sa n ds e v e r a lh u n d r e do fp r o c e s ss t e p si naw a f e r f a b a l lo ft h e s eb r i n gd i f f i c u l t yt om a k ep r o d u c t i o np l a no fs e m i c o n d u c t o rp r o c e s sl i n e s o nt h eo t h e rh a n d w i t ht h ed i v e r s i f i c a t i o na n di n d i v i d u a l i z a t i o no fm a r k e td e m a n d ， j o bs h o pm a n u f a c t u r i n g h a sb e c o m eap o p u l a rp r o d u c t i o nm o d eo fm o r e s e m i c o n d u c t o re n t e r p r i s e s t h i sm o d ec a nm e e td i v e r s i f i e da n di n d i v i d u a l i z e d d e m a n do ft h em a r k e t h o w e v e r , i ta l s ob r i n g sal o to fd i f f i c u l t i e st op r o d u c t i o n m a n a g e m e n t f o re x a m p l e ，t h ep r o d u c t s a r ew i d ei nv a r i e t y , t h ep r o c e d u r e sa r e d i f f e r e n t ，a n dt h eo u t p u th a sn o t h i n gi nc o m m o ne i t h e r t h e s ea l la d dt od i f f i c u l t yo f m a k i n gp r o d u c t i o np l a no fs e m i c o n d u c t o rp r o c e s sl i n e p e o p l eu s e dt oa d o p t h e u r i s t i c r u l e so re x p e r i e n c er u l e st om a k ep r o d u c t i o np l a no fs e m i c o n d u c t o rp r o c e s sl i n e h o w e v e r , w i t ht h ee x p a n s i o no ft h em a n u f a c t u r i n gs c a l ea n dm a r k e tc o m p e t i t i o n , t h e s em e t h o d sc a n n o ts a t i s f yt h em a n a g e ro fs e m i c o n d u c t o re n t e r p r i s ea n y m o r e d e p e n d i n go nt h ec h a r a c t e r i s t i c sa n dp r o d u c t i o nm o d e o fs e m i c o n d u c t o rp r o c e s s l i n e ，t h ep a p e ra d v a n c e an e wm e t h o df o rm a k i n ga n do p t i m i z i n gt h ep r o d u c t i o np l a n o fas e m i c o n d u c t o rp r o d u c t i o nl i n e ，i n c l u d i n gb u i l d i n gao p t i m i z i n gm o d e lf o r p r o d u c t i o np l a n n i n ga n da ni n t e g r a t e di n t e u e c t i v ea l g o r i t h mw h i c hi su s e dt od e a l w i t ht h em o d e l b yt a k i n gt h el i m i to fp r o d u c t i o nc a p a c i t ya sc o n s t r a i n e dc o n d i t i o n ， s t a b i l i z i n gw l pa n dd e c r e a s i n gt h ed e l a yr a t e a st h eg o a l ，w eh a v eb u i l taf u z z y o p t i m i z i n gm o d e lt h a ti sd i f f e r e n tf r o mt h et r a d i t i o n a lo p t i m i z i n gm o d e l t h e n ，a f u z z ys i m u l a t i o n ，a r t i f i c i a ln e u t r a ln e t w o r k ，a n da r t i f i c i a li m m u n ea l g o r i t h m b a s e d i l i n t e 灯a t e di n t e l l e c t i v ea 1 9 0 r i t h mw a sp r e s e n t e d t od e a lw i t ht h em o d e l a sa r e s u l t , a f e a s i b l ea i l d0 p t i m i z e dp r o d u c t i 。np l a nw a so b t a i n e d a tl a s t ，w e b u i l tap r o d u c t i o n p l a n n i n gs y s t 吼w i t ht h ep r e s e n t e d m e t h o da c c o r d i n gt oa r e a ls 锄i c o n d u c t o rp r o s s i i n e t h es i m u l a t i o nr e s u l t sh a s s h o w nm ee 仟e c t i v e i l e s s o f m ep r c s e n t e d m e t h o 也 k e yw 。r d s ：s e m i c o n d u c t 。r m a n u f a c t u r i n g ；p r o d u c t i o np l a n n i n g ；如z z yc h a l l c e c o n s t r a i n e dp r o g r a m m i n g ；h y b r i di n t e l l i g e n ta l g o r i t h m i l l 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部f j 或者枧构送交论文的复印件和电子版；在不以赢利为冒的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：套母谚 7 o o ，年 月泌曰 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名：鸯帖佳 年月日年月西 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：夺寸f 佳 伽c ? 年弓月z o 日 第1 章绪论 第1 章绪论 制造业是国民经济的重要支柱，半导体制造业由于其技术含量高、资金投 入大、高收益与高风险并存，且产品更新速度快，成为了制造业的一个重要分 支，在国民经济中具有越来越重要的作用。半导体制造的主要产品是集成电路 器件，通常需用到上百台设备，几百道加工工序。由于投资金额大，市场竞争 激烈，生产企业需要通过制定切实可行的生产计划以提高设备利用率及生产率， 降低产品生产周期，满足用户需求，提高投资收益率。 目前，全球的半导体制造企业间的市场竞争只益激烈。为了提高竞争力， 在制造过程中如何最大限度地利用和合理分配现有的资源已经成为各制造企业 降低生产成本、提高生产率的一项重要课题。 1 1 课题研究背景和意义 1 1 1 课题背景 1 1 1 1 半导体制造业的特点与生产模式 随着市场竞争的同趋激烈，半导体企业需要建立适合本行业特点和生产模 式的生产计划系统以应对市场的挑战。 半导体生产线是区别于作业车间和流水车间的第三类生产系统一可重入生 产系纠2 1 ，其结构复杂、设备多且加工特性各异，具有高度可重入性和不确定性， 这些特点都为其生产计划的制定和优化带来了极大的困难。 从生产环境和计划方式的角度来看，制造业的产品生产有三种类型：面向库 存的生产( m a k et os t o c k ，简称m t s ) 、面向订单的生产( m a k et oo r d e r ，简称 m t o ) 、混合型( 同时存在m t s 和m t o ) 的生产。从工艺流程的角度看，产品 生产又可分为离散式的生产、流程式的生产及半流程式( 介于离散式生产与流 程式生产间) 的生产。 不同的企业有着不同的生产模式，半导体制造业的生产模式是属于面向订 单的离散式生产。因此，在解决半导体生产线的生产计划问题时，必须充分考 第1 章绪论 虑到其生产模式上的这两点特性。 1 1 1 2 半导体生产线生产计划的层次与内容 生产计划是企业生产决策和生产管理的主要职能【5 】。生产计划的合理与否直 接关系到半导体企业生产和经营目标的实现。半导体生产线生产计划就是要制 定合理的生产计划以有效地利用生产线上的各种可用资源，生产满足市场和用 户需要的产品。 考虑到生产经营活动的复杂性，制造业的生产计划一般可分为上层集约计 划、中层生产计划和下层作业计划【8 】三个层次。上层集约计划【卜4 】通常是企业经 营决策者根据未来2 3 年内营运发展战略，所确定的产品大类及各产品系列的产 量。中层生产计划的任务是根据销售预测和销售订单，制定一个投料计划，并 通过对生产线资源能力与负荷的比较来分析投料计划的可行性。下层作业计划 则需要根据中层生产计划下达的生产任务按照工艺路线来对各道工序的生产时 间、加工设备等进行安排。层次愈高，管理愈宏观，企业的总目标愈清晰，周 期愈长；层次愈低则相反【7 】。 在上述不同层次的生产计划中，中层生产计划是生产计划中的核心部分。 它需要确定一个投料计划以规定在一段时期内，企业应在什么时间，将哪些产 品原料投入生产，具体需要投入多少。本文所研究的半导体生产线生产计划仅 限于中层生产计划。 中层生产计划的核心任务是要确定一个合理的投料计划，而根据计划期跨 度和单位时段粒度的不同，投料计划又可分为长期投料计划和短期投料计划。 其中，长期投料计划的单位时段粒度通常为“月 或“季，它用来确保上层集 约计划的实现，并为短期投料计划的制定提供指导。而短期投料计划的单位时 段粒度通常为“同”或“周 ，它用来确保长期投料计划的实现，并为下层作业 计划的制定提供指导。 半导体生产线生产计划的层次和内容如表1 1 所示。 2 第1 章绪论 表1 1 半导体生产线生产计划的层次和内容 计划层 计划期时间粒度 计划内容 计划结构图 次跨度单位 上层集若干年年 ii i 、 i 约计划 7 、 2 0 啤1 月l p 7 p 籼1 2 月3 1 8 月3 1 日 中层生年季 | ，7 、 ，1 ，氰舯利h i h 洲$ 年7 川uz 0 0 9 年叭u 粤 产计划 季月 i 一7 、一i ，7、 i 、 月同 l 一7、j ”师，1 p ii ! ，t lit i 、-lf| | 1 2 h 砷刖日 ，、 下层作日分钟 t午i2n,l、一、 口船丹、1 , $ 1 1 1 口船丹 ，、 业计划 响l l l i l i l i i i i l i i l l 而1 1 1 1 3 半导体生产线生产计划的优化方法 实际生产中的计划问题都可以归结为组合优化问题，即要从问题的所有可 行解中求出最优解。半导体生产线生产计划是一类典型的组合优化问题。由于 半导体制造业具有生产线规模大、产品种类多、加工流程复杂，因而其生产计 划问题是一类具有n p h a r d 特性的复杂组合优化问题，相关的研究一直受到国内 外学者的广泛关注。 组合优化问题的一般数学模型【9 】为： ， m i n f ( 孟) s t g ( 孑) 0 ( 1 1 ) i d 其中，i 为决策向量，d 为决策向量的定义域，是一个由有限个元素组成的集合。 f = 何lg ( 孟) 0 ，i d ，为可行域，也是一个由有限个元素组成的集合，f 中的任 何一个元素称为该问题的一个可行解。厂( i ) 为目标函数。 当前，半导体生产线生产计划的优化方法包括：传统运筹学方法、启发式 方法和计算智能方法。其中，传统运筹学方法在理论上能求得问题的全局最优 解，但计算量偏大，在求解规模稍大的组合优化问题时需要很长的计算时间， 因此通常只能用来求解规模较小的优化问题。启发式方法是一种基于直观经验 或规则构造的算法。这种方法虽然能在可接受的时间内得到解，但在实际应用 第l 章绪论 时却容易陷入局部最优，故常常只能得到问题的次优解。另一方面，启发式方 法中的直观经验或规则往往高度依赖于待求解问题，这也大大地限制了其通用 性。计算智能方法是一种比启发式方法更为高效的算法，他通过模拟某种自然、 物理规律或生物的行为方式作为其运算机理，既能够在可接受的时间内给出问 题的可行解，又能以一定概率保证该可行解的全局最优性。 随着半导体制造业生产线规模的增大，其生产线生产计划问题的规模也相 应地扩大。在这种情况下，传统运筹学方法显然已无法适用。而启发式方法虽 然计算量小、效率高，但其优化规则通常是基于局部信息构造的，因此搜索效 果不够理想，通常只能得到问题的次优解。而计算智能算法作为继传统运筹学 方法、启发式方法之后发展起来的一种新的优化方法，在求解像半导体生产线 生产计划这样的复杂组合优化问题时，已体现出了明显的优越性。 1 1 2 研究意义 复杂制造系统生产计划是工业企业生产管理的核心问题之一，生产计划的 合理与否直接关系到企业生产目标的实现。因此，生产计划方面的研究和应用， 一直是控制科学与工程领域的一项重要课题。随着市场竞争的日趋激烈，制造 企业迫切需要切实可行的生产计划来有效地利用企业里的各种生产资源，在生 产出满足市场和用户需要的产品的同时，使企业效益最大化。 半导体制造系统作为一种复杂的制造系统，具有规模大、结构复杂、重入 性高等特点，这为其生产计划的制定和优化带来了极大的困难。半导体生产线 生产计划的研究是生产计划领域的研究热点和难点之一。目前，半导体制生产 线生产计划的应用研究还停留在运筹学与启发式规则的层面上。然而，实际生 产环境和市场环境中存在大量不确定性，传统的确定型生产计划模型缺乏柔性， 与实际情况有一定的背离。另一方面，企业生产计划本身就是一类复杂组合优 化问题。利用数学规划或启发式规则求最优解的方法在实际应用中解决半导体 生产线生产计划的优化问题是行不通的，需要探索新的方法。智能优化算法作 为继经典最优化方法、启发式方法之后的一种新的优化方法，在求解复杂组合 优化问题时已体现出了明显的优越性。然而，各智能算法虽都有一些各自的优 点，但也都有一些不可避免的不足之处。目前的研究大多局限于一种智能算法， 将不同计算智能算法结合起来解决计划问题的研究还很少。如何有目的地融合 4 第1 章绪论 不同的智能算法、充分利用各种不同方法的优点，更为有效地解决实际问题， 这是一个研究的难题同时也是一个富有前途的方向。 本文的研究以国家9 7 3 项目“复杂生产制造过程实时智能控制与优化理论和 方法研究”的子课题“大规模、带复杂约束、多目标、不确定型生产制造过程 实时智能优化调度理论与算法研究( 项目编号：2 0 0 2 c b 3 1 2 2 0 2 ) 、国家自然科 学基金“组件化可重构多重入复杂制造系统生产计划与调度体系结构及其关键 技术研究”( 项目编号：7 0 5 3 1 0 2 0 ) 及同济大学c i m s 研究中心与上海某半导体生 产企业合作项目“硅片制造生产线调度与仿真系统研发”为研究背景，以半导 体生产线为研究对象，在充分了解实际半导体生产线的生产工艺流程的基础上， 利用模糊建模方法建立半导体生产计划优化模型，并采用结合了模糊模拟、人 工神经网络和人工免疫算法的混合智能算法来研究半导体生产线生产计划的制 定和优化。 1 2 国内外研究现状评述 1 2 1 生产计划的研究现状 当前，生产计划的研究现状及主要存在问题如下：缺乏可靠的大系统建模方 法及优化算法，没有将整个企业看作一个统一的系统【l l 】；多为确定型模型【l 引， 使生产计划缺乏应有的适应性和柔性，生产系统和市场中的不确定因素对生产 计划的影响很大。 目前，对生产计划的优化，除了传统的混合整数线性规划及非线性规划外， 提出了许多针对离散制造业生产计划的新方法，如目标规划、多模型方法、基 于知识的层次法等【l3 1 。然而，企业生产计划的优化大多仍采用混合整数线性规 划及非线性规划，该方法对于解决不确定环境下的企业生产计划问题，缺乏应 有的柔性和有效性。 有些研究者已将模糊概念引入生产计划的优化【1 4 】【1 5 】【1 6 】【1 7 1 ，以增加生产计划 的柔性，文献1 1 8 】将单件制造业提前拖期生产调度问题扩展到带有资源能力约束 的生产计划问题。文献【1 9 j 将产品对工序的资源需求描述为时间的函数。文献 【2 0 】【2 1 1 1 2 2 1 建立了单件制造业e y r 生产计划模型文献【2 3 】【2 4 1 述了分布式多工厂单件 制造业e y r 的生产计划。但生产计划的模糊优化模型的处理方法大多是将其转 第1 章绪论 化为相应的确定型等价模型，然后再用确定性模型的相应求解算法进行求解。 但问题是，不是所有的模糊优化模型都能很容易地转化成相应的确定性等价模 型。因此，这种模糊优化模型的处理方法有一定的局限性【2 5 1 。 1 2 1 计算智能算法的研究现状 大规模企业的生产计划问题是一类具有n p h a r d 特性的复杂组合优化问题 【2 6 1 。对于该类问题，目前唯一可行的方法基于局部启发式搜索的是计算智能算 法。 计算智能算法以人类、生物的行为方式或物质的运动形态为背景，经过数学 抽象建立算法模型，通过计算机的数值计算来求解组合最优化问题f 27 1 。智能算 法包括：人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ) 、模拟退火( s i m u l a t e d a n n e a l i n g ) 、遗传算法( g e n e t i ca l g o r i t h m ) 、禁忌搜索( t a b us e a r c h ) 、人工免 疫算法( a r t i f i c i a li m m u n ea l g o r i t h m ) 等。 其中，模拟退火算法将组合优化问题与统计力学中的热平衡问题相类比，理 论上，模拟退火算法可以得到一个全局最优解，但是按照理论要求达到平稳分 布来应用模拟退火算法是不可能的，因为要达到平稳分布需要迭代无穷次或者 要求温度下降的迭代步数是指数次【2 6 1 。遗传算法虽然有较强的全局搜索能力， 且同其他启发式算法有较好的兼容性，但也有未成熟收敛、局部搜索能力弱、 收敛速度慢等缺点【9 t 2 8 1 。而在禁忌搜索中，如果禁忌表太长，则耗费在扫描禁忌 表上的时间会大大增加，算法的计算速度会受到严重影响。目前，还没有一个 比较明确的方法用来确定禁忌表的长度【2 6 1 。人工神经网络利用人工神经元相互 连接组成一个计算网络来并行高效地求解问题。它的主要特点是能够自学习， 通过给网络提供一定训练的样本，根据网络的实际输出与希望输出之间的偏差， 利用某种方法逐步修改各人工神经元之间的连接权，使之形成求解某些问题的 能力。目前，人工神经网络在半导体制造系统计划调度中一般是与其他方法结 合起来运用【2 。 相比较而言，人工免疫算法是一种新的计算智能方法。目前，一般的免疫算 法大多采用类似遗传算法的搜索策略，借用了g a 的选择、交叉和变异算子，但 在群体搜索策略、解的表示和记忆单元设置等方面与g a 有所不同。采用g a 算子 的免疫算法目前尚无统一框架，但已经在求解许多组合优化等问题中显示了强 6 第1 章绪论 大的优化搜索能力，如旅行商问题( t s p ) 【2 5 1 、二次分配问题( q a p ) 1 3 2 】、装箱问题【3 3 1 、 调度问题瞰】【3 5 1 等。在多数情况下，免疫算法取得了比其他计算智能算法更好的 求解结果，尤其在求解的效率方面，显示出免疫算法在智能优化领域具有广阔 应用前景。另一方面，人工免疫算法继承了遗传算法的兼容性和通用性。对比 发现，在知识存储和模型结构方面，人工免疫模型与人工神经网络模型遗传算 法十分相似【了7 1 。因此，这两种算法的融合是十分自然、富有前途的。 1 2 1 智能优化算法在生产计划中的应用现状 目前，不少学者已开始考虑用智能算法来求解生产计划问题【2 5 1 。f o o 3 8 j 等最 将h o p f i e l d 神经网络用于求解j s p 计划调度问题。其后r a b e l o 3 9 】等利用前向神经 网络对生产计划调度问题也进行了研究。s i k o r a 等人m 】采用了遗传算法来解决 批量确定和排序问题。l i u 和1 w a m u r a 提出了采用遗传算法( g a ) 求解那些无法转 化为清晰等价类的复杂模糊机会约束规划【4 。 然而，各智能算法虽都有一些优点，但同时也有一些不可避免的不足之处。 人工神经网络善长于直接从数据中进行学习，但其寻优能力不强；免疫算法很 适合于求解全局最优问题，也具有一定学习能力，但其学习的精度不如神经网 络。目前的研究大多都使用一种智能算法，将不同计算智能算法结合起来解决 计划问题的研究还很少。 1 3 本文主要研究内容及各章节安排 1 2 1 本文主要研究内容 将模糊集合论引入半导体生产线生产计划的建模，建立生产计划模型。 研究人工神经网络、人工免疫算法的计算模型、运行机理及相应操作 算子和关键参数。在充分掌握各算法的结构、机制和框架的基础上， 实现两种智能算法的融合。 使用基于模糊模拟、人工神经网络、人工免疫算法的混合智能算法求 解生产计划模型，得到月投料计划。 基于产品的交货期紧急度和加工周期长短构造启发式策略，将第1 级 7 第l 章绪论 的月投料计划进一步细化为同投料计划。 夺通过模型仿真，对比混合智能算法与其他求解方法的计算结果及求解 效率，并对计算结果进行评价。 1 2 2 本文各章节安排 本论文各章节安排如下： 第1 章：综述了半导体生产线生产计划的主要特点及其建模与优化方法的研究 现状、主要内容及应用。 第2 章：综述了组合优化问题中几种常见的智能优化算法，并着重介绍人工免 疫算法的基本原理及算法框架，然后分析研究了人工免疫算法与其他智能算法 的融合。 第3 章：首先介绍了模糊规划的基本概念，然后针对半导体生产线中可用产能 资源的不确定性，分析研究了如何利用模糊建模的思想建立半导体生产计划优 化模型。 第4 章：首先研究了如何利用模糊模拟技术来为优化模型的模糊产能约束条件 中的不确定函数生成输入输出数据。在此基础上，以人工免疫算法为基本框架， 设计了一个结合模糊模拟、神经网络、人工免疫算法的混合智能算法来求解模 糊优化模型，以得到一个优化的月投料计划。随后，分析研究了如何构造启发 式策略，将月投料计划进一步细化成日投料计划。 第5 章：以上海某半导体生产企业6 寸半导体生产线为背景，运用本文提出的 建模与优化方法建立一个生产计划系统。该系统能够根据客户订单和生产数据 得到一个可行的日投料计划。随后，借助模型仿真的手段，比较了本方法所生 成的日投料计划与其他一些优化方法所生成的日投料计划。通过对比不同投料 计划下的仿真结果和性能指标，验证了本方法的可行性和优越性。 第6 章：结论，总结了全文的工作和研究成果，并提出需进一步解决的问 题和研究方向。 第2 章计算智能算法综述 2 1 引言 第2 章计算智能算法综述 组合优化问题普遍存在于国民经济的众多领域如企业管理、国防、工业工 程、交通运输、通信网络等，是运筹学中的一个重要分支。这类问题的共同特 征是要通过数学方法的研究去寻找离散事件的最优、分组、次序或筛选等【9 l 。半 导体生产线生产计划问题就是一类典型的组合优化问题。其中，对于待决策订 单中各种产品的具体投料日期和投料数量都是计划过程中的参数变量；计划区 间的各个时段中产品加工对各设备组的产能占用不超过相应设备组的生产能力 资源是对参数变量的约束；保持生产线上在制品水平的均衡、减少拖期交货率 等都是生产计划的目标。 组合优化问题的一般形式【9 】为： m i n 厂( i ) s 2 g ( 孑) 0( 2 1 ) i r ” 其中，i = ( ，x 2 ，以) r 为取值离散的决策向量，r ”为i 的定义域，厂( i ) 为目 标函数，g ( i ) 为约束函数。f = 辑ig ( i ) o ，i r ”，为可行域，即f 中的元素都 是该问题的可行解。通常，r ”和f 都是有限集合。理论上，只要f 不是空集， 就可以用穷举f 中元素的方法获得问题的最优解1 4 2 1 。 在用优化理论和方法解决自然科学和实际生产中的具体组合优化问题时， 一般分为以下两个步骤： ( 1 ) 建立数学模型 通过对待求解问题的分析研究，抽象出问题的决策变量和各种参量，并确 定反映决策目标的目标函数以及反映参量间约束关系的约束方程，以形成优化 问题的数学模型。 ( 2 ) 模型的求解 针对已建立的数学模型，选择或提出适当的计算方法，亦即优化算法。然 后，按照优化算法编制相应的计算机程序以利用计算机来计算求解该数学模型。 当前，组合优化问题的求解方法可分为t 传统运筹学方法、启发式方法和 9 第2 章计算智能算法综述 计算智能方法。 ( 1 ) 传统运筹学方法 传统运筹学方法是一种确定型的最优化算法，如d a n t z i g 在1 9 4 7 年提出的 求解线性规划的单纯形法、l a n d 和d o i n g 于1 9 6 0 年开发出的针对整数规划的分 枝定界法、b a l a s 于1 9 6 5 年提出的求解0 1 规划的隐枚举法等。传统运筹学方法 的优点是理论上总能求得问题的全局最优解：其不足之处是计算量偏大，尤其 是当问题的规模较大时，往往需要很长的运行时间。因此，运筹学方法通常只 能用来求解规模较小的优化问题。 ( 2 ) 启发式方法 启发式方法是一种基于直观或经验构造的算法，在可接受的花费( 指计算时 间、占用空间) 下给出待解决组合最优化问题的一个可行解，该可行解与最优解 的偏离长度不一定事先可以预计 9 1 。常用的启发式方法包括：启发式规则和专家 系统方法和拉格朗同松弛法。这种方法的优点是能够在可接受的计算开销去寻 找最好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下， 无法阐述所得解同最优解的近似程度【i0 1 。另一方面，启发式方法中的直观经验 或规则往往高度依赖于待求解问题，这也大大地限制了其通用性。 ( 3 ) 计算智能算法 计算智能算法又叫“现代启发式方法 。与启发式方法基于直观或经验不同， 计算智能算法通常是对某种物理规律、生物进化过程或自然机理的模拟。作为 一种更为高效的启发式方法，智能算法在可接受的计算时间内给出问题的一个 可行解的同时，还能保证该可行解以一定的概率收敛到全局最优解。一些经过 改进的智能算法，如保优遗传算法、人工免疫算法等能以概率1 收敛到全局最 优解。 半导体制造业生产线规模大、产品种类多、加工流程复杂，因而其生产计 划问题是一类具有n p h a r d 特性的复杂组合优化问题，相关的研究一直受到国内 外学者的广泛关注。当前，半导体制造业生产线规模日益扩大，其生产线生产 计划问题的规模也在相应增大。在这种情况下，传统运筹学方法显然已无法适 用。而启发式方法虽然具有计算量小、效率高的优点，但其优化规则的构造通 常都是基于一些直观经验或局部信息，因此在实际应用中搜索效果往往不够理 想，通常只能得到问题的次优解。而计算智能算法作为继传统运筹学方法、启 发式方法之后发展起来的一种更为高效的优化方法，在以可接受的时间开销得 i o 第2 章计算智能算法综述 到问题可行解的同时，还能保证该可行解以一定的概率收敛到全局最优解。因 而，在求解像半导体生产线生产计划这样的复杂组合优化问题时，已体现出了 明显的优越性。 2 2 计算智能算法 计算智能算法是一类以人类、生物的行为方式或物质的运动形态为背景， 经过数学抽象建立算法模型，并通过计算机的计算来求解组合优化问题的优化 算法【2 7 】。作为一种比较新的优化算法，计算智能算法的发展非常迅速，在许多 经典优化问题如旅行商问题、背包问题、装箱问题、工件排序问题等中都已得 到了应用，并体现出了强大的优化搜索能力。近年来，不同计算智能算法之间 的融合已成为学术界的研究热点。 本节中将简要介绍几种常见的计算智能算法，包括：模拟退火算法、禁忌 搜索算法、遗传算法、人工神经网络与人工免疫算法。 2 2 1 模拟退火算法 模拟退火算法( s a ，s i m u l a t e da n n e a l i n g ) 是基于m e n t ec a r l o 迭代求解策略的 一种随机寻优算法，其算法思想最早由m e t r o p o l i s 于1 9 5 3 年提出，k i r k p a t r i c k 于1 9 8 3 年成功地将该算法应用在组合优化问题上。模拟退火算法的出发点是基 于物理中固体物质的退火过程与一般组合优化问题之间的相似性2 7 】( 如表2 1 所 示) 。 表2 1 退火过程与组合优化问题的相似性 组合优化问题物理退火 可行解状态 最优解能量最低状态 目标函数能量 求解过程退火过程 模拟退火算法的思想f 4 3 1 源于物理中的固体退火原理：将固体加热至一定温 度后让其逐渐冷却。在加热时，固体内部的粒子随着温度的升高变为无序状， 第2 章计算智能算法综述 内能增大；而在慢慢冷却的过程中，这些粒子则渐渐趋于有序，在每个温度都 达到平衡态，最后在常温时达到基态，内能减为最小。根据m e t r o p o l i s 准则，粒 子在温度t 时趋于平衡的概率为ek t ，其中e 为温度t 时的内能，衄为其改变 量，k 为b o l t z m a n n 常量。当我们用固体退火过程来模拟组合优化问题的求解过 程时，将内能e 模拟为目标函数值f ，温度t 模拟为控制参数t ，就能得到求解 组合优化问题的模拟退火算法，其搜索过程是_ 种基于蒙特卡罗迭代求解法的 启发式随机搜索过程：由初始解i 和控制参数初值t 开始，对当前解重复“产生 新解一计算目标函数差一接受或舍弃”的迭代，并逐步衰减t 值，算法终止时所 对应的当前解就是问题的近似最优解。 模拟退火算法具有渐近收敛性，并已在理论上被证明是一种以概率l 收敛于 全局最优解的全局优化算法。因而已被广泛应用到n p 难问题的求解中。然而， 模拟退火算法在实际应用中也存在着以下几点问题m j ： ( 1 ) 退火速度问题 退火速度是影响模拟退火算法全局搜索性能的重要因素之一。通常情况下， 同一温度下的“充分”搜索( 退火) 是相当必要的。然而，同一温度下搜索地越充 分，所需要的计算时间也越长。实际应用中，要针对具体问题的性质和特征设 置合理的退火平衡条件。 ( 2 ) 初始温度t 。的设置问题 模拟退火算法的全局搜索性能与初始温度t 。也是密切相关的。初始温度高， 则算法的全局搜索性能较好，但需所需的搜索时间较长；反之，则可缩短搜索 时间，但搜索到全局最优解的可能性可能会减小。在实际应用过程中，初始温 度一般需要依据实验结果进行若干次调整。 ( 3 ) 温度管理问题 温度管理问题也是模拟退火算法中的一个难点。实际应用中，必须综合考 虑问题的复杂性和算法的可行性，采用合理的降温方式。 2 2 2 禁忌搜索算法 禁忌搜索( t s ，t a b us e a r c h ) 算法最早由g l o v e r 于1 9 8 6 年提出，它是局部邻 域搜索算法的推广。它的一个重要思划2 7 1 是给已得到的局部最优解或求解的过 程作标记，并在进一步的迭代中避开这些局部最优解或过程，以避免陷入局部 1 2 第2 章计算智能算法综述 最优。该算法在实现时，需要借助禁忌表这样一种技术。具体地，将已到达过 的局部最优点或达到局部最优的一些过程记录在禁忌表中。从而在下一次搜索 中，避开禁忌表中的这些点或过程，以此来跳出局部最优点。 禁忌搜索算法既能够从一点出发，在这点的邻域内作局部搜索，以找到局 部最优解；又能通过对禁忌表中的点的禁忌，以达到一些没有搜索的点，从而 跳出局部最优解，实现对更大区域的搜索。 然而，禁忌搜索算法在具体应用中的最大问题是：禁忌长度难以确定。禁忌 长度为禁忌对象的受禁时间，如果禁忌长度过短，则会造成循环的出现；如果 禁忌长度过长，又会造成计算时间较大。实际上，禁忌长度的选取与实际问题、 实验和设计者的经验有密切联系。目前，还没有一个比较明确的方法用来确定 禁忌表的长度【2 6 1 。 2 2 3 遗传算法 遗传算法( g a ，g e n e t i ca l g o r i t h m ) 4 5 】是由美国学者h o l l a n d 于1 9 7 5 年提 出的。它基于达尔文适者生存、优胜劣汰的进化原则，对包含可能解的群体反 复使用遗传基本操作，不断生成新的群体，使种群不断进化。同时以全局并行 搜索技术来搜索优化空间中的最优个体，以求得满足要求的最优解。与其它搜 索算法如随机查找、梯度下降、模拟退火等方法相比，g a 的主要特点是简单、 鲁棒性强。由于g a 实行全局并行搜索，并且在搜索过程中不断向可能包含最优 解的方向进化，因此易于寻找到最优解或准最优解。 然而，尽管遗传算法在各方面的研究中取得了很大进展，也得到了比较多 的应用，然而在一些应用研究中却发现g a 存在着明显的不足，如早熟与欺骗问 题、搜索效率低、不能很好地保持个体的多样性等m 】，甚至在组合优化的应用 中可能出现致死遗传子【4 7 1 ，从而影响了g a 在一些优化设计中的正确性和有效 性。 2 2 4 人工神经网络 人工神经网络的第一个模型是由m c c u l l o c h 2 9 1 等人在1 9 4 3 年建立的，它是 由大量称为神经元的简单基本元件相互联接而成的自适应非线性动态系统。这 些神经元通过前馈或反馈的方式相互关联和作用，每个神经元的结构和功能比 第2 章计算智能算法综述 较简单，但大量神经元组合产生的系统行为却非常复杂。人工神经网络以其分 布存储、大规模计算、自组织、自适应学习以及非线性处理的能力，已经被广 泛应用到函数逼近、系统辨识、模式识别、专家系统、优化计算、智能控制等 多个领域。 目前，人们已提出了许多种的神经网络模型，如多层前馈神经元网络、放 射函数网络、适应理论网络、h o p f i e l d 网络、双向辅助网络、计数传播网络等 等。这些模型都有其各自的优缺点，各有各的主要应用领域。其中，由m i n s k y 和 p a p e r t 提出的多层前馈神经元网络是目前最为常用的网络结构。它被广泛地应 用到模式分类和函数逼近当中。 h o p f i e l d 首次成功地将人工神经网络用于组合优化问题【3 们，并提出了两种神 经网络模型。其主要思想是用人工神经元相互连接组成一个计算网络，并行高 效地求解问题。它的主要特点是能够自学习，通过给网络提供一定训练的样本， 根据网络的实际输出与希望输出之间的偏差，利用某种方法逐步修改各人工神 经元之间的连接权，使之形成求解某些问题的能力。目前，人工神经网络在半 导体制造系统计划调度中一般是与其他方法结合起来运用【2 7 】。 2 3 人工免疫算法 生命科学一直是智能计算的灵感来源。自然界中，生物体凭借其自身的免疫 系统，能够在复杂多变、充满伤害的生存环境中，有效地抵御各种病毒或有害 物质的侵害。正是在生物免疫系统的多样性、适应性、记忆机制等特点的启发 下，人们提出了人工免疫算法这样一种新型的智能算法。人工免疫算法一经提 出，便引起许多不同领域研究人员的广泛兴趣，在优化计算方面表现出卓越的 性能和效率，具有寻优成功率高、个体多样性好等特点，成为计算智能领域中 一个新的研究方向。 目前，人工免疫算法的相应研究还处在一个比较低的水