Uygunluk kısıtlı çok kaynaklı genelleştirilmiş atama problemi için bir tavlama benzetimi algoritması

Abstract

Genelleştirilmiş atama problemi (GAP), kapasite kısıtlı atama problemidir. Çok kaynaklı GAP (ÇKGAP), her ajanın birden fazla kapasite kısıtlı kaynağının olduğu GAP'ın özel bir çeşididir. Problemin amacı, toplam atama maliyetini enküçüklemektir. Bu çalışmada, uygunluk kısıtlı ÇKGAP problemi iki amaçlı olarak ele alınmıştır. Amaçlardan biri yüklerin dengeli bir şekilde ajanlara dağıtılmasını sağlarken, diğer amaç işlerin atandığı toplam ajan sayısını enküçüklemektedir. Geliştirilen matematiksel modelin çözümü için ağırlıklı toplam yöntemi kullanılmış ve GAMS paket programının Dicopt çözüsü ile çözülmüştür. Önerilen yöntemin işlerliği, oluşturulan örnek problem üzerinde gösterilmiştir. Büyük boyutlu problemlerin çözümü için bir tavlama benzetimi algoritması geliştirilmiştir. Oluşturulan farklı boyuttaki test problemleri, önerilen yöntemler ile çözülmüş ve elde edilen sonuçlar karşılaştırılmıştır. Yapılan deneyler sonucunda, geliştirilen tavlama benzetimi yöntemi ile daha başarılı sonuçlar elde edildiği gözlemlenmiştir.

Generalized assignment problem (GAP) is a capacity constrained assignment problem. Multiresource GAP (MRGAP) is a special type of GAP where each agent has more than one capacity limited resource. The aim of the problem is to minimize the total assignment cost. In this study, MRGAP problem with compliance constraints is addressed for two objectives. One of the objectives is to ensure that the loads are distributed to the agents in a balanced way, while the other is to minimize the total number of agents to which jobs are assigned. For the solution of the developed mathematical model, the weighted sum method was used and it was solved with the Dicopt solution of the GAMS package program. The operability of the proposed method is shown on the sample problem. A simulated annealing algorithm has been developed to solve large size problems. The generated test problems for the different dimensions were solved with the suggested methods and the results obtained were compared. As a result of the experiments, it was observed that more successful results were obtained with the simulated annealing method developed.