Sınav çizelgelemesi için matematiksel model yaklaşımı
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.
Mathematical modelling approach for exam timetabling
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.
___
- 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