Sıra bağımlı ilişkisiz paralel makine çizelgeleme problemi için yeni bir sezgisel algoritma önerisi

Abstract

Üretim aşamasında makinelerin işleyişinin belirlendiği çizelgeleme, işletmelerde etkin bir üretim için son derece önemlidir. İşletmeler büyüdükçe planlama ve üretim aşamasında işlerin hangi çizelgede yapılması gerektiği daha karmaşık hal almaktadır. Küçük makine-iş konfigürasyonunda en uygun çizelgeleme, uzman görüşü veya tam sayılı programlama teknikleri ile elde edilebilir. İşlerin ve makinelerin sayısı arttıkça kesin çözümün bulunması imkânsız hale gelmektedir. Kesin çözümün bulunamadığı durumlarda yaklaşık çözümler metasezgisel algoritmalar ile elde edilmektedir. Çalışma kapsamında ele alınan problem, kesin çözümü bulunamayan ve metasezgisel algoritmalar ile çözülebilen sıra bağımlı hazırlık süreli ilişkisiz paralel makine çizelgeleme problemidir. Bu çalışma, üretim süresini minimize etmeyi amaçlamaktadır. Bu çalışmada, birçok araştırmacı tarafından daha önce farklı metasezgisel algoritmalar ile yaklaşık en iyi çözümü bulunmaya çalışılmış bir kıyas veri seti üzerine çalışılmıştır. Bu tez kapsamında kıyas veri setini çözmek için uyarlanmış yeni bir değişken komşuluk arama algoritması önerilmektedir. Yeni önerilen algoritma, komşuluk yapılarına 2 farklı parametre seçimi eklemektedir. Bu eklenen yeni parametrelerin sonuç üzerine etkisi tartışılmış ve bulgular bu yeni parametreleri kullanmanın faydalı olduğunu göstermektedir. Değişken komşuluk arama algoritmasındaki yerel arama modülü, birden fazla yerel arama ile çeşitlendirilmiş ve komşuluk değerlerine göre yerel arama seçim fazı eklenmiştir. Eklenen seçim fazı, algoritmayı gereksiz yerel aramalardan kurtarmaktadır. Algoritma kıyas veri setinde 50’den fazla test edilmiş ve en iyi sonuçlar raporlanmıştır. Denenen 540 adet veri setinin 141 tanesinde bilinen en iyi sonuçtan daha iyi değerler elde edilmiştir. 140 örnekte ise bilinen en iyi çözümlere ulaşılmıştır. Önerilen algoritma, tüm örneklerde ortalama %0,095 hata ile çalışmaktadır.

Scheduling, determines which job will be performed by which machine at the production stage, is extremely important for an effective production in businesses. As a business grow, scheduling will be more complex in the planning and production stages. In a business, optimal scheduling in small machine job environment can be done by an expert opinion or integer programming techniques. As the number of jobs and machines increase, it becomes impossible to find an exact solution. When the exact solution cannot be found, approximate solutions are obtained with metaheuristic algorithms. The problem studied in this study is the one that can be solved by metaheuristic algorithms that cannot be found exact solutions. This is an unrelated parallel machine scheduling problem with setup times. The study aims to minimize makespan. In this problem, machines are unrelated. Each job has different process time on different machines and different setup times on different machines. In this study, a benchmark dataset has been studied. Many researchers have tried to find the approximate best solution with different metaheuristic algorithms. In this thesis, a new Adapted Variable Neighborhood Search Algorithm is proposed to solve the benchmark dataset. The new proposed algorithm adds 2 different parameters to the neighborhood structures. The effect of added parameters on the result was discussed and it was seen that the findings were beneficial in using these new parameters. The local search module in the proposed variable neighborhood search algorithm has 4 different local search algorithms. A new local search selection phase was added according to the neighborhood makespan values. The local search selection phase saves the algorithm from unnecessary local searches. The benchmark dataset was tested more than 50 times and best results were stored. When the results obtained with the proposed algorithm were compared with the best known results, it was seen that the proposed algorithm is successful in some machine job configurations. Better results than the best known results were obtained in 141 of 540 sample in the data set. In 140 samples, the best known solutions were reached. The proposed algorithm works with an average error of 0.095% in all samples.