Meta-heuristic algorithms for wafer sorting scheduling problems

Abstract

Wafer sorting is usually regarded as the most critical stage in the whole wafer probing process. This paper discusses the wafer sorting scheduling problem (WSSP) with total setup time minimization as the primary criterion and the minimization of the number of machines used as the secondary criterion. Although the need to consider multiple criteria in real-world WSSPs is widely recognized, the present study is the first attempt to investigate this argument with setups consideration. In view of the strongly NP-hard nature of this problem, three meta-heuristic algorithms—an ant colony system algorithm, a Genetic algorithm, and a Tabu search algorithm are proposed. The proposed meta-heuristics are empirically evaluated by 480 simulation instances based on the characteristics of a real wafer testing shop-floor and found to be very effective in terms of finding good quality solutions.

Keywords:

• wafer sorting scheduling problem
• meta-heuristic
• parallel machine scheduling problem

Acknowledgements

This research was partially supported by the National Science Council of the Republic of China, Taiwan, under Contract Nos. NSC 97-2221-E-211-016 and NSC 97-2410-H-182-020-MY2. The authors are grateful to the anonymous referees for their useful and constructive comments and suggestions.