Orhan ENGİN, Alpaslan FIĞLALI

Genetik algoritmalarla akış tipi çizelgelemede üreme yöntemi optimizasyonu

Bu çalışmada Akış tipi çizelgeleme problemlerinin Genetik algoritma ile çözümünde çözüm süresi ve kalitesi üzerinde etkin olan üreme operatörü belirlenmiştir. Literatürde kullanılan Akış zamanlı rulet çemberi ve Yapay seçim yöntemi ile yeni geliştirilen Kısmi yapay seçim, Makine verimli rulet çemberi ve Ters yapay seçim üreme yöntemleri farklı büyüklükteki 10 problem üzerinde denenmiştir, işlem süreleri, uniform dağılıma uygun olarak [1-25] dakika arasında rassal olarak üretilen problemler üzerinde yapılan toplam 1250 adet deney sonucunda, akış tipi çizelgeleme problemlerinin Genetik algoritma ile çözümünde, iki makine problemleri için kısmı yapay seçim; çok makine problemleri için akış zamanlı rulet çemberi iyi performans göstermiştir

Reproduction operator optimization of genetic algorithms in flowshop scheduling problems

In this study reproduction operators of genetic algorithms are tested for solving flowshop scheduling problems which are in NP-hard class and the most effective operator is determined. In addition to flowtime roulette wheel and artificial reproduction method, three new developed reproduction methods namely, partial artificial reproduction, machine utility roulette wheel and inverse artificial reproduction are tested on different scaled flowshop scheduling problems with a Genetic algorithm program coded in Turbo Pascal. Processing times of the jobs in machines are generated randomly between [1- 25] minutes according to uniform distribution. Problems are examined in two categories: 2-machine and multi-machine problems. In 2-machine problems the optimal solutions are determined with Johnson Algorithm and then compared with the solutions obtained with the Genetic Algorithms for different reproduction operators in six different scaled problems. In multi-machine problems the same reproduction operators are tested for 3-machine x 10-job, 4-machine x 10-job, 5-machine x 10-job and 7-machine x 15-job problems. The most effective reproduction operator is determined for both categories according to the results of 1250 experiments. As a result, partial artificial reproduction is determined to be the best performing reproduction operator for 2-machine problems and flowtime roulette wheel for multi-machine problems depending on the best makespan values.

PDF

___

Campbell, H. G., Dudek, R. A., Smith, B. L., (1970). A Heuristic Algorithm For The n-Job, m- Machine Sequencing problem, Management Science, 16, pp:16.
Chen. C. L.. Neppalli. R. V.. Aljaber. N.. (1996). Genetic Algorithms Applied To The Continuous Flow Shop Problem. Computers And Industrial Engineering. 30. 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.
Chou. F. D.. Lee. C. E.. (1999). Two Machine Flowshop Scheduling with Bicriteria Problem. Computers And Industrial Engineering. 36. 549-564.
Cicirello. V. A.. Smith. S. F.. (2000). Modeling GA Performance For Control Parameter Optimization. Proceedings. Genetic And Evolutionary Computation Conference (Gecco 2000). July 8-12. 2000. Lasvegas. Nevada. USA.
Cleveland. G. A.. Smith. F. S.. (1989). Using Genetic Algorithm To Schedule Flow Shop Release. Proceedings. 3rd International Conference on Genetic Algorithms Applications. 160-169. California. USA.
Croce. F.D.. Tadei. R.. Volta. G. (1995). A Genetic Algorithm For The Job Shop Problem. Computers And Operations.Research. 22. 1. 15-24.
Dannenbring, D. G., (1977). An Evaluation of Flow- Shop Sequencing Heuristic, Management Science, 23, pp:11.
Engin. O., (2001). Akış Tipi Çizelgeleme Problemlerinin Genetik Algoritma ile Çözümün Performansının Artırılmasında Parametre Optimizasyonu. Yayımlanmamış Doktora Tezi. İ.T.Ü. Fen Bilimleri Enstitüsü. İstanbul.
Gen. M.. (1996). Genetic Algorithms And Industrial Engineering. Computers And Industrial Engineering. 30. 4. 835-837.
Ghedjati. F.. (1999). Genetic Algorithms For The Job-Shop Scheduling Problem With Unrelated Parallel Constraints: Heuristic Mixing Method Machines And Precedence. Computers And Industrial Engineering. 37. 39-42.
Goldberg. D. E.. (1989). Genetic Algorithms in Search Optimization And Machine Learning. Addion Wesley Publishing Company. USA.
Gupta, J. N. D., (1971). A Functional Heuristic Algorithm For Flow-Shop Scheduling Problem, Operations Research, 22, pp:39-47.
Ho, J. C., Chang, Y., (1991). A new Heuristic For The n-Job, m-Machine Flow-Shop Problem, European J. oj Operations Research, 52, pp:194-202.
Jain. N.. Bagchi. T. P.. (2000). Hybridized GAs: Some New Results in Flowshop Scheduling. Proceedings. Modelling And Simulation (Ms2000) International Conference. http://citeseer.nj.nec.com. Pittsburg. USA.
Johnson, S. M., (1954). Optimal Two Three-Stage Production Schedule With Setup Times Included, Nav. Research Logistics Quarterly, No:1, pp:61-68.
Maturana. F.. Gu. P.. Naumann. A.. Norrie. D. H.. (1997). Object-Oriented Job Shop Scheduling Using Genetic Algorithm. Computers In Industry. 32. 281-94.
Min. L.. Cheng. W.. (1999). A Genetic Algorithm For Minimizing The Makespan in The Case Of Scheduling Identical Parallel Machines. Artificial Intelligence in Engineering. 13. 399-403.
Nawaz, M., Enscore, J. E., Ham, I., (1983). A Heurestic Algortihm For The m-Machine, n-Job Flow-Shop Sequencing Problem, OMEGA, The International Journal of Management Science, 11/1, pp:91-95.
Palmer, D. S., (1965). Sequencing Jobs Through a Multi-Stage Process in Minimum Total Time a Quick Method of Obtaining a Near Optimum, Operations Research, 16, pp:10