2

I am designing a program to

  1. allocate faculty to subjects based on their preferences; and then
  2. allocate hours for each student; based on preferences of each teacher and characteristics of each subject (dont schedule a tough subject for friday afternoon).

It leads to 100k-ish combinations. And there are lots of special cases.

I searched around and saw language-agnostic questions that dealt with raw algorithms.

Algorithm for computing timetable given restrictions

Seating plan software recommendations (does such a beast even exist?)

Question: What is a good mathematical model that can be manipulated by a Python number-crunching package?

I am thinking something straightforward like (for the sake of example only):

A bridge problem > Graph model> A graph package that detects cycles

Community
  • 1
  • 1
Jesvin Jose
  • 22,498
  • 32
  • 109
  • 202
  • Dijkstra is the first thing on graphs that come to mind. But you might also want to look into clustering algorithms. – Martin Stam Dec 19 '11 at 12:24
  • clustering? Please explain how that can lead to a solution – Jesvin Jose Dec 19 '11 at 12:32
  • What's *faculty* in your question? – MattH Dec 19 '11 at 12:37
  • @MattH , it is a collective term for teachers. I Shouldnt have used a culturally-biased term here, right? :-) – Jesvin Jose Dec 19 '11 at 12:45
  • Wasn't sure, suggesting that students got to pick their preferred teachers made me think it must mean something else. – MattH Dec 19 '11 at 12:50
  • 1
    This was one of the first softwares Bill Gates sold! :) [look here](http://portfolio.educ.kent.edu/boutaharn/billgates.htm). – Pratik Deoghare Dec 19 '11 at 13:05
  • In the past, I've done some work on data-clustering by placing parameters in n-dimensional space, rather than building graphs of possibilities. Then, by calculating euclidean distances, rather than managing graph connections, one can define clusters of connected data. This was years ago, and one of the few things I can remember that I ran across some research done by 'Bethlehem'. Can't find the article anymore though. :( – Martin Stam Dec 19 '11 at 13:17

1 Answers1

0

You may try setting the possibilities up as a weighted graph or tree. Both are very 'traditional' data structures as far as I can tell, and should play nicely with different libraries. Like Martin Stam mentioned, you could search through them using Dijkstra's or any other type of search algorithm.

I'm not sure I entirely understand your situation.

Peter Downs
  • 482
  • 1
  • 4
  • 14