1. Home
  2. Issues
  3. Volume 28, Issue 4 (2017)
  4. A Column Generation Mathematical Model f ...

Informatica


A Column Generation Mathematical Model for a Teaching Assistant Workload Assignment Problem
Volume 28, Issue 4 (2017), pp. 583–608
Pub. online: 1 January 2017      Type: Research Article      Open accessOpen Access
Received
1 January 2017
Accepted
1 September 2017
Published
1 January 2017

Abstract

This paper presents a column generation-based modelling and solution approach for a teaching assistant workload scheduling problem that arises at academic institutions. A typical weekly workload schedule involves teaching deficiency classes, instructing problem-solving tutorial sessions, and allocating help-hours for students. For this purpose, a mixed-integer programming model that selects valid combinations of weekly schedules from the set of all feasible schedules is formulated. Due to the overwhelming number of variables in this model, an effective column generation procedure is developed. To illustrate the proof-of-concept along with modelling and algorithmic constructs, a case study related to the Department of Mathematics at Kuwait University is addressed. Computational results based on real data indicate that the generated schedules using the proposed model and solution procedure yield improved weekly workloads for teaching assistants in terms of fairness, and achieve enhanced satisfaction levels among assistants, as compared to schedules obtained using ad-hoc manual approaches.

References

 
Al-Yakoob, S.M., 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., Sherali, H.D. (2007). A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations. European Journal of Operational Research, 180(3), 1028–1044.
 
Al-Yakoob, S.M., Sherali, H.D. (2015). A column generation mathematical programming approach for a class-faculty assignment problem with preferences. Computational Management Science, 12(2), 297–318.
 
Al-Yakoob, S.M., Sherali, H.D., Al-Jazzaf, M. (2010). A mixed-integer mathematical modeling approach to exam timetabling. Computational Management Science, 7(1), 19–46.
 
Avella, P., Vasil’Ev, I. (2005). A computational study of a cutting plane algorithm for university course timetabling. Journal of Scheduling, 8(6), 497–514.
 
Baker, M.A., Aksop, C. (2008). A 0–1 integer programming approach to a university timetabling problem. Hacettepe Journal of Mathematics and Statistics, 37(1), 41–55.
 
Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W., Vance, P.H. (1998). Branch-and-price: column generation for solving huge integer programs. Operation Research, 46(3), 316–329.
 
Bazaraa, M.S., Jarvis, J.J., Sherali, H.D. (2010). Linear Programming and Network Flows. 4th ed. John Wiley and Sons, Hoboken.
 
Birbas, T., Daskalaki, S., Housos, E. (1997). Timetabling for Greek high schools. Journal of the Operational Research Society, 48(2), 1191–1200.
 
Boland, N., Hughes, B.D., Merlot, L.T., Stuckey, P.J. (2008). New integer programming approaches for course timetabling. Computers and Operations Research, 35(7), 2209–2233.
 
Burke, E.K., Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280.
 
Burke, E.K., Gendreau, M. (2008). Practice and theory of automated timetabling (PATAT). In: Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling, August 19–22, Montreal, Canada.
 
Burke, E.K., Marecek, J., Parkes, A., Rudova, H. (2010). Decomposition, re-formulation, and diving in university course timetabling. Computers and Operations Research, 37(3), 582–597.
 
Daskalaki, S., Birbas, T., Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153(1), 117–135.
 
de Werra, D., Asratian, A.S., Durand, S. (2002). Complexity of some special types of timetabling problems. Journal of Scheduling, 5(2), 171–183.
 
Dimopoulou, P., Miliotis, P. (2001). Implementation of a university course and examination timetabling system. European Journal of Operational Research, 153(1), 202–213.
 
Eikelder, Willemen R. J, H.M. (2001). Some complexity aspects of secondary school timetabling problems. In: Computer Science Practice and Theory of Automated Timetabling III, Lecture Notes in Computer Science, Vol. 2079, pp. 18–27.
 
Even, S., Itai, A., Shamir, A. (1976). On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5(4), 691–703.
 
Ismayilova, N.A., Sagir, M., Gasimov, R.N. (2007). A multiobjective faculty-course-time slot assignment problem with preferences. Mathematical and Computer Modeling, 46(7–8), 1017–1029.
 
Lewis, R. (2007). A survey of metaheuristic-based techniques for university timetabling problems. OR Spectrum, 30(1), 167–190.
 
McCollum, B. (2007). A perspective on bridging the gap between research and practice in university timetabling. In: Burke, E., Rudova, H. (Eds.), Practice and Theory of Automated Timetabling VI, LNCS, Vol. 3867. Springer-Verlag, Berlin, pp. 3–23.
 
McCollum, B., McMullan, P., Paechter, B., Lewis, R., Schaerf, A., Gaspero, L.D., Parkes, A.J., Qu, R., Burke, E. (2010). Setting the research agenda in automated timetabling: the second international timetabling competition. INFORMS Journal on Computing, 22(1), 120–130.
 
MirHassani, S.A. (2006). A computational approach to enhancing course timetabling with integer programming. Applied Mathematics and Computation, 175(1), 814–822.
 
Ozdemir, M.S., Gasimov, R.N. (2004). The analytic hierarchy process and multiobjective 0–1 faculty course assignment problem. European Journal of Operational Research, 157(2), 398–408.
 
Papoutsis, K., Valouxis, C., Housos, E. (2003). A column generation approach for the timetabling problem of Greek high schools. Journal of the Operational Research Society, 54(3), 230–238.
 
Petrovic, S., Burke, E.K. (2004). University Timetabling, Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton (Chapter 45).
 
Qu, R., Burke, E.K., McCollum, B., Merlok, L.T., Lee, S.Y. (2009). A survey of search methodologies and automated approaches for examination timetabling. Journal of Scheduling, 12(1), 55–89.
 
Sandhu, K.S. (2001). Automating class schedule generation in the context of a university timetabling information system. PhD dissertation, School of Management, Griffith University, Nathan Campus, Queensland, Australia.
 
Santos, H.G., Uchoa, E., Ochi, L., Maculan, N. (2008). Strong bounds with cut and column generation for class-teacher timetabling. In: Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling, PATAT.
 
Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87–127.
 
Tripathy, A. (1984). School timetabling – a case in large binary integer linear pro-gramming. Management Science, 30(12), 1473–1489.
 
Valouxis, Houso E, C. (2003). Constraint programming approach for school timetabling. Computers and Operations Research, 30(10), 1555–1572.
 
Yuqiang, W. (2007). Models and algorithms for some combinatorial optimization problems: university course timetabling, facility layout and integrated production-distribution scheduling. PhD dissertation, Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, VA.

Biographies

Al-Yakoob Salem M.
salem@al-yakoob.com

S.M. Al-Yakoob is an associate professor at the Department of Mathematics at Kuwait University. His research interests include mathematical programming and optimization with applications to real world problems such as location, transportation, scheduling, and timetabling problems.

Sherali Hanif D.
hanifs@vt.edu

H.D. Sherali is a university distinguished professor and the W. Thomas Rice endowed chaired professor of engineering, Emeritus in the Industrial and Systems Engineering Department at Virginia Polytechnic Institute and State University. His areas of research interest are in analysing problems and designing algorithms for specially structured linear, nonlinear, and integer programs arising in various applications, global optimization methods for non-convex programming problems, location and transportation theory and applications, economic and energy mathematical modelling and analysis. He has published over 345 refereed articles in various operations research journals, has (co-)authored eight books in this area, and serves on the editorial board of ten journals. He is an elected member of the National Academy of Engineering.


Full article Related articles Cited by PDF XML
Full article Related articles Cited by PDF XML

Copyright
© 2017 Vilnius University
Open access article under the CC BY license.

Keywords
academic timetabling scheduling mathematical programming column generation

Metrics
since January 2020
1194

Article info
views

 550

Full article
views
503

PDF
downloads

 216

XML
downloads


Share


RSS