Try and error-based scheduling algorithm for cluster tools of wafer fabrications with residency time constraints

Abstract

To improve the productivity of cluster tools in semiconductor fabrications, on the basis of stating scheduling problems, a try and error-based scheduling algorithm was proposed with residency time constraints and an objective of minimizing Makespan for the wafer jobs in cluster tools. Firstly, mathematical formulations of scheduling problems were presented by using assumptions and definitions of a scheduling domain. Resource conflicts were analyzed in the built scheduling model, and policies to solve resource conflicts were built. A scheduling algorithm was developed. Finally, the performances of the proposed algorithm were evaluated and compared with those of other methods by simulations. Experiment results indicate that the proposed algorithm is effective and practical in solving the scheduling problem of the cluster tools.

Keywords

cluster tools / residency constraints / scheduling model / algorithm / simulation experiments

References

[1] van ZantP.Microchip fabrication: A practical guide to semiconductor processing [M], 20045th Ed.New York, McGraw-Hill: 495-496

[2] YiJ.-g., DingS.-w., SongD.-z., ZhangM.-tao.. Steady-state throughput and scheduling analysis of multi-cluster tools: A decomposition approach [J]. IEEE Transactions on Automation Science and Engineering, 2008, 5(2): 321-336

[3] ZhouB.-h., PanQ.-z., WangS.-j., WuBin.. Modeling of a photolithography process in semiconductor wafer fabrication systems using extended hybrid Petri nets [J]. Journal of Central South University of Technology, 2007, 14(3): 393-398

[4] LEE T E. A review of scheduling theory and methods for semiconductor manufacturing cluster tools [C]// Proceedings of 2008 Winter Simulation Conference. Austin, America, 2008: 2127–2135.

[5] WU Nai-qi, CHU Cheng-bin, CHU Feng, ZHOU Meng-chu. Modeling and schedulability analysis of single-arm cluster tools with wafer residency time constraints using petri net [C]// Proceedings of 2008 IEEE International Conference on Networking, Sensing and Control. Sanya, China, 2008: 84–89.

[6] WuN.-q., ZhouM.-chu.. Analysis of wafer sojourn time in dual-arm cluster tools with residency time constraint and activity time variation [J]. IEEE Transactions on Semiconductor Manufacturing, 2010, 23(1): 53-64

[7] MORRISON J R. Regular flow line models for semiconductor cluster tools: A case of lot dependent process times [C]// Proceedings of the 5th Annual IEEE Conference on Automation Science and Engineering. Bangalore, India, 2009: 465–470.

[8] LeeT. E., ParkS. H.. An extended event graph with negative places and tokens for time window constraints [J]. IEEE Transactions on Automation Science and Engineering, 2005, 2(4): 319-331

[9] KimJ. H., LeeH. T., LeeH. Y., ParkD. B.. Schedulability analysis of time-constrained cluster tools with bounded time variation by an extended Petri net [J]. IEEE Transactions on Automation Science and Engineering, 2008, 5(3): 490-503

[10] ShinY. H., LeeT. E., KimJ. H., LeeH. Y.. Modeling and implementing a real-time scheduler for dual-armed cluster tools [J]. Computers in Industry, 2001, 45(1): 13-27

[11] LEE J H, LEE T E. An open scheduling architecture for cluster tools [C]// Proceedings of the 6th Annual IEEE Conference on Automation Science and Engineering. Toronto, Canada, 2010: 420–425.

[12] YinY.. An algorithm for hoist scheduling problems [J]. International Journal of Production Research, 1994, 32(3): 501-516

[13] ChauvetF., ProthJ. M., WardiY.. Scheduling no-wait production with time windows and flexible processing times [J]. IEEE Transactions on Robotics and Automation, 2001, 17(1): 60-69

[14] YoonH. J., LeeD. Y.. Online scheduling of integrated single-wafer processing tools with temporal constraints [J]. IEEE Transactions on Semiconductor Manufacturing, 2005, 18(3): 390-398

[15] TZENG J, LIU T, CHOU J. Applications of multi-objective evolutionary algorithms to cluster tool scheduling [C]// Proceedings of the First International Conference on Innovative Computing, Information and Control. Beijing, China, 2006: 531–534.

[16] LiX., ZhouB.-h., LuZ.-qiang.. Scheduling algorithm for cluster tools of wafer fabrication based on events-driven [J]. Journal of Shanghai Jiaotong University, 2009, 43(6): 898-901