View Question
 Question
 Subject: School course scheduling algorithm Category: Computers > Algorithms Asked by: anthony3425-ga List Price: \$200.00 Posted: 12 Apr 2006 13:09 PDT Expires: 12 May 2006 13:09 PDT Question ID: 718285
 ```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.```
 There is no answer at this time.

 ```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```