论文部分内容阅读
半导体晶圆制造系统是半导体制造过程中最为复杂和昂贵的环节,晶圆制造系统的调度问题是一类复杂的车间调度问题。尽管目前晶圆制造系统求解调度问题最常见的方法是启发式调度规则,但是智能算法在未来的晶圆制造系统中应用的潜力非常大,这是因为智能算法具有自组织与自调整能力,可以适应调度问题的变化,并在可接受的时间内获得高质量的解。蚁群算法是一类产生不久但发展迅速的智能算法,它不仅具有一般智能算法的优点,而且具有并发多线程搜索机制与正反馈特点,可以更迅速地获得满意的可行解,因而近年来被逐渐应用于解决生产调度问题。但是到目前为止,应用蚁群算法求解晶圆制造系统调度问题的研究还很不深入,这是因为传统蚁群算法不能很好地应对晶圆制造系统的复杂性,特别是其大规模、多重入、混合型生产的特征。基于以上的原因,本文提出基于问题分解的蚁群算法,有针对性地对传统蚁群算法进行改造,并结合问题分解方法,以期获得晶圆制造系统调度问题的高质量解。本文所取得的主要工作成果包括:1)建立应用蚁群算法调度晶圆制造系统的问题分解框架。元启发算法可解决较大规模的调度问题,但是当其用于解决晶圆制造调度这样的大规模调度问题时,随着问题规模急剧扩大,元启发算法的应用会受到制约。为此,应用问题分解方法将大规模问题分解为小规模的子问题,再用蚁群算法分别求解,就成为一条可行的解决途径。本论文提出两类适合晶圆制造系统特征的问题分解方法,包括基于时间的问题分解方法与基于机器类型的问题分解方法。前者用来应对晶圆制造系统的大规模特征。通过对调度时间的分割,在每个时间区间内只需要处理部分机器与工件,降低了问题的规模与难度;后者用来应对混合型生产的特征,通过对机器按照类型进行分解,针对每一类型采用相应的蚁群算法进行处理,使得调度问题更易于解决。在此基础上,建立应用蚁群算法调度晶圆制造系统的问题分解框架,以有效处理大规模晶圆制造系统调度问题。2)提出调度问题分解协调机制。问题分解是一个将各子问题解耦的过程,在各子问题单独求解完成后,这些解合成原问题的解又面临如何协调的问题,这两个问题如何处理是问题分解方法最需要考虑的问题。本文提出三类协调机制,首先针对基于时间的问题分解方法,提出基于重叠区间的协调机制,保证了原问题调度方案的可行性;其次提出了基于工件上下游的协调机制,通过上下游机器的加工信息,决定当前机器的调度策略,以提供调度方案的精度;最后采用蚁群算法的信息素更新机制作为隐性协调机制,针对基于机器的分解方法,采用蚁群算法的信息素保证分解后的机器间信息的沟通。3)针对晶圆制造系统与问题分解方法特征对现有蚁群算法进行改进。为了应对晶圆制造系统的复杂性特征,以及适应前述问题分解方法,对现有蚁群算法进行了改进:首先,针对晶圆制造系统的多重入特征,开发基于重入的蚁群算法,针对加工目标对不同加工阶段的工件赋以不同的信息权重,使其可以获得更好的调度方案。其次,应对基于类型的分解方法,当将子问题分解为若干单机调度问题后,针对其中较难调度且经常为系统瓶颈的批处理设备开发专门的蚁群算法,以保证整个调度问题的顺利求解。最后,提出分类蚁群算法,使得多种类型设备的调度问题可以在一个算法构架下共存。最后,采用仿真实验对所提出的问题分解方法、协调机制与蚁群算法进行验证,实验分别针对单台设备调度问题、子问题调度、大规模调度问题而进行,实验结果证明了本文所提出方法的可以有效地处理晶圆制造系统的复杂特征,并获得高质量的调度方案。