半导体最终测试阶段批处理机调度问题优化方法研究
|
摘要
在半导体制造企业中,最终测试流程占有的市场规模越来越大,占用的资金越来越密集,由于测试流程中表现出不确定性、可重入性以及批处理等特点,因此对半导体测试站的研究已成为近年来研究调度问题的热点。而批处理操作在整条测试流程中占据的操作时间最长,是测试过程中的瓶颈工序,所以,优化批处理机的调度问题在提高整条测试流程的调度效率上显得尤为重要。
批处理机的调度问题来解决的是工件分批和批调度两个关键问题。随着批处理机的调度问题变得极其复杂,且大多数被证明为NP难问题,依据传统的最优化方法和启发式方法已很难解决,而智能算法在解决复杂问题时表现突出,本文通过引入智能算法寻找批处理机调度问题的最优解或者较优解。本文首先给出了批处理机调度问题的描述方法,介绍两种常用的分批方法,以及目前对于解决该调度问题的优化算法；然后建立单批处理机调度问题的模型,引入提前和拖期(Earliness and Tardiness, E/T)目标函数,提倡工件提前或者拖期交货都不鼓励的思想,依据此问题建立模型,提出基于汉明距离的变邻域搜索算法(Variable Neighborhood Search based on Hamming Distance, HDVNS)的优化算法,通过仿真实验,与遗传算法(Genetic Algorithm, GA)比较,证明HDVNS具有很好的鲁棒性；其次针对平行式批处理机调度问题,根据工件的单位提前和拖期成本,提出两种基于约翰逊法则的初始解产生的方式,仿真实验结果表明,这两种初始解产生方式以其他方式相比,算法优化过程表现效果良好：根据工件在平行式批处理机进行处理时,是先分批还是先把工件分配到机器,提出两种策略,最后通过实验数据显示,两种策略表现效果相差不大,但是工件先分配到机器上的方式在多数算例中,算法的平均运行时间要稍短一些。最后是对本论文的研究内容进行总结和展望。
In most semiconductor manufacturing companies, the process of final testing occupies a larger market and more and more intensive capital, and also shows some characteristics that are the uncertainty, reentrancy and batch processing, so in recent years, the study of the semiconductor testing station has become a hot on scheduling problems. Generally speaking, the batch processing operation occupies the longest time compared with other operations, so it is the bottleneck operation in final testing process. Therefore, the optimization on the batch processing machines to improve the scheduling efficiency of the whole final testing process plays an important part.
The scheduling problem of batch processing machines is to solve two key stages that are the batching rule and the batch scheduling strategy. As most scheduling problems of batch processing machines become more and more complex and are proved to be NP-hard problems, the traditional optimal methods and heuristics have been difficult to resolve, but intelligent algorithms perform outstandingly for solving these complex problems, this paper introduced the intelligent algorithms to find the optimal or nearly optimal solutions. Our paper firstly gives the description method of the batch processing machines scheduling problem, introduces two kinds' of common batching rules and the solution to the scheduling problem optimization algorithms for the scheduling problem of batch processing machines. Secondly, introduces the earliness and tardiness punishing for objective function into the single batching processing machine scheduling problem model, promoting that neither early or delay delivery are not encouraging thoughts. For this model, a variable neighborhood search algorithm based the Hamming distance (HDVNS) is proposed to finding the optimal solution; and through the simulation experiments compared with genetic algorithm (GA). it is demonstrated that HDVNS performs more robust. Thirdly, for the parallel batch processing machines scheduling problem, according to the unit earliness and tardiness costs, we put forward two ways of initial solution methods based on Johnson Method, and the simulation experiments result shows that these two ways perform well compared other methods; then we design two batches scheduling strategies, first batching jobs or assigning job to machines, and through the experiments result shows, two kinds of strategies performance little difference, but if we first assign jobs to the machines, the running time of the our algorithm is slightly shorter than that of first batching jobs. Finally, we summarize our studies and perpose future work in this paper.
批处理机的调度问题来解决的是工件分批和批调度两个关键问题。随着批处理机的调度问题变得极其复杂,且大多数被证明为NP难问题,依据传统的最优化方法和启发式方法已很难解决,而智能算法在解决复杂问题时表现突出,本文通过引入智能算法寻找批处理机调度问题的最优解或者较优解。本文首先给出了批处理机调度问题的描述方法,介绍两种常用的分批方法,以及目前对于解决该调度问题的优化算法；然后建立单批处理机调度问题的模型,引入提前和拖期(Earliness and Tardiness, E/T)目标函数,提倡工件提前或者拖期交货都不鼓励的思想,依据此问题建立模型,提出基于汉明距离的变邻域搜索算法(Variable Neighborhood Search based on Hamming Distance, HDVNS)的优化算法,通过仿真实验,与遗传算法(Genetic Algorithm, GA)比较,证明HDVNS具有很好的鲁棒性；其次针对平行式批处理机调度问题,根据工件的单位提前和拖期成本,提出两种基于约翰逊法则的初始解产生的方式,仿真实验结果表明,这两种初始解产生方式以其他方式相比,算法优化过程表现效果良好：根据工件在平行式批处理机进行处理时,是先分批还是先把工件分配到机器,提出两种策略,最后通过实验数据显示,两种策略表现效果相差不大,但是工件先分配到机器上的方式在多数算例中,算法的平均运行时间要稍短一些。最后是对本论文的研究内容进行总结和展望。
In most semiconductor manufacturing companies, the process of final testing occupies a larger market and more and more intensive capital, and also shows some characteristics that are the uncertainty, reentrancy and batch processing, so in recent years, the study of the semiconductor testing station has become a hot on scheduling problems. Generally speaking, the batch processing operation occupies the longest time compared with other operations, so it is the bottleneck operation in final testing process. Therefore, the optimization on the batch processing machines to improve the scheduling efficiency of the whole final testing process plays an important part.
The scheduling problem of batch processing machines is to solve two key stages that are the batching rule and the batch scheduling strategy. As most scheduling problems of batch processing machines become more and more complex and are proved to be NP-hard problems, the traditional optimal methods and heuristics have been difficult to resolve, but intelligent algorithms perform outstandingly for solving these complex problems, this paper introduced the intelligent algorithms to find the optimal or nearly optimal solutions. Our paper firstly gives the description method of the batch processing machines scheduling problem, introduces two kinds' of common batching rules and the solution to the scheduling problem optimization algorithms for the scheduling problem of batch processing machines. Secondly, introduces the earliness and tardiness punishing for objective function into the single batching processing machine scheduling problem model, promoting that neither early or delay delivery are not encouraging thoughts. For this model, a variable neighborhood search algorithm based the Hamming distance (HDVNS) is proposed to finding the optimal solution; and through the simulation experiments compared with genetic algorithm (GA). it is demonstrated that HDVNS performs more robust. Thirdly, for the parallel batch processing machines scheduling problem, according to the unit earliness and tardiness costs, we put forward two ways of initial solution methods based on Johnson Method, and the simulation experiments result shows that these two ways perform well compared other methods; then we design two batches scheduling strategies, first batching jobs or assigning job to machines, and through the experiments result shows, two kinds of strategies performance little difference, but if we first assign jobs to the machines, the running time of the our algorithm is slightly shorter than that of first batching jobs. Finally, we summarize our studies and perpose future work in this paper.
引文
[1]王凌.车间调度及其遗传算法.清华大学出版社(北京),2003年.
[2]杜先东.计算机仿真及其在后端制造中的应用.苏州大学硕士学位论文,2009年5月.
[3]张智聪,郑力.半导体测试调度研究.现代管理,2008年1月,第33卷第1期.
[4]Pearn WL, Chung SH, et al. A case study on the multistage IC final testing scheduling problem with reentry. International Journal of Production Economics,2004,88:257-267.
[5]Kempf KG, Uzsoy R, Wang CS. Scheduling a single batch processing machine with secondary resourse constraints, Journal of Manufacturing Systems,1998, vol:17(1).
[6]王韬.半导体生产批处理调度的研究现状与对策.科技创新导刊,2009年9月,第27期.
[7]郭秀萍.多目标进化算法及其在制造系统中的应用研究.上海交通大学工学博士学位论文,2007年4月.
[8]吴超超,顾幸生.最优公共交货期单机提前/拖期调度和对应的批次送货.华东理工大学学报,2004年,第30卷第2期.
[9]Melouk, Damodaran, et al. Minimizing makespan for single batch processing machine with nonidentical job sizes using simulated annealing. International Journal of Production Economics.2004. vol:87.
[10]马建辉,牛海军.提前/拖期惩罚的单机批调度优化问题的研究.制造业自动化,2002年,第24卷第7期.
[11]赵玉芳,唐立新.极小化最大完工时间的单机连续性批调度问题.自动化学报,2006年,第32卷第5期.
[12]张玉忠,柏庆国,徐健腾.工件有尺寸且分两批到达的单机单机分批排序.运筹学学报,2006年,第10卷第4期.
[13]Eom DH. Shin HJ. et al. Scheduling jobs on parallel machines with sequence-dependent family set-up times. The Inernational Journal of Advanced Manufacturing Technology,2002, vol:19.
[14]Lee YH. Pinedo M. Scheduling jobs on parallel machines with sequence setup times. European Journal of Operational Research,1997, vol:100.
[15]Luh PB, Hoitomt DJ, et al. Schedule generation and reconfiguration for parallel machines. IEEE Transactions on Robotics and Automation.1990. vol:6(6).
[16]Alidaee B, Rosa D. Scheduling parallel machines to minimize total weighted and unweighted tardiness. Computers and Operations Research, 1997, vol:24.
[17]杜冰,陈华平,杨勃,李小林.聚类视角下的差异工件平行及调度问题.管理科学学报,2011年12月,第14卷第12期.
[18]杨振光,李曙光,王秀红.工件尺寸不同的并行机批调度问题.山东大学学报：自然科学版,2007年,第42卷第4期.
[19]Mason SJ, Fowler JW, et al. A modified shifting bottleback heuristic for minimizing total weighted tardiness in complex job shops. Journal of Scheduling, 2002, 5(3):247-262.
[20]唐立新,黄琳.调整时间与顺序相关的flowshop调度的精确算法.系统工程学报,2002年,第17卷第4期.
[21]程八一,胡吴旋.差异作业批调度的流水车间问题及近似算法.系统工程学报,2011年6月,第26卷第3期.
[22]Liao LM, Huang CJ. Tabu search heuristic for two-machine flowshop with batch processing machines. Computers and Industrial Engineering, 2011, vol: 60.
[23]Graham RL, Lawler EL. et al. Optimization and approximation in deterministic sequencing and scheduling:A survey, Annals of Discrete Mathematics,1979, vol:5.
[24]Chou FD. A joint GA+DP approach for single burn-in oven scheduling problems with makespan criterion. International Journal of Advanced Manufacturing Technology, 2007, vol: 35.
[25]Wang HM, Chou FD. Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics. Expert Systems with Applications,2010. vol:37.
[26]Uzsoy R. A single batch processing machine with nonidentical job sizes. International Journal of Production Research. 1994. vol:32.
[27]Lee CY, Uzsoy R. Martin-Vega LA. Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 1992, vol:40.
[28]Chandru V. Lee CY. Uzsoy R. Minimizing total completion time on batch processing machines. International Journal of Production Research, 1993, vol:31.
[29]Hochbaum DS. Landy D. Scheduling semiconductor burn-in operations to minimize total flow time. Operations Research, 1997. vol:45.
[30]DuPont L. Ghazvin FJ. A branch and bound algorithm for minimizing mean flow time on a single batch processing machine. International Journal of Industrial Engineering. 1997. vol:4.
[31]冯光大,唐立新.单台批处理机总加权完成时间最小化的启发式算法.《控制与决策》,2006年11月,第21卷第11期。
[32]林烈青,郑睿.优化批处理机排序方案的启发式算法研究.《制造业自动化》,2011年,第14期.
[33]Sung CS, Chong YI, Fowler JW. Heuristic algorithm for minimizing earliness-tardiness on a single burn-in oven in semiconductor manufacturing. Processing of 2002 international conference of modeling and analysis for semiconductor manufacturing (MASM), Tempe, Arizona, 2002.
[34]Wang CS, Uzsoy R. A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers and Operations Research, 2002, vol:29.
[35]Monch L, Schabacker R. Genetic algorithm-based subproblem solution procedures for a modified shiffing bottleneck heuristic for complex job shops. European Journal of Operational Research, 2007, vol:177.
[36]Balasubramahian H, Monch L, et al. Genetic algorithm based scheduling of parallel batch processing machines with incompatible job families to minimize total weighted tardiness. International Journal of Production Research, 2004, vol:42(8).
[37]Choung YI, Monch L. A genetic algorithm for minimizing earliness and tardiness on a burn-in oven. Proceeding of 10th annual industrial engineering research conference, Portland, Oregon, USA, 2003.
[38]王克喜,单汩源.基于遗传算法的流水车间调度求解方法.系统工程,2008年10月,第26卷第10期.
[39]Gao J. Sun LY. Gen M. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers and Operations Research, 2008, vol: 35.
[40]Monch L. Unbehaum R. Decomposition heuristics for minimizing earliness-tardiness on parallel burn-in ovens with a common due date. Computers and Operations Research, 2007. vol:34.
[41]Monch L. Balasubramahian H. et al. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Computers and Operations Research.2005, vol: 32.
[42]王凯,杜冰等.不同尺寸工件批调度问题的自适应蚁群退火算法.计算机应用研究,2008年8月,第28卷第8期.
[43]杜宗宗,刘国栋.基于混合遗传模拟退火算法求解TSP问题.计算机工程与应用,2010年,第46卷第29期.
[44]Mladenovic N, Hansen P. Variable neighborhood search. Computer and Operation Research, 1997, vol:24(11).
[45]董红宇,黄敏.变邻域搜索算法综述.控制工程,2009年7月,第16卷增刊.
[46]Behnamian J, Zandieh M, Fatemi Ghomi SMT. Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm. Expert Systems with Applications,2009, vol:36.
[47]Blazewicz J, Pesch E, Stema M, et al. Metaheuristic approaches for the two-machine flow-shop problem with weighted latework criterion and common due date. Computers and Operations Research, 2008, vol:35(2).
[48]Zobolas GI, Tarantilis CD, Ioannou G. Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Computers and Operations Research, 2009, vol:36(4).
[49]Driessel R, Monch L. Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times. Computers and Industrial Engineering, 2010, in press.
[50]Chou FD, Chang PC, Wang HM. A hybrid genetic algorithm to minimize makespan for the single batch machine by dynamic scheduling problem. International Journal and Advanced Manufacture Technology. DOI:10.1007/s00170-005-0194-7.
[51]程八一,陈华平,王拴狮.单机不同尺寸工件批调度问题的优化算法.系统管理学报,2008年,第17卷第3期.
[52]Drazic M. Lavor C, Maculan N. et al. A continuous variable neighborhood search heuristic for finding the three-dimensional structure of a molecule. European Journal of Operation Research, 2008, vol:185(3).
[53]Malve S, Uzsoy R. A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers and Operations Research, 2007, vol:34.
[54]Chung SH. Tai YT. Pearn WL. Minimizing makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes. International Journal of Production Research, 2008. Doi:10.1080/00207540802010807.
[2]杜先东.计算机仿真及其在后端制造中的应用.苏州大学硕士学位论文,2009年5月.
[3]张智聪,郑力.半导体测试调度研究.现代管理,2008年1月,第33卷第1期.
[4]Pearn WL, Chung SH, et al. A case study on the multistage IC final testing scheduling problem with reentry. International Journal of Production Economics,2004,88:257-267.
[5]Kempf KG, Uzsoy R, Wang CS. Scheduling a single batch processing machine with secondary resourse constraints, Journal of Manufacturing Systems,1998, vol:17(1).
[6]王韬.半导体生产批处理调度的研究现状与对策.科技创新导刊,2009年9月,第27期.
[7]郭秀萍.多目标进化算法及其在制造系统中的应用研究.上海交通大学工学博士学位论文,2007年4月.
[8]吴超超,顾幸生.最优公共交货期单机提前/拖期调度和对应的批次送货.华东理工大学学报,2004年,第30卷第2期.
[9]Melouk, Damodaran, et al. Minimizing makespan for single batch processing machine with nonidentical job sizes using simulated annealing. International Journal of Production Economics.2004. vol:87.
[10]马建辉,牛海军.提前/拖期惩罚的单机批调度优化问题的研究.制造业自动化,2002年,第24卷第7期.
[11]赵玉芳,唐立新.极小化最大完工时间的单机连续性批调度问题.自动化学报,2006年,第32卷第5期.
[12]张玉忠,柏庆国,徐健腾.工件有尺寸且分两批到达的单机单机分批排序.运筹学学报,2006年,第10卷第4期.
[13]Eom DH. Shin HJ. et al. Scheduling jobs on parallel machines with sequence-dependent family set-up times. The Inernational Journal of Advanced Manufacturing Technology,2002, vol:19.
[14]Lee YH. Pinedo M. Scheduling jobs on parallel machines with sequence setup times. European Journal of Operational Research,1997, vol:100.
[15]Luh PB, Hoitomt DJ, et al. Schedule generation and reconfiguration for parallel machines. IEEE Transactions on Robotics and Automation.1990. vol:6(6).
[16]Alidaee B, Rosa D. Scheduling parallel machines to minimize total weighted and unweighted tardiness. Computers and Operations Research, 1997, vol:24.
[17]杜冰,陈华平,杨勃,李小林.聚类视角下的差异工件平行及调度问题.管理科学学报,2011年12月,第14卷第12期.
[18]杨振光,李曙光,王秀红.工件尺寸不同的并行机批调度问题.山东大学学报：自然科学版,2007年,第42卷第4期.
[19]Mason SJ, Fowler JW, et al. A modified shifting bottleback heuristic for minimizing total weighted tardiness in complex job shops. Journal of Scheduling, 2002, 5(3):247-262.
[20]唐立新,黄琳.调整时间与顺序相关的flowshop调度的精确算法.系统工程学报,2002年,第17卷第4期.
[21]程八一,胡吴旋.差异作业批调度的流水车间问题及近似算法.系统工程学报,2011年6月,第26卷第3期.
[22]Liao LM, Huang CJ. Tabu search heuristic for two-machine flowshop with batch processing machines. Computers and Industrial Engineering, 2011, vol: 60.
[23]Graham RL, Lawler EL. et al. Optimization and approximation in deterministic sequencing and scheduling:A survey, Annals of Discrete Mathematics,1979, vol:5.
[24]Chou FD. A joint GA+DP approach for single burn-in oven scheduling problems with makespan criterion. International Journal of Advanced Manufacturing Technology, 2007, vol: 35.
[25]Wang HM, Chou FD. Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics. Expert Systems with Applications,2010. vol:37.
[26]Uzsoy R. A single batch processing machine with nonidentical job sizes. International Journal of Production Research. 1994. vol:32.
[27]Lee CY, Uzsoy R. Martin-Vega LA. Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research, 1992, vol:40.
[28]Chandru V. Lee CY. Uzsoy R. Minimizing total completion time on batch processing machines. International Journal of Production Research, 1993, vol:31.
[29]Hochbaum DS. Landy D. Scheduling semiconductor burn-in operations to minimize total flow time. Operations Research, 1997. vol:45.
[30]DuPont L. Ghazvin FJ. A branch and bound algorithm for minimizing mean flow time on a single batch processing machine. International Journal of Industrial Engineering. 1997. vol:4.
[31]冯光大,唐立新.单台批处理机总加权完成时间最小化的启发式算法.《控制与决策》,2006年11月,第21卷第11期。
[32]林烈青,郑睿.优化批处理机排序方案的启发式算法研究.《制造业自动化》,2011年,第14期.
[33]Sung CS, Chong YI, Fowler JW. Heuristic algorithm for minimizing earliness-tardiness on a single burn-in oven in semiconductor manufacturing. Processing of 2002 international conference of modeling and analysis for semiconductor manufacturing (MASM), Tempe, Arizona, 2002.
[34]Wang CS, Uzsoy R. A genetic algorithm to minimize maximum lateness on a batch processing machine. Computers and Operations Research, 2002, vol:29.
[35]Monch L, Schabacker R. Genetic algorithm-based subproblem solution procedures for a modified shiffing bottleneck heuristic for complex job shops. European Journal of Operational Research, 2007, vol:177.
[36]Balasubramahian H, Monch L, et al. Genetic algorithm based scheduling of parallel batch processing machines with incompatible job families to minimize total weighted tardiness. International Journal of Production Research, 2004, vol:42(8).
[37]Choung YI, Monch L. A genetic algorithm for minimizing earliness and tardiness on a burn-in oven. Proceeding of 10th annual industrial engineering research conference, Portland, Oregon, USA, 2003.
[38]王克喜,单汩源.基于遗传算法的流水车间调度求解方法.系统工程,2008年10月,第26卷第10期.
[39]Gao J. Sun LY. Gen M. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers and Operations Research, 2008, vol: 35.
[40]Monch L. Unbehaum R. Decomposition heuristics for minimizing earliness-tardiness on parallel burn-in ovens with a common due date. Computers and Operations Research, 2007. vol:34.
[41]Monch L. Balasubramahian H. et al. Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times. Computers and Operations Research.2005, vol: 32.
[42]王凯,杜冰等.不同尺寸工件批调度问题的自适应蚁群退火算法.计算机应用研究,2008年8月,第28卷第8期.
[43]杜宗宗,刘国栋.基于混合遗传模拟退火算法求解TSP问题.计算机工程与应用,2010年,第46卷第29期.
[44]Mladenovic N, Hansen P. Variable neighborhood search. Computer and Operation Research, 1997, vol:24(11).
[45]董红宇,黄敏.变邻域搜索算法综述.控制工程,2009年7月,第16卷增刊.
[46]Behnamian J, Zandieh M, Fatemi Ghomi SMT. Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm. Expert Systems with Applications,2009, vol:36.
[47]Blazewicz J, Pesch E, Stema M, et al. Metaheuristic approaches for the two-machine flow-shop problem with weighted latework criterion and common due date. Computers and Operations Research, 2008, vol:35(2).
[48]Zobolas GI, Tarantilis CD, Ioannou G. Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Computers and Operations Research, 2009, vol:36(4).
[49]Driessel R, Monch L. Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times. Computers and Industrial Engineering, 2010, in press.
[50]Chou FD, Chang PC, Wang HM. A hybrid genetic algorithm to minimize makespan for the single batch machine by dynamic scheduling problem. International Journal and Advanced Manufacture Technology. DOI:10.1007/s00170-005-0194-7.
[51]程八一,陈华平,王拴狮.单机不同尺寸工件批调度问题的优化算法.系统管理学报,2008年,第17卷第3期.
[52]Drazic M. Lavor C, Maculan N. et al. A continuous variable neighborhood search heuristic for finding the three-dimensional structure of a molecule. European Journal of Operation Research, 2008, vol:185(3).
[53]Malve S, Uzsoy R. A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers and Operations Research, 2007, vol:34.
[54]Chung SH. Tai YT. Pearn WL. Minimizing makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes. International Journal of Production Research, 2008. Doi:10.1080/00207540802010807.