Word version (Better formatting then text here):
http://programaccess.com/documents/CourseScheduleAlgorithmDefinition.doc

///////////////////////////////////////////////////////
// School course scheduling algorithm

///////////////////////////////////////////////////////
// Summary of problem:  Find an efficient method of creating a
schedule of courses (for a school) to satisfy student graduation
requirements while minimizing the number of courses offered by the
school over a given period of time.

We will have new students coming in every semester and need to run
this algorithm at that time to figure out which courses to offer in
the coming semester.

///////////////////////////////////////////////////////
// Data-type definitions:
	1)	Course
		a.	Credits: An arbitrary integer.
		b.	Pre-requisites: A list of 0 or more courses that must be
completed before this course is taken
	2)	Semester
		a.	A set of Courses to be taught by the school at any one given time
	3)	Student
		a.	History: A list of completed courses
			i.	Not all students will have History
		b.	Program: A list of courses needed to take in order to graduate
	4)	School schedule: A chronological list of Semesters

Input:
	1)	Courses 1?m
	2)	Students 1?n
	3)	Planned minimal school schedule (Known from a student perspective
as the ?Planned track?)
		a.	The school is at minimum planning to teach theses courses. 
Although the courses are not set in stone, this information should
help dramatically with heuristics (See ?Data information? 2)
	4)	Integer: X
	5)	Integer: Y

///////////////////////////////////////////////////////
// Constraints:
	1)	Students must not go above x units per Semester
	2)	Students must not fall below y units for any 2 sequential Semesters

///////////////////////////////////////////////////////
// Output:
	1)	A School schedule with the minimum number of Courses over all
semesters that will fulfill every student?s program
		a.	Note: It does not matter how many students are in a course

///////////////////////////////////////////////////////
// Possible Solutions:
	1)	An algorithm that will solve this problem in a reasonable amount
of time (would be computable by a p4 3Ghz in under 1 day
approximately), please provide the following:
		a.	Please provide asymptotic behavior of the given algorithm (It?s
okay if not all are given but we need a reasonable assurance we can
use the algorithm)
			i.	O-notation (big-oh) 
			ii.	o-notation (little-oh) 
			iii.	?-notation 
			iv.	?-notation 
			v.	?-notation 
		b.	Heuristics can be used to bring down the running time.


	2)	Pre-built software that will solve this problem with little configuration
		a.	We need to plug this into a PHP/MySQL based system.  Something
that we can run in real time through such system is preferable.
		b.	We may later need to add other constraints to the system, so it
is preferable that such system allows this easily
			i.	Or if it?s heavily developed enough pre-defined constraints may already exist

We do not need both solutions, but if multiple are easily available
feel free to mention everything so we may choose what best suites our
needs.

///////////////////////////////////////////////////////
//Data information:  The following information may be useful in
developing efficient/effective heuristics
	1)	Most courses will not have long ?pre-requisite chains?
		a.	The longest chain we have currently is 4 courses long
	2)	We estimate that 85% of students will have been new students for
us at one point, and hence we will be able to put them on the ?planned
track?.
		a.	We came up with this planned track because a ?new? student comes
with no history and because we have minimal pre-requisites for our
courses.  For example if there were no pre-requisites and no history
100% of the students could be in 1 course at any given time.  The
?new? students that look like they are starting in the middle would
simply start ?loop? back to the first courses once that semester came
and finish all the courses from there.
	3)	The remaining 15% of the incoming students will likely have
homogeneous course backgrounds (general education / lower division). 
We estimate that 80% of Student history will fall into 30% of the
courses.
	4)	We expect a student to take approximately 1-3 courses per semester
and to complete their program in 15 semesters.

Good luck. The course scheduling problem is known to be NP-hard. Here
is one study on a specific instance as a referance:
http://www.springerlink.com/(3t3ctzvnxr02upyarotxgmzi)/app/home/contribution.asp?referrer=parent&backto=issue,6,17;journal,2409,3795;linkingpublicationresults,1:105633,1

The problem is NP-hard, but it's certainly able to be calculated so
long as there are small number of students/courses.

I'd recommend looking into lingo/lindo or GAMS for methods of solving
this in a decent amount of time.  However, if you have no
deterministic optimization / modelling experience, doing so will be
quite difficult.

There are also methods to find suboptimal solutions although they are
more complex.

Neither of these methods will be able to take advantage of your heuristics though.

You can automatically generate the LINDO/GAMS input with php in
addition to running them with a script.

Scheduling problem is a Non-Polynomial(NP)-Complete optimization
problem subject to multiple constraints.
Since the 1960s, AI (Artificial Intelligence) methods have emerged as
powerful tools for solving a variety of NP-complete constrained
optimization problems.
The best known AI methods are Genetic Algorithms (GA), Tabu Search
(TS), Ant Colonies (AC), Simulated Annealing (SA), Evolution
Strategies, ... .
You can find loads of scheduling papers based on GS, TS, SA, AC, ? on
the web. If you need more info. about these AI techniques?particularly
TS and GA ? then let me know. I will explain it as much as I can.
Good luck