Genelleştirilmiş karesel çoklu sırt çantası problemi için melez bir çözüm yaklaşımı
A hybrid solution method for the generalized quadratic multiple knapsack problem
Yazar: TUĞBA SARAÇ
Danışman: YRD. DOÇ. DR. AYDIN SİPAHİOĞLU
Eskişehir Osmangazi Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2007
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Bu çalışmada önemine rağmen yazında diğer sırt çantası problemlerine kıyasla daha az yer almış olan karesel çoklu sırt çantası problemi (KÇSÇP) ele alınmıştır. Bu problemin çözümüne yönelik olarak bir genetik algoritma (GASS) geliştirilmiş ve önerilen algoritmanın özellikle sırt çantası sayısı fazla olan test problemlerinde oldukça başarılı olduğu gösterilmiştir. Bunun yanı sıra KÇSÇP'nin matematiksel modeli, gerçek hayat problemlerinin çözümünde karşılaşılabilecek bazı özel durumları kapsayacak şekilde genelleştirilmiş ve GASS, genelleştirilmiş modeli çözebilecek şekilde geliştirilmiştir. Ayrıca yine genelleştirilmiş problemin çözümüne yönelik olarak, genetik algoritma ve uygun çözüm temelli genişletilmiş subgradient algoritmasının melezlenmesi ile elde edilmiş olan ikinci bir çözüm yaklaşımı önerilmiştir. Son olarak enjeksiyon makinalarının çizelgelenmesi problemi için bir genelleştirilmiş KÇSÇP modeli ve bu modelin parametrelerinin belirlenebilmesi için iki farklı yaklaşım önerilmiştir. Önerilen çözüm yöntemlerinin performansları, rassal türetilmiş test problemleri kullanılarak araştırılmış, elde edilen sonuçlar ve gelecek çalışmalara ilişkin öneriler sunulmuştur.Anahtar Kelimeler: Karesel çoklu sırt çantası problemi, genetik algoritma, uygun çözüm temelli genişletilmiş subgradient algoritması (UÇT-GSA), melez algoritma, enjeksiyon makinalarının çizelgelenmesi problemi.

Abstract:
The quadratic multiple knapsack problem (QMKP) is a generalization of the quadratic knapsack problem, which is one of the well-known combinatorial optimization problems, from a single knapsack to k knapsacks with (possibly) different capacities. Although it is an important problem, it is not taken in a large scale in the literature. In this study, a genetic algorithm (GASS) is developed for solving the QMKP and it is shown that GASS is very successful especially on the literature test problems which have large number of knapsack. Moreover, the mathematical model of the QMKP is generalized as covering the constraints that we may face in real life problems. Two distinct solution approaches are proposed for solving the generalized QMKP (G-QMKP). One of them is a genetic algorithm (GAGSS) which has similar genetic operators with GASS. The second one is a hybrid algorithm, that genetic algorithm and modified subgradient algorithm based on feasible values run together. Finally, a G-QMKP model for injection machine scheduling problem and two approaches to determine the parameters of this model are proposed. The performance of the proposed solution approaches are analyzed by using randomly generated test instances. Successful results are obtained and some suggestions for future studies are presented.Keywords: Quadratic multiple knapsack problem, genetic algorithm, modified subgradient algorithm based on feasible values (F-MSG), hybrid algorithm, injection machine scheduling problem.