A 0-1 Integer Programming Model for the Course Scheduling Problem and A Case Study

Hakan ALTUNAY, Tamer EREN
1.013 589

Abstract


The course scheduling problem is one of the most common timetabling problems which are frequently encountered in all educational institutions, especially universities. This problem which is getting harder to solve day by day, means the assignment of the lessons and lecturers into the most suitable timeslots and classrooms, provided that various constraints are taken into account. These constraints peculiar to the problem are consisted due to various factors such as the characteristics and the rules of the educational institutions, preferences of lecturers, students’ requests and suggestions. In this study, a novel 0-1 integer programming model that considers preferences of lecturers is proposed for the course scheduling problem. The proposed mathematical model is also tested with a case study from Uludag University. Thus, the performance of the mathematical model can be tested and the results can be analyzed. The results of the carried out application show efficient results in preparing a course schedule that meets the preferences of the lecturers and complies with the rules of the institutions.


Keywords


Course Scheduling Problem, 0-1 Integer Programming, Scheduling, Operations Research

Full Text:

PDF (Türkçe)


References


Akkoyunlu, E.A. (1973) A linear algorithm for computing the optimum university timetable, The Computer Journal, 16, 4, 347-350.

Al-Yakoob, S.M. ve Sherali, H.D. (2006) Mathematical programming models and algorithms for a class-faculty assignment problem. European Journal of Operational Research, 173, 2, 488-507,

Al-Yakoob, S.M. ve Sherali, H.D. (2007) A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations. Aug. 1, European Journal of Operational Research, 180 (3): 1028-1044, 2007.

Avella P. ve Vasiliev I. (2005) A computational study of a cutting plane algorithm for university course timetabling, Journal of Scheduling 8/6, 497-514.

Badri, M.A. (1996) A two-stage multiobjective scheduling model for faculty-course-time assignments. European Journal of Operational Research, 94, 16–28.

Badri, M.A., Davis, D.L., Davis, F.D. ve Hollingsworth, J. (1998) A multi-objective course scheduling model: Combining faculty preferences for courses and times, Computers and Operations Research, 25, 4, 303-316.

Baker K.R., Magazine M. J. ve Polak G. G. (2002) Optimal Block Design Models for Course Timetabling. Operations Research Letters 30: 1-8.

Bakır, M.A. ve Aksop, C. (2008) A 0-1 integer programming approach to a university timetabling problem. Hacettepe Journal of Mathematics and Statistics, 37 (1): 41–55.

Boronico, J. (2000) Quantitative modeling and technology driven departmental course scheduling. The International Journal of Management Science, 28 (3): 327-346.

Botsalı A.R. (2000) A timetabling problem: constraint and mathematical programming approaches. Yüksek Lisans Tezi, Bilkent Üniversitesi, Ankara.

Burke, E. K. MacCarthy, B. Petrovic, S. ve Qu, R. (2001) Case-based reasoning in course timetabling: An attribute graph approach. Case-Based Reasoning Research and Development, Jul-Aug, Proceedings of the 4th International Conference on Case-Based Reasoning, Vancouver, Canada, 90-104.

Burke, E.K., Petrovic, S. ve Qu, R. (2006) Case-based heuristic selection for timetabling problems. Journal of Scheduling, vol 9, no. 2, 115-132.

Burke, E.K., Marecek, J., Parkes, A. J. ve Rudová, H., (2008) Penalizing patterns in timetables: Novel integer programming formulations. Operations Research Proceedings, Berlin, Springer, Germany, ISSN 0721-5924, 2007, 409-414.

Cacchiani V., Caprara A., Roberti R. ve Toth P. (2013) A new lower bound for curriculum-based course timetabling. Computers and Operations Research, Volume 40, Issue 10, October 2013, Pages 2466-2477.

Carter M.W. ve Laporte G. (1998) Recent developments in practical course scheduling. in: E.K. Burke, P. Ross (Eds.), The Practice and Theory of Automated Timetabling: vol. 2, Springer, Berlin, 3-19.

Cheng, E. ve Kruk, S. (2007) A case study of an integer programming model for instructor assignments and scheduling problem. Aug 28-31, Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), Paris, France, 267-275.

Daskalaki, S., Birbas, T. ve Housos, E. (2004) An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153, 117–135.

Daskalaki, S., ve Birbas T. (2005) Efficient solutions for a university timetabling problem through integer programming. European Journal of Operational Research, 160, 1, 106-120.

Dimopoulou, M. ve Miliotis, P. (2001) Implementation of a university course and examination timetabling system. European Journal of Operational Research, 130, 202-213.

Dimopoulou, M. ve Miliotis, P. (2004) An automated university course timetabling system developed in a distributed environment: A case study. European Journal of Operational Research, 153, 136-147.

Dinkel, J.J. Mote, J. ve Venkataramanan M.A. (1989) An efficient decision support system for academic course scheduling, Operations research, 37, 6, 853-864.

Ferland, J.A. ve Roy, S. (1985) Timetabling problem for university as assignment of activities to resources. Computers and Operations Research, 12, 2, 207-218.

Ferland, J.A. ve Fleurent, C. (1994) SAPHIR: A decision support system for course scheduling. Interfaces 24, 105-115.

Güldalı A. (1990) Seri iş-akışlı atölye çizelgelemesinde sezgisel teknikler. Yüksek Lisans Tezi, Gazi Üniversitesi, Ankara.

Gosselin, K. ve Truchon, M. (1986) Allocation of classrooms by linear programming. The Journal of the Operational Research Society, 37, 6, 561-569.

Harwood, G.B. ve Lawless, R.W. (1975) Optimizing organizational goals in assigning faculty teaching schedules. Decision Sciences, 6, 3, 513-524.

Martin C.H. (2004) Ohio University’s college of business uses integer programming to schedule classes. Interfaces 34(6):460-465.

McClure, R.H. ve Wells, C.E. (1984) A mathematical programming model for faculty course assignment. Decision Sciences, 153, 409-420.

MirHassani, S.A. (2006) A computational approach to enhancing course timetabling with integer programming. Applied Mathematics and Computation, 175 (1), 814-822.

Özyandı G. (2010) Ders çizelgeleme probleminin 0-1 tamsayılı programlama tabanlı uygulaması. Yüksek Lisans Tezi, Gazi Üniversitesi, Ankara.

Pinedo, M. L. (2005) Planning and Scheduling In Manufacturing and Services. Springer, New York.

Qu R., Burke E.K., McCollum B., Merlot L.T.G. ve Lee S.Y. (2009) A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling 12(1), 55–89.

Sarin, S. C., Wang, Y ve Varadarajan A. (2005) Solving a timetabling problem using benders’ decomposition. In proceedings of the 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA, pages 673-675.

Sarin S. C, Wang Y. ve Varadarajan A. (2010) A university-timetabling problem and its solution using Benders’ partitioning: a case study. Journal of Scheduling, 13(2): 131-141.

Schaerf, A. (1999) A survey of automated timetabling. Artificial Intelligent Review, 13, 87-127.

Schaerf, A. ve Di Gaspero, L. (2001) Local search techniques for educational timetabling problems. In L. Lenart, L. Stirn Zadnik ve S. Drobne, eds., Proceeding of the 6th International Symposium on Operational Research (SOR-01), Preddvor, Slovenia., 13-23.

Shih, W. ve Sullivan, J.A. (1977) Dynamic course scheduling for college faculty via zero-one programming. Decision Sciences, 8, 711-721.

Tripathy, A. (1984) School timetabling-a case in large binary integer linear programming. Management Science, 30, 12, 1473-1489.

Wren A. (1996) Scheduling, timetabling and rostering - a special relationship. In Proceedings of The Practice and Theory of Automated Timetabling, LNCS 1153, Springer Verlag, 46-76.

Günalay, Y. ve Şahin, T. (2006) A decision support system for the university timetabling problem with instructor preferences. Asian Journal of Information Technology, 5, 12, 1479-1484.

MirHassani, S.A. (2006) A computational approach to enhancing course timetabling with integer programming. Applied Mathematics and Computation, 175 (1), 814-822.

Ismayilova, N.A. Sagir, M. ve Gasimov, R.N. (2007) A multiobjective faculty-course-time slot assignment problem with preferences. Mathematical and Computer Modelling, 46, 7-8, 1017 – 1029.

Schimmelpfeng, K. ve Helber, S. (2007) Application of a real-world university-course timetabling model solved by integer programming, OR Spectrum, 29, 783–803.

Gunawan, A., Ng, K. M. ve Ong, H. L. (2008) A genetic algorithm for the teacher assignment problem for a university in Indonesia. Information and Management Sciences, 19 (1): 1-16.

Van Den Broek, J. Hurkens, C. ve Woeginger, G. (2009) Timetabling problems at the TU Eindhoven. Aug 1, European Journal of Operational Research, 196 (3): 877-885.

Van Den Broek, J. ve Hurkens, C. (2012) An Ip-based heuristic for the post enrolment course timetabling problem of the itc2007. Annals of Operational Research, 194, 439-454.




Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.