A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint

Abstract

The multi-resource generalized assignment problem (MRGAP) is an assignment problem in which each agent has more than one capacity-constrained resource. Although each agent cannot perform each job in real life, in the MRGAP literature it is generally assumed that each job can be assigned to each agent. In addition, working with as few agents as possible can create significant advantages, as each new agent creates audit tracking difficulties and additional costs. For this reason, in this study, the MRGAP problem, in which eligibility constraints are taken into account, has been addressed in a bi-objective manner. The objectives are to minimize the total load squares and the total number of agents. The objective of minimizing the total number of agents has been discussed for the first time in the MRGAP literature. These two objectives considered were scalarized by using the weighted sum method. A simulation annealing algorithm has been developed to solve large-scale problems. Randomly generated test problems were solved with the proposed methods and the obtained results were compared.

Keywords

• Generalized assignment problems
• Simulated annealing algorithm
• Load balancing

Uygunluk Kısıtlı Çok Kaynaklı Genelleştirilmiş Atama Problemi İçin Bir Tavlama Benzetimi Algoritması

Öz

Çok kaynaklı genelleştirilmiş atama problemi (ÇKGAP), her ajanın birden fazla kapasite kısıtlı kaynağının olduğu bir atama problemidir. Gerçek hayatta ajanların her işi gerçekleştiremediği durumlarla karşılaşılmasına rağmen, ÇKGAP literatüründe genellikle her işin her ajana atanabildiği varsayılmaktadır. Ayrıca, her yeni ajanın denetleme, izleme güçlüğü ve ek maliyetler yaratması nedeniyle, mümkün olduğunca az ajanla çalışmak ciddi avantajlar yaratabilmektedir. Bu nedenle bu çalışmada, uygunluk kısıtlarının dikkate alındığı ÇKGAP problemi iki amaçlı olarak ele alınmıştır. Amaçlar, yük kareleri toplamının toplam ajan sayısının enküçüklenmesidir. Toplam ajan sayısının enküçüklenmesi amacı ÇKGAP literatürde ilk kez ele alınmıştır. Dikkate alınan iki amaç, ağırlıklı toplam yöntemi kullanılarak birleştirilmiştir. Büyük boyutlu problemlerin çözümü için bir tavlama benzetimi algoritması geliştirilmiştir. Rassal olarak türetilen test problemleri, önerilen yöntemler ile çözülmüş ve elde edilen sonuçlar karşılaştırılmıştır.

Anahtar Kelimeler

• Genelleştirilmiş atama problemi
• Tavlama benzetimi
• Yük dengeleme

Kaynakça

1. [1] Shtub, A., Kogan, K., Capacity planning by the dynamic multi-resources generalized assignment problem (DMRGAP), European Journal of Operational Research, 105, 91-99, 1998.
2. [2] LeBlanc, L.J., Shtub, A., Anandalingam, G., Formulating and solving production planning problems, European Journal of Operational Research, 112, 54-80, 1999.
3. [3] Yagiura, M., Iwasaki, S., Ibaraki, T., Glover, F., A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem, Discrete Optimization, 1 (1), 87–98, 2004.
4. [4] Mitrović-Minić, S., Punnen, A. P., Local search intensified: Very large-scale variable neighborhood search for the multi-resource generalized assignment problem, Discrete Optimization, 6 (4), 370–377, 2009.
5. [5] Özçelik, F., Saraç, T., Farklı yeteneklere ve önceliklere sahip ajanların ve aynı ajana atanması gereken işlerin olduğu çok kaynaklı genelleştirilmiş atama problemi için bir hedef programlama modeli, Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji, 5 (1) , 75-90, 2017.
6. [6] Janak, S.L., Taylor M.S., Floudas C.A., Novel and effective integer optimization approach for the NSF panel-assignment problem: A multiresource and preference-constrained generalized assignment problem, Industrial & Engineering Chemistry Research, 45, 258-265, 2006.
7. [7] Karsu, Ö., Azizoglu, M., The multi-resource agent bottleneck generalised assignment problem, International Journal of Production Research, 50 (2), 309-324, 2012.
8. [8] Özçelik F., Saraç T., The bottleneck multi resource generalised assignment problem with agent and resources eligibility restrictions, International Symposium for Production Research, Vienna, Austria, 13-15 September 2017.

9. [9] Karsu, Ö., Azizoglu, M., Bicriteria multiresource generalized assignment problem, Naval Research Logistics, 61, 621-636, 2014.
10. [10] Hasani, K., Kravchenko, S. A., Werner, F., 2014, Simulated annealing and genetic algorithms for the two machine scheduling problem with a single server, International Journal of Production Research, 52 (13), 3778- 3792.