Esnek atölye tipi çizelgeleme problemi için bir hibrid genetik algoritma yaklaşımı

Abstract

One of the important and classical problems for production systems is the scheduling. Furthermore, one of the most general states of the scheduling problems in production systems is the flexible job-shop scheduling problem (FJSP). The main difference of the flexible job-shop scheduling problems from the regular job-shop scheduling problems is that in the flexible job-shop, we assume that an operation of a job can be performed in several alternative work centers, while in the regular job-shop case an operation can only be performed in a single work center. In order to optimize the result for this important problem, which is considered in NP-hard class, it becomes impossible to solve or long time periods are required for a solution. In this study, we suggest a hybrid meta heuristic for FJSP with the objective of minimizing the makespan. Our algorithm has three stages; a problem perturbation heuristic, a genetic meta algorithm, and a local improvement phase. The perturbation heuristic aims at producing a high quality initial generation of solutions for the genetic algorithm. While producing the initial generation, schedules are formed by means of priority rules by making positive negative changes on processing times of the operations with the perturbation heuristic. The genetic algorithm improves the generations of solutions subsequently and finally a local search phase at the end tries to further improve the solution found in the last generation. Our hybrid meta heuristic which is collated by the approaches we suggested and by the others in the literature is tried on the test problems from the literature and is observed that it works efficiently.

Çizelgeleme problemleri üretim sistemleri için önemli ve klasik problemlerden birisidir. Üretim sistemlerindeki çizelgeleme problemlerinin en genel hallerinden birisi de esnek atölye tipi çizelgeleme problemidir. Esnek atölye tipi çizelgeleme probleminin (EATÇP) atölye tipi problemden temel farkı bir operasyonun yapılabileceği alternatif makinelerin ya da üretim merkezlerinin olmasıdır. NP (Non deterministic polynomial)-zor sınıfa giren bu önemli problem için sonuç en iyilenmeye çalışıldığında problemin büyüklüğüne bağlı olarak ya problem çözülememekte ya da çok uzun zamanlara ihtiyaç duyulmaktadır. Çalışmamızda daha hızlı ve iyi sonuçlar alan bir meta-sezgisel geliştirilmiştir. Geliştirilen algoritma, amaç olarak son işin tamamlanma zamanını alan, hibrid bir meta sezgisel algoritmadır. Algoritmamız üç temel aşamadan oluşmaktadır; problem rassal değişim sezgiseli, genetik meta sezgisel ve lokal iyileştirme aşaması. Problem rassal değişim sezgiseli, genetik algoritma için kaliteli ilk nesil çözümlerinin bulunmasında kullanılmaktadır. İlk nesil oluşturulurken rassal değişim sezgiseli ile operasyonların işlenme zamanları üzerinde eksi ve artı yönde yüzdesel değişiklikler yapılarak seçtiğimiz öncelik bazlı kurallar yardımıyla çizelgeler oluşturulmaktadır. Genetik algoritmayla iyileştirilen çözüm nesilleri son aşamada lokal olarak daha da iyileştirilmeye çalışılmaktadır. Literatürdeki yaklaşımlar ile bizim önerimiz olan bazı yaklaşımları harmanladığımız hibrid sezgiselimiz, literatürdeki test problemleri üzerinde denenmiş ve etkin bir şekilde çalıştığı gözlemlenmiştir.