Stochastic Bottleneck Multi-Resource Generalized Assignment Problem

Year 2024, Volume: 27 Issue: 2, 769 - 775, 27.03.2024

Tuğba Saraç , Feriştah Özçelik

https://doi.org/10.2339/politeknik.1070424

Abstract

The bottleneck multi-resource generalized assignment problem (B-MRGAP) is the assignment of jobs to capacitated resources (periods) of agents to minimize the maximum agent load. The problem of assigning the products (tasks) that a firm has to supply to its sub-industries considering more than one period is an example of B-MRGAP. In this problem, any change in product demands will also change the resource consumption amounts of the tasks in the sub-industries. Since changes in production quantities are common in many sectors, handling resource consumption quantities as stochastic rather than deterministic will lead to more realistic solutions. In this study, resource consumption amounts in B-MRGAP are handled as stochastic. To solve this problem, a two-stage stochastic programming model has been developed. The performance of the proposed method is demonstrated by using randomly generated test problems. When the test results were examined, it was seen that even in small-sized problems, handling the problem stochastically made a contribution. In addition, it was revealed that the contribution increased as the number of agents, the number of tasks, and the resource consumption variability increased.

Keywords

Multi-Resource Generalized Assignment Problem (MRGAP), Two-stage stochastic programming, Stochastic resource consumption quantities

Stokastik Darboğaz Çok Kaynaklı Genelleştirilmiş Atama Problemi

Abstract

Darboğaz çok kaynaklı genelleştirilmiş atama problemi (B-MRGAP) görevlerin, en büyük ajan yükünü enküçükleyecek şekilde ajanların kapasiteli kaynaklarına (dönemlerine) atanması problemidir. Bir firmanın temin etmesi gereken ürünleri (görevleri), birden çok dönemi göz önünde bulunduracak şekilde yan sanayilerine ataması problemi B-MRGAP’a bir örnektir. Bu problemde, talep edilen ürün miktarlarındaki her türlü değişim, görevlerin yan sanayilerdeki kaynak tüketim miktarlarını da değiştirecektir. Pek çok sektörde, üretim miktarlarının değişmesi sık yaşanan bir durum olduğundan kaynak tüketim miktarlarının deterministik değil, stokastik ele alınması daha gerçekçi çözümlere ulaşılmasını sağlayacaktır. Bu çalışmada B-MRGAP’da kaynak tüketim miktarları stokastik olarak ele alınmıştır. Bu problemin çözümü için iki aşamalı stokastik programlama modeli geliştirilmiştir. Önerilen yöntemin performansı rassal türetilen test problemleri kullanılarak gösterilmiştir. Test sonuçları incelendiğinde küçük boyutlu problemlerde bile, problemi stokastik ele almanın katkı sağladığı görülmüştür. Ayrıca ajan sayısı, görev sayısı ve kaynak tüketimi değişkenliği arttıkça sağlanan katkının da arttığı ortaya konmuştur.

Keywords

Çok Kaynaklı Genelleştirilmiş Atama Problemi (MRGAP), İki aşamalı stokastik programlama, Stokastik kaynak tüketim miktarları

References

• [1] Eren T., Koçtepe S. and Cürebal A., “Hedef Programlama Yöntemi ile Akaryakıt İstasyonları Tanıtımı için Personel Çizelgeleme Problemi”, Politeknik Dergisi, 25(3): 921 – 932, (2022).
• [2] Kuğu S., Yolcan O.O. and Köse R., “Kondenser Üretim Hattında Arena16.1 Destekli Hat Dengeleme Çalışması Yapılması”, Politeknik Dergisi, *(*): *, (*).
• [3] Kaymaz E. ve Çavdur F., “Montaj hattı dengelemede yeniden işleme istasyonlarının paralel görevler için kullanımının matematiksel programlama ve simülasyon ile analizi”, Politeknik Dergisi, 25(1): 205-222, (2022).
• [4] Fu Y, Sun J, Lai K. K. and Leung J. W. K., “A robust optimization solution to bottleneck generalized assignment problem under uncertainty”, Annals of Operations Research, 233: 123–133, (2015).
• [5] Kogan K., Khmelnitsky E. and Ibaraki T., “Dynamic Generalized Assignment Problems with Stochastic Demands and Multiple Agent–Task Relationships”, Journal of Global Optimization, 31, 17–43, (2005).
• [6] Morton D.P., Bard J.F. and Wang Y.M., “Solving a stochastic generalized assignment problem with branch and price”, Computational biology: new research, 99-128, (2009).
• [7] Albareda-Sambola M., van der Vlerk M.H. and Fernandez E. “Exact solutions to a class of stochastic generalized assignment problems”, European Journal of Operational Research, 173 (2): 465-487, (2006).
• [8] Sarin S.C., Sherali H.D. and Kim S.K., “A branch-and-price approach for the stochastic generalized assignment problem”, Naval Research Logistics, 61 (2): 131-143, (2014).
• [9] Singh S.K. and Rani D., “A branching algorithm to solve binary problem in uncertain environment: an application in machine allocation problem”. OPSEARCH, 56: 1007–1023, (2019).
• [10] Toktas B., Yen J.W. and Zabinsky Z.B., “Addressing capacity uncertainty in resource-constrained assignment problems”, Computers & Operations Research, ‏ 33(3): 724-745, (2006).
• [11] Yang F. and Chakraborty N., “Algorithm for Multi-Robot Chance-Constrained Generalized Assignment Problem with Stochastic Resource Consumption”, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 4329-4336, (2020).
• [12] Shtub A. and Kogan, K., “Capacity planning by the dynamic multi-resources generalized assignment problem (DMRGAP)”, European Journal of Operational Research, 105: 91-99, (1998).
• [13] LeBlanc L.J. and Shtub A., Anandalingam G., “Formulating and solving production planning problems”, European Journal of Operational Research, 112: 54-80, (1999).
• [14] Yagiura M., Iwasaki S., Ibaraki T. and Glover, F., “A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem”, Discrete Optimization, 1 (1): 87–98, (2004).
• [15] Mitrović-Minić S. and 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).
• [16] Özçelik F. ve 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).
• [17] Janak S.L., Taylor M.S. and 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).
• [18] Karsu Ö. and Azizoglu M., “The multi-resource agent bottleneck generalised assignment problem”, International Journal of Production Research, 50 (2): 309-324, (2012).
• [19] Özçelik F. and 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).
• [20] Karsu Ö. and Azizoglu M., “Bicriteria multiresource generalized assignment problem”, Naval Research Logistics, 61: 621-636, (2014).
• [21] Özçelik F. and Saraç T. “Çok kaynaklı genelleştirilmiş atama probleminde ajan yüklerinin dengelenmesi için bir hedef programlama modeli”. Journal of the Faculty of Engineering and Architecture