Variable neighborhood search for maximum diverse grouping problem
DOI:
https://doi.org/10.2298/YJOR121223003UKeywords:
combinatorial optimization, maximum diverse grouping, metaheuristics, variable neighborhood searchAbstract
This paper presents a general variable neighborhood search (GVNS) heuristic for solving the maximum diverse grouping problem. Extensive computational experiments performed on a series of large random graphs as well as on several instances of the maximum diversity problem taken from the literature show that the results obtained by GVNS consistently outperform the best heuristics from the literature.References
Arani, T. and Lotfi, V., “A three phased approach to final exam scheduling”, IIE Transactions, 21 (1989) 86-96.
Bhadury, J., Mighty, E. J. and Damar, H., “Maximizing workforce diversity in project teams: A network flow approach”, Omega, 28 (2000) 143–153.
Carrizosa, E., Mladenović, N. and Todosijević, R., “Sum-of-Squares Clustering on Networks”, Yugoslav Journal Of Operations Research, 21 (2011) 157-161.
Chen, C. C., “Placement and partitioning methods for integrated circuit layout”, Ph.D. Dissertation, EECS Department, University of California, Berkeley (1986).
Chen, Y., Fan, Z. P., Ma, J. and Zeng, S., “A hybrid grouping genetic algorithm for reviewer group construction problem”, Expert Systems with Applications, 38 (2011) 2401-2411.
Desrosiers, J., Mladenović, N. and Villeneuve, D., “Design of balanced MBA student teams”, Journal of Operational Research Society, 56 (2005) 60-66.
Falkenauer, E., Genetic Algorithms for Grouping Problems, Wiley: New York (1998).
Fan, Z. P., Chen, Y., Ma, J. and Zeng, S., “A hybrid genetic algorithmic approach to the maximally diverse grouping problem”, Journal of the Operational Research Society, 62 (2011) 92-99.
Feo, T., Goldschmidt, O. and Khellaf, M., “One-half approximation algorithms for the k-partition problem”, Operations Research, 40 (1992) S170-S173.
Feo, T. and Khellaf, M., “A class of bounded approximation algorithms for graph partitioning”, Networks, 20 (1990) 181-195.
Gallego, M., Laguna, M., Martí, R., and Duarte, A., “Tabu search with strategic oscillation for the maximally diverse grouping problem”, Journal of the Operational Research Society, 64 (5) 724-734.
Glover, F., Kuo, C. C. and Dhir, K. S., “Heuristic algorithms for the maximum diversity problem”, Journal of Information and Optimization Sciences, 19(1) (1998) 109–132.
Hettich, S. and Pazzani, M. J., “Mining for element reviewers: Lessons learned at the National Science Foundation”, in: Proceedings of KDD’06, ACM: New York, NY, 862–871.
Ilić, A., Urošević, D., Brimberg, J. and Mladenović, N., “A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem”, European Journal of Operational Research, 206 (2010) 289-300.
Kral, J., “To the problem of segmentation of a program”, Information Processing Machines, 2 (1965) 116-127.
Lotfi, V. and Cerveny, R., “A final exam scheduling package”, Journal of the Operational Research Society, 42 (1991) 205-216.
Mingers, J. and O’Brien, F. A., “Creating students groups with similar characteristics: a heuristic approach”, Omega, 23 (1995) 313-321.
Mladenović, N., Todosijević, R. and Urošević, D., “An Efficient General Variable Neighborhood Search for Large Traveling Salesman Problem With Time Windows”, Yugoslav Journal Of Operations Research, 22 (2012).
Mladenović, N., Urošević, D., Perez-Brito, D. and Garcia-Gonzalez, C. G., “Variable neighbourhood search for bandwidth reduction”, European Journal of Operational Research, 200 (2010) 14-27.
O’Brien, F. A. and Mingers, J., “The equitable partitioning problem: a heuristic algorithm applied to the allocation of university student accommodation”, Warwick Business School, Research Paper no. 187 (1995).
Weitz, R. R. and Jelassi, M. T., “Assigning students to groups: a multi‐criteria decision support system approach”, Decision Sciences, 23(3) (1992) 746-757.
Weitz, R. R. and Lakshminarayanan, S., “On a heuristic for the final exam scheduling problem”, Journal of the Operational Research Society, 47 (4) (1996) 599-600.
Weitz, R. R. and Lakshminarayanan, S., “An empirical comparison of heuristic and graph theoretic methods for creating maximally diverse groups, VLSI design, and exam scheduling”, Omega, 25 (4) (1997) 473-482.
Weitz, R. R. and Lakshminarayanan, S., “An empirical comparison of heuristic methods for creating maximally diverse groups”, Journal of the Operational Research Society, 49 (6) (1998) 635-646.
Downloads
Published
Issue
Section
License
Copyright (c) 2014 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
