Bulanık akış tipi çizelgeleme problemi için çok amaçlı genetik algoritma

Üretim planlama problemlerinin çoğu karar vericinin herhangi bir kararı vermeden önce birden fazla kriteri düşünmesini gerektirirken, çizelgeleme alanında yapılan çalışmaların pek çoğunda sadece bir kriter ele alınmıştır. Bu makalede günümüz imalat sistemlerinde büyük öneme sahip m-makineli akış tipi çizelgeleme probleminde işlem zamanları ve teslim tarihleri gibi zaman parametrelerinin belirsiz olduğu durum ele alınarak üretim tamamlanma zamanı, maksimum gecikme ve toplam akış zamanı amaçlarını eş zamanlı eniyileyen genetik algoritma temelli çok amaçlı bir yaklaşım geliştirilmiştir. Geliştirilen bulanık iş ve teslim zamanlı çok amaçlı genetik algoritma sonucunda amaç değerlerinin üyelik fonksiyonlarıyla ifade edildiği etkin çözümler elde edilmektedir. Geliştirilen algoritmanın etkinliği küçük boyutlu problemler kullanılarak gösterilmiştir. Genetik algoritmanın en iyi parametre değerleri faktöriyel deney tasarımı ile belirlenmiştir. Algoritmanın orta ve büyük boyutlardaki problemler için makul zamanda etkin çözümleri ürettiği gösterilmiştir.

Multiobjective genetic algorithm for fuzzy flowshop scheduling problem

The majority of research on scheduling problems addresses only a single criterion while the majority prodution planning problems require the decision maker to consider more than a single criterion for making a decision. In this paper, a problem with uncertain time parameters such as processing times and due dates in the m-machine flow shop scheduling problem, which has a big importance in nowadays manufacturing systems, is considered. Further a multiobjective approach based on genetic algorithm, optimizing fuzzy makespan, fuzzy maximum tardiness and fuzzy total flow time objectives simultaneously, is developed. The algorithm is developed to obtain efficient solutions. In this algorithm the values of the multiobjective function are expressed by using membership functions. The effectiveness of the algorithm is illustrated by using small size problems. The best parameter sets of the genetic algorithm are determined by using factorial design of experiment. It is shown that the algorithm produces efficient solutions for medium and large size problems in a reasonable amount of time.

PDF

___

1. Pinedo, M., Scheduling:Theory, algorithms, and systems, Prentice Hall, New Jersey, A.B.D., 2002.
2. Lee, C.E. ve Chou, F.D., “A two-machine flowshop scheduling heuristic with bicriteria objective”, International Journal of Industrial Engineering,Cilt 5, No 2, 128-139, 1998.
3. Nagar, A., Heragu, S. ve Haddock, J., “A combined branch and bound and genetic algorithm based approach for a flowshop scheduling problem”, Annals of Operations Research, Cilt 63, 397-414, 1996.
4. Şerifoğlu, F.S. ve Ulusoy, G. “A bicriteria twomachine permutation flowshop problem”, European Journal of Operational Research, Cilt 107, No 2, 414-430, 1998.
5. Yeh, W.C., “A new branch-and-bound approach for the n/2/flowshop/$alpha F+beta C_{max}$ flowshop scheduling problem”, Computers and Operations Research, Cilt 26, No13, 1293-1310, 1999.
6. Neppalli, V.R., Chen, C.L. ve Gupta, J.N.D., “Genetic algorihms for the two-stage bicriteria flowshop problem”, European Journal of Operational Research, Cilt 95, No 2, 356-373, 1996.
7. Ishibuchi, H. ve Murata, T., “A Multi-objective genetic local search algorithm and its application to flowshop scheduling, IEEE Transaction on System, Man, and Cybernetics-Part C: Applications and Reviews, Cilt 28, No 3, 392-403,1998.
8. Rajendran C., “Two-stage flow shop scheduling problem with bicriteria”, Journal of the Operational Research Society, Cilt 43, No 9, 871-884, 1992.
9. Gupta, J.N.D., Neppalli, V.R. ve Werner, F., “Minimizing total flow time in a two-machine flowshop problem with minimum makespan”, International Journal of Production Economics, Cilt 69, No 3, 323-338, 2001.
10. Sayın, S. ve Karabatı, S., “A bicriteria approach to the two-machine flow shop scheduling problem”, European Journal of Operational Research, Cilt 113, No 2, 435-449, 1999.
11. Murata, T., Ishibuchi, H., ve Tanaka, H., “Multiobjective genetic algorithm and its applications to flowshop scheduling”,Computers and Industrial Engineering, Cilt 30, No 4, 957-968, 1996.
12. Daniels, R.L. ve Chambers R.J., “Multiobjective flow-shop scheduling”, Naval research Logistics, Cilt 37, 981-995, 1990.
13. Chakravarthy, K. ve Rajendran, C., “A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization” Production Planning and Control, Cilt 10, No 7, 707-714, 1999.
14. Allahverdi, A., “A new heuristic for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness”, Computers and Operations Research, Cilt 31, No 2, 157-180, 2004
15. Ishii, H., Tada, M. ve Masuda T., “Two scheduling problems with fuzzy due-dates”, Fuzzy Sets and Systems, Cilt 46, 339-347, 1992.
16. Ishibuchi, H., Yamamoto, N., Murata, T. ve Tanaka, H., “Genetic algorithms and neighborhood search algorithms for fuzzy flowshop scheduling problems”, Fuzzy Sets and Systems, Cilt 67, 81-100, 1994.
17. Murata, T., Gen, M. ve Ishibuchi, H., “Multi- Objective Scheduling with Fuzzy Due-Date”, Computers and Industrial Engineering, Cilt 35, No 3-4, 439-442, 1998.
18. McCahon, C. S. ve Lee, E. S., “Job sequencing with fuzzy processing times”, Computers and Mathematics with Applications, Cilt 19, No 7, 31-41, 1990.
19. McCahon, C. S. ve Lee, E. S., “Fuzzy job sequencing for a flow shop”, European Journal of Operational Research, Cilt 62, No 3, 294-301, 1992.
20. Hong, T. ve Chuang, T.N., “A new triangular fuzzy johnson algorithm”, Computers and Industrial Engineering, Cilt 36, 179-200, 1999.
21. Hong, T.P. ve Chuang, T.N., “Fuzzy Palmer scheduling for flow shops with more than two machines”, Journal of Information Science and Engineering, Cilt 15, 397-406, 1999.
22. Temiz, İ. ve Erol, S., “Fuzzy branch-and-bound algorithm for flow shop scheduling”, Intelligent Manufacturing Systems, Cilt 15, No 4, 449-454, 2004.
23. Balasubramanian, J. ve Grossmann, I.E., “Scheduling optimization under uncertainty-an alternative approach”, Computers and Chemical Engineering, Cilt 27, 469-490, 2003.
24. Cheng, J., Kise, H. and Matsumoto, H., “A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem”, European Journal of Operational Research, Cilt 96, No 3, 578-590, 1997.
25. Akyol, D.E., “Application of neural network to heuristic scheduling algorithms”, Computers and Industrial Engineering, Cilt 46, No 4, 679-696, 2004.
26. Petrovic, S. And Song, X., “A new approach to two-machine flow shop problem with uncertain processing times, Optimization and Engineering, Cilt 7, No 3, 329-342, 2006.
27. Lai, Y.J. ve Hwang, C.L., Fuzzy Mathematical Programming, Springer-Verlag, Berlin, 1992.
28. Lee, E. S. ve Li, R. J., “Comparison of fuzzy numbers based on probability measure of fuzzy events”, Computers and Mathematics with Applications, Cilt 15, No 10, 887-896, 1988.
29. Tsai, Y.C. ve Chuang, T.N., “A new max operator on triangular fuzzy sets”, Journal of The Chinese Fuzzy Systems Association, Cilt 5, No 2, 71-78, 1999
30. Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, 1989.
31. Gen, M. and Cheng, R.,Genetic Algorithms and Engineering Design, John Wiley & Sons, New York, 1997.
32. Taillard, E., “Benchmarks for basic scheduling problems”, European Journal of Operational Research, Cilt 64, No 2, 278-285, 1993.
33. Temiz, İ., Bulanık İş ve Teslim Zamanlı Akış Tipi Çizelgeleme Problemi için Çok Amaçlı Genetik Algoritma, Doktora Tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, 2004.