Associate Professor Tsung-Che Chiang
Department of Computer Science and Information Engineering
National Taiwan Normal University

Tel: +886-2-77346692    Fax: +886-2-29322378    Email
¡@
¡@

Tsung-Che Chiang, Enhancing rule-based scheduling in wafer fabrication facilities by evolutionary algorithms: Review and opportunity, Computers & Industrial Engineering, vol. 64, no. 1, pp. 524 - 535, 2013.

Full text: Official version; Request a copy

Abstract

Scheduling is a critical and challenging task in manufacturing systems, especially in large-scale complex systems like wafer fabrication facilities. Although evolutionary algorithms (EAs) have demonstrated many successful applications in the field of manufacturing scheduling, there are very few studies on scheduling of wafer fabs using EAs. Dispatching rules are one of the most common techniques for fab scheduling. In this paper, we present six ways of applying EAs for enhancing the rule-based scheduling system. We provide potential EA-based solutions and review relevant literature. Many of the mentioned viewpoints can serve as new research topics for both researchers in the fields of scheduling and evolutionary computation (EC). Several general EC techniques including multiobjective optimization, expensive optimization, and parallelization are also introduced and shown to be helpful to fab scheduling.

Summary

Topic Research opportunities References
Rule construction * Improvement of algorithm design (e.g. expansion of the terminal set in GP)
* Simplification and interpretation of generated rules		 Pickardt et al. (2010)

Rule parameter optimization

 * Performance test in fab environments Stockton et al. (2008)
Chiang and Fu (2004)
Rule selection

* Use of EA for state-dependent or time-dependent rule selection
* Hybrid representation for simultaneous rule selection, state construction, and parameter optimization
* Hyperheuristics techniques
* Effects of candidate rules

Liu and Wu (2004)
Sha and Liu (2003)
Chen et al.(2001)
Rule combination

* Use of EA for hierarchical combination
* Hybrid representation for simultaneous rule selection and rule combination
* Effects of candidate rules

 Chiang, Shen, and Fu (2008)
Model simplification

* Use of EA for model simplification
* Definition of objective function (e.g. model error)
* Use of the simplified model in the previous four EA-based solutions

 Chiang (2010)
Cooperation with rules * Definition of objective function (local or global)
* Prediction and consideration of incoming lots
* Performance test in fab environments		 Monch et al. (2007)
General * Multiobjective optimization
* Expensive optimization
* Parallel and distributed computing

Defersha and Chen (2010)
Senties et al. (2010)
Zhang et al. (2009)

References (For the complete list of references, please refer to the paper.)

Rule construction >>

Geiger, C. D., Uzsoy, R., & Aytug, H. (2006). Rapid modeling and discovery of priority dispatching rules: an autonomous learning approach. Journal of Scheduling, 9(1), 7¡V34.

Geiger, C. D., & Uzsoy, R. (2008). Learning effective dispatching rules for batch processor scheduling.  International Journal of Production Research, 46(6), 1431¡V1454.

Pickardt, C., Branke, J., Hildebrandt, T., Heger, J., Scholz-Reiter, B. (2010). Generating dispatching rules for semiconductor manufacturing to minimize weighted tardiness. Proceedings of the 2010 Winter Simulation Conference, 2504¡V2515.

Tay, J. C., & Ho, N. B. (2008). Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Computers & Industrial Engineering, 54(3), 453¡V473.

Nguyen, S., Zhang, M., Johnston, M., and Tan, K.C. (2013). Learning iterative dispatching rules for job shop scheduling with genetic programming, International Journal of Advanced Manufacturing Technology, DOI 10.1007/s00170-013-4756-9.

Rule parameter optimization >>

Chiang, T. C., & Fu, L. C. (2004). Parameter tuning of production scheduling rules by an ant system-embedded genetic algorithm. Proceedings of IEEE International Conference on Robotics, Automation, and Mechatronics, 1089¡V1094.

Stockton, D. J., Khalil, R., & Ardon-Finch, J. (2008). Control point policy optimization using genetic algorithms. International Journal of Production Research, 46(10), 2785¡V2795.

Rule selection >>

Herrmann, J. W., Lee, C. Y., & Hinchman, J.  (1995). Global job shop scheduling with a genetic algorithm. Production & Operations Management, 4(1), 30¡V45.

Chen, J. H., Fu, L. C., Lin, M. H., & Huang, A. C. (2001). Petri-net and GA-based approach to modeling, scheduling, and performance evaluation for wafer fabrication. IEEE Transactions on Robotics and Automation, 17(5), 619¡V636.

Sha, D. Y., & Liu, C. Y.  (2003). A simulated annealing algorithm for integration of shop floor control strategies in semiconductor wafer fabrication. International Journal of Advanced Manufacturing Technology, 22(1-2), 75¡V88.

Liu, M., & Wu, C. (2004). Genetic algorithm using sequence rule chain for multi-objective optimization in re-entrant micro-electronic production line. Robotics and Computer-Integrated Manufacturing, 20(3), 225¡V236.

Song, D. P., Hicks, C., & Earl, C. F. (2006). An ordinal optimization based evolution strategy to schedule complex make-to-order products. International Journal of Production Research, 44(22), 4877¡V4895.

Yang, T., Kuo, Y., & Cho, C. (2007). A genetic algorithms simulation approach for the multi-attribute combinatorial dispatching decision problem. European Journal of Operational Research, 176(3), 1859¡V1873.

Kapanoglu, M. & Alikalfa M. (2011). Learning IF¡VTHEN priority rules for dynamic job shops using genetic algorithms, Robotics & Computer-Integrated Manufacturing, 27(1), 47¡V55.

Korytkowski, P., Wiśniewski, T., Rymaszewski S. (2013). An evolutionary simulation-based optimization approach for dispatching scheduling, Simulation Modelling Practice and Theory, 35, 69¡V85.

Rule combination >>

Dorndorf, U., & Pesch, E. (1995). Evolution based learning in a job shop scheduling environment. Computers & Operations Research, 22(1), 25¡V40.

Chiang, T. C., Huang, A. C., & Fu, L. C. (2006). Modeling, scheduling, and performance evaluation for wafer fabrication: a queueing colored Petri-net and GA-based approach. IEEE Transactions on Automation Science and Engineering, 3(3), 330¡V337.

Chien, C. F. & Chen, C. H. (2007b). Using genetic algorithms (GA) and a coloured timed Petri net (CTPN) for modeling the optimization-based schedule generator of a generic production scheduling system. International Journal of Production Research, 45(8), 1763¡V1789.

Chiang, T. C., Shen, Y. S., & Fu, L. C. (2008). A new paradigm for rule-based scheduling in the wafer probe center. International Journal of Production Research, 46(15), 4111¡V4133.

Zhang, H., Jiang, Z., & Guo, C. (2009). Simulation-based optimization of dispatching rules for semiconductor wafer fabrication system scheduling by the response surface methodology. International Journal of Advanced Manufacturing Technology, 41(1-2), 110¡V121.

Zhang, H., Jiang, Z., & Guo, C. (2009). An optimized dynamic bottleneck dispatching policy for semiconductor wafer fabrication. International Journal of Production Research, 47(12), 3333¡V3343.

Vázquez-Rodríguez, J. A., & Petrovic, S. (2010). A new dispatching rule based genetic algorithm for the multi-objective job shop problem. Journal of Heuristics, 16(6), 771¡V793.

Model simplification >>

Kim, Y. D., Shim, S. O., Choi, B., & Hwang, H. (2003). Simplification methods for accelerating simulation-based real-time scheduling in a semiconductor wafer fabrication facility. IEEE Transactions on Semiconductor Manufacturing, 16(2), 290¡V298.

Piplani, R., & Puah, S. A. (2004). Simplification strategies for simulation models of semiconductor facilities. Journal of Manufacturing Technology Management, 15(7), 618¡V625.

Upasani, A. A., Uzsoy, R., & Sourirajan, K. (2006). A problem reduction approach for scheduling semiconductor wafer fabrication facilities. IEEE Transactions on Semiconductor Manufacturing, 19(2),216¡V225.

Chiang, T. C. (2010). Model simplification for accelerating simulation-based evaluation of dispatching rules in wafer fabrication facilities. Proceedings of the 11th International Conference on Control, Automation, Robotics, and Vision, 2005¡V2011.

Cooperation with rules >>

Mönch, L., Schabacker, R., Pabst, D., & Fowler, J. W. (2007). Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops. European Journal of Operational Research, 177(3), 2100¡V2118.

Multi-function (hybrid) >>

Pickardt, C. W., Hildbrandt, T., Branke, J. Heger, J., and Scholz-Reiter, B. (2013). Evolutionary generation of dispatching  rule sets for complex dynamic scheduling problems. International Journal of Production Economics. dio:101016/j.ijpe.2012.10.016. [rule construction, machine-dependent rule selection]

Nguyen, S., Zhang, M., Johnston, M., and Tan, K. C. (2013). A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem. IEEE Transactions on Evolutionary Computation, 17(5), 621 - 639. [rule construction, state-dependent rule selection, rule parameter optimization]

For the complete list of references, please refer to the paper. If you think that your research falls in any one of the above categories, please email to me and I am pleased to update the list on this web page.
¡@ ¡@

¡@
¡@

¡@

¡@