İlişkisiz paralel makinelerin ilave kaynaklarla çizelgelenmesi

Abstract

Çalışmada, hazırlık ve proses aşamasında ilave kaynak kullanımının dikkate alındığı ilişkisiz paralel makine çizelgeleme problemi incelenmiştir. Hazırlık aşamasında ilave kaynak olarak ortak sunucu kullanılmaktadır. Ortak sunucu bir adet olup aynı anda bir işin hazırlığı yapılmaktadır. Hazırlık işlemi makine ve sıra bağımlıdır. Her işin uygun makinede işlem görmesini sınırlayan makine uygunluk kısıtları mevcuttur. Proses aşamasında ise proses ilave kaynağının kullanımını içeren kaynak kısıtı söz konusudur. İşler, proses aşamasında ilave kaynak uygun olduğunda makinede işlem görebilmektedir. Ele alınan problem tanımlanmış ve matematiksel model önerilmiştir. Problemin karmaşık yapısından dolayı büyük boyutlu problemleri çözebilmek için metasezgisel yöntemler gerekmiştir. Rassal İniş Arama ve Tavlama Benzetimi algoritmaları problem için önerilmiştir. Problem için gelişmiş komşu türetme yöntemleri ve ek özellikler içeren tavlama benzetimi algoritması versiyonu geliştirilmiştir. Matematiksel model, Rassal İniş Arama algoritması ve Tavlama Benzetimi algoritmalarının test problemlerinde çalışmaları doğrulanmış ve karşılaştırılmıştır. Önerilen Tavlama Benzetimi algoritması ile orta boyutlu problemlerde matematiksel modelin elde ettiği çözümlere kıyasla daha kısa sürede daha iyi çözümlere ulaşılmış, büyük boyutlu problemlerde makul sürelerde uygun çözümler elde edilmiştir.

In the study, the unrelated parallel machine scheduling problem, in which additional resources are used in the setup and processing stages, is examined. In the setup stage, a common server is used as an additional resource. There is only one additional resource and a job is being prepared at the same time. The setup operation is machine and sequence dependent. There are machine availability constraints that limit each job to be processed on the appropriate machine. In the process phase, there is a resource constraint that includes the use of the process additional resource. Jobs can be processed in the machine when the required process additional source is appropriate during the process phase. The studied problem is defined and a mathematical model is proposed. Due to the complexity of the problem, metaheuristic methods are required to solve large-scale problems. Random Descent Search and Simulation Annealing algorithms are proposed for the problem. A simulation annealing algorithm version has been developed for the problem, which includes advanced neighbour generation methods and additional features. The mathematical model, Random Descent Search algorithm and Simulation Annealing algorithms work in test problems are verified and compared. With the proposed Simulation Annealing algorithm, better solutions were obtained in a shorter time compared to the solutions obtained by the mathematical model for medium-sized problems, and feasible solutions were obtained in reasonable times for large-sized problems.