IDEAS home Printed from https://ideas.repec.org/a/ddj/fseeai/y2012i2p5-16.html
   My bibliography  Save this article

Multi Population Hybrid Genetic Algorithms for University Course Timetabling

Author

Listed:
  • Meysam Shahvali KOHSHORI

    (Department of Computer Engineering, Izeh Brach, Islamic Azad University, Izeh, Iran)

  • Mehrnaz Shirani LIRI

    (Department of Computer Engineering, Izeh Brach, Islamic Azad University, Izeh, Iran)

Abstract

University course timetabling is one of the important and time consuming issues that each University is involved with at the beginning of each university year. This problem is in class of NP-hard problem and is very difficult to solve by classic algorithms. Therefore optimization techniques are used to solve them and produce optimal or almost optimal feasible solutions instead of exact solutions. Genetic algorithms, because of their multidirectional search property, are considered as an efficient approach for solving this type of problems. In this paper three new hybrid genetic algorithms for solving the university course timetabling problem (UCTP) are proposed: FGARI, FGASA and FGATS. In the proposed algorithms, fuzzy logic is used to measure violation of soft constraints in fitness function to deal with inherent uncertainty and vagueness involved in real life data. Also, randomized iterative local search, simulated annealing and tabu search are applied, respectively, to improve exploitive search ability and prevent genetic algorithm to be trapped in local optimum. The experimental results indicate that the proposed algorithms are able to produce promising results for the UCTP

Suggested Citation

  • Meysam Shahvali KOHSHORI & Mehrnaz Shirani LIRI, 2012. "Multi Population Hybrid Genetic Algorithms for University Course Timetabling," Economics and Applied Informatics, "Dunarea de Jos" University of Galati, Faculty of Economics and Business Administration, issue 2, pages 5-16.
    • Handle: RePEc:ddj:fseeai:y:2012:i:2:p:5-16
    as

    Download full text from publisher

    File URL: http://www.ann.ugal.ro/eco/Doc2012.2/Meysam%20Shahvali%20KOHSHORI_Mehrnaz%20Shirani%20LIRI.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Daskalaki, S. & Birbas, T. & Housos, E., 2004. "An integer programming formulation for a case study in university timetabling," European Journal of Operational Research, Elsevier, vol. 153(1), pages 117-135, February.
    2. K Papoutsis & C Valouxis & E Housos, 2003. "A column generation approach for the timetabling problem of Greek high schools," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(3), pages 230-238, March.
    3. N/A, 1996. "Note:," Foreign Trade Review, , vol. 31(1-2), pages 1-1, January.
    4. White, George M. & Xie, Bill S. & Zonjic, Stevan, 2004. "Using tabu search with longer-term memory and relaxation to create examination timetables," European Journal of Operational Research, Elsevier, vol. 153(1), pages 80-91, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Salem Al-Yakoob & Hanif Sherali, 2015. "A column generation mathematical programming approach for a class-faculty assignment problem with preferences," Computational Management Science, Springer, vol. 12(2), pages 297-318, April.
    2. Zhang, Defu & Liu, Yongkai & M'Hallah, Rym & Leung, Stephen C.H., 2010. "A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems," European Journal of Operational Research, Elsevier, vol. 203(3), pages 550-558, June.
    3. Haroldo Santos & Eduardo Uchoa & Luiz Ochi & Nelson Maculan, 2012. "Strong bounds with cut and column generation for class-teacher timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 399-412, April.
    4. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    5. Al-Yakoob, Salem M. & Sherali, Hanif D., 2007. "A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations," European Journal of Operational Research, Elsevier, vol. 180(3), pages 1028-1044, August.
    6. Kris James Mitchener & Matthew Jaremski, 2014. "The Evolution of Bank Supervision: Evidence from U.S. States," NBER Working Papers 20603, National Bureau of Economic Research, Inc.
    7. , G. & , & ,, 2008. "Non-Bayesian updating: A theoretical framework," Theoretical Economics, Econometric Society, vol. 3(2), June.
    8. Santiago Moreno-Bromberg & Luca Taschini, 2011. "Pollution permits, Strategic Trading and Dynamic Technology Adoption," Papers 1103.2914, arXiv.org.
    9. Andrei Kapaev, 2013. "Remark on repo and options," Papers 1311.5211, arXiv.org.
    10. Daniel Sanches, 2016. "On the Inherent Instability of Private Money," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 20, pages 198-214, April.
    11. James J. McAndrews & William Roberds, 1999. "Payment intermediation and the origins of banking," Staff Reports 85, Federal Reserve Bank of New York.
    12. Allen Head & Junfeng Qiu, 2007. "Elastic Money, Inflation, And Interest Rate Policy," Working Paper 1152, Economics Department, Queen's University.
    13. Fong, Wai Mun, 1997. "Robust beta estimation: Some empirical evidence," Review of Financial Economics, Elsevier, vol. 6(2), pages 167-186.
    14. Ricardo de O. Cavalcanti & Andres Erosa & Ted Temzelides, 1999. "Private Money and Reserve Management in a Random-Matching Model," Journal of Political Economy, University of Chicago Press, vol. 107(5), pages 929-945, October.
    15. Steven Brams & D. Kilgour, 1998. "Backward Induction Is Not Robust: The Parity Problem and the Uncertainty Problem," Theory and Decision, Springer, vol. 45(3), pages 263-289, December.
    16. Junfeng Qiu, 2011. "Bank money, aggregate liquidity, and asset prices," Annals of Economics and Finance, Society for AEF, vol. 12(2), pages 295-346, November.
    17. Zibo Xu, 2013. "The instability of backward induction in evolutionary dynamics," Discussion Paper Series dp633, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    18. James S. Costain, 1998. "On the quantitative importance of wage bargaining models," Economics Working Papers 262, Department of Economics and Business, Universitat Pompeu Fabra.
    19. Kahn, Charles M & Roberds, William, 1998. "Payment System Settlement and Bank Incentives," The Review of Financial Studies, Society for Financial Studies, vol. 11(4), pages 845-870.
    20. Jim Dolmas & Gregory W. Huffman, 2004. "On The Political Economy Of Immigration And Income Redistribution," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 45(4), pages 1129-1168, November.

    More about this item

    Keywords

    University course timetabling problem(UCTP); Genetic algorithm; Multi population; Fuzzy logic; Local search; Heurestics;
    All these keywords.

    JEL classification:

    • I20 - Health, Education, and Welfare - - Education - - - General
    • I21 - Health, Education, and Welfare - - Education - - - Analysis of Education

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ddj:fseeai:y:2012:i:2:p:5-16. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Gianina Mihai (email available below). General contact details of provider: https://edirc.repec.org/data/fegalro.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.