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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Arabinda Tripathy, 1984. "School Timetabling---A Case in Large Binary Integer Linear Programming," Management Science, INFORMS, vol. 30(12), pages 1473-1489, December.
    7. 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.
    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Boronico, Jess, 2000. "Quantitative modeling and technology driven departmental course scheduling," Omega, Elsevier, vol. 28(3), pages 327-346, June.
    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. 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.
    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. Esmaeilbeigi, Rasul & Mak-Hau, Vicky & Yearwood, John & Nguyen, Vivian, 2022. "The multiphase course timetabling problem," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1098-1119.
    10. 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.
    11. 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.
    12. R. Alan Bowman, 2021. "Developing Optimal Student Plans of Study," Interfaces, INFORMS, vol. 51(6), pages 409-421, November.
    13. 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.
    14. 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.
    15. Haase, Knut & Latteier, Jörg & Schirmer, Andreas, 1997. "The course scheduling problem at Lufthansa Technical Training," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 441, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    16. Barry McCollum & Andrea Schaerf & Ben Paechter & Paul McMullan & Rhyd Lewis & Andrew J. Parkes & Luca Di Gaspero & Rong Qu & Edmund K. Burke, 2010. "Setting the Research Agenda in Automated Timetabling: The Second International Timetabling Competition," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 120-130, February.
    17. Christine Mumford, 2010. "A multiobjective framework for heavily constrained examination timetabling problems," Annals of Operations Research, Springer, vol. 180(1), pages 3-31, November.
    18. 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.
    19. Dönmez, Kadir & Demirel, Soner & Özdemir, Mustafa, 2020. "Handling the pseudo pilot assignment problem in air traffic control training by using NASA TLX," Journal of Air Transport Management, Elsevier, vol. 89(C).
    20. Clarence H. Martin, 2004. "Ohio University's College of Business Uses Integer Programming to Schedule Classes," Interfaces, INFORMS, vol. 34(6), pages 460-465, 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.