基于遗传算法的半导体生产线调度问题研究

摘要

半导体生产线是典型离散动态的制造系统,具有制造工艺复杂、设备复杂、随机性大、可重入性等特点,其调度问题已经被证明是NP难问题,一直是学术和工程界的研究热点。本文研究了半导体生产线中存在的并行离散机生产调度模型及两阶段混合流水作业调度模型,并分别设计了相应的遗传算法进行求解。具体内容为:
　　 本文首先研究了多阶段、多任务、在同一台机器上的相邻两个任务具有转换时间、目标函数分别为所有任务完工时间之和最小化和总加工时间最小化的并行离散机的调度问题。对该问题设计了一种遗传算法对其求解,算法中采用随机产生初始种群的编码方式,即每条染色体包含与阶段数目相同的基因片段,每个片段均包含任务序列和对应可行的机器序列两部分。并将活跃排序技术和修复策略应用到工期的计算当中。数值实验证明,本文设计的遗传算法能得到更好的解。
　　 其次研究了两阶段混合流水作业问题,该问题的第一阶段包含了不同的并行离散机,每个并行离散机一次只能加工一个任务；第二阶段包含了容量不同的并行批处理机。并行批处理机可同时加工多个任务,每批的加工时间为该批中任务的最大加工时间,每批任务的开始和完工时间相同。我们将动态规划算法与遗传算法相结合对该问题进行求解。数值实验结果表明,本文设计的算法是有效的。

目录

文摘

英文文摘

第一章 绪论

1.1 引言

1.2 半导体生产线制造流程简介

1.3 半导体生产线的特点

1.4 半导体生产线研究方法

1.5 论文结构及安排

第二章 遗传算法理论介绍

2.1 引言

2.2 遗传算法的发展及现状

2.3 遗传算法的基本概念

2.4 遗传算法的过程和流程

2.5 遗传算法的基因操作

2.6 遗传算法控制参数设定

2.7 遗传算法的特点及理论

第三章 多阶段多产品的并行离散机调度问题的研究

3.1 问题描述及其数学模型

3.2 研究现状

3.3 求解多阶段多产品的并行离散机调度问题的遗传算法

3.4 数值实验

第四章 带有批处理机的两阶段混合流水作业调度问题的研究

4.1 两阶段混合流水作业调度问题介绍及其数学模型

4.2 研究现状

4.3 求解两阶段混合流水作业调度问题的遗传算法

4.4 数值实验

第五章 总结与展望

5.1 本文小结

5.2 展望

参考文献

致谢