|
Vol: 53(67) No: 4 / December 2008 A Scheduling Strategy for Flexible Job Shop Factories with Probabilistic Events, Applicable in Semiconductor Industry Artur M. Kuczapski Computer and Software Engineering Department, “Politehnica” University of Timisoara, V. Parvan Blvd., 2, 300223 Timisoara, Romania Silviu M. Trebuian Advanced clean production Information Technology (acp-IT), Celebi Evlia 16, 300226 Timisoara, Romania Mihai G. Novac Computer and Software Engineering Department, “Politehnica” University of Timisoara, V. Parvan Blvd., 2, 300223 Timisoara, Romania Mihai V. Micea Computer and Software Engineering Department, “Politehnica” University of Timisoara, V. Parvan Blvd., 2, 300223 Timisoara, Romania Vladimir I. Cretu Computer and Software Engineering Department, “Politehnica” University of Timisoara, V. Parvan Blvd., 2, 300223 Timisoara, Romania Laurentiu A. Maniu Advanced clean production Information Technology (acp-IT), Celebi Evlia 16, 300226 Timisoara, Romania Keywords: Scheduling, Flexible Job Shop, Composite Dispatching Rules, Genetic Programming, Semiconductor Manufacturing, Petri Nets. Abstract he paper proposes and analyzes a scheduling strategy and a prediction method for flexible job shops with probabilistic events. The presented strategy uses several scheduling heuristics and simulation methods in order to predict and mitigate the impact of unexpected events, like machine breakdowns, rework cycles and scrapping, which could influence the efficiency of the production. The solution uses Genetic Programming to generate Composite Dispatching Rules that lead to better results and still present robustness against unscheduled events. These dispatching rules are evaluated by advanced simulation methods based on Timed Petri Nets and the Proxel simulation method. The advantage of the Proxel method is that it is able to simulate in parallel multiple execution scenarios and hence make the estimation of the average performance of the production possible. By using the results of the simulation, a better execution forecast is obtained and the generated dispatching rules are thoroughly evaluated. An important feature of the proposed method is that the used algorithms are chosen in such a way that the required computational power makes the solution applicable to large factories like those in the semiconductor industry. In the presented paper, all the measurements and experiments are realized on a virtual semiconductor factory extended from the Intel Five-Machine Six-Step Mini-Fab model. References [1] Gary S. May and Costas J. Spanos, Fundamentals of Semiconductor Manufacturing and Process Control, 1st ed., Ed. Wiley-IEEE Press, 2006, ch. 1. [2] S. Wolf, Microchip Manufacturing, 1st ed., Ed. Sunset Beach: Lattice Press, 2004. [3] Michael L. Pinedo, Planning and Scheduling in Manufacturing and Services, 1st ed., Ed. New York: Springer, 2006, ch. 1–5. [4] Katariina Kemppainen, Priority Scheduling Revisited – Dominant Rules, Open Protocols, and Integrated Order Management, Ed. Helsinki School of Economics, 2005. [5] Vincent T\'Kind and Jean-Charles Billaut, Multicriteria Scheduling, 2nd ed., Ed. Berlin: Springer, 2006, ch. 1, 2, 3, 4, 8. [6] Nhu Binh Ho and Joc Cing Tay, “Evolving Dispatching Rules for solving the Flexible Job-Shop Problem”, Proceedings of the 2005 IEEE Congress on Evolutionary Computation, 2005, vol. 3, pp. 2848–2855. [7] Ilka Habenicht and Lars Mönch, “A finite-capacity beam-search-algorithm for production scheduling in semiconductor manufacturing”, Proceedings of the 2002 Winter Simulation Conference, vol. 2, pp. 1406–1413. [8] Cintia Rogao Scrich, Vinicius Amaral Armentano and Manuel Laguna, “Tardiness minimization in a flexible job shop: A tabu search approach”, Journal of Intelligent Manufacturing, vol. 15, pp. 103–115, Feb. 2004. [9] Anant Singh Jain and Sheik Meeran, “A State-of-the-art review of job-shop scheduling techniques”, Department of Applied Physics, Electronic and Mechanical Engineering University of Dundee, Dundee, Scotland, UK, DD1 4HN. [10] Tadao Murata, “Petri Nets: Properties, Analysis and Applications”, Proceedings of the IEEE, vol. 77, pp. 541–580, April 1989. [11] Peter J. Haas, “Stochastic Petri Nets for Modeling and Simulation”, Proceedings of the 2004 Winter Simulation Conference, 2004. [12] Peter G. Haas, Stochastic Petri Nets: Modeling, Stability, Simulation, 1st ed., Ed. New York: Springer, 2002, ch. 2, 3, 6, 8. [13] W.M.P van der Aalst, “Petri Net Based Scheduling”, Computing Science Reports No. 95, Eindhoven University of Technology, 1995. [14] Graham Horton, “A New Paradigm for the Numerical Simulation of Stochastic Petri Nets with General Firing Times”, Proceedings of the European Simulation Symposium 2002, Dresden. [15] Wolfgang Banzhaf, Peter Nordin, Robert E. Keller and Frank D. Francone, Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications, 1st ed., Ed. San Francisco: Morgan Kaufmann, 1997, ch. 4, 5, 6, 7, 9, 10. [16] Ramirez-Hernandez, J.A. Heshan Li Fernandez, E. McLean, C. Swee Leong, ”A framework for standard modular simulation in semiconductor wafer fabrication systems”, Proceedings of the 2005 Winter Simulation Conference, 2005. |