Transformation of Course Timetablinng Problem to RCPSP

Authors: M. Ahmad, M. Gourgand, C. Caux

Abstract:

The Resource-Constrained Project Scheduling Problem (RCPSP) is concerned with single-item or small batch production where limited resources have to be allocated to dependent activities over time. Over the past few decades, a lot of work has been made with the use of optimal solution procedures for this basic problem type and its extensions. Brucker and Knust[1] discuss, how timetabling problems can be modeled as a RCPSP. Authors discuss high school timetabling and university course timetabling problem as an example. We have formulated two mathematical formulations of course timetabling problem in a new way which are the prototype of single-mode RCPSP. Our focus is to show, how course timetabling problem can be transformed into RCPSP. We solve this transformation model with genetic algorithm.

Keywords: Course Timetabling, Integer programming, Combinatorial optimizations

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

References:

[1] P. Brucker and S. Knust. Resource-constrained project scheduling and timetabling. Burke and Erben (Eds): PATAT 2000, LNCS 2079, Springer-Verlag Berlin Heidelberg: 277-293, 2001.
[2] A.Wren. Scheduling, timetabling and rostering-A special relationship. Burke and Ross (eds), Springer-Verlag Berlin Heidelberg, 46-75, 1996.
[3] D.Werra. An introduction to timetabling. European journal of Operational research, 19: 151-162,1985.
[4] E. K. Burke and S.Petrovic. Recent research directions in automated timetabling. European Journal of Operational Research, 140: 266-280, 2002.
[5] R.Lewis. A survey of metaheuristic-based techniques for University Timetabling problems. OR Spectrum, 30:167-190, 2008.
[6] J. A.Breslaw. A linear programming solution to the faculty assignment problem. Socio-Economic Planning Science, 10: 227-230, 1976.
[7] K. Schimmelpfeng and S.Helber. Application of a real-world universitycourse timetabling model solved by integer programming. OR Spectrum, 29:783-803,2007.
[8] S.Daskalaki,T.Birbas and E.Housos. An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153: 117-135, 2004.
[9] N. Boland, B. D. Hughes, L.T.G. Merlot and P. J. Stuckey. New integer linear programming approaches for course. Computers & Operations Research, 35: 2209-2233, 2008.
[10] T. Birbas, S. Daskalaki and E. Housos. Timetabling for Greek high schools. Journal of the Operational Research Society, 48: 1191-1200, 1997.
[11] A. Mingozzi, V. Maniezzo, S. Ricciardelli and L.Bianco. An exact algorithm for the resource-constrained project scheduling problem based on a new mathematical formulation. Management Sci. 44:714-729,1998.
[12] F.Ballest─▒n,V.Valls and S. Quintanilla. Pre-emption in resourceconstrained project scheduling. European Journal of Operational Research, 189:1136-1152,2008.
[13] S.Hartmann and D. Briskorn. A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207: 1-14,2010.
[14] S. Hartmann and R. Kolisch. Experimental evaluation of the state of the art heuristics for the resource constrained project scheduling problem. European Journal of Operational Research, 127:394-407, 2000.
[15] S.N.Jat and S.Yang. A Guided Search Genetic Algorithm for the University Course Timetabling Problem. Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2009), Dublin, Ireland, 10-12 August 2009.
[16] A.Jain, S.Jain and P.K. Chande. Formulation of Genetic Algorithm to Generate Good Quality Course Timetable. International Journal of Innovation, Management and Technology, Vol. 1, No. 3, ISSN: 2010- 0248, August 2010.
[17] S. Abdullah and H. Turabieh . On the use of multi neighbourhood structures within a Tabu-based memetic approach to university timetabling problems. Information Sciences, 191: 146-168, 2012.
[18] L. Davis. Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1991.
[19] A. Colorni, M. Dorigo, and V. Maniezzo. Genetic algorithms - A new approach to the timetable problem. In Akgul et al. (eds.), NATO ASI Series, Combinatorial Optimization, Lecture Notes in Computer Science, F(82), pp. 235-239, 1990.
[20] M. W. Carter and G. Laporte. Recent developments in practical course timetabling. Proc. of the 2nd Int. Conf. on Practice and Theory of Automated Timetabling, LNCS 1408, pp. 3-19, 1998.