Files

Abstract

The resource allocation problem is a traditional kind of NPhard problem. One of its application domains is the allocation of educational resources. In most universities and business schools today, students select the courses they would like to attend by ranking the proposed courses. However, to ensure the quality of a course, the number of seats is limited, so not all students can enroll in their preferred courses. Therefore, the school administration needs some mechanism to assign the available resources as soon as possible, trying to optimize the students' wishes. In this paper, the course allocation problem has been modeled as a Constraint Satisfaction Optimization Problem (CSOP) and two metrics have been defined to quantify the satisfaction of students. The problem is solved with Gecode, and its results are compared with a greedy-based algorithm showing how the CSP approach is able to optimize the allocation of resources optimizing the students'satisfaction. Another contribution of this work is related to the possibility to allocate simultaneously several courses, generating feasible solutions in a short time. The allocation procedures are based on preferences for courses defined by students, and on the administration's constraints that define the available resources at Ecole Hôtelière de Lausanne. Ten data sets have been generated using the distribution of preferences of students for courses, and a complete experimental analysis has been carried out using these data sets evaluating the performance of the algorithms considered.

Details

Actions