Challenge Team Interim Report

[Challenge Logo]

    Team Number: 007

    School Name: Albuquerque Academy

    Area of Science: Mathematics

    Project Title: 3-D Scheduler

Final Report

Our project seems to be developing very well. So far we have programmed 5 functions in C++ that lay the groundwork for our scheduling algorithm. We hope to soon implement a large 3-d array to store the Boolean values that will represent student choices / class assignments. Once we have devised the data storage method, we will work on a schedule optimization algorithm. This algorithm will optimize 2-d cross sections of the 3-d array. As a result, our algorithm will require a supercomputer to deal with the larger number of cross sections in the large 3-d array.

We have reviewed many possibilities for the 2-d optimization algorithm. Our sponsor has introduced us to the concepts of simulated annealing and genetic selection algorithms. We have also reviewed a research paper that indicates that genetic selection algorithms may prove to be superior to simulated annealing in np-complete problems. As a result, we will probably try to implement genetic selection at some level (we may also look at training a neural network to implement a viable scheduling routine).

In order to test the efficiency and success of our algorithm, we will compare it to a random scheduling algorithm and to our own school's scheduling algorithm. We hope that our algorithm will be considerably more successful than the random algorithm and at least partially more successful than the school's algorithm. However, a direct comparison with the school's algorithm may not be possible, as we do not currently know if we will be given access to the scheduling data; in addition, we may not implement enough complexity to schedule an entire high school correctly. In spite of these limitations, we believe that our scheduling algorithm could serve as, at the very least, a basis for solving a real world scheduling problem.

If the initial tests of our algorithm go well, we may, at some future date, refine the algorithm to actually include even more of the complexities of a real world problem (complexities such as multiple grades, multiple grade courses, rigidly limited resources, psychological factors, public funding politics, and district socioeconomic realities). However, in order to include these crucial factors, our mathematical model would have to be upgraded considerably to include nonlinear systems (a subject which we are not terribly familiar with at this time!!!). This future aspect of our project has myriad intriguing possibilities. We look forward to investigating the "frontier" math consequences inherent to a scheduling program.

Team Members

Sponsoring Teachers

Project Advisor(s)