Generic Model for Timetabling Problems by Integer Linear Programming Approach
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:71482", author = "N. A. H. Aizam and V. Uvaraja", title = "Generic Model for Timetabling Problems by Integer Linear Programming Approach", 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.", volume = "9", number = "12", pages = "707-8", }
