FARKLI YETENEKLERE VE ÖNCELİKLERE SAHİP AJANLARIN VE AYNI AJANA ATANMASI GEREKEN İŞLERİN OLDUĞU ÇOK KAYNAKLI GENELLEŞTİRİLMİŞ ATAMA PROBLEMİ İÇİN BİR HEDEF PROGRAMLAMA MODELİ

Yıl 2017, Cilt: 5 Sayı: 1, 75 - 90, 20.03.2017

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

Öz

Genelleştirilmiş atama problemi (GAP), kapasite kısıtları altında işlerin ajanlara atanması problemidir. GAP’ın özel bir çeşidi olan çok kaynaklı GAP (ÇK-GAP)'ta her ajanın farklı sayıda kısıtlı kaynağı vardır. Problemin amacı atamalar sonucu oluşan toplam maliyeti enküçüklemek olup her iş sadece bir ajana atanmaktadır. Bu çalışmada, farklı yeteneklere ve önceliklere sahip ajanların ve aynı ajana atanması gereken işlerin olduğu ÇK-GAP ele alınmıştır. Bu çalışmanın motivasyon kaynağı, bir buzdolabı işletmesinin plastik enjeksiyon kalıplarının yan sanayilerine atanması problemidir. Ele alınan problem için 0-1 karma tamsayılı bir hedef programlama modeli geliştirilmiştir. Geliştirilen modelin performansı farklı özelliklere sahip test problemleri kullanılarak test edilmiştir. Problemlerin çözümünde GAMS/Cplex çözücüsü kullanılmıştır. Elde edilen sonuçlar geliştirilen modelin gerçek hayat problemlerinin çözümünde başarıyla kullanılabileceğini göstermektedir.

Anahtar Kelimeler

Çok kaynaklı genelleştirilmiş atama problemi, Plastik enjeksiyon kalıplarının yan sanayilere atanması problemi; Hedef programlama

Kaynakça

• Fisher, M.L., Jaikumar, R., Van Wassenhove, L.N. 1986, “A Multiplier Adjustment Method for the Generalized Assignment Problem”, Management Science, 32, 1095-1103.
• Cohen, R., Katzir, L. and Raz, D. 2006, “An Efficient Approximation for the Generalized Assignment Problem”, Information Processing Letters, 100, 162-166.
• Martello, S. and Toth, P. 1981, “An Algorithm for the Generalized Assignment Problem”, Proceedings of the 9th IFORS Conference, Hamburg, Germany.
• Martello, S. and Toth, P. 1990, “Knapsack Problems: Algorithms and Computer Implementations”, John Wiley and Sons, Chichester, England.
• Wilson, J.M. 1997a, “A Simple Dual Algorithm for the Generalized Assignment Problem”, Journal of Heuristics, 2(4), 303-311.
• Cattrysee, D.G., Salomon, M. and Van Wassenhove, L.N. 1994, “A Set Partitioning Heuristic for the Generalized Assignment Problem”, European Journal of Operational Research, 72, 167-174.
• Lorena, L.A.N. and Narcisio, M.G. 1996, “Relaxation Heuristics for a Generalized Assignment Problem”, European Journal of Operational Research, 91, 600-610.
• Narcisio, M.G. and Lorena, L.A.N. 1999, “Lagrangean/Surrogate Relaxation for Generalized Assignment Problems”, European Journal of Operational Research, 114, 165-177.
• Haddadi, S. 1999, “Lagrangian Decomposition Based Heuristic for the Generalized Assignment Problem”, INFOR, 37(4), 392-402.
• Haddadi, S. and Ouzia, H. 2001, “An Effective Lagrangian Heuristic for the Generalized Assignment Problem”, INFOR, 39(4), 354-356.
• Trick, M.A. 1992, “A Linear Relaxation Heuristic for the Generalized Assignment Problem”, Noval Research Logistics, 39, 137-152.
• Cattrysee, D.G. 1990, “Set Partitioning Approaches to Combinatorial Optimization Problems”, PhD Thesis, Katholieke University Leuven, Department Wertuigkunde, Centrum Industrieel Beleid, Belgium.
• Osman, I.H. 1995, “Heuristics for the Generalized Assignment Problem: Simulated Annealing and Tabu Search Approaches”, OR Spectrum, 17, 211-225.
• LeBlanc, L.J., Shtub, A., Anandalingam, G. 1999, “Formulating and solving production planning problems”, European Journal of Operational Research, 112, 54-80.
• Diaz, J.A. and Fernandez, E. 2001, “A Tabu Search Heuristic for Generalized Assignment Problem”, European Journal of Operational Research, 132, 22-38.
• Higgins, A.J. 2001, “A Dynamic Tabu Search for Large-Scale Generalized Assignment Problem”, Computers & Operations Research, 28 (10), 1039-1048.
• Yagiura, M., Iwasaki, S., Ibaraki, T., Glover, F. 2004, “A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem”, Discrete Optimization, 1 (1), 87–98.
• Woodcock A. J. and Wilson J. M. 2010, “A hybrid tabu search/branch & bound approach to solving the generalized assignment problem”, European Journal of Operational Research, 207 (2), 566-578.
• Karsu, Ö. and Azizoglu, M. 2014, “Bicriteria Multiresource Generalized Assignment Problem”, Naval Research Logistics, 61, 621-636.
• Yang, Z. and Niu, Z. 2013, “Energy Saving in Cellular Networks by Dynamic RS–BS Association and BS Switching”, IEEE Transactions On Vehicular Technology, 62, 9.
• Chu, P.C. and Beasley, J.E. 1997, “A Genetic Algorithm for the Generalized Assignment Problem”, Computers and Operations Research, 24(1), 17-23.
• Wilson, J.M. 1997b, “Genetic Algorithm for the Generalized Assignment Problem”, Journal of the Operational Research Society, 48(8), 804-809.
• Lorena, L.A.N., Narciso, M.G. and Beasley, J.E. 2002, “A constructive Genetic Algorithm for the Generalized Assignment Problem”, Evolutionary Optimization.
• Liu L., Mu H., Song Y., Luo H., Li X., Wu F. 2012, “The equilibrium generalized assignment problem and genetic algorithm”, Applied Mathematics and Computation, 218, 6526-6535.
• Liu, Y.Y. and Wang, S. 2015, “A scalable parallel genetic algorithm for the Generalized Assignment Problem”, Parallel Computing, 46, 98-119.
• Li, T. and Luyuan, F. 1991, “Competition Based Neural Networks for Assignment Problems”, Journal of Computer Science and Technology, 6(4), 305-315.
• Monfred, M.A.S. and Etemadi, M. 2006, “The Impact of Energy Function Structure on Solving Generalized Assignment Problem Using Hopfield Neural Network”, European Journal of Operational Research, 18, 339-348.
• Lourenço, H.R.D. and Serra, D. 2002, “Adaptive Approach Heuristics for the Generalized Assignment Problem”, Mathware and Soft Computing, 9, 209-234.
• Özbakir, L., Baykasoğlu A., Tapkan P. 2010, “Bees algorithm for generalized assignment problem”, Applied Mathematics and Computation, 215, 3782-3795.
• Bozdoğan, A.Ö., Yılmaz, A.E. and Efe, M. 2010, “Performance Analysis of Swarm Optimization Approaches for the Generalized Assignment Problem in Multi-Target Tracking Applications”, Turk J Elec Eng & Comp Sci,18, No.6.
• Tapkan, P., Özbakır, L. and Baykasoğlu, A. 2013, “Solving Fuzzy Multiple Objective Generalized Assignment Problems Directly via Bees Algorithm and Fuzzy Ranking”, Expert Systems with Applications, 40, 892-898.
• Sharkey, T. and Romeijn H.E. 2010, “Greedy Approaches For a Class of Nonlinear Generalized Assignment Problems”, Discrete Applied Mathematics, 158, 559-572.
• Rainwater, C., Geunes J., Romeijn H. E. 2009, “The generalized assignment problem with flexible jobs”, Discrete Applied Mathematics, 157, 49-67.
• Moccia L., Cordeau J. F., Monaco M. F., Sammarra M. 2009, “A column generation heuristic for a dynamic generalized assignment problem”, Computers & Operations Research, 36, 2670-2681.
• Krumke, S.O. and Thielen, C. 2013, “The generalized assignment problem with minimum quantities”, European Journal of Operational Research, 228, 46-55.
• Zheng, F., Cheng Y., Xu Y., Liu M. 2013, “Competitive strategies for an online generalized assignment problem with a service consecution constraint”, European Journal of Operational Research, 229, 59-66.
• Shtub, A., Kogan, K. 1998, “Capacity planning by the dynamic multi-resources generalized assignment problem (DMRGAP)”, European Journal of Operational Research, 105, 91-99.
• Toktaş, B., Yen, J. W., Zabinsky Z.B. 2006, “Addressing capacity uncertainty in resource-constrained assignment problems”, Computers and Operations Research, 33(3), 724-745.
• Mitrović-Minić, S., Punnen, A. P. 2009, “Local search intensified: Very large-scale variable neighborhood search for the multi-resource generalized assignment problem”, Discrete Optimization, 6 (4), 370–377.
• Li, J.Q., Borenstein, D. and Mirchandani, P.B. 2008, “Truck Scheduling for Solid Waste Collection in the City of Porto Alegre, Brazil”, Omega, 36, 1133-1149.
• Liang, Z., Li, Y., Lim, A. and Guo, S. 2010, “Load Balancing in Project Assignment”, Computers & Operations Research, 37, 2248-2256.
• Gaudioso, M., Moccia L. and Monaco, M.F. 2010, “Repulsive Assignment Problem”, Journal of Optimization Theory and Applications, 144, 255-273.
• Beausoleil, R. and Miro, Y.V. 2013, “One-Side Oscillation Strategic Approach”, Revista de Matematica: Teoria y Aplicaciones, 20(1), 35-48.
• Zapfel, G. and Bögl, M. 2012, “Two Heuristic Solution Concepts for the Vehicle Selection Problem in Line Haul Transports”, European Journal of Operational Research, 217,448-458.
• Topcuoglu, H.R., Ucar, A. and Altin, L. 2014, “A hyper-heuristic based framework for dynamic optimization problems”, Applied Soft Computing, 19, 236-251.
• Srivastava, V. and Bullo, F. 2014, “Knapsack Problems with Sigmoid Utilities Approximation Algorithms via Hybrid Optimization”, European Journal of Operational Research, 236, 488-498.
• Gotsis A.G., Komnakos, D.I., Vouyioukas, D.D. and Constantinou, P. 2014, “Radio resource allocation algorithms for multi-service OFDMA networks: the uniform power loading scenario”, Telecommunication Systems, 56, 467-480.
• Fu, Y., Sun, J., LAi, K.K. and Leung, J.W.K. 2015, “A robust optimization solution to bottleneck generalized assignment problem under uncertainty”, Annals of Operations Research, 233, 123-133.
• Marchetti-Spaccamela, A., Rutten, C., van der Ster, S. and Wiese, A. 2015, “Assigning sporadic tasks to unrelated machines”, Math. Program., Ser. A, 152, 247-274.
• Korupolu, M., Meyerson, A., Rajaraman, R. and Tagiku, B. 2015, “Coupled and k-sided placements generalizing generalized assignment”, Math. Program., Ser. B, 154, 493-514.
• Lou, L.,Chakraborty, N. and Sycara, K. 2015, “Distributed Algorithms for Multirobot Task Assignment With Task Deadline Constraints”, IEEE Transactions on Automation Science And Engineering, Vol. 12, No. 3.
• Conti, M., Crispo, B., Diodati, D., Nurminen, J.K., Pinotti, C.M. and Teemaa, T. 2015, “Leveraging Parallel Communications for Minimizing Energy Consumption on Smartphones”, IEEE Transactions on Automation Science And Engineering, Vol. 26, No. 10.
• Bender, M., Thielen, C. and Westphal, S. 2015, “Packing items into several bins facilitates approximating the separable assignment problem”, Information Processing Letters, 115, 570-575.
• Wang, Z., Lü, Z. and Ye, T. 2016, “Multi-neighborhood local search optimization for machine reassignment problem”, Computers & Operations Research, 68, 16-29.
• Aroca, J.A., Anta, A.F., Mosteiro, M.A., Thraves, C. and Wang, L. 2016, “Power-efficient assignment of virtual machines to physical machines”, Future Generation Computer Systems, 54, 82-94.
• Avella, P., Boccia, M. and Vasilyev, I. 2010, “A Computational Study of Exact Knapsack Separation for the Generalized Assignment Problem”, Computational Optimization and Applications, 45, 543-555.
• Lee, C. and Park, S. 2011, “Chebyshev Center Based Column Generation”, Discrete Applied Mathematics, 159, 2251-2265.
• Anghinolfi, D., Paolucci, M., Sacone, S. and Siri, S. 2011, “Freight Transportation in Railway Networks with Automated Terminals A Mathematical Model and MIP Heuristic Approaches”, European Journal of Operational Research, 214, 588-594.
• Benders, J.F. and Van Nunen, J.A. 1983, “A Property of Assignment Type Mixed Linear Programming Problems”, Operations Research Letters, 2, 47-52.
• French, A.P. and Wilson J.M. 2007, “An LP-based heuristic procedure for the generalized assignment problem with special ordered sets”, Computers & Operations Research, 34, 2359-2369.
• Zhang, C.W. and Ong H.L. 2007,” An efficient solution to biobjective generalized assignment problem”, Advances in Engineering Software, 38, 50-58.
• Fisher, M.L. 1981, “The Lagrangian Relaxation Method for Solving Integer Programming Problems”, Management Science, 27(1), 1-18.
• Fisher, M.L. 2004, “The Lagrangian Relaxation Method for Solving Integer Programming Problems”, Management Science, 50(12), 1861-1871.
• Ross, G.T. and Soland, R.M. 1975, “A Branch and Bound Approach for the Generalized Assignment Problem”, Mathematical Programming, 8, 91-105.
• Guignard, M. and RosenWein, M.B. 1989, “An Improved Dual Based Algorithm for the Generalized Assignment Problem”, Operations Research, 37(4), 658-663.
• Imai, A., Nishimura, E. and Current, J. 2007, “A Lagrangian Relaxation-Based Heuristic for the Vehicle Routing with Full Container Load”, European Journal of Operational Research, 176, 87-105.
• Jeet, V. and Kutanoğlu, E. 2007, “Lagrangian Relaxation Guided Problem Space Search Heuristic for Generalized Assignment Problems”, European Journal of Operational Research, 182, 1039-1056.
• Mazzola, J.B. and Neebe, A.B. 2012, “A Generalized Assignment Model for Dynamic Supply Chain Capacity Planning”, Naval Research Logistics, 59(6),470–485.
• Posta, M., Ferland, J.A. and Michelon, P. 2012, “An Exact Method With Variable Fixing for Solving the Generalized Assignment Problem”, Computational Optimization and Applications, 52, 629-644.
• Jörnsten, K. and Nasberg, M. 1986, “A New Lagrangian Relaxation Approach to the Generalized Assignment Problem”, European Journal of Operational Research, 27, 313-323.
• Barcia, P. and Jörnsten, K. 1990, “Improved Lagrangean Decomposition: An Allpication to the Generalized Assignment Problem”, European Journal of the Operational Research, 46, 84-92.
• Amini, M.M. and Racer, M. 1994, “A Rigorous Computational Comparison of Alternative Solution Methods for the Generalized Assignment Problem”, Management Science, 40(70), 868-890.
• Yagiura, M., Yamaguchi, T and Ibaraki, T. 1999, “A Variable Depth Search Algorithm for the Generalized Assignment Problem”, In Metaheuristics: Advances and Trends in Local Search Paradigms for Optimization; Kluwer Academic Publisher Boston; MA, 459-471.
• Janak, S.L., Taylor M.S., Floudas C.A., 2006, “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.
• Alidaee, B., Gao, H. and Wang, H. 2010, “A Note on Task Assignment of Several Problems”, Computers & Industrial Engineering, 59, 1015-1018.
• Alidaee, B., Wang, H. and Landram, F. 2011, “On the Flexible Demand Assignment Problems Case of Unmanned Aerial Vehicles”, IEE Transactions on Automation Science and Engineering, 8, No.4.
• Golfarelli, M., Rizzi, S. and Turricchia, E. 2013, “Multi-Sprint Planning and Smooth Replanning An Optimization Model”, The Journal of Systems and Software, 86, 2357-2370.
• Maleki, M., Majlesinasab, N. and Sepehri, M.M. 2014, “Two new models for redeployment of ambulances”, Computers & Industrial Engineering, 78, 271-284.
• Nauss, R.M. 2003, “Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach”, INFORMS Journal on Computing, 15(3), 249-266.
• Haddadi, S. and Ouzai, H. 2004, “Effective Algorithm and Heuristic for the Generalized Assignment Problem”, European Journal of Operational Research, 153, 184-190.
• Cattrysse, D.G., Degraeve, Z. and Tistaert, J. 1998, “Solving the Generalized Assignment Problem Using Polyhedral Results”, European Journal of Operational Research, 108, 618-628.
• Albareda -Sambola, M., van der Vlerk, M.H. and Fernandez, E. 2006, “Exact Solutions to a Class of Stochastic Generalized Assignment Problems”, European Journal of Operational Research, 173(2), 465-487.
• Karsu, Ö. and Azizoglu, M. 2012, “The multi-resource agent bottleneck generalised assignment problem”, International Journal of Production Research, 50 (2), 309-324.
• Savelsbergh, M.W.P. 1997, “A Branch-and-Price Algorithm for the Generalized Assignment Problem”, Operations Research, 45, 831-841.
• Nemhauser, G.L., Savelsbergh, M.W.P. and Sigismondi, G.C. 1994, “MINTO, A Mixed Integer Optimizer”, Operations Research Letters, 15, 47-58.
• Pigatti, A., de Aragoa, M.P. and Uchoa, E. 2004, “Stabilized Branch-and-Cut-and-Price for the Generalized Assignment Problem”, Electronic Notes in Discrete Mathematics, 19, 389-395.
• Avella P., Boccia M., Vasilyev I. 2013, “A Branch-and-Cut Algorithm for the Multilevel Generalized Assignment Problem”, IEEE Access, 1, 475 - 479.
• Öncan, T. 2007, “A survey of the generalized assignment problem and its applications”, INFOR, 45 (3), 123-141.