How to implement a seat distribution algorithm for uni lectures

Question

we have about 1000 free seats for our lectures at our uni, and around 2000 seats demanded (maybe 500 students demanding 4 places each).
I'm developing a webapp with CakePHP, which lets students make a wishlist and enter 4 lectures per block, with priorities from 1 to 4. (This then goes into a MySQL-database)

Now, the web frontend is done, the admin actions (add lectures, add lecturers, etc) are done.. the only thing left is writing the distribution algorithm.

How should I best do this? A MySQL-script seems useful, but mysql is not very friendly when it comes to loops and if-constructs, is it?
Would it be smart to export the data somewhere and let another language handle the problem?

Edit: dnagirl requested more info about the algorithm: We don't have business rules for the algorithm. We adapted an existing (very expensive) app from someone else at another university, which has rules we just adapted.
What he is doing (and what I am trying to clone, to save the big per-semester fee), is this:

• Events (the lectures, exercises etc.) all belong to a block (block is e.g. International Politics, which has maybe 4 or 5 different events)
• Students can apply for up to 4 events per block, with priorities 1 to 4.
• The algorithm works per block. For each block, divide the students into different groups according to their ranking. (The ranking is "the higher the better". Normal rankings are from 0 to 20)
• From the group of students with the highest ranking, randomly pick one. Give him a seat in the event which he chose with priority 1. If this event is full, give him the seat he chose with priority 2; etc, down to 4.
• Choose the next student, and do the same, until every student with this ranking has a seat. Then, go to the next lower ranking, and do everything again. When this block is finished, do everything again with the next block until all blocks are done.

I know this algorithm isn't the best solution, but I thought I'll just clone it for now, and maybe afterwards work on an improvement in the logic/possibilities.

Answer 1

You probably want some sort of genetic algorithm:

• Create a random distribution of students over lectures
• Calculate a score (fulfilled wishes score high, overbooked lectures produce a penalty, etc.)
• Make a change (e.g. move one student to a different lecture). If the score increases, keep it, otherwise reject.
• Keep iterating until no change can be found that increases the score: you have found a local minimum
• Repeat the entire thing a few times to find other local minima. Then go with the best-scoring solution.

You'll have to run a few tests and tweak the scoring weights to get it right.

MySQL is not really very suitable for this; you better solve this in PHP and then persist in one go. If the performance isn't good enough, you might even consider implementing it in C++, but I suggest you try PHP first and see if it's fast enough. It's not like you're going to run this every 2 seconds.