A multi-start iterated tabu search algorithm for the multi-resource agent bottleneck generalized assignment problem
DOI:
https://doi.org/10.11121/ijocta.01.2020.00796Keywords:
Multi- start iterated local search, Multi- resource bottleneck generalised assignment problem, Agent qualifications, Integer linear programming modelAbstract
In this study, a multi-resource agent bottleneck generalized assignment problem (MRBGAP) is addressed. In the bottleneck generalized assignment problem (BGAP), more than one job can be assigned to an agent, and the objective function is to minimize the maximum load over all agents. In this problem, multiple resources are considered and the capacity of the agents is dependent on these resources and it has minimum two indices. In addition, agent qualifications are taken into account. In other words, not every job can be assignable to every agent. The problem is defined by considering the problem of assigning jobs to employees in a firm. BGAP has been shown to be NP- hard. Consequently, a multi-start iterated tabu search (MITS) algorithm has been proposed for the solution of large-scale problems. The results of the proposed algorithm are compared by the results of the tabu search (TS) algorithm and mixed integer linear programming (MILP) model.
Downloads
References
Pentico, D.W. (2007). Assignment problems: A golden anniversary survey. European Journal of Operational Research, 176, 774- 793.
Mazzola, J. B., & Wilcox, S.P. (2001). Heuristics for the multi- resource generalized assignment problem. Naval Research Logistics, 48, 468- 483.
Karsu, Ö., & Azizoğlu, M. (2012). The multi- resource agent bottleneck generalised assignment problem. International Journal of Production Research, 5(2), 309- 324.
Ross, G. T. (1975). A branch and bound algorithm for the generalized assignment problem. Mathematical Programming, 8, 91- 103.
Posta, M., Ferland, J.A., & Michelon, P. (2012). An exact method with variable fixing for solving the generalized assignment problem. Computational Optimization and Applications, 52, 629- 644.
Avella, P., Boccia, M., & Vasilyev, I. (2010). A computational study of exact knapsack separation for the generalized assignment problem. Computational Optimization and Applications, 45, 543- 555.
Savelsbergh, M. (1997). A branch- and- price- algorithm for the generalized assignment problem. Operations Research, 831- 841.
Pigatti, A., Poggi, M., & Uchoa, E. (2005). Stabilized branch- and- cut- and- price for the generalized assignment problem. Electronic Notes in Discrete Mathematics, 19, 389- 395.
Öncan, T., Şuvak, Z., Akyüz, M. H., & Altınel, İ. K. (2019). Assignment problem with conflicts. Computers and Operations Research (In press).
Wu, W., Iori, M., Martello, S., & Yagiura, M. (2018). Exact and heuristic algorithms for the interval min- max regret generalized assignment problem. Computers and Industrial Engineering, 125, 98- 110.
Öncan, T. (2007). A survey of the generalized assignment problem and its applications. Information Systems and Operational Research, 45 (3), 123- 141.
Higgins, A. J. (2001). A dynamic tabu search for large- scale generalised assignment problems. Computers and Operations Research, 28, 1039- 1048.
Diaz, J. A., & Fernandez, E. (2001). A tabu search heuristic for the generalized assignment problem. European Journal of Operational Research, 132, 22- 38.
Osman, İ. (1995). Heuristics for the generalized assignment problem: simulated annealing and tabu search approaches. Operations Research- Spektrum, 17, 211- 225.
Chu, P. L., & Beasley, J. E. (1997). A genetic algorithm for the generalized assignment problem. Computers and Operations Research, 24 (1), 17- 23.
Ozbakır, L., Baykasoğlu, A., & Tapkan, P. (2010). Bees algorithm for generalized assignment problem. Applied Mathematics and Computation, 11, 3782- 3795.
Jeet, V., & Kutanoglu, E. (2007). Lagrangian relaxation guided problem space search heuristics for generalized assignment problem. European Journal of Operational Research, 182 (3), 1039- 1056.
Litvinchev, I., Mata, M., Rangel, S., & Saucedo, J. (2010). Lagrangian heuristic for a class of the generalized assignment problems. Computers and Mathematics with Applications, 60 (4), 1115- 1123.
French, A. P., & Wilson, J. M. (2007). An LP- based heuristic procedure for the generalized assignment problem with special ordered sets. Computers and Operations Research, 34 (8), 2359- 2369.
Souza, D. S., Santos H. G., & Coelho, I. M. (2017). A hybrid heuristic in GPU- CPU based on scatter search for the generalized assignment problem. Procedia Computer Science, 108, 1404- 1413.
Sethanan, K., & Pitakaso, R. (2016). Improved differential evolution algorithms for solving generalized assignment problem. Expert Systems with Applications, 45, 450- 459.
Liu, Y. Y., & Wang, S. (2015).A scalable parallel genetic algorithm for the generalized assignment problem. Parallel Computing, 46, 98- 119.
Degroote, H., Velarde, J., & Causmaecker, P. (2018). Applying algorithm selection- a case study for the generalized assignment problem. Electric Notes in Discrete Mathematics, 69, 205- 212.
Chakravarthy, V. K., Ramana, V., & Umashankar, C. (2018). Investigation of task bottleneck generalized assignment problems in supply chain optimization using heuristic techniques. IOSR Journal of Business and Management, 20 (5), 41- 47.
Fadaei, S., & Bichler, M. (2017). Generalized assignment problem: truthful mechanism design without money. Operations Research Letters, 45 (1), 72-76
Sahni, S., & Gonzalez, T. (1976). P-complete approximation problems. Journal of the Association for Computing Machinery, 23, 556- 565.
Yagiura, M., Komiya, A., Kojima, K., Nonobe, K., Nagamochi, H., Ibaraki, T., & Glover, F. (2007). A path- relinking approach for the multi- resource generalized quadratic assignment problem. Engineering stochastic local search algorithms, designing, implementing and analyzing effective heuristics, 4638, 121- 135.
Gavish, B., & Pirkul, H. (1991). Algorithms for the multi- resource generalized assignment problem. Management Science, 37 (6).
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, 87- 98.
Mitrovic- Minic, S., & Punnen, A. (2009). Local search intensified: Very large scale variable neighborhood search for the multi- resource generalized assignment problem. Discrete Optimization, 6, 370- 377.
Moussavi, S. E., Mahdjoub, M., & Grunder, O. (2018). A hybrid heuristic algorithm for the sequencing generalized assignment problem in an assembly line. IFAC- Papers OnLine, 51(2), 695-700.
Qin, T., Peng, B., Benlic, U., Cheng, T. C. E., Wang, Y., & Lü, Z. (2015). Iterated local search based on multi- type perturbation for single- machine earliness/ tardiness scheduling. Computers and Operations Research, 61, 81- 88.
Ibaraki, T., Imahori, S., Nonobe, K., Sobue, K., Uno, T., & Yagiura, M. (2008). An iterated local search algorithm for the vehicle routing problem with convex time penalty functions. Discrete Applied Mathematical, 156 (11), 2050- 2069.
Subramanian, A., Drummond, L. M. D. A., Bentes, C., Ochi, L. S., & Farias, R. (2010). A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers and Operations Research, 37 811), 1899- 1911.
Penna, P. H. V., Subramanian, A., & Ochi, L. S. (2013). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 19 (2), 201- 232.
Michallet, J., Prins C., Amodeo, L., Yalaoui, F., & Vitry, G. (2014). Multi- start iterated local search for the periodic vehicle routing problem with time Windows and time spread constraints on services. Computers and Operations Research, 41, 196- 207.
Stützle, T. (2006). Iterated local search for the quadratic assignment problem. European journal of Operations Research, 174 (3), 1519- 1539.
Avcı, M., & Topaloglu, S. (2017). A multi- start iterated local search algorithm for the generalized quadratic multiple knapsack problem. Computers and Operations Research, 83, 54- 65.
Guan, J., Lin, G., & Feng, H. (2018). A multi- start iterated local search algorithm for the uncapacitated single allocation hub location problem. Applied Soft Computing, 73, 230- 241
Meignan, D., & Knust, S. (2019). A neutrality- based local search for shift scheduling optimization and interactive reoptimization. European Journal of Operational Research, 279 (2), 320- 334.
Mozdgir, A., Mahdavi, I., Badeleh, I. S., & Solimanpur, M. (2013). Using the Taguchi method to optimize the differential evolution algorithm parameters for minimizing the workload smoothness index in simple assembly line balancing. Mathematical and Computer Modelling, 57 (1-2), 137- 151.
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
