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

Saraç, Tugba; ERTEN, KUMSAL; Ozcelik, Feristah

doi:10.29109/gujsc.919665

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

Kumsal ERTEN, (Eskişehir Osmangazi Üniversitesi, Mühendislik Mimarlık Fakültesi, Endüstri Mühendisliği Bölümü, Eskişehir, Türkiye)

Tuğba SARAÇ, (Eskişehir Osmangazi Üniversitesi, Mühendislik Mimarlık Fakültesi, Endüstri Mühendisliği Bölümü, Eskişehir, Türkiye)

Feriştah ÖZÇELİK (Eskişehir Osmangazi Üniversitesi, Mühendislik Mimarlık Fakültesi, Endüstri Mühendisliği Bölümü, Eskişehir, Türkiye)

Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji

1 1

Yıl: 2021 Cilt: 9 Sayı: 3 Sayfa Aralığı: 385 - 401 Metin Dili: İngilizce DOI: 10.29109/gujsc.919665 İndeks Tarihi: 29-07-2022

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

Öz:

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.

Anahtar Kelime: Load balancing Simulated annealing algorithm

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 Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

[1] Ahmed, Z.H., Performance analysis of hybrid genetic algorithms for the generalized assignment problem, IJCSNS International Journal of Computer Science and Network Security, 19 (9), 216-222, 2019.
[2] Bender, M., Thielen, C., Westphal, S., Packing items into several bins facilitates approximating the separable assignment problem, Information Processing Letters, 115, 570–575, 2015.
[3] D’Ambrosio, C., Martello, S., Monaci, M., Lower and upper bounds for the non-linear generalized assignment problem, Computers and Operations Research, 120, 104933, 2020.
[4] De Armas, L., Valdes, D., Morell, C., Bello, R., Solutions to storage spaces allocation problem for import containers by exact and heuristic methods, Computación y Sistemas, 23(1), 197–211, 2019.
[5] Dörterler, M., A New Genetic algorithm with agent-based crossover for the generalized assignment problem, Journal of Information Technology and Control, 48(3), 389-400, 2019.
[6] Dörtler, M., Bay, Ö.F., Akçayol, M.A., A modified genetic algorithm for a special case of the generalized assignment problem, Turkish Journal of Electrical Engineering & Computer Sciences, 25, 794-805, 2017.
[7] Fadaei S., Bichler, M., Generalized assignment problem: Truthful mechanism design without money, Operations Research Letters, 45, 72–76, 2017.
[8] Haddadi, S., Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem, 4OR, 17, 261–295, 2019.
[9] Litvinchev, I., Mata, M., Saucedo, J., Rangel, S., Improved lagrangian bounds and heuristics for the generalized assignment problem, Journal of Computer and Systems Sciences International, 56(5), 803– 809, 2017.
[10] Liu, Y.Y., Wang, S.A., Scalable parallel genetic algorithm for the generalized assignment problem, Parallel Computing, 46, 98-119, 2015.
[11] Luo, L., Chakraborty, N., Sycara, K., Distributed algorithms for multirobot task assignment with task deadline constraints, IEEE Transactions on Automation Science and Engineering, 12 (3), 876-888, 2015.
[12] Valentin, E., de Freitas, R., Barreto, R., Towards optimal solutions for the low power hard real-time task allocation on multiple heterogeneous processors, Science of Computer Programming, 165, 38–53, 2018.
[13] Munapo, E., Lesaoana, M., Nyamugure, P., Kumar, S., A transportation branch and bound algorithm for solving the generalized assignment problem, International Journal of System Assurance Engineering and Management, 6(3), 217–223, 2015.
[14] Murthy, I., Ransbotham, S., A new extended formulation of the Generalized Assignment Problem and some associated valid inequalities, Discrete Applied Mathematics, 271, 119–143, 2019.
[15] Dauzère-Pérès, S., Hassoun, M., Sendon, A., A Lagrangian heuristic for minimising risk using multiple heterogeneous metrology tools, International Journal of Production Research, 58(4), 1222-1238, 2020.
[16] Rawitz, D., Voloshin, A., Flexible allocation on related machines with assignment restrictions, Discrete Applied Mathematics, 250, 309–321, 2018.
[17] Sethanana, K., Pitakaso, R., Improved differential evolution algorithms for solving generalized assignment problem, Expert Systems with Applications, 45, 450–459, 2016.
[18] Singh, S.K., Rani, D, A branching algorithm to solve binary problem in uncertain environment: an application in machine allocation problem, OPSEARCH, 56, 1007–1023, 2019.
[19] Wang, J., Liu, K, Li, B., Liu, T., Li, R., Han Z., Delay-Sensitive multi-period computation offloading with reliability guarantees in fog networks, IEEE Transactions on Mobile Computing, 19(9), 2062- 2075, 2020.
[20] Ceselli, A., Fiore, M., Premoli, M., Secci, S., Optimized assignment patterns in Mobile Edge Cloud networks Computers and Operations Research, 106, 246–259, 2019.
[21] Masoud, M., Elhenawy, M., Almannaa, M.H., Liu, S.Q., Glaser, S., Rakotonirainy, A., Heuristic approaches to solve e-scooter assignment problem, IEEE Access, 7, 175093-175105, 2019.
[22] Wang, G., Lei, L., Integrated operations scheduling with delivery deadlines, Computers & Industrial Engineering, 85, 177–185, 2015.
[23] Yang, L., Yao, H., Wang, J., Jiang, C., Benslimane, A., Liu Y., Multi-UAV-Enabled load-balance mobile-edge computing for IoT networks, IEEE Internet of Things Journal, 7(8), 6898-6908, 2020.
[24] Fu, Y., Sun, J., Lai, K.K, Leung, J.W.K., A robust optimization solution to bottleneck generalized assignment problem under uncertainty, Annals of Operations Research, 233,123–133, 2015.
[25] Wu, W., Iori M., Martello, S., Yagiura, M., Exact and heuristic algorithms for the interval min-max regret generalized assignment problem, Computers & Industrial Engineering, 125, 98–110, 2018.
[26] Amorim, J.C., Alves, V., de Freitas, E. P., Assessing a swarm-GAP based solution for the task allocation problem in dynamic scenarios, Expert Systems with Applications, 152, 113437, 2020.
27] Tanganelli, G., Mingozzi, E., Energy-Efficient IoT service brokering with quality of service support, Sensors, 19, 693, 2019.
[28] Xu, Y., Wang, X., Sun, T., Heuristic routing algorithm toward scalable distributed generalized assignment problem, Soft Computing, 22, 845–859, 2018.
[29] Kat B., An algorithm and a decision support system for the panelist assignment problem: The case of TUBITAK, Journal of the Faculty of Engineering and Architecture of Gazi University, 36(1), 69-87, 2021.
[30] LeBlanc, L.J., Shtub, A., Anandalingam, G., Formulating and solving production planning problems, European Journal of Operational Research, 112, 54-80, 1999.
[31] Osman, I.H., “Heuristics For The Generalized Assignment Problem: Simulated Annealing And Tabu Search Approaches”, OR Spectrum, 17, p. 211-225, 1995
[32] Zhang, Z., Li, C., Wang, M.,Wu, Q., A Hybrid Multi-Objective Evolutionary Algorith Operating Room Assignment Problem, Journal of Medical Imaging and Health Informatics, 7(1),47-54, 2017.
[33] Shtub, A., Kogan, K., Capacity planning by the dynamic multi-resources generalized assignment problem (DMRGAP), European Journal of Operational Research, 105, 91-99, 1998.
[34] 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.
[35] 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.
[36] Ö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
[37] 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.
[38] Karsu, Ö., Azizoglu, M., The multi-resource agent bottleneck generalised assignment problem, International Journal of Production Research, 50 (2), 309-324, 2012.
[39] Ö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.
[40] Karsu, Ö., Azizoglu, M., Bicriteria multiresource generalized assignment problem, Naval Research Logistics, 61, 621-636, 2014.
[41] Fisher, M. L., Jaikumar, R., Van Wassenhove, L. N., A multiplier adjustment method for the generalized assignment problem, Management Science, 32(9), 1095-1103, 1986.
[42] Ehrgott, M., Multicriteria Optimization, 2nd ed., 323 p, 2005.
[43] Kendall, G., 2000, “Artificial Intelligence Methods”, http://www.cs.nott.ac.uk/~pszgxk/aim/, Erişim tarihi: 21.06.2021.

APA	ERTEN K, Saraç T, Ozcelik F (2021). A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint. , 385 - 401. 10.29109/gujsc.919665
Chicago	ERTEN KUMSAL,Saraç Tugba,Ozcelik Feristah A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint. (2021): 385 - 401. 10.29109/gujsc.919665
MLA	ERTEN KUMSAL,Saraç Tugba,Ozcelik Feristah A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint. , 2021, ss.385 - 401. 10.29109/gujsc.919665
AMA	ERTEN K,Saraç T,Ozcelik F A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint. . 2021; 385 - 401. 10.29109/gujsc.919665
Vancouver	ERTEN K,Saraç T,Ozcelik F A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint. . 2021; 385 - 401. 10.29109/gujsc.919665
IEEE	ERTEN K,Saraç T,Ozcelik F "A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint." , ss.385 - 401, 2021. 10.29109/gujsc.919665
ISNAD	ERTEN, KUMSAL vd. "A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint". (2021), 385-401. https://doi.org/10.29109/gujsc.919665

APA	ERTEN K, Saraç T, Ozcelik F (2021). A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint. Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji, 9(3), 385 - 401. 10.29109/gujsc.919665
Chicago	ERTEN KUMSAL,Saraç Tugba,Ozcelik Feristah A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint. Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji 9, no.3 (2021): 385 - 401. 10.29109/gujsc.919665
MLA	ERTEN KUMSAL,Saraç Tugba,Ozcelik Feristah A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint. Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji, vol.9, no.3, 2021, ss.385 - 401. 10.29109/gujsc.919665
AMA	ERTEN K,Saraç T,Ozcelik F A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint. Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji. 2021; 9(3): 385 - 401. 10.29109/gujsc.919665
Vancouver	ERTEN K,Saraç T,Ozcelik F A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint. Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji. 2021; 9(3): 385 - 401. 10.29109/gujsc.919665
IEEE	ERTEN K,Saraç T,Ozcelik F "A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint." Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji, 9, ss.385 - 401, 2021. 10.29109/gujsc.919665
ISNAD	ERTEN, KUMSAL vd. "A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint". Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji 9/3 (2021), 385-401. https://doi.org/10.29109/gujsc.919665