General discussion


Optimal allocation of students to timetabling blocks

By nigel.angus ·
I have a 5x8 array (but I want the solution to work for mxn). The 5 rows represent the (up to 5) subjects a student is applying to study at our college. The 8 columns represent the (currently) 8 timetabling blocks available. Students cannot take more than one subject in each block. Subjects can be (and usually are) offered in more than one block. A cell in the array represents the number of vacancies in that subject in that block. An empty cell means the subject is not offered in that block.

The problem is to find the combination of subject/blocks that has the most total number of vacancies.

I have a solution which uses brute force to examine every combination. It is ugly and does not lend it itself to generalisation (i.e it is hard coded for 5 and 8 - the 8 is easy to change but not the 5) It uses nested loops - but I'm convinced there is a recursive solution lurking there somewhere.

The other approach I tried is to find mathematical algorithms that could be adapted (network traversal, assignment, transportation, binary trees etc.)

I am a sort of self-taught amateur hacker (there are lots of us in secondary education) and this problem has exhausted my limited abilities.

Any help/advice/pointers would be gratefully received.

Yours humbly

Nigel Angus - Sussex Downs College (Lewes, East Sussex, UK)

This conversation is currently closed to new comments.

Thread display: Collapse - | Expand +

All Comments

Related Discussions

Related Forums