Online Rescheduling in Semiconductor Manufacturing
Masao Sugi*, Mingang Cheng**, Masashi Yamamoto***, Hiroki Ito***, Kazuyoshi Inoue***, and Jun Ota*
*Research into Artifacts, Center for Engineering (RACE), The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
**Wuxi Paradise Software Co., Ltd., No.2, West Binjiang Road, Jiangyin City, Jiangsu Province, China
**NS Solutions Corporation, 3-1 Minatomirai 3-chome, Nishi-ku, Yokohama-shi, Kanagawa 220-8401, Japan
Semiconductor manufacturing rescheduling problems are difficult to solve in real time due to numerous disturbances. We focus on maintaining the existing schedule and propose online semiconductor manufacturing rescheduling. To handle temporary disturbances and obtain a new feasible schedule, our proposal revises the given schedule based on affected operation rescheduling with operation sorting (sorting-AOR) based on schedule stability. To reduce deadline violations, we propose improving schedules two or more days ahead based on a fast local search algorithm for semicritical paths. In problems with 200,000 processes, this handles disturbances and gets new feasible schedules and better revised schedules in less than 1 minute. This is more effective than conventional dispatching-rule-based approaches, some of which have been applied in different facilities because it provides higher schedule stability and fewer deadline violations.
-  H. Toba, “Segment-based approach for real-time reactive rescheduling for automatic manufacturing control,” IEEE Transactions on Semiconductor Manufacturing, Vol.13, No.3, pp. 264-272, 2000.
-  S. D. Wu, R. H. Storer, and P.-C. Chang, “One-machine rescheduling heuristics with efficiency and stability as criteria,” Computers & Operations Research, Vol.20, pp. 1-14, 1993.
-  A. K. Gupta and A. I. Sivakumar, “Job shop scheduling techniques in semiconductor manufacturing,” International Journal of Advanced Manufacturing Technology, Vol.27, Nos.11-12, pp. 1163-1169, 2004.
-  C. S. Sung and Y. I. Choung, “Minimizing makespan on a single burn-in oven in semiconductor manufacturing,” European Journal of Operational Research, Vol.120, pp. 559-574, 2000.
-  P. B. Luh and D. J. Hoitomt, “Scheduling of manufacturing systems using the Lagrangian relaxation technique,” IEEE Transactions on Semiconductor Manufacturing, Vol.38, No.7, pp. 1066-1079, 1993.
-  S. Cavalieri, F. Crisafulli, and O. Mirabella, “A genetic algorithm for job-shop scheduling in a semiconductor manufacturing system,” IEEE Transaction on Engineering Management, Vol.41, No.2, pp. 957-961, 1999.
-  S. J. Yim and D. Y. Lee, “Scheduling cluster tools in wafer fabrication using candidate list and simulated annealing,” Journal of Intelligent Manufacturing, Vol.10, No.6, pp. 531-540, 1999.
-  R. M. Dabbas and J. W. Fowler, “A new scheduling approach using combined dispatching criteria in wafer fabs,” IEEE Transactions on Semiconductors Manufacturing, Vol.16, No.3, pp. 501-510, 2003.
-  M. Manfred and K. S. Alexander, “Comparison of dispatching rules for semiconductor manufacturing using large facility models,” Proceedings of the 1999 Winter Simulation Conference, pp. 709-713, 1999.
-  M. D. Johnston, “Reconciling high-speed scheduling with dispatching in wafer fabs,” IEEE International Semiconductor Manufacturing Symposium, pp. 107-110, 2001.
-  Y. D. Kim, J. U. Kim, S. K. Lim, and H. B. Jun, “Due-date based scheduling and control policies in a multi-product semiconductor wafer fabrication facility,” IEEE Transactions on Semiconductor Manufacturing, Vol.11, No.1, pp. 155-164, 1998.
-  Y. D. Kim, S. O. Shim, B. Choi, and H. Hwang, “Simplification methods for accelerating simulation-based real-time scheduling in a semiconductor wafer fabrication facility,” IEEE Transactions on Semiconductor Manufacturing, Vol.16, No.2, pp. 290-298, 2003.
-  R. J. Abumaizar and J. A. Svestka, “Rescheduling job shops under random disruptions,” International Journal of Production Research, Vol.35, pp. 2065-2082, 1997.
-  S. Velusamy and S. R. Amritpal, “mAOR: A heuristic-based reactive repair mechanism for job shop schedules,” International Journal of Advanced Manufacturing Technology, Vol.22, pp. 669-680, 2003.
-  E. Szelke and G. Markus, “A learning reactive scheduler using CBR/L,” Computer Industry, Vol.33, No.1, pp. 31-46, 1997.
-  P. Brandimarte, M. Rigodanza, and L. Roero, “Conceptual modeling of an object oriented scheduling architecture based on the shifting bottleneck procedure,” IIE Transactions, Vol.32, No.10, pp. 921-929, 2000.
-  C. S. Chong and A. I. Sivakumar, “Simulation-based scheduling for dynamic discrete manufacturing,” Proceedings of the 2003 Winter Simulation Conference, pp. 1465-1473, 2003.
-  R. Hino, K. Izuhara, and T. Moriwaki, “Message exchange method for decentralized scheduling,” Proceedings of the 4th IEEE International Symposium on Assembly and Task Planning, pp. 244-249, 2001.
-  R. Hino and T. Moriwaki, “Decentralized job shop scheduling by recursive propagation method,” JSME International Journal Series C, Vol.45, No.2, pp. 551-557, 2002.
-  E. Nowicki and C. Smutnicki, “A fast taboo search algorithm for the job shop problem,” Management Science, Vol.42, No.6, pp. 797-813, 1996.
-  S. S. Panwalkar and W. Iskander, “A survey of scheduling rules,” Operations Research, Vol.25, pp. 45-61, 1977.