Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli
Yıl: 2022 Cilt: 37 Sayı: 1 Sayfa Aralığı: 193 - 205 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.789915 İndeks Tarihi: 29-07-2022
Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli
Öz: Çok kaynaklı genelleştirilmiş atama problemi (MRGAP), toplam atama maliyetini enküçükleyecek şekilde ve kapasite kısıtları altında işlerin ajanlara atanması problemidir. Bu problemde her ajan birden çok kaynağa sahiptir, her görev sadece bir ajana atanmaktadır ve bir ajana birden fazla görev atanması mümkündür. MRGAP probleminde yüklerin ajanlara dengeli dağıtılması önem arz etmektedir. Literatürde ajan yüklerinin dengelenmesine yönelik olarak, en büyük ajan yükünün enküçüklenmesi amacına sahip darboğaz MRGAP ve enbüyük ajan yükü ile enküçük ajan yükü arasındaki farkın enküçüklenmesi amacına sahip dengeli atama MRGAP modelleri önerilmiştir. Bu çalışmada, yük kareleri toplamı modeli MRGAP için uyarlanmış, ayrıca yeni bir hedef programlama MRGAP modeli ve bu modelin çözümüne yönelik olarak bir matsezgisel algoritma geliştirilmiştir. Önerilen model ve algoritmanın performansları rassal türetilen test problemleri kullanılarak literatürdeki modeller ile karşılaştırılmıştır. Elde edilen çözümlerin kalitesi, enbüyük yük, değişim katsayısı ve toplam yük ölçütleri dikkate alınarak belirlenmiştir. Test sonuçları, bu üç ölçüt açısından değerlendirilmiştir. Elde edilen sonuçlar, önerilen hedef programlama modelinin ve matsezgiselin başarısını ortaya koymuştur.
Anahtar Kelime: A goal programming model for balancing agent loads in the multi-resource generalized assignment problem
Öz: The multi-resource generalized assignment problem (MRGAP) is the assignment of jobs to agents under capacity constraints to minimize the total assignment. In this problem, each agent has multiple resources, each job is assigned to only one agent, and multiple jobs can be assigned to one agent. In the MRGAP problem, it is essential to distribute the loads in balance to the agents. In the literature, for balancing agent loads, bottleneck MRGAP with the aim of minimizing the maximum agent load, and balanced assignment MRGAP models with the aim of minimizing the difference between the maximum agent load and the minimum agent load have been proposed. In this study, the sum of load squares model has been adapted for MRGAP, as well as a new goal programming MRGAP model and a matheuristic algorithm for the solution of this model are developed. The performances of the proposed model and the algorithm were compared with the models taken from the literature by using randomly derived test problems. The quality of the obtained solutions is determined by considering the maximum load, coefficient of variation and total load criteria. The test results are evaluated in terms of these three criteria. The results obtained revealed the success of the proposed goal programming model and the matheuristic algorithm.
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. Ceselli, A., Fiore, M., Premoli, M., Secci, S., Optimized assignment patterns in Mobile Edge Cloud networks Computers and Operations Research, 106, 246–259, 2019.
- 5. 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.
- 6. Wang, G., Lei, L., Integrated operations scheduling with delivery deadlines, Computers & Industrial Engineering, 85, 177–185, 2015.
- 7. 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.
- 8. 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.
- 9. Wang, J., Liu, K, Li, B., Liu, T., Li, R., Han Z., DelaySensitive multi-period computation offloading with reliability guarantees in fog networks, IEEE Transactions on Mobile Computing, 19 (9), 2062-2075, 2020.
- 10. 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.
- 11. 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.
- 12. 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.
- 13. Dörterler, M., A New Genetic algorithm with agentbased crossover for the generalized assignment problem, Journal of Information Technology and Control, 48 (3), 389-400, 2019.
- 14. 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.
- 15. Liu, Y.Y., Wang, S.A., Scalable parallel genetic algorithm for the generalized assignment problem, Parallel Computing, 46, 98-119, 2015.
- 16. Haddadi, S., Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem, 4OR, 17, 261–295, 2019.
- 17. Sethanana, K., Pitakaso, R., Improved differential evolution algorithms for solving generalized assignment problem, Expert Systems with Applications, 45, 450–459, 2016.
- 18. 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.
- 19. Shtub, A., Kogan, K., Capacity planning by the dynamic multi-resources generalized assignment problem (DMRGAP), European Journal of Operational Research, 105, 91-99, 1998.
- 20. LeBlanc, L.J., Shtub, A., Anandalingam, G., Formulating and solving production planning problems, European Journal of Operational Research, 112, 54-80, 1999.
- 21. 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.
- 22. 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.
- 23. Ö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 (A goal programming model for multi-resource generalized assignment problem that contains agents with different abilities and priorities along with jobs to be assigned to the same agents), Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji, 5 (1), 75-90, 2017.
- 24. 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.
- 25. Karsu, Ö., Azizoglu, M., The multi-resource agent bottleneck generalised assignment problem, International Journal of Production Research, 50 (2), 309-324, 2012.
- 26. Ö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.
- 27. Karsu, Ö., Azizoglu, M., Bicriteria multiresource generalized assignment problem, Naval Research Logistics, 61, 621-636, 2014.
- 28. Pentico D.W., Assignment Problem: A golden anniversary survey, European Journal of Operational Research, 176, 774-793, 2007.
- 29. Karsu, Ö., Azizoğlu, M., An exact algorithm for the minimum squared load assignment problem, Computers and Operations Research, 106, 76–90, 2019.
- 30. Akyol Özer, E., Saraç, T., MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints, An Official Journal of the Spanish Society of Statistics and Operations Research, 27, 94–124, 2019.
| APA | Ozcelik F, Saraç T (2022). Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli. , 193 - 205. 10.17341/gazimmfd.789915 |
| Chicago | Ozcelik Feristah,Saraç Tugba Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli. (2022): 193 - 205. 10.17341/gazimmfd.789915 |
| MLA | Ozcelik Feristah,Saraç Tugba Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli. , 2022, ss.193 - 205. 10.17341/gazimmfd.789915 |
| AMA | Ozcelik F,Saraç T Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli. . 2022; 193 - 205. 10.17341/gazimmfd.789915 |
| Vancouver | Ozcelik F,Saraç T Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli. . 2022; 193 - 205. 10.17341/gazimmfd.789915 |
| IEEE | Ozcelik F,Saraç T "Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli." , ss.193 - 205, 2022. 10.17341/gazimmfd.789915 |
| ISNAD | Ozcelik, Feristah - Saraç, Tugba. "Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli". (2022), 193-205. https://doi.org/10.17341/gazimmfd.789915 |
| APA | Ozcelik F, Saraç T (2022). Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 37(1), 193 - 205. 10.17341/gazimmfd.789915 |
| Chicago | Ozcelik Feristah,Saraç Tugba Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 37, no.1 (2022): 193 - 205. 10.17341/gazimmfd.789915 |
| MLA | Ozcelik Feristah,Saraç Tugba Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.37, no.1, 2022, ss.193 - 205. 10.17341/gazimmfd.789915 |
| AMA | Ozcelik F,Saraç T Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2022; 37(1): 193 - 205. 10.17341/gazimmfd.789915 |
| Vancouver | Ozcelik F,Saraç T Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2022; 37(1): 193 - 205. 10.17341/gazimmfd.789915 |
| IEEE | Ozcelik F,Saraç T "Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 37, ss.193 - 205, 2022. 10.17341/gazimmfd.789915 |
| ISNAD | Ozcelik, Feristah - Saraç, Tugba. "Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 37/1 (2022), 193-205. https://doi.org/10.17341/gazimmfd.789915 |
