Project-assignment-problem

🏗️ About:

This project aims to optimise the problem of project assignment through the simulated annealing approach.

❓ Problem:

We have a list of students with the projects they want to take on. Also, the projects are given in order of their preference. Now we have to help the institute assign students to the teachers in such a way that no teacher is assigned more than their capacity and we can achieve maximum student satisfaction. Other constraints include that no project can be assigned to more than one student.

📄 Algorithm:

• Draw a random student x project matrix where we assign a project to student.
• Then check for the following constraints
  • The project allocated belongs to student's choice list
  • No. of possible projects under a teacher are not more than their capacity
  • One project is taken by only one student
• Now we assign some scores to the assignment of projects according to the following formula
         S = p₁ + p₂ + p₃ + ... + p_n

               where p_i denotes the preference offered to student s_i (here greater value of p_i denotes higher preference

• We iterate over as many no. of combinations of allocation possible, calculate score of each, compare it with the current maxima and make it the new maxima based upon the following calculation
         If the current score is greater than maxima then accept the current state as the maxima
         else, calculate probability to accept this state with the following formula
        
• We finally return the maxima as the solution to the allocation.