AKIŞ TİPİ ÇİZELGELEME PROBLEMLERİNİN YAPAY BAĞIŞIKLIK SİSTEMLERİ İLE ÇÖZÜMÜNDE YENİ BİR YAKLAŞIM

Yıl 2007, Cilt: 8 Sayı: 1, 12 - 27, 01.01.2007

Orhan Engin , Alper Döyen

Öz

n iş m makina akış tipi iş çizelgeleme problemi en genel iş çizelgeleme problemlerinden biridir. Bu çalışma akış tipi çizelgeleme problemi için toplam tamamlanma zamanı minimizasyonu ile ilgilenmektedir. Yapay Bağışıklık Sistemleri YBS , çizelgeleme problemlerinde son dönemlerde kullanılan yeni bir problem çözme tekniğidir. YBS, doğal bağışıklık sisteminin prensiplerini ve mekanizmalarını kullanarak problemlere çözüm üreten bir hesaplama sistemidir. Bu çalışmada, bağışıklık tepkisinin iki ayrı mekanizması olan klonel seçim prensibi ve benzerlik mekanizması üzerine kurulmuş bir metod kullanılmıştır. Meta sezgisel yöntemlerde seçilen operatörler, çözüm kalitesi üzerinde önemli bir role sahiptir. Bu nedenle, yapay bağışıklık sisteminin etkin parametrelerinin belirlenmesinde çok aşamalı bir deney tasarımı prosedürü uygulanmıştır. Deney sonuçları, yapay bağışıklık sistemlerinin klasik çizelgeleme ve tavlama benzetimi algoritmalarından daha iyi sonuçlar verdiğini göstermiştir

Anahtar Kelimeler

Akış tipi çizelgeleme, yapay bağışıklık sistemleri, klonel seçim

A NEW APPROACH TO SOLVE FLOWSHOP SCHEDULING PROBLEMS BY ARTIFICIAL IMMUNE SYSTEMS

Öz

The n-job, m-machine flow shop scheduling problem is one of the most general job scheduling problems. This study deals with the criteria of makespan minimization for the flow shop scheduling problem. Artificial Immune Systems AIS are new intelligent problem solving techniques that are being used in scheduling problems. AIS can be defined as computational systems inspired by theoretical immunology, observed immune functions, principles and mechanisms in order to solve problems. In this research, a computational method based on clonal selection principle and affinity maturation mechanisms of the immune response is used. The operation parameters of meta-heuristics have an important role on the quality of the solution. Thus, a generic systematic procedure which bases on a multi-step experimental design approach for determining the efficient system parameters for AIS is presented. Experimental results show that, the artificial immune system algorithm is more efficient than both the classical heuristic flow shop scheduling algorithms and simulated annealing.

Anahtar Kelimeler

Flow Shop Scheduling, Artificial Immune Systems, Clonal Selection

Kaynakça

• ADA, G.L., NOSSAL, G. (1987). The clonal selection theory. Scientific American, vol.2, pp.50-57.
• CAMPBELL, H.G., DUDEK, R.A., SMITH, M.L (1970). A heuristic algorithm for the n-job, m-machine sequencing problem. Management Science, 16/B, pp. 630-637.
• CARLIER, J. (1978). Ordonnancements a contraintes disjonctives. R.A.I.R.O. Operational Research 12, pp. 333-351.
• COSTA, A.M., VARGAS, P.A., VON ZUBEN, F.J.AND FRANÇA, P.M. (2002).
• IEEE World Congress on Computational Intelligence, In the proc. of the special sessions on artificial immune systems in the 2002 Congress on Evolutionary Computation, Makespan minimization on parallel processors: An immune based approach, Honolulu, Hawaii.
• DANNENBRING, D.G. (1970) An evaluation of flow shop sequencing heuristics, Management Science, vol. 23, pp. 1174-1182.
• DASGUPTA, D., FORREST, S. (1996). Proceedings of the ISCA’96, Novelty detection in time series data using ideas from immunology.
• DASGUPTA, D., FORREST, S. (1999). Proceedings of the Second International Conference on Intelligent Processing and Manufacturing Materials (IPMM) Artificial immune systems in industrial applications, Honolulu, July 10-15.
• DE CASTRO, L.N., VON ZUBEN, F.J. (1999). Artificial immmune systems: Part 1- Basic theory and applications. Technical Report, TR-DCA 01/99.
• (2000). GECCO 2000 – Workshop proceedings The clonal selection algorithm with engineering applications. pp.36-37. [Available form: ftp://ftp.dca.fee.unicamp.br/pub/docs/vonzuben/ lnunes/gecco00.pdf].
• (2002). Learning and optimization using the clonal selection principle. IEEE Transactions on Evolutionary Computation, Special Issue on Artificial Immune Systems, vol.6, no.3, pp.225.
• DE CASTRO, L.N., TIMMIS, J.I. (2002a). Artificial immune systems: A novel paradigm for pattern recognition, In L. ALONSO J. CORCHADO, and C. FYFE (eds). Artificial Neural Networks in Pattern Recognition, pages 67-84, University of Paisley.
• (2002b). Artificial Immune Systems: A New Computational Intelligence Approach. Springer-Verlag,.
• (2003). Artificial immune systems as a novel soft computing paradigm. Soft Computing Journal, vol.7, Isuue 7.
• ENGİN, O., FIĞLALI, A. (2001). Performance analysis of classical heuristic methods and artificial intelligence techniques used in flow shop scheduling problems: A comparative approach. Journal of Engineering and Architecture Faculty of Selcuk University, v.16, n.2, pp.7-17.
• FIĞLALI, A., ENGİN, O., FIĞLALI, N. (2002). International Conference on Fuzzy Systems, Soft Computational Intelligence in Management and Industrial Engineering A systematic procedure for setting ant system parameters, May 29-31, İstanbul, Turkey.
• FORREST, S., PERELSON, A., ALLEN, L., CHERUKURI, R. (1994). Proceedings of the IEEE Symposium on Research in Security and Privacy. Self-nonself discrimination in a computer, pp. 202-212.
• FORREST, S.,. HOFMEYR, S.A. (2001). Engineering an immune system. Graft, vol. 4:5, pp. 5-9.
• GOLDBERG, D.E. (1989). Genetic Algorithms in Search Optimization and Machine Learning. Addison-Wesley Publishing Company, USA.
• GUPTA, J.N.D. (1971). A functional heuristic algorithm for the n-job, m-machine flow shop proble., Operational Research Quartely , vol.22 , pp. 39-47.
• HART, E., ROSS, P.AND NELSON, J. (1998). Proc. of ICEC’98. Producing robust schedules via an artificial immune system, pp.464-469.
• HO, J.C, CHAN, Y.L. (1991). A new heuristic for the n-job m-machine flow shop problem, European Journal of Operational Research, 52, pp.194-202.
• HUNDAL, T.S., RAJGOPAL, J. (1988). An extension of Palmer’s heuristic for the flow-shop scheduling problem. International Journal of Production Research, 26, pp. 1119-1124.
• JOHNSON, S.M. (1954). Optimal two and three stage production schedules with set up times included. Naval Research Logistics Quartely, vol. 1, pp. 61-68.
• MORI, M., TSUKIYAMA, M., FUKUDA, T. (1997). Proc. of the IEEE Systems, Man and Cybernetics Conference. Artificial immunity based management system for a semiconductor production line, pp. 851-855.
• NASAROUI, O., DASGUPTA, D., GONZALES, F. (2002). Workshop on Web Analytics at Second SIAM International Conference on Data Mining (SDM) The promise and challenges of artificial immune system based web-usage mining: preliminary results. Arlington VA, April 11-13.
• NAWAZ, M., ENSCORE, E.E., HAM, I. (1983). A heuristic algorithm for the m- machine, n-job flow shop sequencing problem. Omega, vol.11, pp .91-95.
• OGBU, F.A., SMITH, D.K. (1990). The application of the simulated annealing algorithm to the solution of the n/m/Cmax flow shop problem. Computers, Operations Research, 17, pp.243-253.
• OSMAN, I.H., POTTS, C.N. (1989). Simulated annealing for permutation flow shop scheduling. Omega, 17, pp,551-557.
• PALMER, D.S. (1965). Sequencing jobs through a multi stage process in the minimum total time - a quick method of obtaining a near optimum. Operational Research Quartely, 16, pp., 101-107.
• RUSS, S.H., LAMBERT, A., KING, R., RAJAN, R., REESE, D. (1999). Proc. of the Symposium on High Performance Distributed Computing. An artificial immune system model for task allocation.
• TARANAKOV, A., DASGUPTA, D. (2000). A formal of an artificial immune system. Biosystems, vol. 55/1-3, pp.151-158.
• TIAN, P., MA, J., ZHANG, D.M. (1999). Application of the Simulated Annealing Algorithm to the Combinatorial Optimization problem with permutation property: An investigation of generation mechanism. European Journal of Operational Research, 118- 81-94.
• TIMMIS, J., NEAL, M.J. (2000). Research and Development in Intelligent Systems XVII, A resource limited artificial immune system for data analysis, pp.19-32.
• TROJANOWSKI, K., WIERZCHON, S.T. (2002). The Elevent International Symposium on Intelligent Information systems. Searching for memory in artificial immune system, June 3-6.