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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chen TR, Chang TS, Chen CW and Kao J (1995). Scheduling for IC sort and test with preemptiveness via Lagrangian relaxation . IEEE T Syst Man Cy 25: 1249–1256.
Chiang TC, Shen YS and Fu LC (2008). A new paradigm for rule-based scheduling in the wafer probe centre . Int J Prod Res 46: 4111–4133.
Christian B (2005). Beam-ACO—Hybridizing ant colony optimization with beam search: An application to open shop scheduling . Comput Opns Res 32: 1565–1591.
Clark G and Wright J (1964). Scheduling of vehicles from a central depot to a number of delivery points . Opns Res 12: 568–581.
Dorigo M and Gambardella LM (1997). Ant colony system: A cooperative learning approach to the travelling salesman problem . IEEE T Evolut Comput 1: 53–66.
Dorigo M, Di Caro G and Gambardella LM (1999). Ant algorithms for discrete optimization . Artif Life 5: 137–172.
Ellis KP, Lu Y and Bish EK (2004). Scheduling of wafer test processes in semiconductor manufacturing . Int J Prod Res 42: 215–242.
Gagné C, Price WL and Gravel M (2002). Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times . J Opl Res Soc 53: 895–906.
Glover F (1989). Tabu search-Part I . ORSA J on Comput 1: 190–206.
Glover F (1990). Tabu search-Part II . ORSA J on Comput 2: 4–32.
Glover F and Laguna M (1997). Tabu Search . Kluwer Academic Publisher: Dordrecht.
Goldberg DE (1989). Genetic Algorithms in Search, Optimization, and Machine Learning . Addison-Wesley Publishing Company: Massachusetts.
Grabowski J and Wodecki M (2004). A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion . Comput Opns Res 10: 281–284.
Holland JH (1975). Adaptation in Natural and Artificial Systems . University of Michigan Press: Ann Arbor.
Lee CY, Lee ZJ, Lin SW and Ying KC (2008). An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem. Appl Intell, Published online (DOI: 10.1007/s10489-008-0136-9).
Lin JT, Wang FK and Lee WT (2004). Capacity-constrained scheduling for a logic IC final test facility . Int J Prod Res 42: 79–99.
Ovacik IM and Uzsoy R (1996). Decomposition methods for scheduling semiconductor testing facilities . Int J Flex Manuf Syst 8: 357–387.
Pearn WL, Chung SH and Yang MH (2002a). The wafer probing scheduling problem (WPSP) . J Opl Res Soc 53: 864–874.
Pearn WL, Chung SH and Yang MH (2002b). Minimizing the total machine workload for the wafer probing scheduling problem (WPSP) . IIE Trans 34: 211–220.
Pearn WL, Chung SH and Yang MH (2002c). A case study on the wafer probing scheduling problem . Prod Plan Control 13: 66–75.
Pearn WL, Chung SH, Yang MH and Chen YH (2004). Algorithms for the wafer probing scheduling problem with sequence-dependent set-up time and due date restrictions . J Opl Res Soc 55: 1194–1207.
Pearn WL, Chung SH, Yang MH and Shiao KP (2008). Solution strategies for multi-stage wafer probing scheduling problem with reentry . J Opl Res Soc 59: 637–651.
Pinedo M (2008). Scheduling, Theory, Algorithms, and Systems, 3rd edn. Springer Science+Business Media, LLC: New York.
Rajendran C and Ziegler H (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs . Eur J Oper Res 155: 426–438.
Syswerda G (1989). Uniform crossover in genetic algorithms . In: Schaffer J (ed). Proceedings the Third International Conference on Genetic Algorithms. Morgan Kaufmann Publishers: San Mateo, CA, pp. 2–9.
Ullman JD (1975). NP-complete scheduling problem . J Comput Syst Sci 10: 384–393.
Uzsoy R, Lee CY and Martin-Vega LA (1992). A review of production planning and scheduling models in the semiconductor industry part I: System characteristics, performance evaluation and production planning . IIE Trans 24: 47–58.
Yang J and Chang TS (1998). Multiobjective scheduling for IC sort and test with a simulation test bed . IEEE Trans Semicond Manuf 11: 304–315.
Ying KC and Liao CJ (2003). An ant colony system approach for scheduling problems . Prod Plan Control 14: 68–75.
Ying KC and Liao CJ (2004). An ant colony system for permutation flow-shop sequencing . Comput Opns Res 31: 791–801.
Ying KC and Lin SW (2006). Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach . Int J Prod Res 44: 3161–3177.
Ying KC and Lin SW (2007). Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems . Int J Adv Manuf Tech 33: 793–802.
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.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lin, SW., Lee, ZJ., Ying, KC. et al. Meta-heuristic algorithms for wafer sorting scheduling problems. J Oper Res Soc 62, 165–174 (2011). https://doi.org/10.1057/jors.2009.182
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2009.182