Using graph theory to generate an exam schedule

Question

I came across this website while looking for help on the internet regarding adj. matrix / graph theory.

My program layout is as follows:

• student name + courses stored in a 2D
• array array with all distinct courses

I am trying to achieve the following:

• use adjacency matrix to create an exam schedule where no student needs to write more than one exam a day

Once the matrix is made, the results on the screen should be displayed as:

• output a day by day exam schedule by course
• output the exam days of any student inquired

I am not really sure how to work on this. AFAIK, the best approach would be to create an overall exam schedule of all the distinct courses and computing it in such a way that no exams conflict with one another.

Any help/advice/links is greatly appreciated.

---

Any suggestions on how to program this? I can't seem to find any pseudo code or guidance on programming the graph coloring problem.

Answer 1

I would suggest taking the brute-force approach, to start. The number of possible arrangements of exams is likely small enough to exhaustively search them.

To give more detail for a solution, it would help to know more about the problem: How many exams per day? Is it possible for there to be multiple simultaneous exams, or are they all sequential?

Answer 2

You can model your problem as a graph coloring-problem.

Edit: Another heuristic approach using genetic algorithms.