Hey everyone!

Two friends of me and I are working on a big project, and one of the things we need to do, is making a website, where a teacher can make a planning for tests. They gave us the task to to this, which is actually hard Sad .
Now I'm asking if anyone can help us, by giving either an algorithm or tips or whatever.

What do we have as input?
We got a bunch of tests, the teacher made. One example would look like this:

Code:
Subject: English
Week: 6
Duration (in multiplies of 45 minutes): 90
Class: 6Va (don't mind this)

For each test, we added the students(number) to the database.
Let's say we have class 6Va, 6Vb and 6Vc.

What are the constraints?
[-]Preferable not at Monday
[-]Exam classes have the same test at the same time
[-]No student two tests at the same time
[-]Preferable no student with two tests at a day
[-]They prefer the test at the day and hour of the week, the class has that subject.

How would a schedule look like?
This is an example:

Code:
Monday Tuesday Wednesday Thursday Friday
German     1       1        1       1
   2       2    Science     2       2
   3       3       3       Math     3
Math       4       4        4       4
   5       5       5        5       5
   6       6       6        6       6
   7       7       7        7       7

and even more subjects, but it is something like this.

Some general information
[-]The amount of tests per week is 0-~20
[-]We need to make it for ~40 weeks, so time limit is also important.

I hope you have information to help me, and otherwise I'm willing to answer questions Smile
I had the idea to brute force it, but I've no idea how, and if it's possible with the time limit. Any ideas?
I think my old school district used an algorithm similar to this for constructing class schedules based on the courses you had selected. I would begin by constructing a list for each student of the classes they are in. Then you can iterate through the list of students to see if all of the conditions are satisfied. If the conditions are not satisfied, increment (or change somehow) the exam time for the last conflicting exam. Repeat this until the conditions are satisfied for each student, or until all possible exam times are exhausted. If all possible times are exhausted, pick the times that have the least number of unsatisfied conditions.
jonbush wrote:
I think my old school district used an algorithm similar to this for constructing class schedules based on the courses you had selected. I would begin by constructing a list for each student of the classes they are in. Then you can iterate through the list of students to see if all of the conditions are satisfied. If the conditions are not satisfied, increment (or change somehow) the exam time for the last conflicting exam. Repeat this until the conditions are satisfied for each student, or until all possible exam times are exhausted. If all possible times are exhausted, pick the times that have the least number of unsatisfied conditions.
So in fact a kind of brute force, in combination with the Minimax method? I will see if that will work.
Well, long time ago I posted something in this topic Smile
We were just busy with creating the algorithm, and now I wanna ask you:
When you have a giant database, and you need some specific rows, is it faster to say

Code:
"SELECT * FROM `bla` WHERE <statement>"

or use a PHP-loop to get the specific rows?
You should restrict the results as much as possible in SQL before doing any final sorting or filtering of the results in PHP.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement