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. 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.
    2. N/A, 1996. "Note:," Foreign Trade Review, , vol. 31(1-2), pages 1-1, January.
    3. 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.
    4. 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.
    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. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Hiroshi Fujiki & Edward J. Green & Akira Yamazaki, 1999. "Sharing the risk of settlement failure," Working Papers 594, Federal Reserve Bank of Minneapolis.
    7. 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.
    8. , G. & , & ,, 2008. "Non-Bayesian updating: A theoretical framework," Theoretical Economics, Econometric Society, vol. 3(2), June.
    9. Santiago Moreno-Bromberg & Luca Taschini, 2011. "Pollution permits, Strategic Trading and Dynamic Technology Adoption," Papers 1103.2914, arXiv.org.
    10. Andrei Kapaev, 2013. "Remark on repo and options," Papers 1311.5211, arXiv.org.
    11. 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.
    12. 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.
    13. James J. McAndrews & William Roberds, 1999. "Payment intermediation and the origins of banking," Staff Reports 85, Federal Reserve Bank of New York.
    14. Andrea Bettinelli & Valentina Cacchiani & Roberto Roberti & Paolo Toth, 2015. "An overview of curriculum-based course timetabling," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(2), pages 313-349, July.
    15. Allen Head & Junfeng Qiu, 2007. "Elastic Money, Inflation, And Interest Rate Policy," Working Paper 1152, Economics Department, Queen's University.
    16. Hentati-Kaffel, R. & Prigent, J.-L., 2016. "Optimal positioning in financial derivatives under mixture distributions," Economic Modelling, Elsevier, vol. 52(PA), pages 115-124.
    17. Fong, Wai Mun, 1997. "Robust beta estimation: Some empirical evidence," Review of Financial Economics, Elsevier, vol. 6(2), pages 167-186.
    18. Xavier Freixas & Bruno Parigi & Jean-Charles Rochet, 2000. "Systemic risk, interbank relations, and liquidity provision by the central bank," Proceedings, Federal Reserve Bank of Cleveland, pages 611-640.
    19. Massimiliano Caramia & Stefano Giordani, 2020. "Curriculum-Based Course Timetabling with Student Flow, Soft Constraints, and Smoothing Objectives: an Application to a Real Case Study," SN Operations Research Forum, Springer, vol. 1(2), pages 1-21, June.
    20. repec:ulb:ulbcvp:p0025 is not listed on IDEAS
    21. 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.

    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.