A simulated annealing approach with probability matrix for semiconductor dynamic scheduling problem

摘要

The dynamic scheduling problem of semiconductor burn-in operations is studied in this paper. The burn-in oven is a batch-processing machine and the size of each job is independent of the oven’s capacity. The processing time for each batch is represented by the largest processing time of the jobs in a batch. The objective function of this problem is to minimize the total weighted completion time subject to deadline constraints. A mixed integer programming model is formulated to solve small size of problems optimally, and then a SA with a probability matrix integrated with a greedy heuristic is developed to solve the problem in practical sizes. The greedy heuristic has a backtrack procedure to ensure the obtained solutions can avoid the infeasible region and the solutions derived can be further applied as initial solutions to the proposed novel SA procedure. In the novel SA, the probability matrix is designed as a probabilistic neighbor-generation procedure to guide the searching directions. Computational experiments indicated the novel SA could effectively and efficiently obtain optimal solutions for small size of problems and provide high-quality solutions efficiently for large size of problems.