Abstract
This thesis addresses a production scheduling problem for multi-head test machine in semiconductor back-end manufacturing. Multi-head test machine consists of CPU(central process unit) and testing handler. A CPU is often connected with many testing handlers to reduce idle time of CPU in an actual testing facility. This study formulates the scheduling problem as a parallel machine sequencing problem with the objective of minimizing makespan ( ). The difference between a traditional parallel machine problem and test machine scheduling is the processing time. In a test machine scheduling problem, the processing time depends on the lot combination on testing heads, which increases the complex of this problem. Hence, we propose an amendable searching algorithm to solve this scheduling problem. Our searching algorithms have two phases : In the first phase, Gannt-chart heuristic is developed to generate an initial solution in a short computation time. In the second phase, tabu search, simulated annealing and genetic algorithm procedure are used with embedded heuristics, which are developed based on the character of the problem. Extensive computational experiments evaluating the performance of all algorithms are reported.