The research problem at hand revolves around the optimization of the University Course Assignment System. Within a department, there are "n" faculty members categorised into three distinct groups: "x1," "x2," and "x3." Faculty in each category are assigned different course loads, with "x1" handling 0.5 courses per semester, "x2" taking 1 course per semester, and "x3" managing 1.5 courses per semester.
In this system, faculty members have the flexibility to take multiple courses in a given semester, and conversely, a single course can be assigned to multiple faculty members. When a course is shared between two professors, each professor's load is considered to be 0.5 courses. Moreover, each faculty member maintains a preference list of courses, ordered by their personal preferences, with the most preferred courses appearing at the top. Importantly, there is no prioritisation among faculty members within the same category.
The primary objective of this research problem is to develop an assignment scheme that maximises the number of courses assigned to faculty while aligning with their preferences and the category-based constraints ("x1," "x2," "x3"). The challenge lies in ensuring that a course can only be assigned to a faculty member if it is present in their preference list.
This problem is unique due to the flexibility it offers regarding the number of courses faculty members can take, distinct from typical Assignment problems. Potential modifications may include adjusting the maximum number of courses "y" for each category of professors, instead of requiring exact adherence, or extending the number of professor categories beyond the existing three to devise a more generalised solution.
I have used backtracking to assign 30 faculties to there preferences in a course assignment problem where every faculty gives 12 preferences and there are 3 types of faculties x1(available course load = 0.5) x2 (1) and x3(1.5) and number of courses = total load available for the 30 faculties. However backtracking alone is taking a lot of time for the problem and I have decided to produce incomplete assignments(where all the faculties have been assigned something but there load constraints are not filled) and I am able to generate these kinds of assignments very quickly and most of the time only 3-4 faculties are left with incomplete assignments and this will also leave some unassigned courses as well(which will not be in the preferences list of the incompletely assigned faculty). How can I use some sort of local search to keep shifting the assignments(replacing assignment of faculty with some free course in there preference) until I get the best possible assignment(with all faculties fully assigned)? I believe this method will be much faster. I am happy to provide any code as I am not sure where to do so as this is my first question on stack overflow.