IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v54y2003i11d10.1057_palgrave.jors.2601628.html
   My bibliography  Save this article

A two-phase multiple objective approach to university timetabling utilising optimisation and evolutionary solution methodologies

Author

Listed:
  • S K Mirrazavi

    (Temposoft (UK) Ltd)

  • S J Mardle

    (CEMARE, University of Portsmouth)

  • M Tamiz

    (University of Portsmouth)

Abstract

The timetabling problem is generally large, highly constrained and discrete in nature. This makes solution by exact optimisation methods difficult. Therefore, often a heuristic search is deemed acceptable providing a simple (non-optimal) solution. This paper discusses the timetabling problem for a university department, where a large-scale integer goal programming (IGP) formulation is implemented for its efficient optimal solution in two phases. The first phase allocates lectures to rooms and the second allocates start-times to lectures. Owing to the size and complicated nature of the model, an initial analysis procedure is employed to manipulate the data to produce a more manageable model, resulting in considerable reductions in problem size and increase of performance. Both phases are modelled as IGPs. Phase 1 is solved using a state-of-the-art IGP optimisation package. However, due to the scale of the model, phase 2 is solved to optimality using a genetic algorithm approach.

Suggested Citation

  • S K Mirrazavi & S J Mardle & M Tamiz, 2003. "A two-phase multiple objective approach to university timetabling utilising optimisation and evolutionary solution methodologies," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(11), pages 1155-1166, November.
    • Handle: RePEc:pal:jorsoc:v:54:y:2003:i:11:d:10.1057_palgrave.jors.2601628
    DOI: 10.1057/palgrave.jors.2601628
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2601628
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2601628?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Burke, Edmund Kieran & Petrovic, Sanja, 2002. "Recent research directions in automated timetabling," European Journal of Operational Research, Elsevier, vol. 140(2), pages 266-280, July.
    2. Badri, Masood A., 1996. "A two-stage multiobjective scheduling model for [faculty-course-time] assignments," European Journal of Operational Research, Elsevier, vol. 94(1), pages 16-28, October.
    3. Arabinda Tripathy, 1984. "School Timetabling---A Case in Large Binary Integer Linear Programming," Management Science, INFORMS, vol. 30(12), pages 1473-1489, December.
    4. Arthur, Jeffrey L. & Ravindran, A., 1980. "A branch and bound algorithm with constraint partitioning for integer goal programming problems," European Journal of Operational Research, Elsevier, vol. 4(6), pages 421-425, June.
    5. Markland, R. E. & Vickery, S. K., 1986. "The efficient computer implementation of a large-scale integer goal programming model," European Journal of Operational Research, Elsevier, vol. 26(3), pages 341-354, September.
    6. Tamiz, M. & Mirrazavi, S. K. & Jones, D. F., 1999. "Extensions of Pareto efficiency analysis to integer goal programming," Omega, Elsevier, vol. 27(2), pages 179-188, April.
    7. Mirrazavi, S. Keyvan & Jones, Dylan F. & Tamiz, M., 2001. "A comparison of genetic and conventional methods for the solution of integer goal programmes," European Journal of Operational Research, Elsevier, vol. 132(3), pages 594-602, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. S. Mirrazavi & Henri Beringer, 2007. "A web-based workforce management system for Sainsburys Supermarkets Ltd," Annals of Operations Research, Springer, vol. 155(1), pages 437-457, November.
    2. C Gagné & M Gravel & W L Price, 2005. "Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(6), pages 687-698, June.
    3. K A Willoughby & C J Zappe, 2006. "A methodology to optimize foundation seminar assignments," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(8), pages 950-956, August.
    4. Johnes, Jill, 2015. "Operational Research in education," European Journal of Operational Research, Elsevier, vol. 243(3), pages 683-696.
    5. Raphael Medeiros Alves & Francisco Cunha & Anand Subramanian & Alisson V. Brito, 2022. "Minimizing energy consumption in a real-life classroom assignment problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(4), pages 1149-1175, December.
    6. 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.
    7. 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.

    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. Mirrazavi, S. Keyvan & Jones, Dylan F. & Tamiz, M., 2001. "A comparison of genetic and conventional methods for the solution of integer goal programmes," European Journal of Operational Research, Elsevier, vol. 132(3), pages 594-602, August.
    2. Aouni, Belaid & Kettani, Ossama, 2001. "Goal programming model: A glorious history and a promising future," European Journal of Operational Research, Elsevier, vol. 133(2), pages 225-231, January.
    3. Vermuyten, Hendrik & Lemmens, Stef & Marques, Inês & Beliën, Jeroen, 2016. "Developing compact course timetables with optimized student flows," European Journal of Operational Research, Elsevier, vol. 251(2), pages 651-661.
    4. 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.
    5. P. Solano Cutillas & D. Pérez-Perales & M. M. E. Alemany Díaz, 2022. "A mathematical programming tool for an efficient decision-making on teaching assignment under non-regular time schedules," Operational Research, Springer, vol. 22(3), pages 2899-2942, July.
    6. 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.
    7. Boronico, Jess, 2000. "Quantitative modeling and technology driven departmental course scheduling," Omega, Elsevier, vol. 28(3), pages 327-346, June.
    8. Edmund Burke & Jakub Mareček & Andrew Parkes & Hana Rudová, 2012. "A branch-and-cut procedure for the Udine Course Timetabling problem," Annals of Operations Research, Springer, vol. 194(1), pages 71-87, April.
    9. Song, Kwonsik & Kim, Sooyoung & Park, Moonseo & Lee, Hyun-Soo, 2017. "Energy efficiency-based course timetabling for university buildings," Energy, Elsevier, vol. 139(C), pages 394-405.
    10. Gerhard Post & Samad Ahmadi & Sophia Daskalaki & Jeffrey Kingston & Jari Kyngas & Cimmo Nurmi & David Ranson, 2012. "An XML format for benchmarks in High School Timetabling," Annals of Operations Research, Springer, vol. 194(1), pages 385-397, April.
    11. De Causmaecker, Patrick & Demeester, Peter & Vanden Berghe, Greet, 2009. "A decomposed metaheuristic approach for a real-world university timetabling problem," European Journal of Operational Research, Elsevier, vol. 195(1), pages 307-318, May.
    12. C Beyrouthy & E K Burke & D Landa-Silva & B McCollum & P McMullan & A J Parkes, 2009. "Towards improving the utilization of university teaching space," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 130-143, January.
    13. X Li & P Beullens & D Jones & M Tamiz, 2009. "An integrated queuing and multi-objective bed allocation model with application to a hospital in China," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(3), pages 330-338, March.
    14. R Qu & E K Burke, 2009. "Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1273-1285, September.
    15. Cangalovic, Mirjana & Kovacevic-Vujcic, Vera & Ivanovic, Lav & Drazic, Milan, 1998. "Modeling and solving a real-life assignment problem at universities," European Journal of Operational Research, Elsevier, vol. 110(2), pages 223-233, October.
    16. Oliver Czibula & Hanyu Gu & Aaron Russell & Yakov Zinder, 2017. "A multi-stage IP-based heuristic for class timetabling and trainer rostering," Annals of Operations Research, Springer, vol. 252(2), pages 305-333, May.
    17. Kristiansen, Simon & Sørensen, Matias & Stidsen, Thomas R., 2011. "Elective course planning," European Journal of Operational Research, Elsevier, vol. 215(3), pages 713-720, December.
    18. Daskalaki, S. & Birbas, T., 2005. "Efficient solutions for a university timetabling problem through integer programming," European Journal of Operational Research, Elsevier, vol. 160(1), pages 106-120, January.
    19. Carrasco, M. P. & Pato, M. V., 2004. "A comparison of discrete and continuous neural network approaches to solve the class/teacher timetabling problem," European Journal of Operational Research, Elsevier, vol. 153(1), pages 65-79, February.
    20. Asratian, A. S. & de Werra, D., 2002. "A generalized class-teacher model for some timetabling problems," European Journal of Operational Research, Elsevier, vol. 143(3), pages 531-542, December.

    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:pal:jorsoc:v:54:y:2003:i:11:d:10.1057_palgrave.jors.2601628. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    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.