（电工理论与新技术专业论文）半导体生产线多批处理机流水车间调度方法研究.pdf

武汉理工大学硕士学位论文 摘要 随着全球经济的快速发展，用户对产品要求变化速度越来越快，多品种， 小批量生产越来越普遍，这种生产方式使得生产环境越来越复杂。如何降低生 产成本、提高生产效率和简化流程对于企业来说至关重要，要使生产效率能够 有较大的提升，根据经验的管理模式很难有所提高，只能在其他方面寻找突破， 即有效的生产调度。随着在生产过程中的逐步应用，生产调度技术对于企业生 存与发展越来越重要。 在半导体制造系统中，设备一般都很昂贵，一台设备不止加工固定工艺流 程中的某一道工序，而是工艺流程中大量存在相同工序重复访问同一台机器。 如何合理分配和利用系统中有限的设备和资源，这正是其调度的目的。本文基 于集成的方法把批处理机调度问题的两个子问题：工件分批和批调度，作为整 体进行研究，提出了几种有效的调度算法，并通过仿真实验验证了算法的各项 性能指标。 首先利用禁忌搜索来研究了多批处理机流水车间调度问题以最小化最大完 成时间，利用启发式方法给定初始解，根据加工容量进行分批，并通过n e h 对 批次进行批调度。然后，通过互换方式获得新的邻域解，并决定是否接受新解。 并和其他算法比较。计算结果验证了禁忌搜索在批处理调度方面具有良好的搜 索性能。 其次针对目标函数为延迟时间的多批处理机流水车间调度问题进行研究。 提出了一种有效的邻域搜索算法，通过工件互换和批互换直接得到了两个子问 题的解。首先通过邻域搜索产生初始解，然后运用两种邻域操作来获得调度问 题的解。通过仿真实验测试，计算结果显示针对多批处理机流水车间调度问题 的求解该算法性能优越。 最后研究了多目标批处理机流水车间调度问题，集合了上述研究的两个目 标函数：延迟时间和最大完成时间。利用获得的非劣解进行档案维护，提出了 邻域搜索算法并运用加权方法平衡多个目标来获得最优解。 关键词：流水车间；邻域搜索；禁忌搜索；批处理机调度；多目标 武汉理工大学硕士学位论文 a b s t r a c t d u et of a s tg r o w i n go fw o r l de c o n o m y , t h er e q u i r e m e n tf r o mu s e r st ot h e p r o d u c t i t s e l fh a sb e c o m em o r er e s t r i c t e d d i f f e r e n tv a r i a t i o n s s m a l l a m o u n t p r o d u c t i o nd o m i n a t e dt o d a y sm a r k e t h o w e v e r , t h em e t h o d so fp r o d u c t i o ni ns u c h k i n da l ea l w a y sc o m p l i c a t e da n dm a s s i v e s o ，f o rt h o s eg i a n te n t e r p r i s e s ，h o wt o r e d u c es u c hc o m p l e x i t y , o r , i no t h e rw o r d ，h o wt oe n h a n c et h ee f f i c i e n c y - t o - c o s tr a t i o h a sb e c o m et h ev e r yf i r s tp r i o r i t y i no r d e rt ob o o s tu pt h ee f f i c i e n c y , f o l l o w i n go l d w a y h a sb e e na p p r o v e dt ob eu n s u c c e s s f u lb u to n l ym a k eas h o r td e t o u r , n a m e l y , p r o d u c t i o ns c h e d u l i n g w i t hp r o d u c t i o ns c h e d u l i n gb e i n ga p p l i e di nt h ep r o c e s s ，s u c h t e c h n i q u ei st h ek e yt oac o m p a n y ss u r v i v a l t h eh a r d w a r es y s t e mf o rm a n u f a c t u r i n gs e m i c o n d u c t o ri se x p e n s i v e ，n o t b e c a u s ei tt a k e sc h a r g ei ns i n g l es t e po ft h ep r o c e s s ，b u ti ti sb e e nv i s i t e dm a n yt i m e s b yal o to fs i m i l a rs t e p sr e d u n d a n t l yi nt h ew h o l ep r o c e s s s o ，t h i sp r o b l e mc o m e st o t h ep u r p o s eo f p r o d u c t i o ns c h e d u l i n g t h a ti s ，h o wt oe f f i c i e n t l yd i s p a t c ha n du t i l i z e t h el i m i t e ds o u r c e si nt h eh a r d w a r es y s t e m i nt h i sa r t i c l e ，t h ea u t h o rc o m b i n e db a t c h f o r m a t i o na n db a t c hs c h e d u l i n gw h i c ha r et w om a j o ra s p e c t so ft h eh a r d w a r es y s t e m b a t c hp r o c e s s i n gm a c h i n et o g e t h e ra sas i n g l er e s e a r c hs u b j e c t b a s e do nr e s e a r c h ， t h ea u t h o rp r o p o s e ds e v e r a le f f e c t i v es c h e d u l i n gm e t h o d o l o g i e sa n da l s op r o v e dt h e i r p e r f o r m a n c e st h r o u g hs y s t e ms i m u l a t i o n f i r s t l y , t os o l v em u l t i m a c h i n eb a t c hp r o c e s s i n gm a c h i n e ( b p m ) f l o ws h o p s c h e d u l i n gu s i n gt a b us e a r c hf o rm i n i m i z i n gm a k e s p a n h e u r i s t i cm e t h o d sa r eu s e dt o s e tag i v e ni n i t i a ls o l u t i o na n db a t c hf o r m a t i o ni sb a s e do nt h ec a p a c i t y , a n dn e hi s u s e dt op e r f o r mb a t c hs c h e d u l i n g t h e n ，t h en e wn e i g h b o r h o o ds o l u t i o ni so b t a i n e d t h r o u g hs w a p ，a n dd e c i d e st h a tt h en e ws o l u t i o ni sa c c e p t e d t a b us e a r c hi sc o m p a r e d w i t l l g e n e t i ca l g o r i t h m s t h ec o m p u t a t i o n a l r e s u l t sd e m o n s t r a t e dt h e g o o d p e r f o r m a n c eo f t a b us e a r c hi nm a n y - b p mf l o ws h o ps c h e d u l i n g s e c o n d l y , t h i st h e s i sp r e s e n t e dt h es c h e d u l i n gp r o b l e mo nf l o ws h o pw i t hb a t c h p r o c e s s i n gm a c h i n e st om i n i m i z em a x i m u mt a r d i n e s s a ne f f i c i e n tn e i g h b o r h o o d s e a r c hi sp r o p o s e df o rt h ep r o b l e m ，i nw h i c h j o bp e r m u t a t i o na n db a t c hp e r m u t a t i o n a r eo p t i m i z a t i o no b j e c ta n dt h es o l u t i o no ft w os u b - p r o b l e m sc a l lb ed i r e c t l yo b t a i n e d b yu s i n gt h ep e r m u t a t i o n s t oo b t a i n t h ep r o m i s i n gr e s u l t s ，a ni n i t i a ls o l u t i o no f n e i g h b o r h o o ds e a r c hi sf i r s tp r o d u c e da n dt h e nt w os w a po p e r a t i o n sa r ea p p l i e dt o i m p r o v et h es o l u t i o n t h ep r o p o s e dn e i g h b o r h o o ds e a r c hi s f i n a l l yt e s t e da n dt h e c o m p u t a t i o n a l r e s u l t ss h o wi t s g o o dp e r f o r m a n c e o nm a n y - b p mf l o ws h o p s c h e d u l i n g f i n a l l y , t h i s t h e s i sc o n s i d e r e dt h es c h e d u l i n gp r o b l e mo nf l o ws h o pw i t h m u l t i o b j e c t i v eb a t c hp r o c e s s i n gm a c h i n e st o m i n i m i z em a x i m u mt a r d i n e s sa n d m i n i m i z i n gm a k e s p a n u s i n ga r c h i v em a i n t e n a n c et oo b t a i nn o n i n f e r i o rs o l u t i o n ， a n du s i n gt h ew e i g h t e dm e t h o dt oo b t a i nb a l a n c em u l t i p l et a r g e t st h eo p t i m a l s o l l l t i o n k e y w o r d s ：f l o ws h o p ；n e i g h b o r h o o ds e a r c h ；t a b us e a r c h ；b a t c h p r o c e s s i n g m a c h i n es c h e d u l i n g ；m u l t i - o b j e c t i v e i 武汉理工大学硕士学位论文 目录 第1 章绪论1 1 1 半导体生产线简介1 1 2 批处理机调度研究的意义。2 1 3 批处理机调度研究的难点和不足3 1 4 批处理机调度研究的发展现状。4 1 4 1 启发式方法在批处理机调度上的应用4 1 4 2 数学规划方法在批处理机调度上的运用。5 1 4 3 智能算法在批处理机调度上的运用6 1 5 本文研究的主要内容7 1 6 本文的创新点8 第2 章批处理机调度理论与方法9 2 1 批处理机调度问题9 2 2 批处理机调度问题的描述9 2 2 1 批处理机调度问题的分类1 1 2 2 2 批处理机调度的特点1 3 2 3 本课题涉及的算法13 2 3 1 遗传算法1 3 2 3 2 模拟退火算法1 6 2 3 3n e h 算法l8 2 3 4 邻域搜索算法l8 2 3 5 禁忌搜索算法1 9 2 4 月、结2 1 第3 章基于禁忌搜索的多批处理机流水车间调度2 2 3 1 半导体生产线批处理机调度介绍2 2 3 2 问题描述2 3 3 3 基于禁忌搜索的多批处理机流水车间调度算法2 4 3 3 1 算法流程2 4 i v 武汉理工大学硕士学位论文 3 3 2 编码与解码2 5 3 3 3 禁忌表2 8 3 3 4 禁忌对象2 8 3 3 5 邻域结构。2 8 3 4 计算结果分析2 9 3 5 本章小结3 0 第4 章基于邻域搜索的多批处理机流水车间调度3 2 4 1 引言3 2 4 2 问题描述：3 2 4 3 邻域搜索3 3 4 3 1 编码与解码3 3 4 3 2 邻域搜索方法3 7 4 4 计算结果分析3 8 4 5 本章小结4 1 第5 章基于邻域搜索的多目标批处理机流水车间调度4 2 5 1 多目标优化基本概念4 2 5 2 多目标流水车间调度概述4 3 5 3 邻域搜索4 4 5 4 性能分析4 5 5 5 本章小结4 6 第6 章全文总结与展望4 7 6 1 全文总结4 7 6 2 展望4 8 致谢4 9 参考文献5 0 攻读硕士学位期间发表的学术论文5 5 v 武汉理工大学硕士学位论文 第1 章绪论 1 1 半导体生产线简介 随着经济的快速发展，半导体产业取得长足的进步，半导体制造业一直是国 家经济发展中的支柱性产业，作为人类经济生活中的重要部分，具有重要的战略 意义。半导体产业主要有四个部分组成：半导体设计业、半导体制造业、半导 体封装业和半导体测试业。作为支柱性产业，半导体产业的发展对于其他相关 产业的发展也具有强劲的带动作用。 在半导体制造工艺中主要设计生产芯片，即集成电路，其主要就是对硅片 进行加工。其中包括硅片的装备、硅片的加工、芯片的测试以及分类、装配与 封装和产品测试等环节。而硅片的加工过程最为复杂，通常称为半导体硅片加 工生产线，简称半导体生产线。本文只要以半导体生产线为主要研究对象。在 对硅片进行加工的过程中需要利用各种昂贵的机器对硅片进行各种物理、化学 方面的工序处理。主要包括氧化、淀积、离子注入、溅射、光刻、刻蚀和清洗 等。通过这些工序的处理使得硅片能够达到实际使用要求。例如光刻这一工序 被认为是i c 制造中最关键的加工步骤，使用的设备也是最昂贵，光刻实质上也 是一系列的工序组合，包括涂胶、软烘、曝光和烘焙等，这些工序在加工过程 中使用的都是批量加工设备，如何使得在加工的过程中更加有效的提高机器的 利用率，正是本文所研究的重点。其次，半导体生产线具有高度的复杂性，主 要包括：工艺流程复杂、多重入加工流程、不确定性、多种类型同时加工、混 合加工模式和顺序相关的设备整定时间等，在生产中硅片的加工周期一般都很 长，包括的工序可能包含几十道甚至上百道；其次不同型号，不同版本类型的 工件同时投入生产线进行加工，不同类型的产品使用的加工工艺有非常大的区 别，因此，这造成了半导体生产线产品工艺流程的复杂性及调度的难度。 在现阶段，半导体制造业是加工最为复杂的行业，国内很多企业都引进先 进技术，加强制造过程的自动化，加强计划、调度和控制之间的协同管理，但 是在生产过程中由于企业的决策者和实施者之间存在严重的脱节，使得现有企 业的生产管理多是凭着经验来进行的，而根据经验来对生产过程进行控制的技 术已经发展的非常完善了，对于在这方面的改进很难有所突破，要使生产效率 能够有较大幅度的提升，基本不再有太大的可能，因此需要在其他的方面寻找 武汉理工大学硕士学位论文 突破，生产调度理论与方法研究如何充分利用企业有限的能力和物力等资源， 以获得更低的生产成本，更高的机器利用率和顾客满意度等，从而满意企业提 高生产效率的目的。 生产调度问题就是指在满足顾客所要求的一些性能指标情况下，在规定的 时间之内，现有的资源情况下，通过对资源进行分配、加工，并对生产任务进 行排序的过程。在现实的实际生产过程中，生产调度能够比较好的在决策者和 实施者之间进行衔接。在满足工件加工流程和其他约束条件的基础之上，合理 分配和利用生产线上有限的设备和资源，在生产活动中尽可能优化系统的各项 性能指标【l 】，从而在很大程度上弥补决策者和实施者之间沟通不足的问题，使得 在生产过程中获得最大的效益。因此，生产调度技术的提高对于工业生产的发 展具有不可忽视的作用。 1 2 批处理机调度研究的意义 在半导体制造系统中存在着大量的批处理机调度问题，例如在工件完成加 工后需要对工件进行封装，装配与封装其加工形式多为批量方式，如何有效安 排工件在机器上面加工，使得调度过程更加合理，批量调度自然成为我们研究 的焦点。 批量调度突破了经典调度问题中j n ：i ：数量等于l 的这一约束，批量调度存 在两种不同类型的问题。第一类问题通过工件组批来节省时间，使得在同一个 批内先后加工的两个工件无需准备时间，批加工时间为批内所有加工时间之和； 另一类问题为批处理机调度。在加工处理过程中，由于实际的需要批量调度引 起了人们广泛的研究兴趣，两种类型的批量调度都有一定程度的研究，并且取 得了一些有价值的研究成果，尤其是批处理机调度，其研究随着半导体和钢铁 等行业的发展，受到了学术界和工程界越来越多的关注。 批处理机产生于大规模的现代化生产流水作业线，广泛应用于半导体的扩 散和氧化操作、半导体测试的老化操作、金属加工的热处理、印刷电路板封装 以及视屏、化工、制药和钢铁等。批处理机在加工之前先对工件进行分批，每 批的工件根据批次的不同数目也不同，工件以批为单位在机器上面加工，每个 批的加工时间为每个批中加工时间最长的那个工件的加工时间或者为常数，虽 然工件以批为单位进行加工，但是每个批的工件数目不能高于机器的加工容量， 当机器开始加工某个批时，其加工不能被中断，也不能加入新的工件到批中， 或者从批中移出工件【2 j 。 2 武汉理工大学硕士学位论文 批处理机调度主要包含两个子问题：工件分批和批量排序。由于两个子问 题本身就是n p 难问题，且两个子问题之间又存在着复杂的相互作用，使得批处 理机调度更加复杂，求解难度更大。如何获取高质量的调度解，一直都是学术 研究的难点和热点；其次批处理机调度对于企业的生产有着至关重要的作用， 企业决策者十分关心如何高效率的利用这些机器设备，来为企业创造更大的效 率，而只有采用先进的调度手段如利用先进的调度方式，来获得满意的调度方 案，才能为企业带来显著的经济效益【2 】。因此，研究批处理机调度具有重要的理 论价值和现实意义。 1 3 批处理机调度研究的难点和不足 在批处理机调度问题中，由于该问题包含了若干子问题，而每个子问题之 间又存在着复杂的相互作用，使得该问题变得更加复杂，越来越多的学者对此 产生了浓厚的兴趣。 第一，批处理机调度相对于传统的调度模型来说，形式上可能比较相似， 但是在内容上已经有很大的变化。在传统的调度问题中工件数一般为1 ；而批处 理机调度问题中工件有多种工件类型，同类型的工件才能组批，这样导致不同 的工件分批将产生不同数量的批；其次，批在每台机器上的加工时问通常是不 确定的，由于批加工时间由加工时间最长的工件决定，随着工件分批的改变， 导致某些批内工件的组成可能会发生变化，导致批的加工时间也可能发生了变 化。因此，如何分配批内的工件使得批加工时间最小和性能指标更好，一直是 我们关注的重点。 第二，由于工件分批和批调度相互作用相互影响，当工件进行分批时，由 于工件的加工时间不同和加工数量的不同将直接影响批加工时间和批数大小， 从而影响批调度的搜索空间、求解难度和计算结果；反之，合理有效的结合工 件分批和批调度问题，形成一个完整调度，才能确定分批是否合理。 第三，现阶段批处理机调度问题研究还不够充分，很多学者也仅仅是研究 调度问题中的某一个方面，这样导致用于进行测试的最佳结果很难获取，使得 算法性能的评价困难。 第四，目前很多学者所研究的调度模型都比较单一，如果在研究过程中考 虑一些实际加工约束等，那么子问题将更加错综复杂，若再考虑机器发生故障， 或是紧急订单等其他多种情况，考虑诸多因素对于调度问题在实际应用中更加 有效。 3 武汉理工大学硕士学位论文 第五，现阶段的研究主要考虑单目标问题，对于多目标问题的研究较少， 而实际上决策者通常要考虑多种相互冲突的目标，只有通过研究多目标问题， 才能使研究结果有更好的应用。 1 4 批处理机调度研究的发展现状 在过去的2 0 多年里，智能调度算法在经典调度问题中的应用研究已经很充 分，通过对各种约束和目标条件下的调度问题研究，提出了许多高效的调度方 法，但对于批处理机调度问题的应用还不够充分，因此本文将在这方面进行研 究。 目前，批处理机调度研究已经取得了一些进展，具体包括单批处理机调度、 并行批处理机调度和流水车间批处理机调度问题的求解。其中，模拟退火 ( s a e 3 1 ) 、遗传算法( g a ) 【4 】和在线调度算法【5 】已应用于工件分批，j o l a i 6 】主要考虑 了在单批处理机中如何最小化工件延迟问题。证明了此问题是n p 难问题，并且 研究了多项式时间复杂度的动态规划算法。他们还考虑了当组内工件具有相同 的交货期时可以用伪多项式时间方法来解决；k o h 等【7 】针对大规模的调度问题提 出了一种简单的整数规划模型，并研究了几种启发式方法和混合遗传算法来解 决该调度问题；l i u 等【8 】研究了具有相同加工时间，目标函数为最小化总加权完 成时间、最小化最大延迟时间和总延迟时间的单批处理机调度问题。在并行机 调度研究方面，又许多学者提出了改进的在线调度算法【5 】、g a 【9 】、启发式方法【1 0 1 、 改进的调度规则【l l 】等。对于流水车间调度问题，m c n j e s h w a r 等l l2 j 研究了双批处 理机流水车间调度问题以最小化最大完成时间，并提出了基于j o h n s o n 算法和 s a 的一种新的解决办法。d a m o d a r a n 等【l3 】为双机流水车间环境下的批量调度问 题建立了混合整数模型。o u l a m a r a h 】针对不同机器上面进行批量调度和批处理 机调度问题研究了零等待双机流水车间批量调度。通过上面的研究可知，已经 有很多学者在调度方面取得了丰硕的成果。下面将根据启发式方法、数学规划 方法和智能算法三种方法对批处理机调度问题的研究现状进行简要介绍。 1 4 1 启发式方法在批处理机调度上的应用 启发式算法是相对最优算法提出来的，启发式算法是一种基于直观或经验 构造的算法，在可接受的条件下给出待解决问题实例的一个可行解，该可行解 与最优解的偏离程度不一定事先可以预知，甚至没办法得到当前解与最优解的 近似程度，它是一种技术，使得在可接受条件下去寻找最优解，但不一定保证 4 武汉理工大学硕士学位论文 可行性和最优性u 引。 j o h n s o n t l 6 l 于1 9 5 4 年提出求解具有两台机器的流水车间调度问题的最优算 法。p e r e z o r 等f l 7 】研究了半导体晶圆制造系统调度问题以满足客户两方面的需要： 最大化加权平均交货期和最小化延迟时间。提出了有效的启发式算法以解决该 问题。m o s h e i o v 掣1 8 】研究了单批处理机调度问题以最小化总流经时间。m a z d e h 等【1 9 】利用分支定界算法研究了单批处理机调度问题以最小化最大完成时间和 总交付成本。g h a z v i n i t 等【2 0 】研究了目标函数为最小化工件完工时间的问题，该 调度针对没有工件限制的单批处理机调度。s u n g 等【2 i 】研究了能处理相似批次工 件的多阶段流水车间批处理机调度问题，他们针对最大完成时间和总加工完成 时间利用混合启发式算法进行处理。 o u l a m a r a 等【2 2 】运用启发式方法研究了具有两机器的流水车间调度问题以最 小化最大完成时间。d a m o d a r a n 等【2 3 】研究了并行批处理机调度问题以最小化最 大完成时间，并研究了一些启发式算法，以及运用模拟退火及商业软件获得性 能指标进行比较。 1 4 2 数学规划方法在批处理机调度上的运用 数学规划方法是求解制造过程的传统方法之一。该类方法通常以寻求问题 的最优解为目标，首先将调度问题描述为整数规划或混合整数规划等模型，然 后采用相应的数学工具对其求解【l 引。 y i m e r 和d e m i r l i 2 4 】考虑了混合整数模糊规划模型和遗传算法来研究家具制 造批处理机调度问题以最小化最大加工完成时间。l u 等【2 5 】研究了无限制并行批 处理机调度问题。w a n g 等f 2 6 】研究了具有当前工件动态到达特性的单批处理机问 题以最小化最大拖后时间。l i 等【2 7 】研究了半导体制造系统中批处理机调度问题 以最小化最大延迟时间和延迟工件数，当工件的释放时间、交货期和加工时间 是可行时，运用动态规划算法能较好解决该问题。t a n g 等【2 8 】研究了在钢铁工业 中的半连续单机批量生产调度问题，其目标函数为最大加工完工时间和总的完 成时间。 c h e n g 和y a n g 2 9 】研究了具有加工优先次序、最小化释放时间和相同加工时 间的单机并行批处理机调度问题以最小化常见的目标函数如加工完成时间等。 j o l a i 6 1 主要考虑了在单批处理机中如何最小化工件延迟问题。证明了此问题是 n p 难问题，并且研究了多项式时间复杂度的动态规划算法。他们还考虑了当组 内工件具有相同的交货期时可以用伪多项式时间方法来解决。s u n g 等【3 0 】针对半 导体制造过程中出现的流水作业车间调度问题，研究了两机器流水车间调度问 5 武汉理工大学硕士学位论文 题。每个工件先在一台机器上a n - r _ ，然后在第二个机器上加工。l i u 等m j 研究了 在单批处理机上具有相同加工时间的工件调度问题。针对目标函数为最小化总 加权完成时间、最小化最大延迟时间和总的延迟时间，他们研究了f u l lb a t c h e a r l i e s td u ed a t e 针对最小化延迟工件数，研究了m o d i f i e dm o o r e - h o d g s o n ，针 对最小化加权延迟工件数问题，研究了w e i g h t e dm o d i f i e dm o o r e - - h o d g s o n ，l i a o c ta 1 【3 l 】研究了双批处理机流水车间调度问题以最小化最大完成时间。提出了改进 型的混合整数线性规划模型。s u n g 等【3 2 】运用动态规划算法研究了针对目标函数 为提前时间延迟时间指标和具有共同交货期的双机流水车间批处理机调度问 题。 赵玉芳等【3 3 】研究了极小化总完工时间的单机连续型批处理机调度问题，对 最优解的性质进行了理论分析，给出了一个多项式可解的动态规划算法。 d a m o d r a n 和s r i h a r i t l 3 1 研究了双机流水车间批调度问题两模型。给出了其数学公 式，该方法可用来解决缓冲能力为无限或是为零时的调度问题。m o s h e i o v 等【3 4 j 运用动态规划算法研究了具有相同加工时间的膨台机器的流水车间和两机器的 作业车间批调度问题，其目标函数为最小化最大完成时间。b e l l a n g e r 等【3 5 j 研究 了两阶段的混合流水车间调度问题以最小化最大完成时间。f u 等d 6 j 研究了工件 在并行批处理机系统中允许重新启动的在线调度问题。他们处理无限制模型， 每批的容量足够大。他们针对该问题研究了竞争率为3 2 的线性在线算法。p o r t s 等【3 7 】利用动态规划算法考虑了配料决策方面的批处理机调度问题。赵玉芳等【3 8 】 针对链式约束条件为工件释放时间和工期同序的情况，证明了即使所有工件都 是单位加工时间时，极小化最大拖期问题也是强n p 难问题。张丽华等【3 9 】运用 动态规划给出了一个求解问题最优解的算法，研究了目标函数为最小化工件的 提前与延迟时间的均值的批处理机随机e r r 调度问题，此算法的时间复杂度为 o ( n 2 8 2 ) ( b 七一，则转( 2 ) ； 武汉理工大学硕士学位论文 ( 7 ) 算法结束，输出优化解。 上述算法实现的初始阶段，确定了邻域结构集及其使用顺序，产生一个初 始解y 作为当前解，并选取算法终止条件。在搜索循环中，首先应用第一个邻域 结构随机生成当前解y 的一个邻域解y ；然后将y 作为局域搜索的输入解，对 其进一步优化得到局部最优解y ，再将y 与当前解y 进行质量比较。若y 。优于 y ，即得到改进解，y 代替y ，并以更新后的y 作为新的初始解开始新一轮的 搜索。否则，采用下一个邻域结构进入下一个搜索循环，即不断地变化邻域结 构。扰动过程将搜索转换到新的区域并开始新的局域搜索。若所有邻域都已搜 索，但没有得到当前解的改进解，算法开始下次迭代，仍然从当前解的基于第 一个邻域结构的邻域解开始搜索。以上步骤不断重复直到满足某个终止条件。 2 3 5 禁忌搜索算法 禁忌搜索( t s ) 算法是局部搜索的一种扩展，是通过邻域搜索不断改变搜索区 域而达到全局优化，是对人类智力过程的一种模拟。t s 算法引入一种灵活的存 储结构和相应的禁忌准则来避免迂回搜索，并通过描述准则来赦免一些被禁忌 的优良状态，进而保证多样化的有效搜索以最终实现全局优化。禁忌搜索在组 合优化、生产调度、机器学习和神经网络等诸多领域得到了成功的应用。下面 简要介绍t s 算法基本思想。 t s 算法的基本思想是先给其设定一个当前解，以及设计一种邻域结构，并 在当前解的邻域中确定若干候选解；若最佳候选解所得到的目标函数优于已保 留的最好解，则忽视其禁忌特性，用其替代当前解和最好解，并将相应的特性 加入到禁忌表中，同时对禁忌表进行修改，若不存在上述候选解，则在候选解 中选择非禁忌的做好衔接并作为新的当前解，不需要考虑它与当前解的优劣， 同时将解的相应特性加入禁忌表阱】。同时修改禁忌表，反复进行，直到满足停 止准则。图2 3 给出了禁忌算法的流程图。 从流程图可以看出，邻域结构、禁忌特性、禁忌表和藐视准则是t s 的关键， 通过选定合适邻域搜索方式、设计合适的禁忌特性以及藐视准则等，这样才能 够获得良好的调度解。 由于t s 所独有的特性，其禁忌特性和禁忌表能够避免在搜索过程中陷入局 部最优，能够通过记录之前的搜索结果，并利用藐视准则可以解除禁忌表中的 一些优良状态，从而可以转向其他的搜索区域，这样既避免了陷入局部最优， 而且还提高了解空间的搜索区域，从而更好获得全局最优解。 1 9 武汉理工大学硕士学位论文 一般而言，要设计一个禁忌搜索算法，需要确定算法的一些关键步骤： ( 1 ) 初始解 与其他的算法类似，t s 的初始解通常可以随机产生，或基于问题信息借助 图2 3 禁忌搜索算法的流程图 一些启发式方法来获得初始解。 ( 2 ) 邻域结构 邻域结构的设计一般跟具体研究的问题有关，现用运用最多一般为互换、 插入和逆序等操作来产生新的邻域解。 ( 3 ) 候选解选择 首先要确定候选解的数量；然后确定最佳候选解的选取。原则上应对当前 解的所有邻域解进行遍历，但当问题规模较大时，当前解的邻域解数量将很大， 考虑到邻域搜索的效率，仅选取邻域解集的子集。至于最佳候选解的选取，一 般做法是选择候选解集中满足藐视准则或非禁忌的最好解。 武汉理工大学硕士学位论文 ( 4 ) 禁忌长度 禁忌长度可以是固定的，也可以是自适应的，因为这是根据问题特性、研 究者的经验有关。 ( 5 ) 藐视准则 藐视准则一般有以下四种常用方式：基于适应值的准则、基于搜索方向的 准则、基于最小错误的准则和基于影响力的准则。最常用的藐视准则即若某个 解优于最优解，则无视其禁忌特性，直接选取它为当前解。 ( 6 ) 终止条件 常见的终止条件一般为最好解持续保持不变的最大迭代次数。 2 4 小结 本章首先阐述了批处理机调度问题解的各项评价指标，然后对该调度问题 的特点进行了简要介绍，并根据批处理机调度问题的分类，分别介绍了各种类 型的特点。最后对所研究的问题涉及的算法进行了简要介绍，以便于在后面章 节中更好的理解和运用。 2 1 武汉理丁大学硕士学位论文 第3 章基于禁忌搜索的多批处理机流水车间调度 3 1 半导体生产线批处理机调度介绍 批处理机调度是兴起于上世纪9 0 年代初应用背景很强的一类最优化问题， 它主要存在于大规模的现代化生产流水作业线如半导体生产、航空工业、钢铁 制造、测试电子电路等，其中半导体生产流水线，是被研究和应用最广泛、最 深刻的领域。 经典排序和调度问题通常假设机器在任何时刻最多只能加工一个工件，但 在实际生产中却并不是这样，有的机器能够同时加工多个工件，例如，在一个 面包机中就能够同时烘烤多个品种。在大规模集成电路芯片制造中，包含芯片 制作、芯片测试、装配和成品检测四个阶段，而在芯片测试阶段所使用的预烧 炉，每个芯片都有同样的一道加工工序那就是烘烤，并且都会有预定的烘烤时 间，只有通过这个阶段的测试的芯片才算是合格的产品。而预烧炉不可能说能 够一次性把所有的工件进行加工，肯定是会有一定的加工容量限制，加工芯片 的数量之和不能大于预烧炉的容量，满足预烧炉容量的工件进行组批，然后对 批进行烘烤，在这个加工的过程中是不允许中间停止的。在实际的加工过程中， 可能在同一批的工件中，工件的加工时间可能不一样，为了保证这一批的工件 质量，同一批中的芯片实际烘烤时间为这一批工件中预定时间最长的工件时间。 相对于其他工序来说，烘焙的时间用时很长，所以称为集成电路芯片测试过程 的一个瓶颈。因此，有效对芯片进行分批并进行合理调度对于提高生产设备利 用率和生产效益有重要的意义，我们称这一类问题为批处理机调度问题，这类 问题的研究对于钢铁生产等行业也具有广泛的应用价值。 半导体生产线包括氧化、扩散和淀积等加工工序，其加工区存在一类并行 批量加工设备，即批加工设备。而在实际生产过程中，有的工序是单个进行加 工的，存在着批加工设备和非批加工设备并存的问题，也就导致了半导体生产 线上的加工不稳定的问题。一般在实际生产过程中，能够进行批加工的加工设 备都一般满足下列特性：第一，在加工过程中只能是同类工件才能进行组批进 行加工，并且只有当机器满足当前工序才能够在此机器上面加工。第二，机器 的加工时间和加工的工件数目是没有关系的，仅仅只是跟该批工件中某一个工 件的加工时间有关，即该批工件中加工时间最长工件的加工时间即为该批的加 武汉理工大学硕士学位论文 工时问。第三，机器的a n - r 容量同样是一个很重要的指标，在进行加工的过程 中，组批的工件数量之和不能大于机器的加工容量。第四，在加工过程中，当 机器开始加工工件以后，就不能再增加或者减少工件，并且工件加工是非抢占 式的，也就是说只有一批工件加工完成之后才能开始下一批工件的加工。 3 2 问题描述 本文描述的为多处理机批调度问题，可描述为：有n 个待加工工件 ，2 ，。，和m 台批处理机，每个工件j ，在机器m 女似。，m 2 ，m 。) 上的 加工时间为p 工件大小为s ，每个工件的到达时间均为0 。所有工件加工路 径一样，被划分为个不相容的工件类型，只有同类型工件才能组批，任何b b 内所有工件的大小之和不能超过机器的加工容量c ，批b 在机器m 。上的加工时 间等于批内工件的最大加工时间，即p t 掀= m a x p 腩，j i b ) ，b 表示所有批次的 集合。 其它假设还包括： 批内所有工件的加工同时进行。 一旦一批工件的加工开始，其加工不能被中断。 在批加工过程中，新的工件不能加入到批中，批内工件也不能从批中移出。 一台批处理机器不能同时加工多批工件等等。 考虑如下目标： m i n i m i z e c 嗽= m a x c 6j ( 3 - 1 ) 其中，c 。表示批b 的完成时间。 多批处理机调度问题主要包括两个子问题：工件分批和批的优先级排序。 工件分批的任务就是通过合适的方法选择同一类型的工件进行组批，例如，当 加工工件数目为2 0 ，并有两种类型的工件，类型一的工件个数为1 0 个，另一种 类型也为1 0 个，而在实际加工的过程中只能是同一类型工件才能进行组批，而 且每台机器都有加工容量的限制，需要根据机器的加工容量对同一类型的工件 进行组批，怎样对工件进行工件组批是我们要考虑的问题；另一方面，当工件 分批完成后，不同类型的工件都完成了分批，就需要考虑批的排序问题，批次 的加工顺序不同，对于机器的利用率，以及生产效率都有很大的影响。 本章主要利用禁忌搜索算法处理多批处理机流水车间调度问题。 武汉理工大学硕士学位论文 3 3 基于禁忌搜索的多批处理机流水车间调度算法 目前批处理机调度的研究方法主要有两种，一种是基于分解的方法，一种 是基于集成的方法。批处理机调度也包含两个子问题：工件分批和批排序。基 于分解的方法主要是把两个子问题处理成单独的问题分别进行研究，分别进行 优化，；而基于集成的方法主要是把两个子问题作为一个整体进行研究，同时对 这两个子问题进行优化。在以往的研究过程中，基于分解的方法因为实现方式 简单，且一个阶段只需考虑一个子问题，但是往往求解的质量不高，而基于集 成的方法需要把两个问题进行统一融合，由于每个子问题本身就是一个n p 难的 问题，将两个问题融合之后使问题研究更加复杂，但往往通过这种方法得到的 解质量比较高，优化效果比较明显。