

Subject:
School course scheduling algorithm
Category: Computers > Algorithms Asked by: anthony3425ga 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. /////////////////////////////////////////////////////// // Datatype definitions: 1) Course a. Credits: An arbitrary integer. b. Prerequisites: 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. Onotation (bigoh) ii. onotation (littleoh) iii. ?notation iv. ?notation v. ?notation b. Heuristics can be used to bring down the running time. 2) Prebuilt 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 predefined 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 ?prerequisite 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 prerequisites for our courses. For example if there were no prerequisites 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 13 courses per semester and to complete their program in 15 semesters. 

There is no answer at this time. 

Subject:
Re: School course scheduling algorithm
From: frankcorraoga on 12 Apr 2006 14:04 PDT 
Good luck. The course scheduling problem is known to be NPhard. 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 
Subject:
Re: School course scheduling algorithm
From: afrocheesega on 18 Apr 2006 17:50 PDT 
The problem is NPhard, 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. 
Subject:
Re: School course scheduling algorithm
From: nejlaga on 22 Apr 2006 14:05 PDT 
Scheduling problem is a NonPolynomial(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 NPcomplete 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 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 