Skip to main content
SpringerLink
Log in

A hybrid genetic algorithmic approach to the maximally diverse grouping problem

  • Theoretical Paper
  • Published:
Journal of the Operational Research Society

An Erratum to this article was published on 23 June 2010

Abstract

The maximally diverse grouping problem (MDGP) is a NP-complete problem. For such NP-complete problems, heuristics play a major role in searching for solutions. Most of the heuristics for MDGP focus on the equal group-size situation. In this paper, we develop a genetic algorithm (GA)-based hybrid heuristic to solve this problem considering not only the equal group-size situation but also the different group-size situation. The performance of the algorithm is compared with the established Lotfi–Cerveny–Weitz algorithm and the non-hybrid GA. Computational experience indicates that the proposed GA-based hybrid algorithm is a good tool for solving MDGP. Moreover, it can be easily modified to solve other equivalent problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3

Similar content being viewed by others

References

  • Aarts E and Lenstra JK (2003). Local Search in Combinatorial Optimization . Princeton University Press: New Jersey.

    Google Scholar 

  • Arani T and Lotfi V (1989). A three phased approach to final exam scheduling . IIE T 21: 86–96.

    Article  Google Scholar 

  • Azimi ZN (2005). Hybrid heuristics for examination timetabling problem . Appl Math C 163: 705–733.

    Article  Google Scholar 

  • Baker BM and Benn C (2001). Assigning pupils to tutor groups in a comprehensive school . J Opl Res Soc 52: 623–629.

    Article  Google Scholar 

  • Baker KR and Powell SG (2002). Methods for assigning students to groups: A study of alternative objective functions . J Opl Res Soc 53: 397–404.

    Article  Google Scholar 

  • Bhadury J, Mighty EJ and Damar H (2000). Maximizing workforce diversity in project teams: A network flow approach . Omega 28: 143–153.

    Article  Google Scholar 

  • Bock F (1958). An algorithm for solving ‘traveling salesman' and related network optimization problems. Talk given at the 14th ORSA Meeting, St. Louis, 23 October, 1958.

  • Croes GA (1958). A method for solving traveling salesman problems . Operns Res 6: 791–812.

    Article  Google Scholar 

  • Davis L (1985). Job shop scheduling with genetic algorithms. In: Grenfenstette JJ (ed). Proceedings of the First International Conference on Genetic Algorithms. L. Erlbaum Associates: Hillsdale, NJ, pp 136–140.

  • Davis L and Steenstrup M (1987). Genetic algorithms and simulated annealing: An overview . In: Davis L (ed). Genetic Algorithm and Simulated Annealing. Morgan Kaufmann Publishers: San Mateo, CA, pp. 1–11.

    Google Scholar 

  • Etiler O, Toklu B, Atak M and Wilson J (2004). A genetic algorithm for flow shop scheduling problems . J Opl Res Soc 55: 830–835.

    Article  Google Scholar 

  • Falkenauer E (1998). Genetic Algorithms for Grouping Problems . Wiley: New York.

    Google Scholar 

  • Feo T and Khellaf M (1990). A class of bounded approximation algorithms for graph partitioning . Networks 20: 181–195.

    Article  Google Scholar 

  • Feo T, Goldschmidt O and Khellaf M (1992). One-half approximation algorithms for the k-partition problem . Opns Res 40(1): 170–173.

    Article  Google Scholar 

  • Gen M and Cheng R (1997). Genetic Algorithms and Engineering Design . Wiley: New York.

    Google Scholar 

  • Goldberg DE (1989). Genetic Algorithms in Search, Optimization and Machine Learning . Addison-Wesley: MA.

    Google Scholar 

  • Gorges-Schleuter M (1989). ASPARAGOS: An asynchronous parallel genetic optimization strategy. In: Schaffer J (ed). Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann Publishers: San Mateo, CA, pp 422–427.

  • Hettich S and Pazzani MJ (2006). Mining for element reviewers: Lessons learned at the national science foundation. In: Proceedings of the KDD'06. ACM: New York, NY, pp 862–871.

  • Holland JH (1975). Adaptation in Natural and Artificial Systems . University of Michigan Press: Ann Arbor, USA.

    Google Scholar 

  • Lotfi V and Cerveny R (1991). A final-exam-scheduling package . J Opl Res Soc 42: 205–216.

    Article  Google Scholar 

  • Miller J, Potter W, Gandham R and Lapena C (1993). An evaluation of local improvement operators for genetic algorithms . IEEE T Syst Man Cybern 23: 1340–1351.

    Article  Google Scholar 

  • Mühlenbein H (1992). How genetic algorithms really work: Part I. Mutation and hill-climbing . In: Männer R and Manderick B (eds). Parallel Problem Solving from Nature: PPSN II. Elsevier Science Publishers: North-Holland, pp. 15–26.

    Google Scholar 

  • Shi G (1997). A genetic algorithm applied to a classic job-shop scheduling problem . Int J Sys Sci 28: 25–32.

    Article  Google Scholar 

  • Vaessens RJM, Aarts EH and Lenstra JK (1998). A local search template . Comput Opns 25: 969–979.

    Article  Google Scholar 

  • Vasko FJ, Knolle PJ and Spiegel DS (2005). An empirical study of hybrid genetic algorithms for the set covering problem . J Opl Res Soc 56: 1213–1223.

    Article  Google Scholar 

  • Wang HF and Wu KY (2003). Modeling and analysis for multi-period, multi-product and multi-resource production scheduling . J Intell M 14: 297–309.

    Article  Google Scholar 

  • Wang HF and Wu KY (2004). Hybrid genetic algorithm for optimization problems with permutation property . Comput Opns 31(14): 2453–2471.

    Article  Google Scholar 

  • Weitz RR and Jelassi MT (1992). Assigning students to groups: a multi-criteria decision support system approach . Dec Sci 23: 746–757.

    Article  Google Scholar 

  • Weitz RR and Lakshminarayanan S (1996). On a heuristic for the final exam scheduling problem . J Opl Res Soc 47: 599–600.

    Article  Google Scholar 

  • Weitz RR and Lakshminarayanan S (1998). An empirical comparison of heuristic methods for creating maximally diverse groups . J Opl Res Soc 49: 635–646.

    Article  Google Scholar 

  • Whitley D, Starkwether T and Shaner D (1991). The traveling salesman and sequence scheduling problems: Quality solutions using genetic edge recombination . In: Davis L (ed). Handbook of Genetic Algorithms. Van Nostrand Reinhold: New York, USA, pp. 350–372.

    Google Scholar 

  • Yannakakis M (1990). The analysis of local search problems and their heuristics. In: Choffrut C and Lengauer T (eds). Proceedings 7th Annual Symposium on Theoretical Aspects of Computer Science (STACS 90), Lecture Notes in Computer Science, Vol. 415. Springer-Verlag: London, pp 298–311.

Download references

Acknowledgements

This work was partly supported by the National Science Fund for Distinguished Young Scholars of China (Project No. 70525002), National Science Fund for Excellent Innovation Research Group of China (Project No. 70721001). Leading Academic Discipline Program, 211 Project for Shanghai University of Finance and Economics (the 3rd phase).

Author information

Authors and Affiliations

  1. Northeastern University, Shenyang, China

    Z P Fan

  2. Shanghai University of Finance & Economics, Shanghai, China

    Y Chen

  3. City University of Hong Kong, Kowloon, Hong Kong

    J Ma

  4. University of Arizona, USA

    S Zeng

Authors
  1. Z P Fan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Y Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. J Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. S Zeng
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

An erratum to this article is available at http://dx.doi.org/10.1057/jors.2010.92.

Appendix

Appendix

Procedure: LS illustration

figure a

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fan, Z., Chen, Y., Ma, J. et al. A hybrid genetic algorithmic approach to the maximally diverse grouping problem. J Oper Res Soc 62, 92–99 (2011). https://doi.org/10.1057/jors.2009.168

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2009.168

Keywords

Search

Navigation