产能约束下半导体芯片测试生产线调度优化研究

摘要

芯片测试是半导体制造的最后一个阶段，负责对封装好的集成电路进行各种性能检测。随着集成电路芯片集成度和复杂度地不断增加，芯片测试的技术含量越来越高，成本也随之增加，已占到了集成电路总成本的三成。芯片测试已成为我国半导体产业发展的一个瓶颈，开始得到管理科学、工业工程、自动化等领域学者的广泛关注。
　　 半导体生产调度问题具有大规模、可重入、混合加工模式和资源受限等特点，是一类复杂的组合优化问题。目前，大部分学者的研究都仅考虑了机器设备的产能约束，而假设其他附属资源的产能无限，与现实中需要机器设备和操作手等附属资源同时具备的情况并不相符，另外，很少有学者在优化调度中考虑基于工件顺序转换时间的约束，导致研究结果很难应用于实际。本文针对半导体芯片测试生产线的特殊性，突出在机器设备及附属资源产能有限的约束下，对带有基于工件顺序转换时间的复杂生产系统进行优化调度。我们将半导体芯片测试生产线上存在的调度问题简化为拥有功能测试与老化测试两个工序的柔性流水作业调度问题，对其采用“先分段，后整合”的策略先对功能测试与老化测试工序存在的调度问题分别进行优化，随后将两子问题整合为一个柔性流水作业调度问题，并为其设计出了一种混合微粒群优化算法。
　　 对于功能测试工序调度问题，我们为其建立了同时考虑附属资源与基于工件顺序转换时间两个约束的同型平行机调度问题模型，求解出问题最优解并设计出一个遗传算法和一个变邻域搜索算法用于对大规模问题进行优化调度。
　　 对于老化测试工序调度问题，我们将其看作带有基于工件顺序转换时间的单机调度问题，运用商业优化软件和六种不同算法对其进行了优化。实验结果证明，在求解大规模问题时仅需一次运算的启发式方法明显优于其他需上千次运算的算法。
　　 对于两阶段生产线调度问题，我们提出一种混合微粒群优化算法。在该算法中，微粒群优化用于执行全局优化操作，而变邻域搜索则被用于执行单个工序局部优化的操作，这样既有效弥补了微粒群优化算法局部搜索能力有限的缺点，又使得该混合算法具备了很强的可扩展性，稍作修改即可应用于多阶段生产线的调度问题优化。另外，算法中各微粒独立运行局部搜索操作，可以更方便的应用并行运算技术使其运算效率得到更大提高。

目录

声明

摘要

第1章 绪论

1．1 引言

1．2 生产调度问题简介

1．2．1 生产调度问题

1．2．2 三参数表示

1．3 半导体生产调度

1．3．1 工艺流程

1．3．2 问题特点

1．4 本文主要内容及结构安排

1．4．1 主要内容

1．4．2 结构安排

第2章 半导体功能测试工序调度优化

2．1 功能测试工序调度问题介绍

2．2 RSPS相关文献综述

2．3 混合整数规划模型

2．3．1 变量定义

2．3．2 目标函数与约束函数

2．4 求解RSPS的遗传算法

2．4．1 遗传算法概述

2．4．2 编码与解码

2．4．3 适配值函数与初始化方法

2．4．4 算子操作

2．5 求解RSPS的变邻域搜索算法

2．5．1 变邻域搜索算法总体流程

2．5．2 编码解码、初始解与SA Acceptance

2．5．3 Shaking

2．5．4 Local Search

2．6 算例实验

2．6．1 小规模算例

2．6．2 大规模算例

第3章 半导体老化测试工序调度优化

3．1 老化测试工序调度问题介绍

3．2 STS相关文献综述

3．3 混合整数规划模型

3．3．1 变量定义

3．3．2 目标函数与约束函数

3．4 几种求解STS的智能优化算法

3．4．1 遗传算法(Genetic Algorithm，GA)

3．4．2 模拟退火(Simulated Annealing，SA)

3．4．3 变邻域搜索(Variable Neighborhood Search，VNS)

3．4．4 混合变邻域搜索(VNSSA)

3．4．5 随机搜索(Random Search，RAN)

3．4．6 启发式规则(Heuristic Method，HM)

3．5 算例实验

3．5．1 初始解随机生成的算法对比

3．5．2 初始解由HM生成的算法对比

第4章 两阶段生产线调度优化

4．1 半导体芯片测试生产线调度问题介绍

4．2 RSFF相关文献综述

4．3 混合整数规划模型

4．3．1 参数定义

4．3．2 变量定义

4．3．3 目标函数与约束函数

4．4 求解RSFF的混合微粒群优化算法

4．4．1 微粒群优化算法概述

4．4．2 CPSO总体流程

4．4．3 编码与解码

4．4．4 初始化与初始解码

4．4．5 PSO更新操作

4．4．6 第一工序局部优化

4．4．7 第二工序局部优化

4．5 问题下界

4．6 算例实验

4．6．1 小规模算例

4．6．2 大规模算例

结论

致谢

参考文献

攻读硕士学位期间发表的论文及科研成果