集束型晶圆制造装备调度及其优化算法

本书可供从事集束型晶圆制造装备计划、调度和优化等相关领域研究工作的科研人员，自动化控制、工业工程等专业研究生和教师、制造管理及微电子制造行业生产管理或工程技术人员等阅读和参考。

    本书以半导体集束型装备为研究对象，在全面分析其调度特点的基础上，详细解剖、分析半导体集束型装备各类调度问题，建立了调度模型并运用智能化方法设计了相应的求解方案。本书在认真总结靠前外多年的半导体集束型装备调度研究成果的基础上，结合作者多年在生产调度，特别是半导体集束型装备领域的研究与应用成果，对复杂的半导体集束型装备调度问题从理论到方法再到应用进行了多方面、系统化的论述。

    李林瑛，大连外国语大学软件学院副教授。

目  录

第1章  绪  论 1
1.1  半导体装备制造产业的战略意义 1
1.2  半导体制造工艺简介 4
1.3  集束型晶圆制造装备的高度复杂性 8
1.4  制造系统调度简介 13
1.4.1  车间调度 14
1.4.2  机器人制造单元调度 16
1.4.3  抓钩调度 19
1.5  集束型装备调度 21
1.5.1  基本概念 21
1.5.2  调度资源 23
1.5.3  约束条件 24
1.6  集束型晶圆制造装备调度分类 25
1.6.1  基于调度类型的分类方法 25
1.6.2  基于三邻域（α？β？γ）的分类方法 27
1.6.3  基于调度环境和任务的分类方法 28
本章参考文献 29
第2章  集束型晶圆制造装备的建模方法 36
2.1  基于马尔科夫模型的集束型装备建模 36
2.1.1  马尔科夫模型基础理论 37
2.1.2  集束型装备马尔科夫建模过程 38
2.2  基于数学规划模型的集束型装备建模 39
2.2.1  数学规划模型基本理论 40
2.2.2  集束型装备数学规划建模过程 41
2.3  基于时序图模型的集束型装备建模 43
2.3.1  时序图模型基础理论 43
2.3.2  集束型装备时序图建模过程 44
2.4  基于Petri网模型的集束型装备建模 48
2.4.1  Petri网模型基础理论 48
2.4.2  集束型装备Petri网建模过程 54
2.5  基于仿真模型的集束型装备建模 58
2.5.1  仿真模型的基本理论 59
2.5.2  集束型装备仿真建模过程 61
2.6  小结 66
本章参考文献 66
第3章  集束型晶圆制造装备的调度方法 71
3.1  基于运筹学方法的集束型装备调度 71
3.1.1  运筹学方法概述 72
3.1.2  混合整数规划在集束型装备调度中的应用 79
3.1.3  分支定界算法在集束型装备调度中的应用 88
3.2  基于多项式算法的集束型装备调度 94
3.2.1  多项式算法概述 94
3.2.2  多项式算法在集束型装备调度中的应用 97
3.3  基于启发式方法的集束型装备调度 99
3.31  启发式方法概述 100
3.3.2  启发式方法在集束型装备调度中的应用 105
3.4  基于智能优化方法的集束型装备调度 107
3.4.1  智能优化方法概述 108
3.4.2  智能优化方法在集束型装备调度中的应用 118
3.5  小结 120
本章参考文献 121
第4章  集束型晶圆制造装备的重入和混流调度 129
4.1  引言 129
4.2  重入调度的混合整数规划模型 130
4.2.1  问题描述 130
4.2.2  约束条件分析 132
4.2.3  仿真 136
4.3  混流调度的混合整数规划模型 138
4.3.1  调度问题 139
4.3.2  混合整数规划模型 141
4.3.3  生产周期下界分析 144
4.3.4  仿真 148
4.4  小结 151
本章参考文献 151
第5章  集束型晶圆制造装备的多机械手调度 154
5.1  引言 154
5.2  基于分解方法的两集束型装备调度 155
5.2.1  符号定义和问题描述 155
5.2.2  问题的分解分析和模型的建立 157
5.2.3  机械手在缓冲模块无碰撞的判断条件 159
5.2.4  基于分解方法和线性规划模型的搜索算法 161
5.2.5  仿真 162
5.3  有滞留时间约束的两集束型装备调度模型 164
5.3.1  符号定义和问题描述 164
5.3.2  集束型装备的混合整数规划模型 166
5.3.3  并行加工模块 168
5.3.4  仿真 169
5.4  求解k晶圆周期序列的多集束型装备调度 173
5.4.1  符号定义和问题描述 174
5.4.2  k序列的平均周期下界 175
5.4.3  k序列的构造策略 177
5.4.4  仿真 182
5.5  小结 191
本章参考文献 192
第6章  集束型晶圆制造装备的滞留时间约束调度 194
6.1  引言 194
6.2  单臂机械手集束型装备可调度性与调度 195
6.2.1  问题描述 195
6.2.2  并行加工模块加工时间的等效性证明 197
6.2.3  可调度性分析 199
6.2.4  仿真 201
6.3  双臂机械手集束型装备可调度性与调度 203
6.3.1  符号定义和问题描述 203
6.3.2  有晶圆滞留时间约束的线性规划模型 204
6.3.3  集束型装备的可调度性分析 205
6.3.4  仿真 207
6.4  单臂机械手的集束型装备启发式搜索方法 211
6.4.1  问题描述 212
6.4.2  调度模型 213
6.4.3  基于线性规划模型和冲突控制策略的启发式搜索方法 214
6.4.4  仿真 216
6.5  基于分解思想的多集束型装备启发式调度方法 217
6.5.1  问题描述和定义 217
6.5.2  周期性调度过程分析 218
6.5.3  启发式调度方法 219
6.5.4  仿真 220
6.6  基于遗传算法的集束型装备调度方法 222
6.6.1  问题描述和调度问题 222
6.6.2  改进遗传算法 224
6.6.3  仿真 228
6.7  小结 230
本章参考文献 231
第7章  集束型晶圆制造装备的应急调度 234
7.1  引言 234
7.2  基于PSO的启发式调度方法 236
7.2.1  调度问题描述和数学模型 236
7.2.2  基于前向和后向递归方法的内层算法 237
7.2.3  微粒群算法优化算法分析 242
7.2.4  基于微粒群算法的两层在线调度方法 245
7.2.5  仿真 247
7.3  基于量子进化算法的在线调度方法 250
7.3.1  在线调度问题 250
7.3.2  在线调度方法 251
7.3.3  外层量子进化算法 253
7.3.4  仿真 256
7.4  小结 258
本章参考文献 259
第8章  基于SEMI标准的集束型晶圆制造装备控制平台 261
8.1  引言 261
8.2  CTC控制软件概述 262
8.2.1  国内外半导体制造自动化公司 262
8.2.2  SEMI协会和SEMI标准 264
8.3  实时调度系统框架模型 266
8.3.1  基于SEMI标准的CTC控制软件 266
8.3.2  实时调度系统框架模型 267
8.4  实时调度系统的监督控制层 268
8.4.1  扩展有限状态机 269
8.4.2  基于EFSM的调度控制逻辑模型 269
8.5  基于CTMC标准的实时调度系统模块管理层 272
8.5.1  作业分解过程 272
8.5.2  基于CTMC的作业执行 273
8.6  数据通信协议的分析与设计 276
8.6.1  通信协议简介 276
8.6.2  通信协议设计 308
8.6.3  通信协议开发 311
8.6.4  通信协议实现 316
8.7  模块控制器层 320
8.7.1  加工模块控制器软件架构 320
8.7.2  模块控制器层模型 321
8.8  实时调度系统的测试与验证 321
8.8.1  测试和验证过程概述 322
8.8.2  测试和验证系统需求分析 322
8.8.3  测试和验证系统实现 323
8.9  小结 326
本章参考文献 326

前  言  半导体芯片制造业是一个尖端技术及高附加值产业，对国民经济的发展具有巨大的战略价值，世界各国政府都将其视为国家的骨干产业。在世界制造业中心向亚太地区转移的大背景下，在国家产业政策的推动下，中国的半导体芯片产业获得了飞速的发展。要保持我国半导体芯片制造业良好的发展势头，提升我国半导体芯片制造业国际竞争能力，不仅要扩大规模，而且要注重提高制造系统绩效。把我国的半导体芯片做大、做强，不仅需要先进的半导体芯片设计技术、制造工艺技术及装备技术，而且需要先进的生产管理技术。半导体制造的源头是芯片制造，芯片制造的关键是其制造装备。集束型晶圆制造装备（Cluster  Tools）是由物料搬运机械手和若干单晶圆加工设备构成的自动化组合制造系统，代表着当今半导体制造装备的先进水平，越来越多地应用到芯片的制造中。集束型装备调度问题与生产调度问题一样具有复杂性，如建模困难（数学模型或仿真模型难以建立）、高度重入加工（半导体制造过程中晶圆多次进入相同的设备加工）、存在多约束耦合（加工能力、滞留时间、机械手能力等约束耦合）、不确定（加工时间波动、设备自动清洗、临时晶圆插入、设备故障、返工等）、多种类型机械手（单臂机械手、双臂机械手、多机械手）、多种类型晶圆混合加工（晶圆代工厂要同时生产几十种产品，生产调度要同时考虑晶圆排序和机械手搬运作业排序）、存在不同的晶圆流模式（表现为串行、并行和重入晶圆模式）、大规模（晶圆和机械手搬运作业数量庞大，解空间可能随问题规模的增大而呈指数增长等）。研究表明，绝大多数集束型装备调度问题属于NP-hard性质的问题，其研究具有重要的学术意义和工程价值。本书力图总结作者和国内外同行在集束型晶圆制造装备调度问题方面所取得的一系列研究成果，主要讨论集束型晶圆制造装备重入和混流调度、集束型晶圆制造装备的多机械手调度、集束型晶圆制造装备的滞留时间约束调度、集束型晶圆制造装备的应急调度、集束型晶圆制造装备混合晶圆调度等问题的数学模型、问题特性及优化调度算法，以及基于SEMI标准的集束型装备控制平台的设计与验证等。全书共8章，主要内容如下：第1章为绪论，简要介绍半导体制造产业的战略意义、半导体制造工艺、集束型装备的高度复杂性、制造系统调度、集束型装备调度资源和约束条件、集束型装备调度的分类。第2章介绍集束型晶圆制造装备的建模方法，包括基于马尔科夫模型、数学规划模型、时序图模型、Petri网模型及仿真模型等。第3章介绍集束型晶圆制造装备的调度方法，包括基于运筹学方法、多项式算法、启发式方法和智能优化方法等。第4章介绍集束型晶圆制造装备的重入和混流调度的混合整数规划模型，该模型包括加工模块能力约束、机械手能力约束、重入模块约束等。第5章论述集束型晶圆制造装备的多机械手调度，重点介绍基于分解方法和线性规划模型的搜索算法、基于LCM和Swap的k序列策略和构造算法等。第6章围绕集束晶圆制造型装备的滞留时间约束调度展开，重点介绍单臂和双臂机械手的可调性条件、基于线性规划模型和冲突控制策略的启发式搜索方法、基于分解思想的多集束型装备启发式调度方法。第7章介绍集束型晶圆制造装备的应急调度，依次对基于微粒群的两层在线调度方法和基于量子进化算法的在线调度方法展开介绍。第8章介绍CTC控制软件架构及SEMI标准，论述了CTC实时调度系统框架模型，该模型分为监督控制层、模块管理层、模块控制器层；接着介绍了通信协议的分析与设计过程，包括SEMI标准SECS-I、HSMS、SECS-II和GEM四个通信协议；最后，介绍了利用“虚拟控制”思想对模型进行仿真、调度和验证的过程。本书所涉及的研究成果是在辽宁省高等学校优秀人才支持计划（LJQ2011132）、辽宁省教育厅科学研究一般项目（L2014456）、大连外国语大学科研基金项目（2014XJYB05）等的资助下取得的。另外，还要特别感谢电子工业出版社对本书的大力支持，感谢吴长莘等在书稿编辑出版过程中所给予的宝贵建议和付出的辛勤劳动。本书可作为计算机科学与技术、管理科学与工程、机械工程等相关学科的教师、学生和研究人员的参考书。集束型晶圆制造装备研究是一类NP特征的调度问题中具有高度复杂性和挑战性的课题，随着国际上对这类问题研究的不断深入，以及我国半导体制造装备的兴起与迅速发展，有关的研究还在不断发展和完善之中，本书作为作者近年来学习和研究的一个阶段性总结，其中难免会有不当甚至错误之处，敬请广大读者批评指正。作  者    2016年11月