Mathematical modelling approach for exam timetabling

Year 2013, Issue: 1, 75 - 86, 01.02.2013

M. Fatih Acar Mehmet Şevkli

Abstract

Exam timetabling problems is one of the most popular problems in academic environment. These schedules can sometimes be done manually, so students might face lots of problems such as; having more than one exam in the same time slot or in the same day. In this research, exam timetabling problem is tried to be solved considering the demands of both lecturers and students. For exam timetabling problems, a new mathematical model is generated. However, this mathematical model can not solve large size problems in a short time, so a new heuristic method based on the mathematical model is constructed. In this research, Xpress-MP software which is one of the most popular programmes in optimization is used. Moreover, the heuristic method is applied to Fatih University dataset.

Keywords

-

Sınav çizelgelemesi için matematiksel model yaklaşımı

Abstract

Sınav çizelgeleme problemi akademik ortamlarda karşılaşılan en popüler problemlerden biridir. Bu çizelgelemeler elle yapılabilmekte, dolayısıyla öğ- rencinin aynı zamanda veya aynı günde iki veya daha fazla sınavı olması gibi çeşitli problemler ortaya çıkabilmektedir. Bununla birlikte sınıfların kapasitesi, gözetmen sayısı gibi kısıtlardan da bahsedilebilir. Bu çalışmada öğretim üye- lerinin ve öğrencilerin istekleri göz önünde bulundurularak sınav çizelgeleme problemi çözülmeye çalışılmıştır. Bu probleme çözüm üretmek için yeni bir matematiksel model oluşturulmuştur. Bu matematiksel model büyük verilere sahip problemleri kısa zamanda çözemediği için matematiksel modellemeye dayalı yeni sezgisel yöntem geliştirilmiştir. Bu araştırmada Xpress-MP adlı ya- zılım kullanılmış ve geliştirilen sezgisel yöntem Fatih Üniversitesi verilerine uy- gulanmıştır.

Keywords

-

References

• 1. ARANI T. and LOTHI V., (1989), “A Lagrangian relaxation approach to solve the second phase of the exam scheduling problem”, European Journal of Operational Research, 34, 372-383, 1989
• 2. BRAILSFORD, S. C., POTTS, C. N., & SMITH, B. M., (1999), “Constraint satisfaction problems: Algorithms and applications”, European Journalof Operational Research, 119, 557–581
• 3. BURKE, E. K., ELLIMAN, D. G., FORD, P. H., & WEARE, R. F., (1996), “Examination timetabling in British universities: A survey”, In E
• K. BURKE & P. ROSS (Eds.), Lecture notes in computer science: Vol. 1153, Practice and theory of automated timetabling I: Selected papers from the 1st international conference, pp. 76–90, Berlin: Springer
• 4. BURKE, E. K., & NEWALL, J. P., (1999), “A multi-stage evolutionary algorithm for the timetable problem”, IEEE Transactions on Evolutionary Computation, 3(1), 63–74
• 5. BURKE, E. K., BYKOV, Y., & PETROVIC, S., (2001), “A multi-criteria approach to examination timetabling”, In E. K. BURKE & W. ERBEN (Eds.), Lecture notes in computer science: Vol. 2079, Practice and theory of automated timetabling III: Selected papers from the 3rd international conference, pp
• 118–131, Berlin: Springer
• 6. BURKE, E. K., KINGSTON, J. H., & DE WERRA, D., (2004), “Applications to timetabling”, In J. Gross & J. Yellen (Eds.), The handbook of graph theory, pp. 445–474, London: Chapman Hall/CRC
• 7. CARTER, M.W., & LAPORTE, G., (1996), “Recent developments in practical examination timetabling”, In E. K. BURKE & P. ROSS (Eds.), Lecture notes in computer science: Vol. 1153, Practice and theory of automated timetabling I: Selected papers from the 1st international Conference, pp. 3–21, Berlin: Springer
• 8. COLIJN, A. W., & LAYFIELD, C., (1995), “Conflict reduction in examination schedules”, In E. K. BURKE & P. ROSS (Eds.), Proceedings of the 1st international conference on the practice and theory of automated timetabling, pp. 297–307, 30 August–1 September 1995, Edinburgh: Napier University
• 9. LANDA Silva, J. D., BURKE, E. K., & PETROVIC, S., (2004), “An introduction to multi-objective meta-heuristics for scheduling and timetabling”, In X. Gandibleux, M. Sevaux, K. Sorensen, & V. Tkindt (Eds.), Lecture notes in economics and mathematical systems: Vol. 535, Multiple objective meta- heuristics, pp. 91–129, Berlin: Springer
• 10. LE HUÉDÉ, F., GRABISCH, M., LABREUCHE, C., & SAVÉANT, P., (2006), “MCS-a new algorithm for multicriteria optimisation in constraint programming”, Annals of Operational Research, 147, 143–174
• 11. LIN, S. L. M., (2002), “A broker algorithm for timetabling problem”, In E. K. BURKE & P. De Causmaecker Eds., Proceedings of the 4th international conference on practice and theory of automated timetabling, pp. 372–386, KaHo St.-Lieven, Gent, Belgium, 21–23
• 12. MCCOLLUM, B., MCMULLAN, P., BURKE, E. K., PARKES, A. J., & QU, R., (2008), “The second international timetabling competition: Examination timetabling track”, Technical Report QUB/IEEE/Tech/ITC2007/Exam/ v1.0/1., Queen’s Belfast University, N. Ireland
• 13. MIRHASSANI S.A., Improving paper spread in examination timetables using integer programming, Applied Mathematics and Computation, 179, 702- 706, 2006
• 14. ŞEVKLİ M., UYSAL Ö., SARI M., (2008), “A Mixed Integer Mathematical Model for Exam Timetabling: A Case Study at Fatih University Vocational School”, Proceedings of the seventh international conference on the practice and theory of automated timetabling, Montreal, Canada, 19- 22
• 15. QU R., BURKE E.K., MCCOLLUM B., MERLOT L.T.G., LEE S.Y., (2009), “A survey of search methodologies and automated system development for examination timetabling”, Journal of Scheduling 12, 55-89
• 16. WHITE, G.M., CHAN, P.W., (1979), “Towards the construction of optimal examination timetables”, INFOR 17, 219–229, 1979