Akış tipi çizelgeleme problemlerinde kullanılan geleneksel sezgisel yöntemlerle yapay zeka tekniklerinin çözüm performanslarının karşılaştırılması

Bu çalışmada, optimum çözümleri bulunamayan NP kapsamında yer alan akış tipi çizelgeleme problemleri çözülmeye çalışılmıştır. J. Carlier tarafından, akış tipi çizelgeleme için geliştirilen, dokuz farklı problem, geleneksel sezgisel yöntemlerden olan; NEH, CDS, Dannenbring, Gupta, Ho-Cheng, Hundal-Rajgopal, Johnson ve Palmer algoritmaları ile çözülerek optimum veya optimuma yakın iş sıraları ve tamamlanma zamanları hesaplanmıştır. Aynı problemler, yapay zeka tekniklerinden olan, genetik algoritma ve tavlama benzetimi yardımı ile çözülerek elde edilen tamamlanma zamanları $C_{max}$, geleneksel sezgisel yöntemler ile karşılaştırılmıştır. Akış zamanı kriterli bu çalışmada yapay zeka tekniklerinin optimum veya optimuma daha yakın sonuç verdiği belirlenmiştir.

Performance analysis of classical heuristic methods and artificial intelligence techniques used in flow-shop scheduling problems: A comperative approach

In this study, the flow shop scheduling problems are tried to be solved. These problems are classified as NP hard and an optimum solution cannot be obtained. Nine different problems, developed by J.Carlier, were solved by using traditional heuristic methods including NEH, CDS, Dannenbring, Gupta, Ho-Cheng, Hundal-Rajgopal, Johnson and Palmer, optimum and near optimum solutions were obtained. Same problems were also solved using artificial intelligence techniques such as, genetic algorithms and simulated annealing. The results, $C_{max}$, the complation time were compared to those obtained by heuristic methods. It is noted that the artifical intelligence tecniques are resulted in optimum or near optimum solutions with flow time criteria.

___

Anonymous, 2000, Simulated Annealing Techniques, http: //informs.org.
Carlier, J., 1978, Akış Tipi Çizelgeleme Problemleri, ftp://mscmga.ms.ic.ac.uk / pub / flowshop l.txt.
Cheng, R., Gen. M., Tsujimura, Y., 1999, A Tutorial Survey of Job Shop Scheduling Problems Using Genetic Algorithms: Part II. Hybrid Genetic Search Strategies, Computers and Industrial Engineering Vol.37, 51-55.
Chen, Ç.L., Neppalli, R.V., Aljaber, N., 1996, Genetic Algorithms Applied to the Continuous Flow Shop Problem, Computers and Industrial Engineering, Vol 30, no:4,919-929.
Chen, C.L., Vempati,V.S., Aljaber, N., 1995, An Application of Genetic Algorithms for Flowshop Problems, European Journal of Operational Research 80, 389-396.
Cleveland, G.A., Smith, F.S., 1989, Using Genetic Algorithm to Schedule Flow Shop Release, Proc.3r Int. Conf. On Genetic Algorithms Applications, 160-169.
Croce, F.D., Tadei, R.,Volta, G., 1995, A Genetic Algorithm for the Job Shop Problem, Computers and Operations Research. Vol.22,No.l.
Engin, O., 2001, Akış Tipi Çizelgeleme Problemlerinin Genetik Algoritma ile Çözümün Performansının Artırılmasında Parametre Optimizasyonu, Doktora Tezi, Î.T.Ü. Fen Bilimleri Enstitüsü, İstanbul.
Goldberg, D.E., 1989, Genetic Algorithms in Search Optimization and Machine Learning, Addison Wesley Publishing Company, USA.
Jain, N., Bagchi, T.P., 2000, Hybridized Gas: Some New Results in Flowshop Scheduling , Modelling and Simulation (MS2000) International Conferance at Pittsburg in May 2000, http://citeseer.nj.nec.com.
Murata, T., Ishibuchi, H., Tanaka, H., 1996a, Genetic Algorithms for Flow Shop Scheduling Problems,Computers and Industrial Enginering Vol.30, No.4, pp 1061-1071.
Murata, T., Ishibuchi, H., Tanaka, H., 1996b, Multi-Objective Genetic Algorithms and Its Applications to Flow shop Scheduling Computers and Industrial Engineering ,vol 30, No 4, pp 957-968.
Ogbu, F.Â., Smith, D.K., 1989, The Application of the Simulated Annealing Algorithm to The Solution of The n/m/Cmax Flowshop Problem, Computers and Operations Research. Vol.17, No.3.
Osman, Ih., Potts, Cn., 1989, Simulated Annealing for Permutation Flow Shop Scheduling, OMEGA, IntJ. of Mgmt Sci., Vol.l7,No.6.
Reeves, C, 1995, Modern Heuristic Techniques for Combinatorial Problems, Me Graw-Hill Book Company, UK.