Allocation algorithm help, using Python.
- by Az
Hi there,
I've been working on this general allocation algorithm for students.
The pseudocode for it (a Python implementation) is:
for a student in a dictionary of students:
for student's preference in a set of preferences (ordered from 1 to 10):
let temp_project be the first preferred project
check if temp_project is available
if so, allocate it to them and make the project UNavailable to others
Quite simply this will try to allocate projects by starting from their most preferred. The way it works, out of a set of say 100 projects, you list 10 you would want to do. So the 10th project wouldn't be the "least preferred overall" but rather the least preferred in their chosen set, which isn't so bad.
Obviously if it can't allocate a project, a student just reverts to the base case which is an allocation of None, with a rank of 11.
What I'm doing is calculating the allocation "quality" based on a weighted sum of the ranks. So the lower the numbers (i.e. more highly preferred projects), the better the allocation quality (i.e. more students have highly preferred projects).
That's basically what I've currently got. Simple and it works.
Now I'm working on this algorithm that tries to minimise the allocation weight locally (this pseudocode is a bit messy, sorry).
The only reason this will probably work is because my "search space" as it is, isn't particularly large (just a very general, anecdotal observation, mind you). Since the project is only specific to my Department, we have their own limits imposed. So the number of students can't exceed 100 and the number of preferences won't exceed 10.
for student in a dictionary/list/whatever of students:
where i = 0
take the (i)st student, (i+1)nd student
for their ranks:
allocate the projects
and set local_weighting to be sum(student_i.alloc_proj_rank, student_i+1.alloc_proj_rank)
these are the cases:
if local_weighting is 2 (i.e. both ranks are 1):
then i += 1 and
and continue above
if local weighting is = N>2 (i.e. one or more ranks are greater than 1):
let temp_local_weighting be N:
pick student with lowest rank
and then move him to his next rank
and pick the other student and reallocate his project
after this if temp_local_weighting is < N:
then allocate those projects to the students
move student with lowest rank to the next rank and reallocate other
if temp_local_weighting < previous_temp_allocation:
let these be the new allocated projects
try moving for the lowest rank and reallocate other
else:
if this weighting => previous_weighting
let these be the allocated projects
i += 1
and move on for the rest of the students
So, questions:
This is sort of a modification of simulated annealing, but any sort of comments on this would be appreciated.
How would I keep track of which student is (i) and which student is (i+1)
If my overall list of students is 100, then the thing would mess up on (i+1) = 101 since there is none. How can I circumvent that?
Any immediate flaws that can be spotted?
Extra info:
My students dictionary is designed as such:
students[student_id] = Student(student_id, student_name, alloc_proj, alloc_proj_rank, preferences)
where preferences is in the form of a dictionary such that
preferences[rank] = {project_id}
