M. Akif BAKIR, Cihan AKSOP

277

A 0-1 integer programming approach to a university timetabling problem

A 0-1 integer programming approach to a university timetabling problem

One of the major problems with course scheduling - a particular type of timetabling - is the difficulty that arises when trying to suitably co-ordinate lectures, students and classrooms according to a set of op- erational rules within a framework of certain constraints. The assign- ment of courses and lectures to periods and classrooms is an important administrative task that must be performed each term. The primary purpose of this paper is to solve an existing course scheduling prob- lem. Organizing courses and lectures according to periods and avail- ability of classrooms is a difficult course scheduling problem, which we are currently experiencing within the Department of Statistics at Gazi University. We have therefore formulated the problem as a 0-1 inte- ger programming model. The aim of this model is to minimize the dissatisfaction of students and lecturers whilst at the same time imple- menting rules bounded by a set of constraints. The model produced has flexibility in terms of embracing new rules and/or criteria.
PDF

___

  • [1] Abramson, D. Constructing school timetables using simulated annealing: sequential and parallel algorithms, Management Science 37, 98–113, 1991.
  • [2] Akkoyunlu, E.A. A linear algorithm for computing the optimum university timetable, The Computer Journal 16 (4), 347–350, 1973.
  • [3] Azimi, Z.N. Hybrid heuristics for examination timetabling problem, Applied Mathematics and Computation 163, 705–733, 2005.
  • [4] Badri, M.A., Davis, D. L., Davis, D. F. and Hollingsworth, J. A multi-objective course scheduling Model: combining faculty preferences for courses and times, Computers and Operations Research 25 (4), 303–316, 1998.
  • [5] Balakrishnan, N. Examination scheduling : A computerized application, International Journal of Management Science 19, 37–41, 1991.
  • [6] Cangolovic, M. and Schreuder, J.A.M. Exact coloring algorithms for weighed graphs applied to timetabling problems with lectures of different lenghths, European Journal of Operational Research 51, 248–258, 1991.
  • [7] Carrasco, M.P. and Rato, M.V. A multiobjective genetic algorithm for the class/teacher timetabling problem, In Burke E, Erben W. (Eds.) (Practice and theory of timetabling III. Lecture Notes in Computer Science. Vol. 2079, Springer-Verlag, 2001), 3–17.
  • [8] Costa, D. A tabu search algorithm for computing an operational timetable, European Journal of Operational Research 76, 98–110, 1994.
  • [9] Daskalaki, S., Birbas T. and Housos, E. An integer programming formulation for a case study in university timetabling, European Journal of Operational Research, 117–135, 2004.
  • [10] De Werra, D., Mahadev, N.V.R. and Peled, U.N. Edge chromatic scheduling with simultaneous constraints, SIAM Journal on Discrete Mathematics 6, 175–182, 1993.
  • [11] De Werra, D. and Hertz, A. Tabu search techniques: a tutorial and an application to neural networks, OR Spectrum 11, 131–141, 1989.
  • [12] Deris, S. B., Ormatu, S., Ohta, H. and Samat, P.A. B.D. University timetabling by constraint-based reasoning: a case study, Journal of the Operational Research Society 48, 1178–1190, 1997.
  • [13] Dimopoulou, M. and Milliotis, P. Implementation of a university course and examination timetabling system, European Journal of Operational Research 130, 2–213, 2001.
  • [14] Gupta, G. Practical Aspects of Declarative Languages (LNCS 1551, Springer-Verlag 1999).
  • [15] Hertz, A. Find a feasible course schedule using tabu search, Discrete Applied Mathematics 35, 255–270, 1992.
  • [16] Hultberg, T.H. and Cardoso, D.M. The teacher assignment problem: a special case of fixed charge transportation problem, European Journal of Operational Research 101, 463–473, 1997.
  • [17] Lawrie, N. L. An integer linear programming model of a school timetabling problem, The Computer Journal 12, 307–316, 1969.
  • [18] Schaerf, A. A Survey of automated timetabling, Artificial Intelligence Review 13, 87–127, 1999.
  • [19] Welsh, D. J.A. and Powell, M. B. An upper bound to the choromatic number of a graph and its application to timetabling problem, The Computer Journal 10, 85–86, 1967.
Hacettepe Journal of Mathematics and Statistics-Cover
  • Yayın Aralığı: Yılda 6 Sayı
  • Başlangıç: 2002
  • Yayıncı: Hacettepe Üniversitesi Fen Fakultesi
Arşiv
Sayıdaki Diğer Makaleler

On the composition of the distributions $x^{-1}ln^m|x|$ and $x^r$

Brian FISHER, İnci EGE, Emin ÖZÇAĞ

Variance estimation in simple random sampling using auxiliary information

Sat GUPTA, Javid SHABBIR

A 0-1 integer programming approach to a university timetabling problem

M. Akif BAKIR, Cihan AKSOP

On semi-continuous mappings, equations and inclusions in a Banach space

Kamal N. SOLTANOV

Binary di-operations and spaces of real difunctions on a texture

Lawrence M. BROWN, Ahmet IRKAD