On-line scheduling of multi-server batch operations
Tóm tắt
The batching of jobs in a manufacturing system is a very common policy in many industries. The main reasons for batching are the avoidance of setups and/or facilitation of material handling. Good examples of batch-wise production systems are the ovens that are found in the aircraft industry and in the manufacture of semiconductors. These systems often consist of multiple machines of different types for the range and volumes of products that have to be handled. Building on earlier research in the aircraft industry, where the process of hardening synthetic aircraft parts was studied, we propose a new heuristic for the dynamic scheduling of these types of systems. Our so-called look-ahead strategy bases its decision to schedule a job on a certain machine on the availability of information on a limited number of near future arrivals. The new control strategy distinguishes itself from existing heuristics by an integrated approach that involves all machines in the scheduling decision, instead of only considering idle machines. It is shown by an extensive series of simulation experiments that the new heuristic outperforms existing heuristics for most system configurations. Especially in the case of complex systems, where multiple products have to be handled by non-identical machines, the new heuristic proves its value as a practical scheduling tool. Important insight is obtained with regard to the relation between the system is configuration and its performance.
Tài liệu tham khảo
Bagchi, T.P. and Templeton, J.C.G. (1972) Numerical methods in Markov chains and bulk queues, in Lecture Notes in Economics and Mathematical Systems, Vol. 72, Beckmann, M., Goos, G. and Künzi, H.P. (eds), Springer Verlag, Berlin.
Chaudry, M.L. and Templeton, J.G.C. (1983) A First Course in Bulk Queues, Wiley, New York.
Deb, R.K. and Serfozo, R.F. (1973) Optimal control of batch service queues. Advances in Applied Probability, 5, 340-361.
Fowler, J.W., Hogg, G.L. and Phillips, D.T. (1992) Control of multiproduct bulk service diffusion/oxidation processes. IIE Transactions, 24, 84-96.
Glassey, C.R. and Weng, W.W. (1991) Dynamic batching heuristic for simultaneous processing. IEEE Transactions on Semiconductor Manufacturing, 4, 77-82.
Glassey, C.R., Markgraf, F. and Fromm, H. (1993) Real time scheduling of batch operations, in Optimization in Industry: Mathematical Programming and Modeling Techniques in Practice, Ciriani, T.A. and Leachman, R.C. (eds), Wiley, Chichester, UK, pp. 113-137.
Hodes, B., Schoonhoven, B. and Swart, R. (1992) On line planning van ovens. Technical Report, University of Twente, Enschede, The Netherlands (in Dutch).
Hoover, S.V. and Perry, R.F. (1989) Simulation — A Problem Solving Approach, Addison Wesley, Reading, MA.
Hopp, W.J. and Spearman, M.L. (1996) Factory Physics — Foundations of Manufacturing Management, Irwin, Chicago, IL.
Law, A.M. and Kelton, W.D. (2000) Simulation Modeling and Analysis, McGraw-Hill, Singapore.
Neuts, M.F. (1967) A general class of bulk queues with Poisson input. Annals of Mathematical Statistics, 38, 759-770.
Robinson, J.K., Fowler, J.W. and Bard, J.F. (1995) The use of upstream and downstream information in scheduling semiconductor batch operations. International Journal of Production Research, 33, 1849-1869.
Silver, E.A. and Meal, H.C. (1973) A heuristic for selecting lot size quantities for the case of a deterministic time varying demand rate and discrete opportunities for replenishment. Production and Inventory Management, 14, 64-74.
Uzsoy, R., Lee, C.Y. and Martin-Vega, L.A. (1992) A review of production planning and scheduling models in the semiconductor industry, part I: system characteristics, performance evaluation and production planning. IIE Transactions, 24, 47-60.
Uzsoy, R., Lee, C.Y. and Martin-Vega, L.A. (1994) A review of production planning and scheduling models in the semiconductor industry, part II: shop-floor control. IIE Transactions, 26, 44-55.
Van der Zee, D.J., Van Harten, A. and Schuur, P.C. (1996) Dynamic job assignment heuristics for multi-server batch operations, in Proceedings of the Second International Conference on Computer Integrated Manufacturing in the Process Industries, Fransoo, J.C. and Rutten, W.G.M.M. (eds), pp. 558-573, Research School BETA, Eindhoven, The Netherlands.
Van der Zee, D.J. (1997) Simulation as a tool for logistics management. PhD thesis, University of Twente, Enschede, The Netherlands.
Van der Zee, D.J., Van Harten, A. and Schuur, P.C. (1997a) Dynamic job assignment heuristics for multi-server batch operations — a cost-based approach. International Journal of Production Research, 35(11), 3063-3093.
Van der Zee, D.J., Van Harten, A. and Schuur, P.C. (1997b) Dynamic scheduling of batch operations with non-identical machines. Technical Report, P4, Research School BETA, Eindhoven, The Netherlands.
Weng, W.W. and Leachman, R.C. (1993) An improved methodology for real-time production decisions at batch-process work stations. IEEE Transactions on Semiconductor Manufacturing, 6, 219-225.