Study On Algorithms Of Batch Processing Machines Scheduling Problems In Semiconductor Final Testing

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.