MBA Student Sectioning
AbstractMaastricht University is offering a MBA program for people that have a bachelor degree and at least 5 years of working experience. Within the MBA program, students work in groups of 5 during a two year cycle. This thesis is about the formation of the student groups. The MBA program contains 60 students. Every year, two intake moments take place that usually allow 15 new students to enter. All 60 students follow the same course at the same time, implying that the order in which a student follows the courses depends only on the moment at which he/she starts the program. Every two periods, The university creates new student groups according to a set of hard and soft constraints, such that well-diversified groups are formed. Therefore, the student-with-student history, gender, nationality, and level of expertise of each student is taken into account. Hence a mapping from a set of students to groups is created that takes into account the corresponding constraints. The university chooses a group leader for each group. Two general solution methods are applied to the MBA sectioning problem. The first method uses the simplex algorithm to solve the problem. Therefore an integer linear program formulation of the problem was needed, and used as an input for an efficient ILP solver. The second approach starts with an initial feasible solution and improves upon this feasible solution using different improvement algorithms. The quality of each feasible solution depends on the calculated objective function value that measures the level of satisfaction of the different constraints. Different initial solution and improvement algorithms are discussed that help to obtain a feasible solution with an objective function value that is as low as possible. The implemented improvement algorithms are the Descent Improvement algorithm, Tabu Search, Simulated Annealing, and the Bipartite Weighted Matching Improvement algorithm. The first three algorithms make individual students swap between existing group formations. The Bipartite Weighted Matching Improvement algorithm iteratively selects a student from each group, and finds local optimal solutions for a bipartite matching problem in order to improve the overall objective value of the whole problem. In order to test the algorithms, one has to make sure that the instance on which the algorithms are tested mimics a real life example. Therefore, a simulation program is established that mimics the two year cycle and produces such an instance. Empirical results show that the best improvement algorithm considered is the Bipartite Weighted Matching Improvement algorithm. This algorithm, combined with an initial solution algorithm, is now being implemented into the current computer system of Maastricht University.
Aarts, E. & Lenstra, J. (2003). Local Search in Combinatorial Optimization. Princeton University Press.
Bandelt, H., Crama, Y. & Spieksma, F. (1994). Approximation algorithms for multi-dimensional assignment problems with decomposable costs. Discrete Applied Mathematics, Special Volume Viewpoints on Optimization, 49(1-3), 25-50.
Burkard, R. (1998). Linear assignment problems and extensions.
Burke, E. & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140, 266–280.
Carter, M. (2001). A comprehensive course timetabling and student scheduling system at the university of waterloo. In Selected papers from the Third International Conference on Practice and Theory of Automated Timetabling III, PATAT ’00, pp. 64–84, London: Springer-Verlag.
Carter, M. and Laporte, G. (1996). Recent developments in practical examination timetabling. In E. Burke and P. Ross (eds), Practice and Theory of Automated Timetabling, volume 1153 of Lecture Notes in Computer Science, pp. 1–21. Berlin Heidelberg: Springer.
Carter, M. and Laporte, G. (1998). Recent developments in practical examination timetabling. In E. Burke and P. Ross (eds), Practice and Theory of Automated Timetabling II, volume 1408 of Lecture Notes in Computer Science, pp. 3–19. Berlin Heidelberg: Springer.
Feo, T. & Khellaf, M. (1990). A class of bounded approximation algorithms for graph partitioning. Networks, 20(2), 181–195.
Kuhn, H. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2), 83–97.
Marte, M. (2002). Models and Algorithms for School Timetabling. PhD thesis.
Muller, T. (2005). Constraint-based Timetabling. PhD thesis, Charles University Prague, Faculty of Mathematics and Physics.
Muller, T. & Murray, K. (2010). Comprehensive approach to student sectioning. Annals of Operations Research, 181(1), 249–269.
Murray, K., Muller, T. & Rudova, H. (2007). Modeling and solution of a complex university course timetabling problem. In Practice And Theory of Automated Timetabling, Selected Revised Papers, pp. 189–209.
Pulleyblank, W. (2012). Edmonds, matching and the birth of polyhedral combinatorics. Documenta Mathematica, Optimization Stories (Extra Volume), 181–197.
Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2), 87–127.
Willemen, R. (2002). School timetable construction: algorithms and complexity. Proefschrift, Technische Universiteit Eindhoven.