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

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

Abstract

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.

Özet

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.