Generic Model for Timetabling Problems by Integer Linear Programming Approach

Authors: N. A. H. Aizam, V. Uvaraja

Abstract:

The agenda of showing the scheduled time for performing certain tasks is known as timetabling. It is widely used in many departments such as transportation, education, and production. Some difficulties arise to ensure all tasks happen in the time and place allocated. Therefore, many researchers invented various programming models to solve the scheduling problems from several fields. However, the studies in developing the general integer programming model for many timetabling problems are still questionable. Meanwhile, this thesis describes about creating a general model which solves different types of timetabling problems by considering the basic constraints. Initially, the common basic constraints from five different fields are selected and analyzed. A general basic integer programming model was created and then verified by using the medium set of data obtained randomly which is much similar to realistic data. The mathematical software, AIMMS with CPLEX as a solver has been used to solve the model. The model obtained is significant in solving many timetabling problems easily since it is modifiable to all types of scheduling problems which have same basic constraints.

Keywords: AIMMS mathematical software, integer linear programming, scheduling problems, timetabling.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1110215

References:

[1] N. A. H. Aizam, and L. Caccetta, “Computational models for timetabling problems,” Numerical Algebra, Control and Optimization, vol. 4, no. 3. pp. 269-285, 2014.
[2] M. Ayob, A. M. Ab Malik, S. Abdullah, A. R. Hamdan, G. Kendall, and R. Qu, “Solving a practical examination timetabling problem: a case study,” Computational Science and Its Applications–ICCSA 2007, pp. 611-624.
[3] M. N. Azaiez and S. S. Al Sharif, “A 0-1 goal programming model for nurse scheduling,” Computers & Operations Research, vol. 32, no. 3, pp. 491-507, 2005.
[4] E. K. Burke and J. P. Newall, “Solving examination timetabling problems through adaption of heuristic orderings,” Annals of operations Research, vol. 129, no. 1-4, pp. 107-134, 2004.
[5] S. Chacha, Mathematical programming formulations for optimization of university course timetabling problem. (Retrieved from http://www.noma.udsm.ac.tz/thesis/Stephen%20Chacha.pdf.), 2012.
[6] B. Cheang, H. Li, A. Lim, and B. Rodrigues, “Nurse rostering problems––a bibliographic survey,” European Journal of Operational Research, vol. 151, no. 3, pp. 447-460, 2003.
[7] M. Chen, and H. Niu, “A model for bus crew scheduling problem with multiple duty types,” Discrete Dynamics in Nature and Society, 2012.
[8] S. Daskalaki, T. Birbas, and E. Housos, “ An integer programming formulation for a case study in university timetabling,” European Journal of Operational Research, vol 153, no. 1, pp. 117-135, 2004.
[9] B. L. Golden, S. Raghavan, and E. A. Wasil, The Next wave in computing, optimization, and decision technologies. Springer Science & Business Media, 2006.
[10] S. Lan, J. P. Clarke, and C. Barnhart, “Planning for robust airline operations: Optimizing aircraft routings and flight departure times to minimize passenger disruptions,” Transportation science vol. 40, no. 1, pp. 15-28, 2006.
[11] B. Maharjan, and T. I. Matis, “An optimization model for gate reassignment in response to flight delays,” Journal of Air Transport Management, vol. 17, no 4, pp. 256-261, 2011.
[12] K. Murray, T. Müller, and H. Rudová, “Modeling and solution of a complex university course timetabling problem,” in Practice and Theory of Automated Timetabling VI. Springer Berlin Heidelberg, 2007, pp. 189-209.
[13] J. Puchinger, and G. R. Raidl, Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification. Springer Berlin Heidelberg, 2005, pp. 41-53.
[14] F. Rothlauf, Design of modern heuristics: principles and application. Springer, 2011.
[15] J. D. L. Silva, E. K. Burke, and S. Petrovic, "An introduction to multiobjective metaheuristics for scheduling and timetabling," Metaheuristics for multiobjective optimization, Springer Berlin Heidelberg, 2004, pp. 91-129.
[16] A. Wren, “Scheduling, timetabling and rostering—a special relationship?” in Practice and theory of automated timetabling, Springer Berlin Heidelberg, 1996, pp. 46-75.