YpSched scheduling tool

This is a program I wrote to schedule students into classes according to preferences and constraints.

Click to download zip file.

This is the file format for the young peoples conference scheduling tool. The file is plain text (use Notepad to edit) and it has four sections.

1. topics
2. periods
3. prereqs (optional)
4. students

Each section must start with a heading line. The heading must be lowercase, in column 1, nothing fancy.

The program reads the file and tries to assign each student to exactly one class in each period in a way that will maximize the happiness of all the students.

The following is a sample data file.

topics 3
Old Testament part 1
Old Testament part 2
New Testament

periods 3 2
Saturday 1:30
0 10 1, 2 11 2
Saturday 6:00
1 10 1, 0 12 3
Sunday 1:30
2 8 1, 1 12 3

0 0, 1 0
1 1, 2 1
2 1, 1 1

students 20
"Sarah Jones",2,1,0
"Bobby Smith",1,2,0
"Bill Miller",0,1,2
.... and so on 17 more students....


Notice these things

The topic line has the number of topics.

The period line has the number of periods and the maximum number of classes in each period. Each period doesn't need to have the same number of classes.

Each period has a name, followed by a list of classes on the next line.

Each class has three numbers. They are: topic, capacity, room. The topic numbers start at zero, thus 0 is the first topic, etc. The capacity number is how many students can enroll in the class (the number of seats.) The room number is any number you like, it is used for output only.

The class list can have a comma every third number.

The prereq section is optional. If present, it must start with a line with the single word prereq.

Each prereq line is four numbers: period class, period class. First period class pair is the prerequisite of the second pair, i.e. a student cannot enroll in the second pair without also enrolling in the first pair. The period and class numbers start at zero, thus 0 0 is the first period and first class.

To make corequisites, i.e. all or none, just make the classes prereq each other. The sample has a coreq between 1 1 and 2 1. You should ensure that the capacity of coreq classes are equal. If one class is the prereq of another, it should have at least as much capacity.

The list of students starts with a heading that tells the number of students. Each student has a name followed by a list of preferences. There must be exactly one preference for each topic. A preference is a "happiness score", thus a preference of 2 means the student likes the topic twice as much as a topic with a score of 1. The program tries to maximize the total happiness.

Preferences can be 0 to 5, or 0 to 10, or 0 to 100. It doesn't matter, as long as you are consistent. Don't use negative numbers or very big numbers.

That's all. If you have any questions or problems, send me an email ypsched@formulus.com

Click to download zip file with everything.

Click to view C source code.

Click to download only the DOS or Windows program.