基于混合蚁群算法的半导体生产线炉管区调度方法

doi:10.16183/j.cnki.jsjtu.2018.232

摘要/Abstract

摘要：

炉管区是半导体生产线的主要瓶颈之一,对整个生产线的性能影响较大.当前针对炉管区调度研究以规则调度为主,且考虑约束较为简单,忽略了存在前后道工序影响的多机台调度以及晶圆加工的重入特性.针对具有等待时间约束、不兼容工艺菜单和重入特性的炉管区β₁→β₂调度问题,构建了目标为最小化晶圆平均流动时间的β₁→β₂调度模型.将该调度问题分成组批、设备选择及批排序3个阶段,提出了一种基于混合蚁群优化算法的炉管区调度算法.针对组批阶段,设计了一种可变阈值控制策略.针对批排序阶段,设计了混合蚁群优化算法.进行了历史生产数据的不同规模54组算例实验,结果表明:混合蚁群算法的性能均优于几种常用启发式规则和遗传算法的性能.将所提出的混合蚁群算法应用于实际晶圆生产线,能够有效减少生产过程中晶圆的流动时间.

关键词: 半导体制造, 炉管, 批调度, 混合蚁群算法

Abstract:

Furnace district is one of the main bottlenecks in semiconductor fabrication, which has a great influence on the entire production line. The current scheduling research in the furnace district mainly focuses on dispatching rules, and the constraints considered are relatively simple. The previous research ignores not only the multi-machine scheduling which contains front and rear procedures but also the re-entrant characteristic of the wafer fabrication. This paper focuses on the scheduling problem of β₁→β₂ type for minimizing the meaning flow time (MFT) in furnace district. The constraints consist of limited waiting time, incompatible families, and re-entrant flow. It builds a novel β₁→β₂ model about the scheduling problem, and decomposes the problem into three stages: batch forming, machine selecting, and batch sorting. An algorithm based on the hybrid ant colony optimization algorithm is proposed, which batches the jobs by using a variable threshold control strategy, and sorts these batches by a hybrid ant colony optimization algorithm. According to the results of 54 sets of different scales based on historical production data, it is concluded that the performance of the hybrid ant colony optimization (ACO) algorithm is better than several common heuristic rules and the genetic algorithm. The proposed hybrid-ACO algorithm is applied to the actual wafer production line, which can effectively reduce the water flow time in the production process.

Key words: semiconductor manufacture, furnace, batch scheduling, hybrid ant colony algorithm

中图分类号:

TH166

蒋小康, 张朋, 吕佑龙, 赵新明, 张洁. 基于混合蚁群算法的半导体生产线炉管区调度方法[J]. 上海交通大学学报, 2020, 54(8): 792-804.

JIANG Xiaokang, ZHANG Peng, LÜ Youlong, ZHAO Xinming, ZHANG Jie. Hybrid Ant Colony Algorithm for Batch Scheduling in Semiconductor Furnace Operation[J]. Journal of Shanghai Jiaotong University, 2020, 54(8): 792-804.

图/表 12

图1

图2

图3

表1

调度问题描述数据

问题参数	取值范围	种类数
MG¹设备数	4、6	2
MG²设备数	4	1
设备最大容量	8^[20]	1
MG¹前道工序菜单类型	1、2、3、4	4
MG¹后道工序菜单类型	1、2、3、4、5、6、7、8	8
MG²工艺菜单类型	1、2、3、4	4
MG¹前道工序不同菜单加工时间	(180,400)均匀分布	1
MG¹后道工序不同菜单加工时间	(180,400)均匀分布	1
MG²工艺不同菜单加工时间	(240,900)均匀分布	1
到达时间/min	(0, $τ M ∑ i = 1 1000$ P_i), τ=0.5,0.75,1均匀分布	3
工件加工层数	(25,30)均匀分布	1
后期MG³加工时间/min	(800,1200)均匀分布	1
工艺间准备时间/min	(5,20)均匀分布	1
等待时间/min	90	1
运输时间/min	(2,5)均匀分布	1
	每个组合的运行次数	10
	总问题数	7680

表1

表2

图4

表3

图5

图6

图7

图8

表4

不同测试问题下炉管区调度方法对比

测试规模	IVTRP-ACO		BRFFERT-AR			GA			CPLEX
测试规模	MFT/s	t/s	MFT/s	t/s	$R ˉ BRFFERT - AR$	MFT/s	t/s	$R ˉ GA$	MFT/s	t/s	$R ˉ CPLEX$
M=4,τ=0.5	108519	1805.6	119856	30.62	10.44%	116398	460.86	7.26%	102410	21600	-5.63%
M=4,τ=0.75	109068	2119.5	121253	29.85	11.17%	116190	594.93	6.52%	117772	21600	7.98%
M=4,τ=1	109980	2705.1	122437	32.02	11.32%	116828	517.29	6.22%	—	21600	—
M=6,τ=0.5	107892	1956.2	116812	30.31	8.26%	116549	450.98	8.02%	138900	21600	28.74%
M=6,τ=0.75	108067	2006.0	119601	32.56	10.67%	116428	567.54	7.73%	143978	21600	33.23%
M=6,τ=1	109445	2548.9	121698	32.69	11.19%	116966	544.32	6.87%	—	21600	—
平均	108828	2190.2	120276	31.34	10.51%	116559	522.65	7.10%	131421	21600	16.08%

表4

参考文献 18

[1]	吴启迪, 乔非, 李莉, 等. 半导体制造系统调度[M]. 北京: 北京为电子工业出版社, 2006.
	WU Qidi, QIAO Fei, LI Li, et al. Scheduling of semiconductor manufacturing system[M]. Beijing: Publishing House of Electronics Industry, 2006.
[2]	IKURA Y, GIMPLE M. Efficient scheduling algorithms for a single batch processing machine[J]. Operations Research Letters, 1986,5(2):61-65. doi: 10.1016/0167-6377(86)90104-5 URL
[3]	PARSA N R, KARIMI B, HUSSEINI S M. Exact and heuristic algorithms for the just-in-time sche-duling problem in a batch processing system[J]. Computers and Operations Research, 2017,80:173-183. doi: 10.1016/j.cor.2016.12.001 URL
[4]	CHENG B, WANG Q, YANG S, et al. An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes[J]. Applied Soft Computing, 2013,13(2):765-772. doi: 10.1016/j.asoc.2012.10.021 URL
[5]	PARSA N, KARIMI B, HUSSEINI S. Minimizing total flow time on a batch processing machine using a hybrid max-min ant system[J]. Computers and Industrial Engineering, 2016,99:372-381. doi: 10.1016/j.cie.2016.06.008 URL
[6]	GURNANI H, ANUPINDI R, AKELLA R. Control of Batch Processing Systems in Semiconductor Wafer Fabrication Facilities[J]. IEEE Transactions on Semiconductor Manufacturing, 1992,5(4):319-328. doi: 10.1109/66.175364 URL
[7]	CEREKCI A, BANERJEE A. Dynamic control of the batch processor in a serial-batch processor system with mean tardiness performance[J]. International Journal of Production Research, 2010,48(5):1339-1359. doi: 10.1080/00207540802641437 URL
[8]	HAM M, LEE Y H, AN J. IP-Based real-time dispatching for two-machine batching problem with time window constraints[J]. IEEE Transactions on Automations Science and Engineering, 2011,8(3):589-597.
[9]	AHMADI J H, AHMADI R, DASU S, et al. Bat-ching and Scheduling Jobs on batch and discrete processors[J]. Operations Research, 1992,40(4):750-763. doi: 10.1287/opre.40.4.750 URL
[10]	李程, 江志斌, 李友, 等. 基于规则的批处理设备调度方法在半导体晶圆制造系统中应用[J]. 上海交通大学学报, 2013,47(2):230-235.
	LI Cheng, JIANG Zhibin, LI You, et al. Rule-based scheduling of batch processing machine applied to semiconductor wafer fabrication system[J]. Journal of Shanghai Jiao Tong University, 2013,47(2):230-235.
[11]	JIA W, CHEN H, JIANG Z, et al. Full-batch-oriented scheduling algorithm on batch processing workstation of β1→ β2 type with re-entrant flow[J]. International Journal of Computer Integrated Manufacturing, 2017,30(10):1029-1042. doi: 10.1080/0951192X.2017.1285425 URL
[12]	田云娜, 李冬妮, 郑丹, 等. 一种基于时间窗的多阶段混合流水车间调度方法[J]. 机械工程学报, 2016,52(16):185-196.
	TIAN Yunna, LI Dongni, ZHENG Dan, et al. A time window-based approach for multi-stage hybrid flow shop[J]. Chinese Journal of Mechanical Engineering, 2016,52(16):185-196.
[13]	张洁, 张朋, 刘国宝. 基于两阶段蚁群算法的带非等效并行机的作业车间调度[J]. 机械工程学报, 2013,49(6):136-144.
	ZHANG Jie, ZHANG Peng, LIU Guobao. Two-stage ant colony algorithm based job shop scheduling with unrelated parallel machines[J]. Chinese Journal of Mechanical Engineering, 2013,49(6):136-144.
[14]	AKCALI E, UZSOY R, TEYNER T J, et al. Alternative loading and dispatching policies for furnace operations in semiconductor manufacturing: A comparison by simulation[J]. Proceedings of the 2000 winter Simulation Conference, 2000: 1428-1435.
[15]	LI L, QIAO F, WU Q. ACO-based scheduling of parallel batch processing machines with incompatible job families to minimize total weighted tardiness[C]// International Conference on Ant Colony Optimization and Swarm Intelligence. Springer, Berlin, Heidelberg, 2008: 219-226.
[16]	李小林. 平行机环境下批处理机调度问题研究[D]. 安徽: 中国科学技术大学, 2012.
	LI Xiaolin. Research on scheduling batch processing machines in parallel[D]. Anhui: University of Science and Technology of China, 2012.
[17]	BALASUBRAMANIAN H, MÖNCH L, FOWLER J, et al. Genetic algorithm based scheduling of para-llel batch machines with incompatible job families to minimize total weighted tardiness[J]. International Journal of Production Research, 2004,42(8):1621-1638. doi: 10.1080/00207540310001636994 URL
[18]	李程. 半导体晶圆制造系统(SWFS)炉管区组批派工策略研究[D]. 上海: 上海交通大学, 2011.
	LI Cheng. Research on scheduling of batch processor in furance area of semiconductor wafer manufacturing system[D]. Shanghai: School Of Mechanical Engineering Shanghai Jiao Tong University, 2011.

试验编号	参数							结果/min
试验编号	α	β	ρ_local	ρ_global	iter	q_m0	Q	结果/min
1	0.95	0.95	0.15	0.15	50	0.15	40	320
2	0.95	0.9	0.1	0.1	80	0.1	50	339
3	0.95	0.85	0.05	0.05	100	0.05	60	340
4	0.9	0.95	0.15	0.1	80	0.05	60	341
5	0.9	0.9	0.1	0.05	100	0.15	40	334
6	0.9	0.85	0.05	0.15	50	0.1	50	336
7	0.85	0.95	0.1	0.15	100	0.1	60	335
8	0.85	0.9	0.05	0.1	50	0.05	40	333
9	0.85	0.85	0.15	0.05	80	0.15	50	329
10	0.95	0.95	0.05	0.05	80	0.1	40	337
11	0.95	0.9	0.15	0.15	100	0.05	50	363
12	0.95	0.85	0.1	0.1	50	0.15	60	330
13	0.9	0.95	0.1	0.05	50	0.05	50	335
14	0.9	0.9	0.05	0.15	80	0.15	60	331
15	0.9	0.85	0.15	0.1	100	0.1	40	347
16	0.85	0.95	0.05	0.1	100	0.15	60	336
17	0.85	0.9	0.15	0.05	50	0.1	40	330

排序方法	组批方法
排序方法	FFLPT	FFERT	MBS	IVTRP	BRFFERT
LPT	1^[16]	2^[16]	4	5
SPT	3			6
AR					8^[16]
ACO				7
GA	9^[17]