Solving single and parallel machine scheduling problems with sequence dependent setup times using differential evolution based algorithms

Abstract

Bu tezde, üretim süresinin en aza indirilmesi amacıyla sıra bağımlı hazırlık süreleri olan tek ve paralel makine çizelgeleme problemleri için Diferansiyel Evrim (DE) algoritmasının bir uygulamasını sunuyoruz. Mevcut bilgilerimiz ışığında yapılan bu çalışma paralel makine çizelgeleme probleminde DE sezgiselinin kullanımı için ilk girişimdir._x000B_Tek makine çizelgeleme probleminde DE algoritmasının sonuç kalitesi ve hesaba dayalı etkinliğini geliştirmek için iliştirilen, ekleme tabanlı komşuluk arama ve değişken komşuluk arama olarak bilinen iki basit yerel arama metodu, melez bir çözüm tekniği oluşturmak için kullanıldı. TSPLIB'den alınan test problemleri çözülerek, saf DE algoritması melez Diferansiyel Evrim algoritmaları ile kıyaslandı. DE algoritmasının melezlenmesinin çözüm kalitesini geliştirdiği görüldü._x000B_DE algoritması, sürekli en iyileme problemlerini çözmek için evrimsel bir en iyileme yöntemidir. Paralel makine problemini çözmek için ilk olarak, DE algoritmasındaki bireyleri temsil etmek üzere Genetik Algoritmadan vektör grup kodlama tekniği uyarlanır. İkinci olarak, DE algoritmasını çizelgeleme problemlerinin çözümünde uygun kılmak için, iş ve makine permutasyonlarına yönelik DE algoritmasındaki bireylerin sürekli değerlerini çevirmek üzere, en büyük sıralama değeri ve alt aralık kodlama kuralları kullanılır. Üçüncü olarak, araştırma tabanlı DE algoritmasından sonra başarımızı arttırmak için etkin bir yerel arama prosedürü uygulanır. Ek olarak, DE algoritmasının performansı, yapıcı bir başlangıç popülasyonu düzenlemesinin görevlendirilmesiyle geliştirilir. Son olarak, önerilen tekniklerin ümit verici sonuçlar verdiğini kanıtlamak için bir hesaplamaya dayalı çalışma yapılmıştır. In this thesis, we present an application of the Differential Evolution (DE) algorithm for the single and parallel machine scheduling problems with sequence dependent setup times for the objective of minimizing makespan. To the best of our knowledge, this is the first attempt to use the DE heuristic for the parallel machine scheduling problem._x000B_To improve the solution quality of the DE algorithm in single machine scheduling problem, two simple local search methods which are insert-based neighborhood search and variable neighborhood search, are respectively embedded in the algorithm for a hybrid solution. Pure DE algorithm is compared with the hybrid DE algorithms by solving problems taken from TSPLIB. It is seen that hybridizing the DE algorithm improves the solution quality._x000B_The DE algorithm is an evolutionary optimization method. For solving the parallel machine problem, vector group encoding technique is adopted from genetic algorithm. Secondly, to make the DE algorithm suitable for solving scheduling problems, the largest order value and sub-range encoding rules are used to convert the continuous values of individuals in the DE algorithm to job and machine permutations. Local search procedure is applied to emphasize exploitation after the DE algorithm based exploration. The performance of the DE algorithm is enhanced by employing a population initialization scheme based on a constructive heuristic. Finally, a computational study is conducted to demonstrate that the proposed technique is capable of producing encouraging solutions.