Scheduling identical wafer sorting parallel machines with sequence-dependent setup times using an iterated greedy heuristic

Abstract

Wafer sorting is one of the most critical processes involved in semiconductor device fabrication. This study addresses the wafer sorting scheduling problem (WSSP), with minimisation of total setup time as the primary criterion and minimisation of the number of testers used as the secondary criterion. In view of the strongly NP-hard nature of this problem, a simple and effective iterated greedy heuristic is presented. The performance of the proposed heuristic is empirically evaluated by 480 simulation instances based on the characteristics of a real wafer testing shop-floor. The experimental results show that the proposed heuristic is effective and efficient as compared to the state-of-art algorithms developed for the same problem. It is believed that this study has developed an approach that is easy to comprehend and satisfies the practical needs of wafer sorting.

Keywords:

• wafer sorting
• identical parallel machine scheduling
• sequence dependent setup times
• iterated greedy
• simulated annealing
• meta-heuristic

Acknowledgements

The authors are most grateful to the Editor and anonymous referees for valuable comments, which enhanced the theoretical presentation of the paper. This research was partially supported by the National Science Council of the Republic of China (Taiwan) under Contract No. NSC 99-2628-E-027-003.