Optimizing The Resource Constrained Scheduling Problems In Semiconductor Final Testing

The performance checking of packaged integrated circuits is named semiconductor final testing. Nowadays, the cost of final testing has arisen to thirty percent of the total cost in integrated circuits manufacturing due to the increase of integration and complexity. The semiconductor final testing has become a bottleneck in the development of China’s semiconductor industry and attracted the attentions of researchers in management science, industrial engineering and automation.Semiconductor manufacture scheduling is an important combinatorial optimization problem characterized by large-scale, reentrant, mixed processing mode and multi-resource constraints. For a long time, researchers considered resource constraint only as machine capacity constraint, assuming other resources were infinite. Moreover, job sequence dependent setup time was rarely concerned in researches on semiconductor manufacture scheduling. Therefore, hardly can every resolutions applied to the semiconductor facility. In this thesis, the scheduling problem encountered in semiconductor final testing operation was researched, considering the multiple resources constraints and job sequence dependent setup times. We simplified the problem as a flexible flowshop scheduling problem with two stages, test and burn-in, to process and used a divide-and-conquer strategy to solve it. At first two stages were optimized separately, then they were integrated to a two-stage flexible Flowshop scheduling problem and a combinatorial particle swarm optimization algorithm was designed to solve it.The scheduling problem on test stage was represented by an identical parallel machine scheduling problem with multiple resources constraint and job sequence dependent setup times. A mixed integer program model and two algorithms, including a Genetic Algorithm and a Variable Neighborhood Search algorithm, were proposed for this problem.We described the scheduling problem on burn-in stage as a single machine scheduling problem with job sequence dependent setup times and used commercial optimization software and six different algorithms to solve it. Experimental results show that the heuristic performed much better than other algorithms on solving large-scale problems.As last, we designed a combinatorial particle swarm optimization algorithm to solve the two-stage flexible flowshop scheduling problem. In this algorithm, particle swarm optimization was used to find global solution and variable neighborhood search was used to perform local optimization, making the algorithm have a good balance between exploration and exploitation. Moreover, the proposed algorithm can easily expanded to the multi-stage scheduling problems with mere change on local search and it is convenient to applied the parallel computing technology on the algorithm, due to the independence of local search operations.